My answer was 7048 steps 
lud
sasajuric
Author of Elixir In Action
I solved this via brute force (so basically computing all paths), and got it to a “reasonable” time with the following optimizations:
- Keep track of current best. Discard any state where more steps have been taken.
- When considering possible next moves, prefer the keys which are closer to me. This brings me sooner to lower results, which helps optimization from 1 eliminate a bunch of combinations that would otherwise be considered fully.
- Keep track of the seen state. If I find my self at the same point I’ve already been at, and my acquired keys are the same as, or a subset of, what I’ve already explored, and the number of steps I’ve taken is the same or larger, I stop tracking further. This one really eliminates a lot of combinations, but it’s quite tricky to do right, and I’m still not certain if I did everything properly. Also, this condition has to be expanded in part 2 to account for mutliple robots.
- When choosing next possible moves, take only immediate points in path. For example, let’s say that I can get to keys a, b, and c, and that a is in path of c. I’ll only take the key a (unless I have it, in which case I’ll take the key c), and b. This also eliminates a bunch of redundant combinations.
- Finally, I’ve precomputed the shortest distances between keys upfront. This is based on the assumption that the shortest path doesn’t change if some door is unlocked.
4
bjorng
Erlang Core Team
I spent a lot of time working on my solution yesterday. My approach was a little bit unusual, in that I used :digraph.get_shortest_path/1 to get the path from the current position to a given key. I combined that with BFS algorithm (with a priority queue based on gb_sets. Because digraph is not purely functional, I had to delete and add edges to lock and unlock doors. I got it to work on all examples, but it needed about 5 minutes for the “evil” example. Attempt at optimizations either didn’t make it faster or resulted in an incorrect result.
Yesterday evening I gave up and scrapped my solution.
Since I am here to improve my Elixir skills, I decided to rewrite @ferd’s Erlang solution to Elixir. I also tried to do more optimizations, but the only one that seemed to give a slight improvement was to use gb_sets for the priority queue instead of queue. I also changed the data representation to get rid of the calls to atom_to_list/1 and list_to_atom/1.
My solution solves both parts in about 20 seconds.
0
ferd
Author of Property-Based Testing with PropEr, LYSE, & Erlang in Anger
I think using gb_sets might give you an optimization you haven’t used where the moment all the keys are found, you can stop the run because you’re guaranteed that what’s left in the set is going to have longer paths.
This isn’t always true of the queue approach where there is a kind of “scheduling” order where it’s possible that some slightly longer paths are processed before shorter ones, and the queue needs emptying.
I don’t know how significant it would be, but it could probably speed-up later runs when most keys are grabbed and a lot of dead-end paths are still being investigated.
1
ihabunek
Late to the party, but solved this challenge recently so here it my take if anyone is interested:
https://git.sr.ht/~ihabunek/aoc2019/tree/master/lib/day18.ex
Same algorithm works on both parts, takes under 4s for each part on my machine.
I’m doing a dijkstra-like search which processes only one move per iteration with the following optimizations:
- keep a set of visited unique vault states (a state comprises of: robot positions, remaining keys and distance traveled so far) and skip any already visited states
- keep the best (shortest) path found so far, and skip any steps which would go over this limit
- keep a cache of possible robot moves given current vault state so it’s not calculated every time from scratch
2