Advent of Code 2019 - Day 15

I changed my Intcode module back to be fully functional (not using processes or message passing).

Here is my solution.

My original pure-functional design of Intcode definitely payed off today! Doing a breadth-first search (which I used to solve both parts) was straightforward. There is some duplication in the solution for each part, and I spend short time figuring out if I could make a more generic BFS abstraction, but in the end I didn’t feel it’s worth it. I might explore this in the future. Anyway, here’s my solution.

This is very hacky, but it works. I’m keeping state by making use of that my intcode interpreter is purely functional, so I can easily snapshot it and try various options in it, no need to revert anything. Tools assisted map searching with savestates :).

Part 2 solution continues from where part 1 did finish, and tries to find the furthest point. Pretty much the same as Part 1, but empty queue is a goal as opposed to finding oxygen (and of course, starting point is different).

Awesome! How beautiful it is!

I worked it out with many more codes. Here is my solution.

The method I use for part 1 is:

• First, walk through the maze, starting from origin, with left hand always on the wall, producing path one.
• Second, walk through the maze, starting over from origin, with the right hand always on the wall, producing path two.
• Third, get the common parts of both the paths above.

Unfortunately, this didn’t fit part 2.

Slightly overcomplicated it by using Dijkstra for part 1, which is not required due to all edges being the same weight:
https://git.sr.ht/~ihabunek/aoc2019/tree/master/lib/day15.ex

I animated the result again:
https://asciinema.org/a/80grPw4uGhl2GTBQjz33hSKip

Since I was short on time, I just went roomba style for part 1 (random movement, preffering unexplored areas to old areas) and drew the map, then I calculated part 1 and 2 by hand (not proud at all).

I will try to do this in a proper way later.
“solution”, part 2 is broken since I tried to explore correctly, by I’m out of time

My solution

Like others, I used the immutable properties of my program to do a breadth first search for both parts.

Part 1 runs the search until the first output of a 2, and prints the depth

Part 2 continues from part 1, and runs the search until all programs at current depth output 0, then prints the depth - 1

I spent quite a lot of time solving this part today, but I really like the approach I took in the end.

After some experiments, I refactored my Intcode to use continuation-passing style to expose fully functional interface (before it was using callbacks).

Then, solving both parts was pretty straightforward flood fill / breadth first search: part 1, part 2.

Relevant diff for Intcode, today’s solution code.

Tough day for me!

For a couple of hours, I pretended I could figure it out with my message passing computer (by cloning/forking my computer process at each recursion depth) but I got totally lost between all my process id

Then I refactored my computer so it can support both behaviors (message passing + pure functional).
After that the challenge itself wasn’t quite hard

My code: advent/lib/2019/day15 at master · cblavier/advent · GitHub

I just had a look at everyone’s solution and I’m surprised to notice that (for once) my solution is among the shortest (30 lines for each part).

Nothing fancy in my code though, it was a pretty straightforward tree traversal