Advent of Code 2024 - Day 11

My solution using ETS. It takes 56.94 ms for Part 2 with a clean cache.

defmodule PlutonianPebbles do
  def init_cache do
    if :ets.whereis(:stones_cache) != :undefined do
      :ets.delete(:stones_cache)
    end

    :ets.new(:stones_cache, [:set, :public, :named_table])
  end

  def blink_stone(0), do: 1

  def blink_stone(stone) do
    digits = Integer.digits(stone)
    len = length(digits)

    if rem(len, 2) == 0 do
      mid = div(len, 2)
      first = Enum.take(digits, mid) |> Integer.undigits()
      second = Enum.drop(digits, mid) |> Integer.undigits()
      {first, second}
    else
      2024 * stone
    end
  end

  def count_stones(stones, depth) when is_list(stones) do
    stones
    |> Enum.map(&count_stones(&1, depth))
    |> Enum.sum()
  end

  def count_stones(stone, depth) do
    cache_key = {stone, depth}

    case :ets.lookup(:stones_cache, {stone, depth}) do
      [{_key, result}] ->
        result

      [] ->
        calculate_stones(stone, depth)
        |> tap(fn result ->
          :ets.insert(:stones_cache, {cache_key, result})
        end)
    end
  end

  defp calculate_stones({_first, _second}, 0), do: 2
  defp calculate_stones(_stone, 0), do: 1

  defp calculate_stones(stone, depth) do
    case blink_stone(stone) do
      {first, second} ->
        count_stones(first, depth - 1) + count_stones(second, depth - 1)

      stone ->
        count_stones(stone, depth - 1)
    end
  end
end

nums = String.split(puzzle_input) |> Enum.map(&String.to_integer(&1))
PlutonianPebbles.init_cache()

# Part 1
PlutonianPebbles.count_stones(nums, 25)

# Part 2
PlutonianPebbles.count_stones(nums, 75)

I used libgraph yet again!

The graph building part:

defmodule AoC2024.Day11 do
  import Integer
  import Bitwise
  
  def build_graph(stones) do
    do_build_graph(Graph.new(type: :directed), stones)
  end

  defp do_build_graph(graph, stones) do    
    not_seen = stones -- Graph.vertices(graph)

    if not_seen == [] do
      graph
    else
      graph = Graph.add_vertices(graph, not_seen)
  
      edges =
        for stone <- stones, neighbor <- transform(stone) do
          {stone, neighbor}
        end
        |> Enum.frequencies()
        |> Enum.map(fn {{from, to}, label} ->
          Graph.Edge.new(from, to, label: label)
        end)
  
      neighbors = edges |> Enum.map(& &1.v2) |> Enum.uniq()
      graph = do_build_graph(graph, neighbors)
  
      Graph.add_edges(graph, edges)
    end
  end

  defp transform(0), do: [1]

  defp transform(n) do
    len = floor(:math.log10(n)) + 1

    if is_even(len) do
      d = 10 ** (len >>> 1)
      [div(n, d), rem(n, d)]
    else
      [n * 2024]
    end
  end
end

The problem solving part:

graph = AoC2024.Day11.build_graph(stones)

stones
|> Enum.frequencies()
|> Stream.iterate(fn freqs ->
  for {num, freq} <- freqs, edge <- Graph.out_edges(graph, num), reduce: %{} do
    freqs2 -> Map.update(freqs2, edge.v2, freq * edge.label, & &1 + freq * edge.label)
  end
end)
|> Enum.at(25)  # <-- change this to 75 to solve Part 2
|> Map.values()
|> Enum.sum()

Once I had coffee and realized that order doesn’t matter I just used plain old Maps:

https://github.com/mexicat/aoc-2024/blob/main/lib/aoc/day_11.ex

Part 1 runs in ~700μs, part 2 runs in ~40ms.

I was stupid. I don’t need a graph.

blink = fn
  0 ->
    [1]

  n ->
    len = floor(:math.log10(n)) + 1

    if Bitwise.band(len, 1) == 1 do
      [n * 2024]
    else
      d = 10 ** Bitwise.bsr(len, 1)
      [div(n, d), rem(n, d)]
    end
end

############################

puzzle_input
|> String.split()
|> Enum.map(&String.to_integer/1)
|> Enum.frequencies()
|> Stream.iterate(fn freqs ->
  for {num, freq} <- freqs, num2 <- blink.(num), reduce: %{} do
    freqs2 -> Map.update(freqs2, num2, freq, & &1 + freq)
  end
end)
|> Enum.at(75)
|> Map.values()
|> Enum.sum()

this goes for part and part2, uses same code

https://github.com/jarlah/advent_of_code/blob/master/lib/2024/day_11/Part1.ex#L10

1-2 seconds for part2 (or less with release …)

PS! i hate repeating code blocks like expanding tuples and building them up again, so i have gotten REALLY fond of lambdas … the beauty of is that you must use all lambda parameters . unless you get compile error …

btw when it comes to 40ms or whatever for run times, do people run the solutions in a non test environment or release or something? because im running mix test with doctests .. so maybe could shave off a second or two just for that

EDIT:

_build/prod/rel/advent_of_code_2024/bin/advent_of_code_2024 eval “:timer.tc(fn → AOC2024.Day11.Part2.Solution.solution(AOC2024.Day11.Input.input()) end) |> then(&Kernel.elem(&1, 0) / 1_000) |> IO.inspect()”
299.952

300ms for 75
1382.429 ms for 150
19452.847 ms for 1000

think i need to look at the o notation for this algo EDIT: its not increasing linearly, i can say that for sure .. O(n^2) maybe .. perplexity suggested O(stones * max_value * log(max_value)) .. i rewrote it from O(n * m * log(m))

For run time checking, I use benchee. Each of my AOC modules has functions called part1_verify and part2_verify that run the full solution without arguments, and those are what I benchmark.

https://github.com/sevenseacat/advent_of_code/blob/main/lib/advent/day.ex#L18-L50

As for today’s solution, I remembered seeing something veeeeeery similar before so used the same technique here. Order doesn’t matter - only the count of each stone matters as they’re all totally independent of each other.

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

A slow (1 sec) solution before optimization using only a lists of {value, count} for each type of stone.

defmodule AdventOfCode.Solutions.Y24.Day11 do
  alias AoC.Input

  def parse(input, _part) do
    input
    |> Input.read!()
    |> String.trim()
    |> String.split(" ")
    |> Enum.map(&String.to_integer/1)
  end

  def part_one(problem) do
    solve(problem, 25)
  end

  def part_two(problem) do
    solve(problem, 75)
  end

  defp solve(problem, cycles) do
    stones = Enum.map(problem, &{&1, 1})
    stones = merge(stones)

    stones =
      Enum.reduce(1..cycles, stones, fn _, stones ->
        stones
        |> blink_all()
        |> merge()
      end)

    Enum.reduce(stones, 0, fn {_, c}, acc -> acc + c end)
  end

  defp blink_all(stones) do
    Enum.flat_map(stones, &blink/1)
  end

  defp blink({0, count}), do: [{1, count}]

  defp blink({figure, count}) do
    digits = Integer.digits(figure)
    len = length(digits)

    if rem(len, 2) == 0 do
      {left, right} = Enum.split(digits, div(len, 2))

      [{Integer.undigits(left), count}, {Integer.undigits(right), count}]
    else
      [{figure * 2024, count}]
    end
  end

  defp merge(new_stones) do
    merge([], new_stones)
  end

  defp merge(old_stones, new_stones) do
    Enum.reduce(new_stones, old_stones, fn new, olds -> insert(olds, new) end)
  end

  defp insert([], kv), do: [kv]
  defp insert([{k, v1} | rest], {k, v2}), do: [{k, v1 + v2} | rest]
  defp insert([{k1, v1} | rest], {k2, v2}) when k1 < k2, do: [{k1, v1} | insert(rest, {k2, v2})]
  defp insert([{k1, v1} | rest], {k2, v2}) when k1 > k2, do: [{k2, v2}, {k1, v1} | rest]
end

Edit:

Optimization with memoization and using a map instead of an ordered list (44ms on average)

defmodule AdventOfCode.Solutions.Y24.Day11 do
  alias AoC.Input

  def parse(input, _part) do
    input
    |> Input.read!()
    |> String.trim()
    |> String.split(" ")
    |> Enum.map(&String.to_integer/1)
  end

  def part_one(problem) do
    solve(problem, 25)
  end

  def part_two(problem) do
    solve(problem, 75)
  end

  defp solve(problem, cycles) do
    stones = build_stones(problem)
    stones = Enum.reduce(1..cycles, stones, fn _, stones -> blink_all(stones) end)
    Enum.reduce(stones, 0, fn {_, c}, acc -> acc + c end)
  end

  defp build_stones(figures) do
    Enum.reduce(figures, %{}, fn k, map -> merge_stone(map, k, 1) end)
  end

  defp merge_stone(map, k, n) do
    Map.update(map, k, n, &(&1 + n))
  end

  defp blink_all(stones) do
    stones
    |> Enum.flat_map(&blink/1)
    |> Enum.reduce(%{}, fn {k, n}, map -> merge_stone(map, k, n) end)
  end

  defp blink({0, count}), do: [{1, count}]

  defp blink({figure, count}) do
    case memoized_blink(figure) do
      {left, right} -> [{left, count}, {right, count}]
      by_2024 -> [{by_2024, count}]
    end
  end

  defp memoized_blink(figure) do
    case Process.get({__MODULE__, figure}, nil) do
      nil ->
        result = blink_figure(figure)
        Process.put({__MODULE__, figure}, result)
        result

      result ->
        result
    end
  end

  defp blink_figure(figure) do
    digits = Integer.digits(figure)
    len = length(digits)

    if rem(len, 2) == 0 do
      {left, right} = Enum.split(digits, div(len, 2))

      {Integer.undigits(left), Integer.undigits(right)}
    else
      figure * 2024
    end
  end
end

I love how the text insists on the stones being on a perfectly straight line.

Here is my solution for Day 11 using a Map to keep of the frequencies for each stone at every level. I kept everything as strings except when I needed to multiply or remove the leading zeros.

Part two solves in 0.2 seconds (using Livebook v0.14.4 on a 13" MBP 2018 with a2.3Ghz Intel i5 processor and 16Gb RAM).

defmodule Day11 do

  def parse_input(input) do
    input
    |> String.split(" ", trim: true)
  end
  
  def solve_part1(arrangement), do: solve(arrangement, 25)
  def solve_part2(arrangement), do: solve(arrangement, 75)
  
  defp solve(arrangement, times) when is_list(arrangement) do
    arrangement
    |> Enum.frequencies()
    |> blink(times)
    |> Enum.sum()
  end

  defp blink(arrangement, 0) do
    arrangement
    |> Map.values()
  end

  defp blink(arrangement, times) when times > 0 do
    arrangement
    |> Enum.map(&handle_stone/1)
    |> List.flatten()
    |> Enum.reduce(%{}, fn {stone, freq}, acc ->
      Map.update(acc, stone, freq, fn v -> v + freq end)
    end)
    |> blink(times - 1)
  end
  
  defp handle_stone({"0", f}), do: {"1", f}

  defp handle_stone({stone, f}) do
   digits = String.length(stone)
    
    if rem(digits, 2) == 0 do
      String.split_at(stone, div(digits, 2))
      |> Tuple.to_list()
      |> Enum.map(&String.to_integer/1)
      |> Enum.map(&Integer.to_string/1)
      |> Enum.map(fn s -> {s, f} end)
    else
      {"#{String.to_integer(stone) * 2024}", f}
    end
  end
end

All remarks and or suggestions for improvement are welcome!

Oh yes, and even when stones are replaced, they always stay in the same order! Makes you think that order is important