Note: This topic is to talk about Day 18 of the Advent of Code 2019.
There is a private leaderboard for elixirforum members. You can join it by following this link and entering the following code:
39276-eeb74f9a
This is the slowest solution ever (takes a minute to execute), requires modifying the input to put @ 4 times in second part, it’s ugly, I picked the worst algorithms, but it works (I think?).
I think if I did start working on the solution when the task began, I would be Top 25 on the leaderboard (but I don’t think this is worth it), and I didn’t try to implement this quickly.
This problem kicked my butt pretty hard. I was able to get part 1 / 2, but I spent way too long on this problem. Like, I don’t want to admit how long I spent on this.
The code is here—I just cleaned it up a slight amount. I tried several techniques and couldn’t get anything to work. Finally I went to a plain old BFS and rethought the problem. I ended up enumerating a very large search space to get the answer. I would say it probably takes 10 minutes to run. My pt2 is also not generically correct—it fails the example but passes for my puzzle.
Great work @xfix!
edit: I got my parts to 7s / 14s respectively. I was using {coordinates, full_graph, remaining} as my node key, and I only needed {coords, remaining}. That cut the search space by several magnitudes.
edit2: Deleted all of the unused functions.
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.
1 Like
I am still stuck on part 1. I have all the tests cases correct, but my solution takes 10 minutes to run : I generate all the possible paths, recursively with the next reachable keys. But I end up with a wrong solution.
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.
1 Like
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.
2 Likes
@ferd Could you tell me if (and how) do you avoid to compute all possible paths from key to key ?
Like if there are a, b, and c I would try abc, acb, etc, stopping when the next key requires a door wich I cannot open yet.
The example in 136 steps takes forever because there are 16^16 possible paths, and obvioulsly many of them fail early because of doors, but still …
I do not know how fail earlier on slow paths. If someone would like to give me some tips that would be appreciated !
This is my code
defmodule Day18 do
@wall ?#
@empty ?.
@entrance ?@
def run(puzzle) do
grid = GridMap.parse_map(puzzle)
keys = GridMap.reduce(grid, %{}, &read_keys/2)
{entrance_xy, @entrance} =
GridMap.find(grid, fn
{_, @entrance} -> true
_ -> false
end)
knames = Map.keys(keys)
# ckeys: collected keys
# mkeys: missing keys
init_state = %{ckeys: [], mkeys: knames, steps: 0, pos: entrance_xy}
walk_to_all_keys(grid, init_state, keys, :infinity)
end
defp walk_to_all_keys(grid, %{mkeys: [], steps: steps} = state, keys, best) when steps < best do
IO.puts("best: #{steps}")
steps
end
defp walk_to_all_keys(_, %{mkeys: []}, _, best) do
best
end
defp walk_to_all_keys(grid, state, keys, best) do
%{mkeys: mkeys, ckeys: ckeys, pos: pos, steps: steps} = state
IO.puts("#{ckeys} -> #{mkeys}")
# create a new branch for all missing keys.
# collected keys (ckeys) are always sorted to help caching paths
Enum.reduce(mkeys, best, fn mk, best ->
destination = Map.fetch!(keys, mk)
case path_length(grid, pos, destination, ckeys) do
:error ->
best
add_steps ->
new_ckeys = insert(ckeys, mk)
new_mkeys = mkeys -- [mk]
new_steps = steps + add_steps
state = %{
state
| steps: new_steps,
ckeys: new_ckeys,
mkeys: new_mkeys,
pos: destination
}
walk_to_all_keys(grid, state, keys, best)
end
end)
end
defguard is_key(key) when key >= ?a and key <= ?z
defguard is_door(door) when door >= ?A and door <= ?Z
defp path_length(grid, from, to, ckeys) do
computed = Process.get({:registered_paths, {from, to}}, %{})
existing =
computed
|> Enum.filter(fn
{used_keys, len_or_error} ->
cond do
used_keys == ckeys -> true
used_keys -- ckeys == [] and len_or_error != :error -> true
true -> false
end
end)
case existing do
[] ->
Process.put(:used_keys, [])
len_or_error =
GridMap.get_path(grid, from, to, fn
@wall ->
false
@entrance ->
true
@empty ->
true
key when is_key(key) ->
true
door when is_door(door) ->
key = door_to_key(door)
if :lists.member(key, ckeys) do
used_keys = Process.get(:used_keys)
Process.put(:used_keys, insert(used_keys, key))
else
false
end
end)
|> case do
{:ok, path} -> length(path)
{:error, _} -> :error
end
used_keys = Process.get(:used_keys)
paths = Process.get({:registered_paths, {from, to}}, %{})
paths = Map.put(paths, used_keys, len_or_error)
Process.put({:registered_paths, {from, to}}, paths)
# IO.puts("#{inspect(from)} -> #{inspect(to)} required keys: #{used_keys}")
len_or_error
found ->
# IO.puts("#{inspect(from)} -> #{inspect(to)} found from cache")
{_, len_or_error} = Enum.min(found)
len_or_error
end
end
def insert([v | _] = list, v), do: list
def insert([c | rest], v) when c < v, do: [c | insert(rest, v)]
def insert(list, v), do: [v | list]
defp door_to_key(door),
do: door + 32
defp read_keys({coords, key}, keys) when is_key(key),
do: Map.put(keys, key, coords)
defp read_keys(_, keys),
do: keys
end
"""
#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################
"""
# """
# ########################
# #...............b.C.D.f#
# #.######################
# #.....@.a.B.c.d.A.e.F.g#
# ########################
# """
# """
# ########################
# #@..............ac.GI.b#
# ###d#e#f################
# ###A#B#C################
# ###g#h#i################
# ########################
# """
# "day18.puzzle"
# |> File.read!()
|> Day18.run()
|> IO.inspect()
As it turned out, extending to part 2 was relatively straightforward. You can see the changes here.
Interestingly enough, part 2 takes only 350ms, which is significantly faster than most times reported here. Normally I’d be proud of that, but in this contrived code I’m actually worried that I’m prematurely discarding some combinations, and that I just got lucky that the code produces the correct solution on my input.
Nice, that is encouraging.
I managed to do part 1 with breadth first and an ugly optimisation : only keep the 1000 best paths at each round.
And checking my input, it required 1876 steps. No wonder why it only took a minute to execute despite not being optimized at all. The algorithm I did use wouldn’t work for ~5400 steps, I’m pretty sure.
My answer was 7048 steps 
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 Likes
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.
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 Like
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 Likes
