Advent of Code 2019 - Day 18

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 day18.erl · GitHub

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

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.

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.

@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.