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.

All files in one zipped archive.

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

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.

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.

Score: 2.

Day 10.

Day 11 — Corporate Policy.

So far my favorite problem!

Submitted 5h56m after puzzle release.

Score: 2.

Day 11.

Day 12 — JSAbacusFramework.io.

Another good puzzle. Uses the JSON module.

Both solutions in one file, just comment one line to get part 1.

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

Score: 2.

Day 12.

Day 13 — Knights of the Dinner Table.

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 13.

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.

Part 1, part 2.

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.

Day 16 — Aunt Sue.

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

Score: 2.

Day 16 part 2.

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.

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.

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.

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.

(un)License

The solution files are in the Public Domain.