Advent of Code 2023 - Day 21

Sample

sample = """
...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
"""

"...........\n.....###.#.\n.###.##..#.\n..#.#...#..\n....#.#....\n.##..S####.\n.##..#...#.\n.......##..\n.##.#.####.\n.##..##.##.\n...........\n"

Input

input = """
...................................................................................................................................
.............#......#.........#....#...#.##.........#.#.#...............#..#................#......#.....#.....###...........#.....
.#............#.#....#......#..#....#..##.........#...#...#.......................#.......#..##.....#......#...........#........#..
.#..##......#.#...##...............#..#....#.#........#...#.........................#.....#........#..#.......#...............#.#..
....#....##......#.#..#.#...#............#.#............#................###...##........#.....#....#..#.#.........................
...#.....#...#....#.#..#..#.#.....#...........#.........#.......#..................###..#.............#.........#......#.....#.....
....#...##..........#.##...#.......#..#..#....#.##....#..........................#.#.#..........#....#.................#...........
......#.....#...........#...#...#....#...........#............#.#.............#.........##.....#...#.##...#..#.................##..
.......#..#...........#........#...#.#........................#..............#........##............#.......#.#...#...........#....
........#.........#..........#.#.#.#.#.#.......##...............#....#.............................#......#..#.............##....#.
.#.##.................#..........##....##.#.#......#..............................##.#......#.......#...........#.#..#....###.#..#.
.#.#......#..........#........##...........#..#............##......#.............#..#...........#.............#..............#.....
....#.............#....#......#....#...........#...............#.............................#.#........#......#.##..#..#.#...###..
....#.............#.................#.............................................#.#....#.#.......#..##..#...........#..#.#.#..#..
...................................#.#...#.#.................#..#..#.....#...........................#....#..#...#.............##..
....##.#...........#.......#...............#..........#.............#.#.............#......##...#........#.........#.....##.##.....
............#..#.......#..................................##......#....................#..##.........#..#.....#...#................
.....###..#.##.#.......#.................................#.....##.........#............#......#......#........#..#.................
..#.#....##.......#.........###......#...#............##..#...........#..##.................##.....#.........###...#.......#.#.....
.................#.#.........##....#................#.............##.#.........................#...............................#...
............................#.#........#............#............................#........#.#..............##.#.#.#.....#..........
...#...#.....#..............#.#..................#.#......##..........#.........#....................##...#.#.....#..#..........#..
..........#...#........#....#.##................##................#.####...#..#.##...........#............#.##......#.#..#..#...#..
.#.....#........#.......#.......#..#...............#........#......#..#..#.###..............#.####....##........#....#.#.......#...
..##....#....................#...............#...............#...................#.................#.#..#........#............#....
...#..#....#........#...##..#.#..#.............................#.......#...#...#.....................#.##....##......#..#..#.....#.
.....#....#..............##..#.............#..#...#........##..#...#...#.........................##.....#....#......#..#...........
.##......#.#...................................#..........#.#.......#...#...##......#...........#..#.....#......#..#...............
.......#..##.........#.............................#.#.............#...##..#.####........#.............#......#.......##.......#...
...#.................#.##..##.#........................#.#..........##.....#......#....#.#.........#...............................
..............#......#.................##..#.........#....###...#........#......#.....#......................##.....#..........#...
......#.......##..#..#.......#..................#.......#..##........#....#..#...#.##...................#..........#......#........
..#..#.#.#.....#...#.........#..............#..#....#......#......#.#.....#......#......#.....................#.#..................
..................#.....................#.#.......#.#..........#.....#.........#....#.....#............##..#...#...#...........#...
.#...#......#.#.#.....................#............#.......#....#.............#..#....#..##.#..........#.......#..#...#....#.......
.#....#..#.#...........##............#.#....#.#..#......###.............#..#.....#..#.##.#..#......................#.........#.....
...#...#.......#.#..#..#............#..#....#..#....#..#.......#.........#......#.#.###...........................#.......###......
...#...........#.......##............#..#.....##..####.......#..........#....#...#.........................#....#..#...............
.........#.......#....#..............#...........#.#................#....#.....##......#......#.............................#..#...
..##....#.#.#....#.................#..#....#...#...#..........#...#...#...#....#.....#........................#......#.............
..#....##.........#.#...........#..#.##.#..........................#......##.....#...#...#.....#..#.............##.................
...#........#...##.#............#..#...#.#.#.#....#.#..#..............#.###.#.#..#......#..#.......#..........#....##.#.....##.....
..#.#..#......#............#.##.....#.....#.....##.....##.......#........#.#......#.....#.#.......#..............#....#...#.#..#...
..................#.........#..#.#.#.#..........#....#......#........#....................#.............#.....................#....
.......................................#..#.....#..#....##............#...........#...#.............#..#......................#....
..#.............#..........#..#........##..#.......................#..#......#...#.#.#......#..#...................#.....#.##......
...#..#................#.#........#.#.................#..#.....#........##.....#...........##......#..#..#......................#..
..###.....#..................#................#.#....................#..............#....#...........................#.#.##.....##.
.........#...#...........#.#...#....#.........#..##.###..............#......#..#....#....###.#.........................#...........
......#..##...........##......#..#..#.#................#..............#...#......#....#.....#...............#...............#...#..
.#......##.........##.......###..#.##.#......#...#.............#..#....#..#.................##...................................#.
...........................................##........#......#....................#.#...................##....#............##.....#.
..#..##..#........#.......###...#.....#............#.#............#..##....#............##..........#.##.......###.................
........#..................#...#.........#..........#.#.....#..............##......................................................
...............#...#......##.................#.......#...#................#..#.............#.....#...........#...#.................
....................#.......#.....#...#.#..#.......#........#......#...#.###........#....#....#.......#...#.#.....#.#..............
...#..............#.#......#.#.#..#.#....#.....#..#........#...............#...##..........................#.......................
...............#........#................#.#.....#....#..#......#......##....##....#.#........##.#.....#.........##.............#..
...#.......#....#......#.....#.#....#...........#.#..........#....#.......#..#............#.#.....#.###............................
.##........#..#...#..##.##..#.#.#.......#......#.#.........................#.....#...............#.................................
.#..............#......#.#.##.#.....##..#..............#....#.#..................##..#....#..#.#...#..#..........#..#..#.........#.
..........#..............#.............#....#...........##.#...#....#...#..#..#......#....#.#.#.....##..............##.............
.............#...#...#............#.....##..#......#.#.#........#.......#................#...........#............#.......#........
..............#...###.#.#.......##........#.#..##......#.#.#..#...........#..............#.......#....#.#.#........................
..........##...###........#........#..#...............##..#....##......##........##...#.......#.....###....#...#..#.#...#..#.......
.................................................................S.................................................................
..............#...##...........................#.....#..#...#......#...................#............#...........##.................
........#..###.........#...#........#..#...#...............#.........#..........#...#............#...#........##..##......#........
............#.....###.....##.....#.#..#..#..#.....#............#.......#.#....#.....#.#...#......##.........#...#....#.#...........
........#....#...##..##...........#.......#.....#........##.....#.......#......#.....................#.....#....#..#...............
...........#..##.#...#...#......#.#.......#............#.......#....#........#....#........##.....#...#....#....#.....#............
....................#........##........#..............#.##.#..##...#..#.....##.............#....#.........#.##..................#..
........................#.........#..................#..#...................#.#.............#...........##..#...#.#...#.........#..
...................##..#........#..............##....#...#.........................#....#....#.##...........##.#...................
.##.................#...#.....#.#..#.#..#.#...#....#..............#..#..#...........##.....................##..#...#...............
...............#.........#....#.###..........#......................##...##.......#..##.###..#.....#...............................
.##..............#.....#.#.#............#......#...............#..#.#.........#.......#..#...#....#.#.........#..#.................
......#.............#..........#................................#..........#...#......#.#...#.....#...........#............##......
..#....#..........#...#.....##......#........#................#.........##............#......#........#..##....#...................
..#...#...................................#..#...........#........#....##.....#....#....#.....###..#..#......#...........#.........
...#.#...#..........##...........#.................##...#.........#......#.....#....#.....#......#..............................#..
.#........#..............##.....#..#.....#...#...##.#........................................#.#....#.......................###....
..#....#.............#.....................#.......#.......#.##.....#............#.....#.....#...#...............................#.
.#...#.#...............#.#.........##.......#.###.....#...............#...#.....#......#..##.....#...#.#.#...............#..##..#..
......##...#................#...........#.#......#.................#....#...#...#..............#.#.......#.........#...#.##........
............#...#.......#.....##.#..#...#...................#.............#...........##.........#..#.....#............##.....#....
....#..###.......#............##...##........#.#....#...................###............#.#...#..#..#.#..............#.........#....
..........#......#........##............##....................#.#..#................#....##.#.#.#....##.#...........##....#........
............##.#...#..............##......#......#.......#...........#.........#..........##.#.................#............#...#..
...#.......#.......................#.......#...#...........................##..#..............#....##..........................#.#.
.#..#.#....#.#....#..............#.........#..........#.......#.#..............#....#.#..##.#....#.....................#..#.#......
..#....#.........#..............#...#...#..#.#..#..##....##..#.........#....................#.......#........##......#...#..#...#..
..##.........#..#.##....................##.#.#......#..#.#........#...........#...#.....#..####....................#...#...........
...#...............#..##...............#......#...##.........#.........#........##.............##..........#.#..#.........#........
....#............................#.#......#....#.#...#......#.......#.........#...........##..................#.#..................
...................#...................................#.....#.....#.#....#...........#.....##...............#...............#.#.#.
..#..#.......#.##.#..#...#................#..#.......#....#..#.......#...#........#...#....#.#..........#......#......###..#.......
.......#.................#..........#.......#..........................#..##...#.##..#..##.#..........#....#.......................
.......#........#.........#...........#.....#..#..............#.......#.#..##......#........#.............##................###....
.#.....#.#....##.....#................#..............#...............#..##..##.#.......#.#.#...........#......#......#..#.#........
.....#..#...............#..#.#..............#..#........................#.....#.#....###...........#......##......#..#.............
.....##..........#.#.#...................#..........#........##.......#....#......#....##.........#.#....#............#..#.........
........#.#........#.#..#.#...#.........................##.#.........#.............##...#.............#..#...##..#..#..............
....#...................#.....#.#.#.......##........#.#.#..#.........#....##......................#...#.#..#......#.........##.....
.....#.....#...........#.....#............................#..#........#............#.................#................##..#.#......
.###..#.......##..#.............#.....................#......##......#..............#..................#..#.........#........#.....
..#.#...#............#........................#............##..#...##....##....#..#......................#..#..........#.#.........
......#.........#..#......................................#.#.#.#.#..#......................#.##...#....#..#.#.....................
....#..........................................#.....##.........................#.................##...........#....##......#...##.
....................#.......#.#....##...#........#.....#...##......#.....#......................#..#.....#.#..#...#...#............
..#................#......#.#...#.......#....................##.#.......#.#...#...............##.#.....#......#.#..###....#..#.#...
........................#........#....#.#.#.......#.#...................#.##....#............#.......#...#....#..#....##....#..#...
..............#...#.#...####.......................#....##.....#...#...#.#.#...#..............#....#.#....#..................##....
.....#.....#..............#...#......#....#.............##................#..................................#..........#..........
......##.........#.......#...#....#...##....#..............#.#.#...........##................#..................#...#...#..........
.#..#.....#.......#.#..#...#......#.....#............................#.....................#..#..#..#....#.......#.........#.#...#.
......#.#..#.#.#..............#....#....#..#..............#............##................#......#......##.#..#....#................
...........#...................##.#..##.#.##...#.........#.##..#.........#............#.#.#.#...#.#.#..#..##.#......##.........##..
........##.......#.#..#........#..##.#..#.#.....#.........#.##.#..................#.##................###..##.....#.....#..........
.....................#...#........#.##.........#...........##..##.#.............#.............#....#.....##....#.#.....#.##........
...#...##...............#.##...........#.#.................#....#...#.#............#.#....##......#.........#..#....#.#.#.......#..
..#..#.#...........#..##....#...#...##..###..#...#................#............................#.........#.......#...#...#.#.#..##.
............#..........#.#.#...##...............#...#.............................###....###..........###......#.......#....#.#....
..#.#.##.........##....#.#...............#...#..#...................#........#.#.........#.#...#......#....#.#....##.....#....#....
...#.#.......#...#...#....#.....#...#..#.....#....#............#...#.......##.#................#...#......#....#.........##........
.................#.#.###........#..#...##............##...........#.............................#.#.#.......#.........#...#....##..
....#..........#.......##.......#..#.....#..#.......................................#..........#..............#.........#.##....#..
......#......#..##..#..##....#........#.#....##........#.#..................#.#.....#.............###.#...#...#........#.....#.....
......#.........##....#...................#...#..#..#..................#............#.....#..#.......#....#......#..#........#.....
..#.............#....#......#...###.......#..#....................................#.........##.........#.#..................#...#..
...................................................................................................................................
"""

"...................................................................................................................................\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.##......#.#...................................#..........#.#.......#...#...##......#...........#..#.....#......#..#...............\n.......#..##.........#.............................#.#.............#...##..#.####........#.............#......#.......##.......#...\n...#.................#.##..##.#........................#.#..........##.....#......#....#.#.........#...............................\n..............#......#.................##..#.........#....###...#........#......#.....#......................##.....#..........#...\n...." <> ...

Part 1

defmodule Part1 do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.reduce(
      {MapSet.new(), nil},
      fn {row, y}, acc ->
        row
        |> String.graphemes()
        |> Enum.with_index()
        |> Enum.reduce(
          acc,
          fn {cell, x}, {rocks, start} ->
            case cell do
              "#" -> {MapSet.put(rocks, {x, y}), start}
              "S" -> {rocks, {x, y}}
              _ -> {rocks, start}
            end
          end
        )
      end
    )
  end

  def move(_, starts, 0), do: starts

  def move(rocks, starts, count) do
    new_starts =
      starts
      |> Enum.map(fn {x, y} ->
        [
          {x + 1, y},
          {x - 1, y},
          {x, y + 1},
          {x, y - 1}
        ]
        |> Enum.filter(fn n ->
          !MapSet.member?(rocks, n)
        end)
      end)
      |> List.flatten()
      |> Enum.into(MapSet.new())

    move(rocks, new_starts, count - 1)
  end
end

{rocks, start} = Part1.parse(input)
Part1.move(rocks, [start], 64) |> MapSet.size()

3615

Part 2

defmodule Part2 do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.reduce(
      {MapSet.new(), nil, 0, 0},
      fn {row, y}, acc ->
        row
        |> String.graphemes()
        |> Enum.with_index()
        |> Enum.reduce(
          acc,
          fn {cell, x}, {rocks, start, width, height} ->
            case cell do
              "#" -> {MapSet.put(rocks, {x, y}), start, max(x + 1, width), max(y + 1, height)}
              "S" -> {rocks, {x, y}, max(x + 1, width), max(y + 1, height)}
              _ -> {rocks, start, max(x + 1, width), max(y + 1, height)}
            end
          end
        )
      end
    )
  end

  def move(rocks, frontier, dists, width, height) do
    new =
      frontier
      |> Stream.flat_map(fn {x, y} ->
        [
          {x + 1, y},
          {x - 1, y},
          {x, y + 1},
          {x, y - 1}
        ]
        |> Stream.filter(fn {nx, ny} ->
          !MapSet.member?(rocks, {Integer.mod(nx, width), Integer.mod(ny, height)}) &&
            !Map.has_key?(dists, {nx, ny})
        end)
        |> Stream.map(fn {nx, ny} ->
          {{nx, ny}, dists[{x, y}] + 1}
        end)
      end)
      |> Enum.into(Map.new())

    {Map.keys(new), Map.merge(dists, new)}
  end
end

# Let's look at some patterns:

# steps = 1000

# {rocks, start, width, height} = Part2.parse(input)
# 1..steps
# |> Enum.reduce(
#   {[start], %{start => 0}},
#   fn n, {frontier, dists} ->
#     {frontier, dists} = Part2.move(rocks, frontier, dists, width, height)
#     count = dists |>  Map.values |> Stream.filter(fn d -> rem(d, 2) == rem(n, 2) end) |> Enum.count
#     IO.puts("#{n}: #{count}")
#     {frontier, dists}
#   end)

# derived formula:
f = fn x ->
  trunc(3734 + 29551 + 29432 * (x * (x + 1) / 2 - 1) + 119 * (x - 1))
end

steps = 26_501_365
# (steps - 65) / 131 = 202300

f.((steps - 65) / 131)

602259568764234