Advent of Code 2024 - Day 10

Same!
I accidentally solved part 2 first and then fixed it to run part1. lol

https://github.com/rugyoga/aoc2023/blob/main/lib/2024/10.ex

Solved Part 2 first, too. Here’s my code using dynamic programming (not very FP, though):

defmodule AoC2024.Day10 do
  @type grid() :: %{coord() => 0..9}
  @type coord() :: {i::non_neg_integer(), j::non_neg_integer()}

  @spec part_1(grid()) :: non_neg_integer()
  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

  @spec part_2(grid()) :: non_neg_integer()
  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_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

  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(&Process.put(key, &1))
    end
  end
end

Benchmark (without the parsing part)

Name             ips        average  deviation         median         99th %
part_2        508.15        1.97 ms     ±3.72%        1.96 ms        2.04 ms
part_1        409.82        2.44 ms     ±1.00%        2.44 ms        2.53 ms

And I also solved part 2 first.

https://github.com/bjorng/advent-of-code/blob/main/2024/day10/lib/day10.ex

Is this the first time I’ve cranked out the graphs for 2024? I think it is…

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day10.ex

Part 2 was trivial after implementing part 1. I like when that happens.

Name                     ips        average  deviation         median         99th %
day 10, part 1          3.87      258.13 ms     ±0.90%      258.51 ms      263.14 ms
day 10, part 2          4.19      238.57 ms     ±0.55%      238.51 ms      241.13 ms

Solving part2 first club++.

I guess the functional language forces us to think recursively, although I found it quite hard to reason about Part 1, it turned out I just needed to add a uniq call to the part 2 solution.

def part1({grid, zeros}) do
  zeros
  |> Enum.map(fn point -> point |> find_trails(grid, 0) |> Enum.uniq() |> Enum.count() end)
  |> Enum.sum()
end

def find_trails(point, _grid, 9), do: [point]

def find_trails({x, y}, grid, height) do
  find_neighbours(x, y, height + 1, grid)
  |> Enum.flat_map(fn {point, _} -> find_trails(point, grid, height + 1) end)
end

def find_neighbours(x, y, height, grid) do
  grid
  |> Map.take([{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}])
  |> Enum.filter(&match?({_, ^height}, &1))
end

https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2024/day10.exs

My solution uses my grid module with BFS search, so it’s not very interesting to share so just the link

Less interesting solution (no brainer):
https://github.com/Aetherus/advent-of-code/blob/0cd3b4686a6cdb4aac1e91ca8dc5742ff0dc6a78/2024/day-10-graph.livemd

After having the most inefficient code yesterday that took almost 40 minutes to run hahaha, I’m surprised that today tooks 2ms to run, at the first try.

Also solved both at the same time.

I think it might be time to build a custom grid module…

https://github.com/jbonet/advent_of_code_2024/blob/main/lib/advent_of_code_2024/days/10.ex

LOC: 21

defmodule Aoc2024.Day10 do
  import Enum
  def part1(file), do: main(file, &hd/1)
  def part2(file), do: main(file, & &1)

  def main(file, fun) do
    rows = file |> File.read!() |> String.trim() |> String.split("\n", trim: true)
    rows = map(rows, fn line -> line |> String.to_charlist() |> map(&(&1 - ?0)) end)
    grid = for {row, i} <- with_index(rows), {x, j} <- with_index(row), into: %{}, do: {{i, j}, x}
    for({{i, j}, 0} <- grid, reduce: 0, do: (sum -> sum + count(-1, 0, {i, j}, grid, fun)))
  end

  def count(x, y, ij, grid, fun), do: trails(x, y, ij, [], grid) |> uniq_by(fun) |> length
  def trails(8, 9, ij, trail, _), do: [[ij | trail]]
  def trails(x, y, _, _, _) when is_nil(y) or y - x != 1, do: []

  def trails(_, y, {i, j}, trail, grid) do
    for({di, dj} <- [{0, 1}, {1, 0}, {-1, 0}, {0, -1}], do: {i + di, j + dj})
    |> flat_map(fn ij -> trails(y, Map.get(grid, ij), ij, [ij | trail], grid) end)
  end
end

I can’t figure out how to build grids on 1 line without import Enum, so grids always take at least 2 lines.

My solution. I tried something different and represented the grid by a single list today.

defmodule Grid do
  def parse(puzzle_input) do
    String.split(puzzle_input, "\n", trim: true)
    |> Enum.reduce({[], 0, 0}, fn row, {list, _width, height} ->
      {list ++ String.graphemes(row), String.length(row), height + 1}
    end)
  end

  def at(grid, width, height, {x, y} = pos) do
    if x >= 0 and x < width and y >= 0 and y < height do
       Enum.at(grid, y * width + x)
    else
      nil
    end
  end

  def find_valid_paths(grid, w, h, {x, y} = pos, last_num, acc) do
    cell = at(grid, w, h, pos) || ""
    
    case Integer.parse(cell) do
      {9, ""} when last_num == 8 ->
        [pos | acc]

      {num, ""} when num == last_num + 1 ->
        [{0, -1}, {1, 0}, {0, 1}, {-1, 0}]
        |> Enum.map(fn {dir_x, dir_y} -> {dir_x + x, dir_y + y} end)
        |> Enum.flat_map(fn new_pos ->
          find_valid_paths(grid, w, h, new_pos, num, acc)
        end)

      _other ->
        acc
    end
  end
end

# Input parsing
{grid, w, h} = Grid.parse(puzzle_input)
coords = for x <- 0..(w - 1), y <- 0..(h - 1), do: {x, y}

# Part 1
Enum.flat_map(coords, fn pos ->
  case Grid.at(grid, w, h, pos) do
    "0" -> Grid.find_valid_paths(grid, w, h, pos, -1, []) |> Enum.uniq()
    _other -> []
  end
end)
|> Enum.count()

# Part 2
Enum.flat_map(coords, fn pos ->
  case Grid.at(grid, w, h, pos) do
    "0" -> Grid.find_valid_paths(grid, w, h, pos, -1, [])
    _other -> []
  end
end)
|> Enum.count()