d16

Section

defmodule D16 do
  def parse(input) do
    for {line, row} <- Enum.with_index(String.split(input)),
        {char, col} <- Enum.with_index(String.to_charlist(line)),
        reduce: {MapSet.new(), nil, nil} do
      {walls, start, finish} ->
        case char do
          ?# -> {MapSet.put(walls, {row, col}), start, finish}
          ?S -> {walls, {row, col}, finish}
          ?E -> {walls, start, {row, col}}
          ?. -> {walls, start, finish}
        end
    end
  end

  defp vec_add({r, c}, {dr, dc}), do: {r + dr, c + dc}
  defp rot_cw({dr, dc}), do: {dc, -dr}
  defp rot_ccw({dr, dc}), do: {-dc, dr}

  defp pop_min(distance, frontier) do
    key = Enum.min_by(frontier, &Map.get(distance, &1))
    {key, MapSet.delete(frontier, key)}
  end

  defp dijkstra(walls, distance, frontier, finish) do
    {key, frontier} = pop_min(distance, frontier)
    {pos, heading} = key

    cond do
      key == finish ->
        distance

      is_nil(heading) ->
        dijkstra(walls, distance, frontier, finish)

      true ->
        {distance, frontier} =
          for {dest = {dpos, _}, cost} <- [
                {{vec_add(pos, heading), heading}, 1},
                {{pos, rot_cw(heading)}, 1000},
                {{pos, rot_ccw(heading)}, 1000},
                {{pos, nil}, 0}
              ],
              reduce: {distance, frontier} do
            {distance, frontier} ->
              new_distance = Map.get(distance, key) + cost
              old_distance = Map.get(distance, dest)

              if !MapSet.member?(walls, dpos) and
                   (is_nil(old_distance) or
                      new_distance < old_distance) do
                {Map.put(distance, dest, new_distance), MapSet.put(frontier, dest)}
              else
                {distance, frontier}
              end
          end

        dijkstra(walls, distance, frontier, finish)
    end
  end

  def part1({walls, start, finish}) do
    key = {start, {0, 1}}
    distance = dijkstra(walls, %{key => 0}, MapSet.new([key]), {finish, nil})
    Map.get(distance, {finish, nil})
  end

  defp reconstruct(_, _, _, visited, []), do: visited

  defp reconstruct(walls, distance, start, visited, [head | heads]) when head == start do
    reconstruct(walls, distance, start, visited, heads)
  end

  defp reconstruct(walls, distance, start, visited, [key = {pos, heading} | heads]) do
    cost = Map.get(distance, key)

    neighbors =
      if is_nil(heading) do
        [{-1, 0}, {0, 1}, {1, 0}, {0, -1}]
        |> Enum.map(&{{pos, &1}, 0})
      else
        [
          {{vec_add(pos, rot_cw(rot_cw(heading))), heading}, 1},
          {{pos, rot_cw(heading)}, 1000},
          {{pos, rot_ccw(heading)}, 1000}
        ]
      end
      |> Enum.filter(fn {key, points} ->
          Map.get(distance, key) == cost - points
      end)
      |> Enum.map(&elem(&1, 0))

    reconstruct(walls, distance, start, MapSet.put(visited, key), neighbors ++ heads)
  end

  def part2({walls, start, finish}) do
    key = {start, {0, 1}}
    distance = dijkstra(walls, %{key => 0}, MapSet.new([key]), {finish, nil})

    reconstruct(walls, distance, key, MapSet.new(), [{finish, nil}])
    |> Enum.map(&elem(&1, 0))
    |> Enum.uniq()
    |> Enum.count()
  end
end

ExUnit.start()

defmodule D16.Test do
  use ExUnit.Case

  test "small" do
    input = "###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############
"
    assert 7036 == D16.parse(input) |> D16.part1()
    assert 45 == D16.parse(input) |> D16.part2()
  end

  test "large" do
    input = "#################
#...#...#...#..E#
#.#.#.#.#.#.#.#.#
#.#.#.#...#...#.#
#.#.#.#.###.#.#.#
#...#.#.#.....#.#
#.#.#.#.#.#####.#
#.#...#.#.#.....#
#.#.#####.#.###.#
#.#.#.......#...#
#.#.###.#####.###
#.#.#...#.....#.#
#.#.#.#####.###.#
#.#.#.........#.#
#.#.#.#########.#
#S#.............#
#################
"
    assert 11048 == D16.parse(input) |> D16.part1()
    assert 64 == D16.parse(input) |> D16.part2()
  end
end

ExUnit.run()

input = File.read!(__DIR__ <> "/input")
D16.parse(input) |> D16.part1()

D16.parse(input) |> D16.part2()