Monday, 2015-12-14

Advent of Code 2015

Project website: Advent of Code.

I started on these puzzles on 7 Dec 2015. So far I’ve completed all of them, all but a few on the same day they were posted.

I use Perl for all the solutions.

Most assume the input data is in a file called input.txt in the same directory as the file. Some require extra modules from CPAN.

A note on scoring

I score my problems to mark where I’ve finished a solution myself or given up and looked for hints. A score of 2 means I solved both the daily problems myself, a score of 1 means I looked up a hint for one of the problems, and a zero score means I didn’t solve any of the problems myself.

Final score: 43 / 50.

Github link.

Days 1 to 4 - Day 5 - Day 6 - Day 7 - Day 8 - Day 9 - Day 10 - Day 11 - Day 12 - Day 13 - Day 14 - Day 15 - Day 16 - Day 17 - Day 18 - Day 19 - Day 20 - Day 21 - Day 22 - Day 23 - Day 24 - Day 25

Days 1 to 4

Day 5 — Doesn’t He Have Intern-Elves For This?

My solution: part 1 - part 2.

I had to get help with part 2 here, found a regexp in the daily solutions thread for this day.

Score: 1.

Day 6 — Probably a Fire Hazard

Part 1 - part 2.

These could definitely be faster, both run in around 30s.

Score: 2.

Day 7 — Some Assembly Required

Had to scrounge around for tips on how to solve this. I had the basic idea down but the problem was keeping track of the solutions as I iterated around.

Score: 0.

Day 7

Update 2017-12-28 Day 7 - alternative complete solution

Day 8 — Matchsticks

Easily the most boring of the problems so far.

Part 2 only.

Score: 2.

Day 9 — All in a Single Night

Essentially the travelling salesman problem but the number of destinations is small enough to brute-force easily. Uses the Algorithm::Combinatorics module. Output is a list of permutations with the total travelling distance prepended, so just use sort -n to find the answer from the output.

Update 2017-12-28 Day 9 - alternative complete solution. This solution removes the need to sort an output file.

Score: 2.

Day 09.

Day 10 — Elves Look, Elves Say

Another computationally expensive problem but even part 2 runs in under 1 minute for me.

Submitted 3h25m after puzzle release.

Update 2017-12-28 Day 10 - alternative complete solution. Much faster regex-based solution from Rosettacode.

Score: 2.

Day 10.

Day 11 — Corporate Policy.

Day 11 - complete solution

So far my favorite problem!

Submitted 5h56m after puzzle release.

Score: 2.

Day 12 —

Another good puzzle. Uses the JSON module.

Day 12 - complete solution

Submitted 9h25m after puzzle release (I blame family commitments on weekends!).

Score: 2.

Day 13 — Knights of the Dinner Table.

Day 13 - complete solution

This is a modified day 9 with bidirectionally. Even part 2 which adds another element to the permutation finishes very quickly using brute force.

Submitted 5h03m after puzzle release.

Score: 2.

Day 14 — Reindeer Olympics.

A troll! The immediate brute force approach is to simply advance time 1s at a time and check the “position” of each deer at that time. But this is “obviously” dumb so I used a quicker approach for part 1. Part 2 made me regret it…

Submitted for 2 stars 4h04m after puzzle release.

Day 14 - complete solution

Day 14 - complete solution with fancy scoreboard

Score: 2.

Day 15 — Science for Hungry People.

A combination of outside factors and frustration at getting my indexes right made this a tedious slog.

Submitted for 2 stars 9h45m after puzzle release.

Score: 2.

Day 15 - complete solution

Day 16 — Aunt Sue.

A fun one. Submitted for 2 stars after 2h37m.

Score: 2.

Day 16 - complete solution

Day 17 — No Such Thing as Too Much

Tried a recursive approach first, but got stuck for the part 2 and looked in the daily thread for inspiration. Figured out how to use combinations by looking at other’s code.

Submitted for 2 stars after 6h18m.

Score: 1.

Day 17 - complete solution

Day 18 — Like a GIF For Your Yard

Conway’s Game of Life! I’ve never coded this before so it was a fun exercise.

I tried using arrayrefs first but got tripped up by the deep copy (dclone in the code) and decided to go for a hash of hashes instead. I think this contributes to the slow execution time of ~15s.

Submitted for 2 stars after 6h00m.

Score: 2.

Day 18 - complete solution

Day 19 (Saturday) — Medicine for Rudolph

A tough one! I solved part 1 no problems but had to hunt around for hints for part 2.

Day 19 - part 1. Day 19 - part 2 alternative solution.

Score: 1.

Day 20 (Sunday) — Infinite Elves and Infinite Houses

Lack of time and impatience led me to look for hints for this. I had the right initial idea but thought looking for divisors of an integer without the PARI package would be too slow, and I have yet to find a way to install that on the machine I’m using.

In the end it didn’t matter but I wanted this done.

Full credits in source.

Day 20.

Score: 0.

Day 21 — RPG Simulator 20XX

I went for a straightforward solution of generating all combos of items and then running a simulated battle with each.

Day 21.

Score: 2.

Day 22 — Wizard Simulator 20XX

Not a very good solution, relies on brute force to simulate all possible spell casts and then prints out a win or loss. Note that I had to run it for 5M iterations to get the answer to part 2. This is the only problem I didn’t finish in the same day as it was released (apart from the 7 first ones).

Day 22.

Score: 2.

Day 23 — Opening the Turing Lock

Straightforward apart from the slightly ambigious jio instruction — read carefully what it means.

Day 23.

Score: 2.

Day 24 (Christmas eve) — It Hangs in the Balance

I tried to finesse the answer by hand first but it didn’t simply work to manually adjust the packages to get desired answer. Instead I checked valid combinations, but with the following assumptions/optimizations:

  1. I sorted the packages in descending order to check those combinations first.
  2. I assumed the answer wouldn’t contain more than 6 elements, so just checked combinations up to that value of k.
  3. I didn’t bother to confirm the remaining packages would sum correctly.

Runs in about 2s.

Day 24.

Score: 2.

Day 25 (Christmas day) — Let It Snow

Straightforward iterative solution. Runs in over half a minute, those with CS backgrounds used modular exponentiation and got much faster results.

Day 25.

Score: 2.


The solution files are in the Public Domain.