Advent of code 2024 Day 11 Part 2 を Livebook で楽しむ

はじめに

Advent of code 2024 Day 11 の Part 2 を解きます

問題文はこちら

実装したノートブックはこちら

Part 1 はこちら

セットアップ

Kino AOC をインストールします

Mix.install([
  {:kino_aoc, "~> 0.1"}
])

Kino AOC の使い方はこちらを参照

入力の取得

"Advent of Code Helper" スマートセルを追加し、 Day 11 の入力を取得します

私の答え

私の答えです。
折りたたんでおきます。
▶を押して開いてください。

回答

75 回繰り返すとなると、とても計算できません

とにかく高速化します

石を数値の配列にするところまでは Part 1 と同じです

small_sample_input = "0 1 10 99 999"

stones =
  small_sample_input
  |> String.split(" ")
  |> Enum.map(&String.to_integer(&1))

実行結果

[0, 1, 10, 99, 999]

まず、常用対数を用いて桁分割を行います

正の整数 $N$ が $n$ 桁の場合、以下の式が成り立ちます

$$
n−1 \leqq log_{10} N < n
$$

https://manabitimes.jp/math/1236

例えば 99 を分割してみます

99 を分割するためには 10 で割った商と余りにすれば良いことがわかります

10 はつまり、 99 の桁数の半分の数だけ 1 の後ろに 0 を持っている数です

$$
n−1 \leqq log_{10} N
$$

から、 n-1 は整数なので

$$
n−1 = \lfloor log_{10} N
$$

となり、

$$
n = \lfloor log_{10} N + 1
$$

と言えます

つまり、 $log_{10}99$ の小数点以下を切り捨て、 1 を足すことで桁数になります

stone = 99

digits = stone |> :math.log10() |> floor() |> Kernel.+(1)

half_power = :math.pow(10, div(digits, 2)) |> round()

{div(stone, half_power), rem(stone, half_power)}

実行結果

{9, 9}

確かに分割できました

また、高速化に欠かせない ETS を使用し、「石を X 回処理した結果の数」をメモ化します

https://elixirschool.com/ja/lessons/storage/ets

指定された繰り返し回数から遡り、すでに計算したことがある石については ETS から数を取得するようにします

defmodule BlinkCounter do
  def start_link do
    if :ets.info(:blink_count_cache) != :undefined do
      :ets.delete(:blink_count_cache)
    end

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

  def blink(0), do: [1]
  def blink(stone) do
    digits = :math.log10(stone) |> floor() |> Kernel.+(1)
    if rem(digits, 2) == 0 do
      half_power = :math.pow(10, div(digits, 2)) |> round()
      left = div(stone, half_power)
      right = rem(stone, half_power)
      [left, right]
    else
      [stone * 2024]
    end
  end

  def count_expansions(_, 0) do
    1
  end

  def count_expansions(stone, steps) when steps > 0 do
    case :ets.lookup(:blink_count_cache, {stone, steps}) do
      [{_, count}] ->
        count

      [] ->
        result =
          blink(stone)
          |> Enum.reduce(0, fn next_stone, acc ->
            acc + count_expansions(next_stone, steps - 1)
          end)

        :ets.insert(:blink_count_cache, {{stone, steps}, result})
        result
    end
  end
end

ETS を初期化します

BlinkCounter.start_link()

まず処理自体が正しく動いていることを確認します

1..6
|> Enum.reduce([0], fn _, acc_stones ->
  acc_stones
  |> Enum.flat_map(fn stone ->
    BlinkCounter.blink(stone)
  end)
  |> IO.inspect()
end)
|> length()

標準出力

[1]
[2024]
[20, 24]
[2, 0, 2, 4]
[4048, 1, 4048, 8096]
[40, 48, 2024, 40, 48, 80, 96]

実行結果

7

確かに正しく処理できています

続いて再帰処理で同じことを実行してみます

BlinkCounter.count_expansions(0, 6)

実行結果

7

この時点で ETS テーブルの中身を見てみましょう

:ets.tab2list(:blink_count_cache)

実行結果

[
  {{1, 1}, 1},
  {{4048, 1}, 2},
  {{1, 5}, 7},
  {{8096, 1}, 2},
  {{2024, 4}, 7},
  {{2, 2}, 2},
  {{20, 3}, 3},
  {{0, 2}, 1},
  {{0, 6}, 7},
  {{24, 3}, 4},
  {{4, 2}, 2}
]

処理中に計算した以下のような内容をキャッシュできています

• 0 の石を 2 回処理すると石が 1 個になる
• 0 の石を 6 回処理すると石が 7 個になる
• 1 の石を 1 回処理すると石が 1 個になる
• 1 の石を 5 回処理すると石が 7 個になる
• 2 の石を 2 回処理すると石が 2 個になる
• 4 の石を 2 回処理すると石が 2 個になる

これを利用することで大量に繰り返していたとしても、すでに知っている繰り返し回数まで遡った時点で計算を止めることができます

入力例について、繰り返しを 1 回実行してみます

stones
|> Enum.reduce(0, fn stone, acc ->
  acc + BlinkCounter.count_expansions(stone, 1)
end)

実行結果

7

実際の入力に対して 75 回繰り返すと、ほぼ一瞬で結果が返ってきます

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

stones
|> Enum.reduce(0, fn stone, acc ->
  acc + BlinkCounter.count_expansions(stone, 75)
end)

まとめ

問題文から ChatGPT に画像を生成してもらいました

やはり、 ETS は偉大ですね