Day 16

Mix.install([:kino_aoc, :image])

Setup

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2024", "16", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))

{:ok,
 "#############################################################################################################################################\n#.....#.......#.............#.........#.......................#.......#...#...............#.....#.#.................................#.#....E#\n#.#####.###.###.#######.###.#.#.#######.#.###.#####.###.#######.#.###.###.#.#####.#####.###.#.#.#.#.#####.###.#.###.#######.###.#.#.#.#.#.#.#\n#.......#...#...#.....#.#.#.#.#.#...#...#.....#...#.#...#.......#...#.#...#...#...#.#...#...............#...#...#.#.......#.#...#.#.#...#.#.#\n#########.#.#.###.#####.#.#.#.#.#.#.#.#########.#.#.###.#.#########.#.#.#.#.###.#.#.#.###.###.#####.###.###.#.#.#.###.###.#.#.###.#.#.###.#.#\n#.......#.#.#.#...#...#.#.#.#.#...#.....#.......#.#...#.#.#...#...#.#...#.#.#...#.....#...#.#...#...#.....#.#.....#.....#.#...#...#.#.#...#.#\n#.#####.#.###.#.#.#.#.#.#.#.###########.#######.#.###.#.#.###.#.#.#.#.#####.#.###.###.#.###.###.#.###.#.###.#.#.#.#.#.#.#.#.#.#.###.###.#####\n#...#...#.......#.#.#...#.#...........................#.#.#...#.#...#.#.....#.#.....#.#...#...#.....................#.#.#...................#\n#.#.#.#######.#####.#####.###########.#######.#####.#.###.#.###.#######.#####.###.#.#.###.#.#.#.#.#######.###.#.#####.#.#.#.#.###.###.#.###.#\n#.#...#.....#.#...#...#.......#.......#.....#...#...#.....#.#...#.....#...#...#.....#...#...#.#...#.......#...#.#...#.#.#.#.#...#.#...#...#.#\n#.#.###.###.###.#.#.#.###.###.#.#.#####.###.###.#.#########.#.###.###.###.#.###.#.###.#######.#####.#######.#.#.#.#.#.###.###.#.#.#.#######.#\n#.#.....#.......#.#.#...#.#...#.#...#...#.#.#.#.#.......#...#...#...#.......................#...#.#.#.....#.#.....#.#.........#...#.#.....#.#\n#.###.###########.#####.#.#####.#.#.#.#.#.#.#.#.###.###.#.#.###.###.#########.###.#.#.#.###.#.#.#.#.#####.#.#.#.#####.#######.#####.#.###.#.#\n#...#...................#.....#.#.#.#.#.#.....#.....#.#...#.#.#...#.....#...#.....#.#.#.#.#.....#.#.....#.#...#.#.........#...........#.....#\n#.#.#.#.###.#.###############.#.#.#.#.#.#############.#####.#.###.#####.#.#.#####.#.#.#.#.#######.#####.#.###.#.#.###.###.#.#.###.###########\n#.#.#.#.#.#.#.#.....#.......#.#...#...#...............#...#...#.#...#...#.#.......#.#.#.#.......#...#...#.....#.#.#.......#.#...#.#.........#\n#.#.###.#.#.###.###.###.#.#.#.###.#.#####.###.###.###.#.#.###.#.#.###.###.###.###.#.#.#.###.###.###.#.###.#####.#.#.#.###.#.#.#.###.#######.#\n#.#.....#.#...#.#.#...#.#.#.#...#.#.#...#...#...#...#...#...#...#.....#...#...#.......#.....#.#.....#...#.......#...#.#...#...#...#.#.#.....#\n#.#######.###.#.#.###.#.#.#.#.#.#.###.#.#####.#.#.#.#########.#.#######.#.#.#.#.#############.#####.###.#########.#####.###.#####.#.#.#.#.###\n#.#.......#.#.....#...#.#.#...#.#.#...#.....#.#.#.#.........#.#.........#.#.#.#.#.................#.#.#...#.......#.........#...#...#.#.....#\n#.#.#####.#.#######.#####.#######.#.#####.#.###.#.#########.#.#.#########.#.#.#.###.#######.#.#####.#.###.#.#######.#.###.###.#.#####.###.#.#\n#.#.....#.......#...#...#...#.....#.#...........#.#.......#...#.#...#.....#.#.#...#.#.......#.#...#...#...#.....#...#...#.#.................#\n#.#####.#######.#.###.#.###.#.#####.#######.#####.#.#.###.#####.#.#.###.###.#.###.###.#####.###.#.###.#.#######.#.#####.#.#####.#.#.###.#.#.#\n#.#...#.#.....#...#...#...#.#.......#.....#.#.....#.#...#.#...#.#.#...#.#...#.#.#...#.#...#.#...#...#.#.........#.....#.#.......#...#...#.#.#\n#.#.#.#.#.###.#.###.#####.#.#.#####.#.###.###.#########.###.#.#.#.###.#.#.###.#.###.#.#.#.###.###.###.###############.#.###########.#.###.#.#\n#.#.#.#.#.#.....#...#...#...#.....#...#.#...#.#...#...#.#...#.#...#...#.#.#.#.#.........#.#...#.#.....#.......#.......#.........#...#.#.....#\n#.#.#.#.#.#######.###.#.#.#.#####.###.#.###.#.#.#.#.#.#.#.###.#####.#####.#.#.#########.#.#.###.#######.#######.###############.#.###.#.#.###\n#.#.#...#.........#...#.#.#.....#...#...#.#.....#...#...#.#.#...#...#.....#.#.....#.....#...#.....#.....#.....#...#...#...#.....#...#.#.#...#\n#.#.#########.#######.#.#.#.###.###.###.#.###########.###.#.###.#.###.#.###.#####.#.#########.#.#.###.#.#.###.#.#.#.#.#." <> ...}

%{?# => walls, ?S => [start], ?E => [finish]} =
  puzzle_input
  |> String.trim()
  |> String.split("\n", trim: true)
  |> Enum.with_index()
  |> Enum.flat_map(fn {row, y} ->
    row
    |> String.trim()
    |> String.to_charlist()
    |> Enum.with_index()
    |> Enum.map(fn {char, x} ->
      {{x, y}, char}
    end)
  end)
  |> Enum.group_by(&elem(&1, 1), &elem(&1, 0))

walls = MapSet.new(walls)

MapSet.new([
  {76, 13},
  {112, 138},
  {38, 2},
  {124, 56},
  {83, 76},
  {140, 11},
  {100, 134},
  {75, 140},
  {103, 106},
  {68, 134},
  {124, 60},
  {35, 30},
  {2, 132},
  {8, 50},
  {78, 98},
  {101, 62},
  {98, 136},
  {95, 56},
  {74, 12},
  {102, 74},
  {22, 38},
  {14, 86},
  {12, 135},
  {86, 10},
  {29, 26},
  {4, 81},
  {31, 42},
  {9, 34},
  {137, 16},
  {86, 138},
  {90, 0},
  {14, 122},
  {120, 42},
  {102, 57},
  {84, 102},
  {138, 124},
  {0, 101},
  {116, 96},
  {54, 138},
  {18, 134},
  {82, 60},
  {15, 92},
  {58, 58},
  {78, 75},
  {75, 0},
  {16, 73},
  {76, 2},
  {58, 84},
  {138, ...},
  {...},
  ...
])

{_, {w, h}} = Enum.min_max(walls)

w = w + 1
h = h + 1

141

put_in(%{}, [Access.key(:a, %{}), :b], 10)

%{a: %{b: 10}}

defmodule Race.B do
  @turns ~w'^ > v <'a

  defguardp score(elements, pos, dir) when :erlang.map_get({pos, dir}, elements).score

  def search_paths(start, finish, dir \\ :>, walls) when dir in @turns do
    result = do_search([{0, [{start, dir}]}], walls, %{})

    %{paths: visited, score: score} = result[{finish, :>}]

    all = get_all(visited, result)

    {score, all}
  end

  def get_all(path, seen) do
    Enum.reduce(path, MapSet.new(), fn p, acc ->
      path = MapSet.new(seen[p].paths, fn {p, _} -> p end)
      MapSet.union(acc, path)
    end)
  end

  def do_search([], _, visited), do: visited

  def do_search([{cost, [{curr, dir} | _] = path} | rest], walls, visited)
      when cost == score(visited, curr, dir) do
    visited = Map.update!(visited, {curr, dir}, &amp;%{&amp;1 | paths: path})

    do_search(rest, walls, visited)
  end

  def do_search([{cost, [{curr, prev} | _] = path} | rest], walls, visited)
      when not is_map_key(visited, {curr, prev})
      when cost < score(visited, curr, prev) do
    visited = Map.put(visited, {curr, prev}, %{score: cost, paths: path})

    @turns
    |> Enum.map(fn dir -> {cost + cost(prev, dir), [{step(curr, dir), dir} | path]} end)
    |> Enum.reject(fn {_cost, [{pos, _} | _]} -> pos in walls end)
    |> sort_merge(rest)
    |> do_search(walls, visited)
  end

  def do_search([{_, [_curr | _]} | rest], walls, visited),
    do: do_search(rest, walls, visited)

  # Going straight is cheap and turning is costly
  defp cost(a, a), do: 1
  defp cost(_, _), do: 1001

  defp step({x, y}, :^), do: {x, y - 1}
  defp step({x, y}, :>), do: {x + 1, y}
  defp step({x, y}, :v), do: {x, y + 1}
  defp step({x, y}, :<), do: {x - 1, y}

  defp sort_merge([], bs), do: bs
  defp sort_merge(as, []), do: as

  defp sort_merge([a | as], [b | bs]) do
    if a < b do
      [a | sort_merge(as, [b | bs])]
    else
      [b | sort_merge([a | as], bs)]
    end
  end
end

{:module, Race.B, <<70, 79, 82, 49, 0, 0, 23, ...>>, {:sort_merge, 2}}

{score, paths} = Race.B.search_paths(start, finish, walls)

{134588,
 MapSet.new([
   {77, 129},
   {17, 138},
   {17, 137},
   {37, 139},
   {19, 137},
   {100, 131},
   {139, 68},
   {14, 139},
   {79, 128},
   {19, 138},
   {50, 137},
   {139, 67},
   {137, 104},
   {137, 117},
   {131, 49},
   {107, 125},
   {3, 127},
   {135, 64},
   {4, 131},
   {21, 134},
   {63, 127},
   {101, 124},
   {5, 139},
   {125, 14},
   {129, 48},
   {139, 70},
   {21, 119},
   {17, 129},
   {137, 120},
   {17, 136},
   {131, 120},
   {32, 139},
   {133, 21},
   {102, 123},
   {12, 111},
   {123, 19},
   {112, 127},
   {73, 129},
   {7, 116},
   {127, 22},
   {7, 137},
   {9, 131},
   {24, 133},
   {137, 95},
   {8, 133},
   {134, 7},
   {129, ...},
   {...},
   ...
 ])}

Part 1

score

134588

Image.new!(w, h)
|> Image.mutate(fn img ->
  for {x, y} <- walls do
    Image.Draw.point(img, x, y, color: [128, 0, 0])
  end

  for {x, y} <- paths do
    Image.Draw.point(img, x, y, color: [0, 255, 0])
  end

  img
end)
|> elem(1)
|> Image.resize!(6, interpolate: :nearest)

Part 2

MapSet.size(paths)

625