Advent of Code 2024 - Day 10

[seeplusplus]

This one wasn’t too bad I actually ended up solving part 2 first, and had to work around it in part 1 to get the answer there!

input = ""
|> String.trim()
tiles = input |> String.split("\n")
  |> Stream.with_index() 
  |> Enum.flat_map(fn {line, l_idx} ->
    line 
    |> String.trim() 
    |> String.graphemes()
    |> Stream.with_index()
    |> Enum.map(fn {".", idx} -> {{idx, l_idx}, nil}
      {c, idx} -> {{idx, l_idx}, c |> String.to_integer()} end)
end)
|> Enum.into(Map.new())
grid = Grid2D.new(
  input |> String.split("\n") |> Enum.at(0) |> String.trim() |> String.length(),
  input |> String.trim() |> String.split("\n") |> Enum.count()
)

defmodule TrailFinder do
  def find_trails(input, tiles, grid) do
    tiles
    |> Stream.filter(fn {_, v} -> v == 0 end)
    |> Enum.map(fn {k, _} -> {k, find_trails(input, tiles, grid, k, 0, [])} end)
  end
  def find_trails(_, _, _, p, 9, acc), do: [[{p, 9} | acc]]
  def find_trails(input, tiles, grid, start, height, acc) do
    Grid2D.neighbors(start, grid, :straight)
    |> Enum.filter(fn p -> Map.get(tiles, p) == height + 1 end)
    |> Enum.flat_map(fn p ->
        find_trails(input, tiles, grid, p, height + 1, [{start, height} | acc])
    end)
  end
end

TrailFinder.find_trails(input, tiles, grid)
|> Enum.map(fn {s, l} -> {s, for [peak |_] <- l, into: MapSet.new do peak end } end)
|> Enum.map(fn {_, s} -> MapSet.size(s) end)
|> Enum.sum()

TrailFinder.find_trails(input, tiles, grid)
|> Stream.map(fn {_, l} -> l |> Enum.count end)
|> Enum.sum()

[rugyoga]

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

rugyoga/aoc2023/blob/main/lib/2024/10.ex

[Aetherus]

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

[bjorng]

And I also solved part 2 first.

bjorng/advent-of-code/blob/main/2024/day10/lib/day10.ex

[sevenseacat]

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

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

[adamu]

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

AdventOfCode/2024/day10.exs at main

[lud]

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

[Aetherus]

Less interesting solution (no brainer):

Aetherus/advent-of-code/blob/0cd3b4686a6cdb4aac1e91ca8dc5742ff0dc6a78/2024/day-10-graph.livemd

[rySeeR]

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…

jbonet/advent_of_code_2024/blob/main/lib/advent_of_code_2024/days/10.ex

[billylanchantin]

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.

[Flo0807]

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()

[mwilsoncoding]

At this rate, I might catch up. Here’s my first pass at part 1:

#!/usr/bin/env elixir

defmodule Day10.Part1 do
  @ascii_adjustment 48
  @trail_head 0
  @destination 9
  @search_depth @destination

  defp parse(str) do
    [row | _rows] =
      rows =
      str
      |> String.split("\n", trim: true)
      |> Stream.map(&to_charlist/1)
      |> Enum.map(fn row ->
        Enum.map(row, &(&1 - @ascii_adjustment))
      end)

    height = Enum.count(rows)
    length = Enum.count(row)

    trail_heads =
      for y <- 0..(height - 1), x <- 0..(length - 1) do
        {x, y}
      end
      |> Enum.reduce(
        [],
        fn {x, y} = pos, trail_heads = acc ->
          c = rows |> Enum.at(y) |> Enum.at(x)

          case c do
            @trail_head -> [pos | trail_heads]
            _ -> acc
          end
        end
      )

    %{
      map: %{
        height: height,
        length: length,
        rows: rows
      },
      trail_heads: trail_heads
    }
  end

  defp on_board?({x, y}, height, length) when x < 0 or x >= length or y < 0 or y >= height,
    do: false

  defp on_board?(_pair, _height, _length), do: true

  defp reachable_neighbors({x, y}, %{height: height, length: length, rows: rows}) do
    current_value = rows |> Enum.at(y) |> Enum.at(x)

    [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
    |> Enum.filter(fn {neighbor_x, neighbor_y} = pair ->
      on_board?(pair, height, length) and
        (rows |> Enum.at(neighbor_y) |> Enum.at(neighbor_x)) - current_value == 1
    end)
  end

  defp reachable_destinations({x, y} = pos, %{rows: rows} = _map, 0 = _search_depth) do
    if rows |> Enum.at(y) |> Enum.at(x) == @destination, do: MapSet.new([pos]), else: MapSet.new()
  end

  defp reachable_destinations(pos, map, search_depth) do
    reachable_neighbors(pos, map)
    |> Enum.reduce(
      MapSet.new(),
      fn neighbor, reachable_destinations ->
        reachable_destinations(neighbor, map, search_depth - 1)
        |> Enum.into(reachable_destinations)
      end
    )
  end

  defp unique_destination_count(trail_head, map, search_depth) do
    reachable_neighbors(trail_head, map)
    |> Enum.reduce(
      MapSet.new(),
      fn neighbor, destinations_already_seen ->
        reachable_destinations(neighbor, map, search_depth - 1)
        |> Enum.into(destinations_already_seen)
      end
    )
    |> Enum.count()
  end

  defp trail_head_scores(%{
         map: map,
         trail_heads: trail_heads
       }) do
    trail_heads
    |> Enum.map(&unique_destination_count(&1, map, @search_depth))
    |> Enum.sum()
  end

  def solve() do
    File.read!("10/input.txt")
    |> parse()
    |> trail_head_scores()
    |> IO.puts()
  end
end

Day10.Part1.solve()

[ntalfer]

solved part 2 first as well xD

[mwilsoncoding]

Woo! Caught up.

Here’s my first pass at part 2. Found it to be simpler than part 1. I’m betting I could refactor my work there tho. In tackling part 2 I found some bits unnecessary due to the guarantees from stopping recursion at the search depth.

#!/usr/bin/env elixir

defmodule Day10.Part1 do
  @ascii_adjustment 48
  @trail_head 0
  @destination 9
  @search_depth @destination

  defp parse(str) do
    [row | _rows] =
      rows =
      str
      |> String.split("\n", trim: true)
      |> Stream.map(&to_charlist/1)
      |> Enum.map(fn row ->
        Enum.map(row, &(&1 - @ascii_adjustment))
      end)

    height = Enum.count(rows)
    length = Enum.count(row)

    trail_heads =
      for y <- 0..(height - 1), x <- 0..(length - 1) do
        {x, y}
      end
      |> Enum.reduce(
        [],
        fn {x, y} = pos, trail_heads = acc ->
          c = rows |> Enum.at(y) |> Enum.at(x)

          case c do
            @trail_head -> [pos | trail_heads]
            _ -> acc
          end
        end
      )

    %{
      map: %{
        height: height,
        length: length,
        rows: rows
      },
      trail_heads: trail_heads
    }
  end

  defp on_board?({x, y}, height, length) when x < 0 or x >= length or y < 0 or y >= height,
    do: false

  defp on_board?(_pair, _height, _length), do: true

  defp reachable_neighbors({x, y}, %{height: height, length: length, rows: rows}) do
    current_value = rows |> Enum.at(y) |> Enum.at(x)

    [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
    |> Enum.filter(fn {neighbor_x, neighbor_y} = pair ->
      on_board?(pair, height, length) and
        (rows |> Enum.at(neighbor_y) |> Enum.at(neighbor_x)) - current_value == 1
    end)
  end

  defp reachable_destinations({x, y} = pos, %{rows: rows} = _map, 0 = _search_depth) do
    if rows |> Enum.at(y) |> Enum.at(x) == @destination, do: MapSet.new([pos]), else: MapSet.new()
  end

  defp reachable_destinations(pos, map, search_depth) do
    reachable_neighbors(pos, map)
    |> Enum.reduce(
      MapSet.new(),
      fn neighbor, reachable_destinations ->
        reachable_destinations(neighbor, map, search_depth - 1)
        |> Enum.into(reachable_destinations)
      end
    )
  end

  defp unique_destination_count(trail_head, map, search_depth) do
    reachable_neighbors(trail_head, map)
    |> Enum.reduce(
      MapSet.new(),
      fn neighbor, destinations_already_seen ->
        reachable_destinations(neighbor, map, search_depth - 1)
        |> Enum.into(destinations_already_seen)
      end
    )
    |> Enum.count()
  end

  defp trail_head_scores(%{
         map: map,
         trail_heads: trail_heads
       }) do
    trail_heads
    |> Enum.map(&unique_destination_count(&1, map, @search_depth))
    |> Enum.sum()
  end

  def solve() do
    File.read!("10/input.txt")
    |> parse()
    |> trail_head_scores()
    |> IO.puts()
  end
end

Day10.Part1.solve()

[newton-peixoto]

I think thats the first day that i liked my solution. In my opinion very clean different than other days such as day 9 which i suffered a lot.

newton-peixoto/advent-of-code/blob/main/2024/livebooks/day-10.livemd

[jarlah]

happy for now

part1: advent_of_code/lib/2024/day_10/Part1.ex at master · jarlah/advent_of_code · GitHub
part2: advent_of_code/lib/2024/day_10/Part2.ex at master · jarlah/advent_of_code · GitHub

i actually sincerely feel that my code is readable and understandable. There is very little going on actually. Took me some time to understand the problem though. But when i had the requirements in my head things started to fall into place …

the irony is that i started on making code to find all unique paths before i figured part1 was actually just to find the first path…

[MikeLindner]

As others I solved part 2 first without realizing it. Then it was a struggle until I finally re-read the instructions and realized I was only supposed to count unique destinations for each trailhead.

require Grid

defmodule Aoc2024.Day10 do
  @moduledoc false

  def part1(file) do
    grid = get_input(file)

    grid
    |> find_trailheads()
    |> Enum.map(&climb(grid, &1))
    |> List.flatten()
    |> Enum.map(fn path ->
      MapSet.to_list(path)
      |> Enum.filter(fn {height, _} -> height == 0 or height == 9 end)
    end)
    |> Enum.uniq()
    |> length()
  end

  def part2(file) do
    grid = get_input(file)

    grid
    |> find_trailheads()
    |> Enum.map(&climb(grid, &1))
    |> List.flatten()
    |> Enum.uniq()
    |> length()
  end

  defp get_input(file) do
    File.read!(file)
    |> Grid.new(&String.to_integer/1)
  end

  defp find_trailheads(grid) do
    Grid.filter(grid, fn v -> v == 0 end)
  end

  defp climb(grid, pos = {x, y}, path \\ MapSet.new()) do
    value = Grid.at(grid, pos)
    path = MapSet.put(path, {value, pos})

    if value == 9 do
      path
    else
      [{-1, 0}, {1, 0}, {0, -1}, {0, 1}]
      |> Enum.reduce([], fn {dx, dy}, good ->
        next = {x + dx, y + dy}

        if Grid.at(grid, next) == value + 1 and not MapSet.member?(path, {value + 1, next}) do
          [next | good]
        else
          good
        end
      end)
      |> Enum.map(fn next ->
        climb(grid, next, path)
      end)
    end
  end
end

[lkuty]

Set up the map in 3633 µs
Part 1: 531
Job done in 2122 µs
Part 2: 1210
Job done in 968 µs

#!/usr/bin/env elixir

# AoC 2024. day 10.

###########################################################
# Part 1

defmodule Part1 do
  def seek(_map, 9, row, col, pos), do: MapSet.put(pos, {row,col})
  def seek(map, curr, row, col, pos) do
    next = map[{row-1,col}]
    pos = (if next == curr+1, do: seek(map, next, row-1, col, pos), else: pos)
    next = map[{row,col+1}]
    pos = (if next == curr+1, do: seek(map, next, row, col+1, pos), else: pos)
    next = map[{row+1,col}]
    pos = (if next == curr+1, do: seek(map, next, row+1, col, pos), else: pos)
    next = map[{row,col-1}]
    (if next == curr+1, do: seek(map, next, row, col-1, pos), else: pos)
  end
end

start = System.monotonic_time(:microsecond)
map = File.stream!("../day10.txt")
  |> Stream.with_index(1)
  |> Enum.reduce(%{}, fn {line, row}, map ->
    line
    |> String.trim_trailing()
    |> String.codepoints()
    |> Enum.with_index(1)
    |> Enum.reduce(map, fn {c, col}, map -> Map.put(map, {row, col}, (if c == ".", do: -1, else: String.to_integer(c))) end)
  end)
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Set up the map in #{elapsed} µs"

start = System.monotonic_time(:microsecond)
map
|> Enum.filter(fn {_k,v} -> v == 0 end)
|> Enum.map(fn {k,_v} -> k end)
|> Enum.reduce(0, fn {row,col}, n -> n+MapSet.size(Part1.seek(map, 0, row, col, MapSet.new())) end)
|> IO.inspect(label: "Part 1")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"


###########################################################
# Part 2

defmodule Part2 do
  def seek(_map, 9, _row, _col), do: 1
  def seek(map, curr, row, col) do
    next = map[{row-1,col}]
    n = (if next == curr+1, do: seek(map, next, row-1, col), else: 0)
    next = map[{row,col+1}]
    n = n + (if next == curr+1, do: seek(map, next, row, col+1), else: 0)
    next = map[{row+1,col}]
    n = n + (if next == curr+1, do: seek(map, next, row+1, col), else: 0)
    next = map[{row,col-1}]
    n + (if next == curr+1, do: seek(map, next, row, col-1), else: 0)
  end
end

start = System.monotonic_time(:microsecond)
map
|> Enum.filter(fn {_k,v} -> v == 0 end)
|> Enum.map(fn {k,_v} -> k end)
|> Enum.reduce(0, fn {row,col}, n -> n+Part2.seek(map, 0, row, col) end)
|> IO.inspect(label: "Part 2")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

[lkuty]

Exactly the same for me

[ken-kost]

I actually ended up solving part 2 first

Same. I misinterpreted part one and as I fixed it and got to part 2 I saw 81 and was like ‘wait, I saw that’.

defmodule Aoc2024.Solutions.Y24.Day10 do
  alias AoC.Input

  def parse(input, part) do
    input
    |> Input.stream!(trim: true)
    |> Stream.with_index()
    |> Enum.reduce({[], %{}}, fn {line, x}, {trailheads, map} ->
      line
      |> String.codepoints()
      |> Stream.with_index()
      |> Enum.reduce({trailheads, map}, fn
        {e, y}, {trailheads, map} ->
          case String.to_integer(e) do
            0 -> {[{x, y} | trailheads], map}
            n -> {trailheads, Map.put(map, {x, y}, n)}
          end
      end)
    end)
    |> Tuple.append(if(part == :part_one, do: MapSet.new(), else: 0))
  end

  def part_one({trailheads, map, init}) do
    solver(trailheads, map, init, 0)
  end

  def part_two({trailheads, map, init}) do
    solver(trailheads, map, init, 0)
  end

  defp solver([], _map, _init, acc), do: acc

  defp solver([{x, y} | rest], map, init, acc) when is_map(init) do
    result = follow_trails(x, y, map, 0, init)
    solver(rest, map, init, acc + MapSet.size(result))
  end

  defp solver([{x, y} | rest], map, init, acc) do
    result = follow_trails(x, y, map, 0, init)
    solver(rest, map, init, acc + result)
  end

  defp follow_trails(x, y, map, n, acc) do
    [{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}]
    |> Enum.reduce([], fn point, acc ->
      value = Map.get(map, point)
      if value == n + 1, do: [{point, value} | acc], else: acc
    end)
    |> Enum.reduce(acc, fn
      {point, 9}, acc ->
        if is_map(acc), do: MapSet.put(acc, point), else: acc + 1

      {{next_x, next_y}, _value}, acc ->
        follow_trails(next_x, next_y, map, n + 1, acc)
    end)
  end
end

In the end I bundled them together, only switching/checking the initial variable. Not good design wise but I like the elegance.

Solution for 2024 day 10
part_one: 760 in 19.68ms
part_two: 1764 in 6.62ms

@lud Also, I have a feeling the benchmarking is not right for part 2? I’m not sure, here is reference for this also.