Advent of Code - 2024 Day 10

Mix.install([
  {:kino_aoc, "~> 0.1.7"},
  {:benchee, "~> 1.3"}
])

Section

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

test_input = """
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
"""
|> String.trim()

evil_input = """
0123456789876543210123456789876543210
1234567898987654321234567898987654321
2345678987898765432345678987898765432
3456789876789876543456789876789876543
4567898765678987654567898765678987654
5678987654567898765678987654567898765
6789876543456789876789876543456789876
7898765412345678987898765432105678987
8987654301234567898987654321214567898
9876543210123456789876543210123456789
8987654321214567898987654301234567898
7898765432105678987898765432321678987
6789876543456789876789876543210789876
5678987654567898765678987654567898765
4567898765678987654567898765678987654
3456789876789876543456789876789876543
2345678987898765432345678987898765432
1234567898987654321234567898987654321
0123456789876543210123456789876543210
1234567898987654321234567898987654321
2345678987898765410145678987898765432
3456789876789876543456789876789876543
4567898765678987652567898765678987654
5678987654567898761678987654567898765
6789876543456789870789012543456789876
7898765432345678989898123432345678987
8987654321234567898987654321234567898
9876543210123456789876543210123456789
8987654321214567898987654321234567898
7898765432105678987898765432345678987
6789876543456789876789876543456789876
5678987654567898765678987654567898765
4567898765678987654567898765678987654
3456789876789876543456789876789876543
2345678987898765432345678987898765432
1234567898987654321234567898987654321
0123456789876543210123456789876543210
"""
|> String.trim()

grid =
  evil_input
  |> String.split("\n")
  |> Enum.map(fn line ->
    line
    |> :binary.bin_to_list()
    |> Enum.map(& &1 - ?0)
  end)

grid =
  for {row, i} <- Enum.with_index(grid),
      {val, j} <- Enum.with_index(row),
      into: %{},
      do: {{i, j}, val}

defmodule AoC2024.Day10 do
  def part_1(grid) do
    Task.async(fn ->
      grid
      |> Enum.filter(&elem(&1, 1) == 0)
      |> Enum.map(&elem(&1, 0))
      |> Enum.map(&dp_1(grid, &1))
      |> Enum.map(&length/1)
      |> Enum.sum()
    end)
    |> Task.await(:infinity)
  end

  defp dp_1(grid, {i, j}) do
    case grid[{i, j}] do
      9 ->
        [{i, j}]

      n ->
        memoized({i, j}, fn ->
          [{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}]
          |> Enum.filter(&grid[&1] == n + 1)
          |> Enum.flat_map(&dp_1(grid, &1))
          |> Enum.uniq()
        end)
    end
  end

  def part_2(grid) do
    Task.async(fn ->
      grid
      |> Enum.filter(&elem(&1, 1) == 0)
      |> Enum.map(&elem(&1, 0))
      |> Enum.map(&dp_2(grid, &1))
      |> Enum.sum()
    end)
    |> Task.await(:infinity)
  end

  defp dp_2(grid, {i, j}) do
    case grid[{i, j}] do
      9 ->
        1

      n ->
        memoized({i, j}, fn ->
          [{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}]
          |> Enum.filter(&grid[&1] == n + 1)
          |> Enum.map(&dp_2(grid, &1))
          |> Enum.sum()
        end)
    end
  end

  defp memoized(key, fun) do
    with nil <- Process.get(key) do
      fun.() |> tap(&amp;Process.put(key, &amp;1))
    end
  end
end

AoC2024.Day10.part_1(grid)

AoC2024.Day10.part_2(grid)

Benchee.run(%{
  part_1: fn -> AoC2024.Day10.part_1(grid) end,
  part_2: fn -> AoC2024.Day10.part_2(grid) end
})