Advent of Code 2024 - Day 11

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

Input

opts = [headers: [{"cookie", "session=#{System.fetch_env!("LB_AOC_SESSION")}"}]]
puzzle_input = Req.get!("https://adventofcode.com/2024/day/11/input", opts).body

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

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

  @doc """
  iex> PlutonianPebbles.blink_stone(1700)
  {17, 0}

  iex> PlutonianPebbles.blink_stone(2)
  4048
  """
  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

  @doc """
  iex> PlutonianPebbles.init_cache()
  iex> PlutonianPebbles.count_stones([125, 17], 6)
  22
  """
  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

Puzzle 1

puzzle_1 = fn ->
  PlutonianPebbles.init_cache()
  PlutonianPebbles.count_stones(nums, 25)
end

puzzle_1.()

Puzzle 2

puzzle_2 = fn ->
  PlutonianPebbles.init_cache()
  PlutonianPebbles.count_stones(nums, 75)
end

puzzle_2.()

Benchmarks

Benchee.run(
  %{
    "puzzle_1" => fn -> puzzle_1.() end,
    "puzzle_2" => fn -> puzzle_2.() end
  })

Brute force

defmodule PlutonianPebblesBruteForce do
  def arrange([], acc, _cache), do: Enum.reverse(acc)

  def arrange([0 | rest], acc, cache), do: arrange(rest, [1 | acc], cache)

  def arrange([head | rest], acc, cache) do
    case Map.get(cache, head, :not_cached) do
      :not_cached ->
        digits = Integer.digits(head)
        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()

          result = [first, second]
          updated_cache = Map.put(cache, head, result)

          arrange(rest, result ++ acc, updated_cache)
        else
          result = [2024 * head]
          updated_cache = Map.put(cache, head, result)

          arrange(rest, result ++ acc, updated_cache)
        end

      value ->
        value ++ acc
    end
  end

  def blink(nums, times) do
    Enum.reduce(1..times, nums, fn i, acc ->
      arrange(acc, [], %{})
    end)
    |> Enum.count()
  end
end