Day 16: Reindeer Maze

Mix.install([
  {:kino, "~> 0.15.0"},
  {:vega_lite, "~> 0.1.11"},
  {:kino_vega_lite, "~> 0.1.13"}
])

Reading

• We’re at the Reindeer Olympics where they are running through a Maze
• Input the map of the maze
  • S denotest the starting point, orientation East
  • E marks the goal/end
  • # is a wall that can’t be passed through
  • . is just a free space
• Moving through the Maze incurs costs:
  • moving in the current facing direction: 1 point
  • rotating 90deg (either direction): 1000 points
• Output the cost of the cheapest way through the maze

Input

{map, size, start, goal} =
  Kino.FS.file_path("day16_input.bin")
  |> File.read!()
  #"################\n#...#...#...#..E#\n#.#.#.#.#.#.#.#.#\n#.#.#.#...#...#.#\n#.#.#.#.###.#.#.#\n#...#.#.#.....#.#\n#.#.#.#.#.#####.#\n#.#...#.#.#.....#\n#.#.#####.#.###.#\n#.#.#.......#...#\n#.#.###.#####.###\n#.#.#...#.....#.#\n#.#.#.#####.###.#\n#.#.#.........#.#\n#.#.#.#########.#\n#S#.............#\n#################\n"
  #"###############\n#.......#....E#\n#.#.###.#.###.#\n#.....#.#...#.#\n#.###.#####.#.#\n#.#.#.......#.#\n#.#.#####.###.#\n#...........#.#\n###.#.#####.#.#\n#...#.....#.#.#\n#.#.#.###.#.#.#\n#.....#...#.#.#\n#.###.#.#.#.#.#\n#S..#.....#...#\n###############"
  #"###############################\n#...........#...........#.....#\n#.#.#######.#.#####.#####.#.#.#\n#.#.......#.#...#...#.....#.#.#\n#.#.#.#.###.#.###.#.#.#.###.###\n#.#...#.#...#.#...#.#...#.#.#.#\n#.#.#.#.#.#.#.#.#.#.###.#.#.###\n#...#...#.................#...#\n###.#.#.#.###.#.###.#.#.#.#####\n#...#.#.#.#...#..............E#\n#.#.#.#.#.#.###########.#.#.###\n#.....#.#.#.....#.............#\n#.#.#.###.#####.###.###.#.#####\n#...........#.#.....#.........#\n#.#.#.#.#.#.#.#######.#.#.#####\n#.#.#.....#...#...#.......#...#\n###.#.#########.#.#.#####.###.#\n#...#...........#.#.........#.#\n#.#.#.###########.###.#.###.#.#\n#.#...#.......#.....#.#.....#.#\n#.#.#.###.###.#.###.#.#.###.###\n#.#.........#.#...#.#.#.#...#.#\n#.#.#.#.###.#####.###.#.#####.#\n#.....#...#...#...#...#.......#\n#.#######.#.#.#.###.###########\n#.......#.....#...........#...#\n#.#####.#####.###########.#.###\n#...#.#.................#.#.#.#\n###.#.#########.#######.#.#.#.#\n#...#.....#...#.#.#S....#.#.#.#\n###############################\n"
  |> String.to_charlist()
  |> Enum.reduce({0,0, %{}}, fn
    ?#, {x, y, acc} -> {x + 1, y, Map.put(acc, {x, y}, :wall)}
    ?S, {x, y, acc} -> {x + 1, y, Map.put(acc, :start, {x, y})}
    ?E, {x, y, acc} -> {x + 1, y, Map.put(acc, :goal, {x, y})}
    ?., {x, y, acc} -> {x + 1, y, acc}
    ?\n, {_x, y, acc} -> {0, y + 1, acc}
  end)
  |> then(fn {_, size, acc} ->
    {start, acc} = Map.pop(acc, :start)
    {goal, acc} = Map.pop(acc, :goal)
    {acc, size - 1, start, goal}
  end)

Implementation

• We’re going to implement the A-Star algorithm to traverse the Maze
• This algorithm uses a scoring function to determine which way is “better”
  • This maps 1:1 to the costs from the input

defmodule Dijkstra do
  defstruct [:candidates, :costTo, :cameFrom]
  @really_high 100_000_000
  
  def solve(map, start, goal) when is_map(map) and is_tuple(start) and is_tuple(goal) do
    state = %Dijkstra{
      candidates: MapSet.new([{start, :east}]),
      # Both: From start _to_ the stored position
      costTo: %{{start, :east} => 0},
      # Maps the position you came from the reach the given one
      cameFrom: %{}
    }

    Stream.repeatedly(fn -> :next_step end)
    |> Enum.reduce_while(state, fn _, state ->
      {position, direction} = next_candidate(state.candidates, state.costTo)

      if position == goal do
        # Found the end, return the cost for the path
        path = reconstruct(state.cameFrom, goal, direction)
        {:halt, {:ok, Map.fetch!(state.costTo, {position, direction}), path}}
      else
        # Don't revisit the current tile again
        state = %{state | candidates: MapSet.delete(state.candidates, {position, direction})}
        
        state =
          position
          |> walkable_neighbours(map)
          |> Enum.reduce(state, fn neighbor, state ->
            {new_cost, new_direction} = cost_function(position, direction, neighbor)
            cost = Map.fetch!(state.costTo, {position, direction}) + new_cost
            
            if cost < Map.get(state.costTo, {neighbor, new_direction}, @really_high) do
              %{state |
                costTo: Map.put(state.costTo, {neighbor, new_direction}, cost),
                cameFrom: Map.put(state.cameFrom, {neighbor, new_direction}, {position, direction}),
                candidates: MapSet.put(state.candidates, {neighbor, new_direction})
              }
            else
              # We have a better route already
              state
            end
          end)

        if MapSet.size(state.candidates) == 0 do
          # Exhausted all options, maze not solvable
          {:halt, :error}
        else
          # We have more options left, continue
          {:cont, state}
        end
      end
    end)
  end

  defp walkable_neighbours({x, y}, map) do
    [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
    |> Enum.reject(fn neighbor -> Map.get(map, neighbor, :free) == :wall end)
  end

  defp next_candidate(candidates, costs) do
    Enum.min_by(candidates, fn pos -> Map.get(costs, pos, @really_high) end)
  end

  @cost_move 1
  @cost_turn 1000
  defp cost_function(current, direction, next) do
    next_dir = get_direction(current, next)
    turn_count = if direction == next_dir, do: 0, else: 1
    cost = @cost_move + (@cost_turn * turn_count)
    {cost, next_dir}
  end

  defp get_direction({from_x, from_y}, {to_x, to_y}) do
    cond do
      from_x < to_x and from_y == to_y -> :east
      from_x > to_x and from_y == to_y -> :west
      from_x == to_x and from_y > to_y -> :north
      from_x == to_x and from_y < to_y -> :south
    end
  end

  defp reconstruct(cameFrom, goal, goal_direction) do
    Stream.repeatedly(fn -> :next_step end)
    |> Enum.reduce_while({goal, goal_direction, [goal]}, fn _, {pos, dir, acc} ->
      case Map.fetch(cameFrom, {pos, dir}) do
        {:ok, {p_pos, p_dir}} -> {:cont, {p_pos, p_dir, [p_pos | acc]}}
        :error -> {:halt, acc}
      end
    end)
  end
end

{:ok, score, path} = Dijkstra.solve(map, start, goal)
score

I had massive issues getting the A* implementation to find the path with the actuall lowest score. It was finding a good path, but not the optimal one.

To make everyhing simpler, I removed the whole heurestic (playing around with that never had any noticable effect) and switched to Dijkstra’s algorithm instead.

To help debug, I hacked together the following visualization. It abuses VegaLite graphs to render boxes “like pixels” onto a grid. It does the job but not very well.

alias VegaLite, as: Vl

# Invert Y-axis because VegaLite draws positive y from bottom-left instead of top-right
map_points = Enum.map(map, fn {{x, y}, _} -> %{"x" => x, "y" => -y, "type" => :wall} end)
path_points = Enum.map(path, fn {x, y} -> %{"x" => x, "y" => -y, "type" => :path} end)

Vl.new(width: 800, height: 800)
|> Vl.data_from_values(Enum.concat(map_points, path_points))
|> Vl.mark(:square)
|> Vl.encode_field(:x, "x", type: :quantitative)
|> Vl.encode_field(:y, "y", type: :quantitative)
|> Vl.encode_field(:color, "type", type: :nominal)

The problem I was having is that my solution would pick the “wrong” turn for a very specific piece of the maze in the top-left corner. With of lot of help from @mathieuDR I fixed the issue like this:

1. Ran my input through his solution to get the actual “best” route through the maze
2. Reduced the map to only the problematic corner, added appropriate start/exit points based on the output above
3. Verified that my solution made the wrong decision (see image below)

The problem was that my solution was not tracking the current direction. Rather, it was using the previous and current position to calculate the current_direction. Then, I used current and neighbor to calculate the neighbor_direction. If current_direction != neighbor_direction, we know we have turned and need to add 1000 to the path cost.

The problem is that I wasn’t tracking the direction with the actual positions in my cameFrom and costTo, my calculated current_direction wasn’t along a potential new path, but always along the currently established one.

At the converging point shown in the image, the established (green) path was weighted at 9070 while the new (red) path was 10050. It was a good 20 steps shorter, but it was incorrectly penalized with an additional turn, making it worse at 10070. This is because the direction calcualted in current_direction was :south (along the green path) rather than :east (along the red path).

Part 2

tbd…