Day 21

Mix.install([:kino_aoc])

Section

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

# puzzle_input =
"""
...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
"""

lines =
  puzzle_input
  |> String.split("\n", trim: true)

map =
  for {line, y} <- Enum.with_index(lines),
      {char, x} <- Enum.with_index(to_charlist(line)),
      char != ?.,
      do: {char, {x, y}}

%{?# => obstacles, ?S => [start]} = Enum.group_by(map, &elem(&1, 0), &elem(&1, 1))

height = length(lines)
width = byte_size(hd(lines))

obstacles = MapSet.new(obstacles)
{sx, sy} = start

defmodule Day21 do
  def build_distance_map(width, height, start, obstacles) do
    distances =
      for x <- 0..width,
          y <- 0..height,
          {x, y} not in obstacles,
          into: %{},
          do: {{x, y}, nil}

    do_build(Map.put(distances, start, 0), neighbours(start, width, height), width, height)
  end

  defp do_build(distances, [], _w, _h), do: distances

  defp do_build(distances, [{x, y} | rest], w, h)
       when is_nil(:erlang.map_get({x, y}, distances)) do
    {min, next} =
      Enum.reduce(neighbours({x, y}, w, h), {nil, []}, fn
        {nx, ny}, {min, acc} ->
          case Map.fetch(distances, {nx, ny}) do
            {:ok, nil} -> {min, [{nx, ny} | acc]}
            {:ok, val} -> {min(min, val), acc}
            :error -> {min, acc}
          end
      end)

    distances
    |> Map.put({x, y}, min + 1)
    |> do_build(rest ++ next, w, h)
  end

  defp do_build(distances, [_ | rest], w, h), do: do_build(distances, rest, w, h)

  defp neighbours({x, y}, w, h),
    do:
      Enum.filter(
        [
          {x + 1, y},
          {x - 1, y},
          {x, y + 1},
          {x, y - 1}
        ],
        &in_map?(&1, w, h)
      )

  def in_map?({x, y}, w, h), do: x in 0..w and y in 0..h
end

dist = Day21.build_distance_map(width, height, start, obstacles)

Part 1

radius = 64

potential_positions =
  for dx <- -radius..radius,
      dy <- -radius..radius,
      rem(dx + dy, 2) == 0,
      p = {sx + dx, sy + dy},
      dist[p] <= radius,
      do: {sx + dx, sy + dy}

length(potential_positions)

Part 2

{width, height}

radius = 26_501_365