Advent of Code - 2019 - Day 15 - 16

The fifteenth problem was a maze puzzle. In part 1 you should discover the maze, and find the shortest path to an object in the maze. In part 2 you should find the point in the maze with the largest distance to another point. Both problems can be solved in a similar way: 1) discover the maze, 2) do a breadth-first search over the maze from the point of interest. This is overkill for part 1, but accidentally I solved part 1 like this (thinking I could optimize later) and that made part 2 trivial!

19> aefa_sophia_test:run_file("/Users/hans/Personal/Repos/AoC2019/15/sol_15.aes", "solve_1", []).
0 steps / 1126122416 gas / 0 reductions / 10622.11ms
20> aefa_sophia_test:run_file("/Users/hans/Personal/Repos/AoC2019/15/sol_15.aes", "solve_2", []).
0 steps / 1397698224 gas / 0 reductions / 11854.60ms

My solution is here

1 Like

The sixteenth problem problem was about flawed frequency transmission. We were tasked with cleaning up a signal (a list of digits 650 long) where each digit had its own filter and where all filters should be run 100 times. This translates into a tight loop over a couple of vectors (or in our case a map). In retrospect this is perhaps the kind of problem where the disadvantage of being in a VM (optimized for block chain operations) will be clearly visible. After being at least somewhat clever part 1 of the problem could be solved in about 5 minutes…

Enter part 2, now the signal isn’t 650 digits, it is 65000000 digits… But since we are tasked with finding a chunk of the resulting signal towards the end (in our case at 5976732) of the signal we could simplify the list of filters (they all degenerate to the same filter). Armed with this we managed to (after optimizing in several steps) get the runtime down to a measly 2300 seconds…

40> f(M), M = aefa_sophia_test:run_file("/Users/hans/Personal/Repos/AoC2019/16/sol_16.aes", "solve_1", []).
0 steps / 370908898489 gas / 0 reductions / 282643.28ms
41> f(M), M = aefa_sophia_test:run_file("/Users/hans/Personal/Repos/AoC2019/16/sol_16.aes", "solve_2", [100]).
0 steps / 164673100419882 gas / 0 reductions / 2296406.90ms

My solution is here