Yes!

Having quickly solved both parts, I had time to experiment with different ways of managing the queue. My initial implementation used gb_sets; I ended up using queue.

The combined runtime for both parts is 4.5 seconds.

Same here, solved easily, the brute force took something like 6 seconds.

Then I used binary search:

• First drop 1024 items from the walls points
• Create a base grid (with grid module) with those 1024 walls
• Then do a binary search for n between 1 and length(rest_of_walls). For each try:
  • take with Enum.take(rest_of_walls, n) and add those walls to the grid.
  • return “search reasult is greater” if the path is possible
  • return “…is lower” if the path is not possible

Of course there is no answer for “search result is equal” so I had to modify my binary search algorithm to detect ties and return them.

Part two is 13ms on my machine.

I thought that was long until I saw you are brute forcing part 2, no binary search.

I timed my first implementation without binary search and got 213 seconds (2013 MBP). Switched the pathfinding to use :queue like yours and got 42 seconds so much faster. Re-added binary search and it’s now 3 seconds including compilation.

My solution. I used Erlang’s queue data type for part 1. For part 2, I implemented a binary search, too.

I implemented my own priority queue with no duplicate values and lazy decrease-key operation.
Part 1 I used that priority queue to implement Dijkstra.
Part 2 I used a totally different approach. For each “byte” dropped down, I check if there are byte chunks horizontally, vertically, or diagonally adjacent to that “byte”, and merge those chunks with the new byte to form a larger chunk. Then I just need to find the first chunk over time that horizontally or vertically crosses the whole “memory space”.

Here’s my approach: