I solved this via brute force (so basically computing all paths), and got it to a “reasonable” time with the following optimizations:

1. Keep track of current best. Discard any state where more steps have been taken.
2. 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.
3. 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.
4. 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.
5. 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.

The inputs you get can apparently greatly impact runtimes. I was comparing my input with @sb8244’s, and the time it takes to run the first problem is almost 10x longer on my input than his. The impact was confirmed on his implementation as well.

Mostly I guess this has to do with the step count required, since longer steps require much larger search rounds. My input had ~5400 steps required, and his ~3000. This probably makes good comparisons very difficult.

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

I’m making large Breadth-first searches with combinatorial explosions, where a cache/memoization using the process dictionary is our only salvation, but only after having gotten it wrong quite a few times. Source at https://gist.github.com/ferd/f23d917e0739df3ca32fc5f34424c755

Ends up taking about 21 and 15 seconds for parts 1 and 2 respectively, but I didn’t feel like making it faster.

I struggled a lot with part 1 today Ultimately I went for brute-force DFS recursion + a bunch of optimizations, such as precomputing shortest paths between keys, keeping track of visited states during the brute-force search, and trying closer keys first. This brought me to about 14sec running time. The solution to part 1 is here. I’ll have to postpone part 2 for some other time.