Advent of Code 2024 - Day 10

Learning Questions & Discussions Coding Challenges
,
21

Those times are derived from only one call. It can be because the system is “cold” at the beginning.

You can call mix aoc.run -b to execute an actual benchmark of the both parts. mix aoc.run -d 8 -b for your day 8.

Edit: on day 8 I got this:

Solution for 2024 day 8
part_one: 228 in 6.97ms      <---- part 1 slower
part_two: 766 in 962µs
Benchmarking part_one ...
Benchmarking part_two ...
Calculating statistics...    r-----part 1 faster
Formatting results...        |
                             v
Name               ips        average  deviation         median         99th %
part_one        1.74 K      574.44 μs    ±13.41%      555.32 μs      821.29 μs <---- faster
part_two        1.24 K      803.35 μs     ±8.98%      793.15 μs     1049.71 μs

Comparison:
part_one        1.74 K
part_two        1.24 K - 1.40x slower +228.91 μs
1 Like
22

I’m a few days late.

Day 10 was not too hard, and surprisingly, I had instant part2 resolution, after struggling a bit on part1’s recursion

Part 1

defmodule Advent.Y2024.Day10.Part1 do
  import Enum

  def run(puzzle) do
    map = parse(puzzle)
    map |> find_zeros() |> map(&hike(map, &1)) |> map(&elem(&1, 0)) |> sum()
  end

  def parse(puzzle) do
    for {row, y} <- puzzle |> String.split("\n") |> with_index(),
        {height, x} <- row |> String.graphemes() |> with_index(),
        into: %{},
        do: {{x, y}, String.to_integer(height)}
  end

  def find_zeros(map), do: for({{x, y}, h} <- map, h == 0, do: {x, y})

  defp hike(map, pos, height \\ 0, visited \\ MapSet.new())
  defp hike(_map, pos, 9, visited), do: {1, MapSet.put(visited, pos)}

  defp hike(map, pos, height, visited) do
    visited = MapSet.put(visited, pos)

    case neighbours(map, pos, height, visited) do
      [] ->
        {0, visited}

      neighbours ->
        for {n, h} <- neighbours, reduce: {0, visited} do
          {total, visited} ->
            {score, visited} = hike(map, n, h, visited)
            {total + score, visited}
        end
    end
  end

  defp neighbours(map, {x, y}, height, visited) do
    for {dx, dy} <- [{-1, 0}, {1, 0}, {0, -1}, {0, 1}],
        {nx, ny} = {x + dx, y + dy},
        not MapSet.member?(visited, {nx, ny}),
        new_height = Map.get(map, {nx, ny}, -1),
        new_height == height + 1,
        do: {{nx, ny}, new_height}
  end
end

Part 2

defmodule Advent.Y2024.Day10.Part2 do
  alias Advent.Y2024.Day10.Part1

  def run(puzzle) do
    map = Part1.parse(puzzle)
    map |> Part1.find_zeros() |> Enum.map(&hike(map, &1, 0)) |> Enum.sum()
  end

  defp hike(_map, _pos, 9), do: 1

  defp hike(map, pos, height) do
    case neighbours(map, pos, height) do
      [] -> 0
      ns -> ns |> Enum.map(fn {pos, h} -> hike(map, pos, h) end) |> Enum.sum()
    end
  end

  defp neighbours(map, {x, y}, height) do
    for {dx, dy} <- [{-1, 0}, {1, 0}, {0, -1}, {0, 1}],
        {nx, ny} = {x + dx, y + dy},
        new_height = Map.get(map, {nx, ny}, -1),
        new_height == height + 1,
        do: {{nx, ny}, new_height}
  end
end

Part 2 is basically a simplified version of part 1, in which I don’t track already visited nodes.

23

I didn’t see a :digraph solution in here yet, so this is mine:

defmodule Trails do
  def read(filename) do
    File.stream!(filename)
    |> Stream.map(&String.trim/1)
    |> Stream.with_index()
    |> Stream.flat_map(fn {row, r_idx} ->
      row
      |> String.codepoints()
      |> Enum.with_index()
      |> Enum.flat_map(fn
        {".", _} -> []
        {c, c_idx} -> [{{r_idx, c_idx}, String.to_integer(c)}]
      end)
    end)
    |> Map.new()
  end

  def trailheads_and_summits(map) do
    Enum.reduce(map, {[], []}, fn
      {pos, 0}, {th_acc, sum_acc} -> {[pos | th_acc], sum_acc}
      {pos, 9}, {th_acc, sum_acc} -> {th_acc, [pos | sum_acc]}
      _, acc -> acc
    end)
  end

  def to_graph(map) do
    graph = :digraph.new()
    points = Map.keys(map)

    Enum.each(points, &:digraph.add_vertex(graph, &1))

    Enum.each(points, fn {row, col} = pos ->
      maybe_add_edge(graph, map, pos, {row+1, col})
      maybe_add_edge(graph, map, pos, {row-1, col})
      maybe_add_edge(graph, map, pos, {row, col+1})
      maybe_add_edge(graph, map, pos, {row, col-1})
    end)

    graph
  end

  defp maybe_add_edge(graph, map, pos1, pos2) do
    case {Map.get(map, pos1), Map.get(map, pos2)} do
      {a, b} when a+1 == b ->
        :digraph.add_edge(graph, pos1, pos2)

      _ ->
        nil
    end
  end

  def score(trailhead, summits, graph) do
    summits
    |> Enum.filter(fn summit ->
      :digraph.get_path(graph, trailhead, summit)
    end)
    |> length()
  end

  def count_paths(_, t, s) when t == s, do: 1

  def count_paths(graph, trailhead, summit) do
    graph
    |> :digraph.out_neighbours(trailhead)
    |> Enum.map(&count_paths(graph, &1, summit))
    |> Enum.sum()
  end
end

map = Trails.read("input.txt")

{trailheads, summits} = Trails.trailheads_and_summits(map)

graph = Trails.to_graph(map)

trailheads
|> Enum.map(&Trails.score(&1, summits, graph))
|> Enum.sum()
|> IO.inspect(label: "part 1")

trailheads
|> Stream.flat_map(fn t -> Stream.map(summits, &{t, &1}) end)
|> Stream.map(fn {t, s} -> Trails.count_paths(graph, t, s) end)
|> Enum.sum()
|> IO.inspect(label: "part 2")

Since there’s a strict “only up by 1” rule for moving on the grid, I used a single scan across the whole grid to calculate an equivalent graph of “can move from A to neighbor B”. With that graph, it’s straightforward to find paths from a given point.

count_paths also has two minor optimizations:

  • since the caller only ever passes in summits, trailhead == summit is sufficient to check for “is the trail over”
  • since the graph is guaranteed to have no cycles, there’s no need for the “visiting” tracking that standard DFS would use
24

Part 2 solved first crowd++

Simple recursion with flat_map based return in part we take &Enum.uniq/2 and then &length/1 whereas in case of part 2 its just &length/1 on each individual trail result and then summation.