Advent of Code 2016

Dec 3, 2016

The second instalment of Advent of Code has started but this time I'm only tackling the problems in Elm (mostly skipping Perl or Ruby - unless Elm is too slow). You can run my solutions, see my input data (which might differ from yours) and get links to my Elm code on this page.

My solutions for last year's problems have been converted to the current version of Elm (0.18). For problems involving MD5 digests I had been using a JavaScript function combined with a native Elm module but now I'm able to use a pure Elm module.

Here are comments on some problems which I found difficult:

- Day 5 part 2: This took several minutes. I did try a similar algorithm for comparison in Perl and it was way faster.
- Day 9: I admit to consulting reddit in order to realise that the answer could be obtained by adding numbers rather than concatenating strings which meant the algorithm could finish in reasonable time.
- Day 11: Too difficult for me.
- Day 14 part 2: My Elm program was still running after about 20 hours so I wrote a Perl 5 script based on the same algorithm which took only 20 seconds! Perl is about 100 times faster than Elm at computing MD5 digests but that alone isn't enough to explain the huge disparity in running time.
- Day 16 part 2: My browser (Vivaldi) window crashed, presumably because it ran out of memory. Anyway, a Perl 5 script again came to the rescue, finishing in under a minute and using a few GB of memory.
- Day 22: Part 1 was easy enough but part 2 looked impossible and I was about to give up until I saw (after consulting reddit) that this problem could be solved by by hand after writing just enough code to print out the grid of nodes with the "wall" of high capacity nodes, the (sole) empty node and the goal node all marked appropriately.
- Day 25: I tried a brute force approach but will never know if it was correct as there was no sign of it terminating. In the end I cheated by checking reddit where people had worked out what the instructions actually did and reduced the solution to a simple equation.

and here are comments on some problems which I particularly enjoyed:

- Day 17: Despite involving MD5 digests and searching a solution space, the Elm program finished in reasonable time, even for part 2. Although a Perl program based on a similar algorithm finished much quicker and was less verbose, it wasn't as readable or elegant.
- Day 18: I'd learnt the lesson from day 9 and knew that since only a total count was required, it wasn't necessary to try to recreate all the rows of tiles before counting them. Instead, counting the tiles in each new row and keeping a running total is sufficient. This was important if part two (with a huge number of rows) was to finish in reasonable time and not run out of memory.
- Day 19: I solved part 1 with a simple algorithm before discovering (from reddit) that it was a known puzzle in recreational mathematics (called the Josephus Problem) and can be solved with a formula involving powers of 2. For part 2, applying the same general technique as used in this video (looking for patterns in the solutions for low numbers and then trying to generalise) led to a formula involving powers of 3.