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

## はじめに

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

問題文はこちら

https://adventofcode.com/2024/day/11

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

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2024/2024_day11_part2.livemd

Part 1 はこちら

https://qiita.com/RyoWakabayashi/private/dede59042fbc676f5c4b

## セットアップ

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

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

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

https://qiita.com/RyoWakabayashi/items/3d3abcf9134cee4dff05

## 入力の取得

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

![スクリーンショット 2024-12-11 21.39.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/f8f5e4bd-621a-615d-d947-432fc81dca95.png)

## 私の答え

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

<details><summary>回答</summary>

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

とにかく高速化します

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

```elixir
small_sample_input = "0 1 10 99 999"
```

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

実行結果

```elixir
[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` を足すことで桁数になります

```elixir
stone = 99

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

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

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

実行結果

```elixir
{9, 9}
```

確かに分割できました

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

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

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

```elixir
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 を初期化します

```elixir
BlinkCounter.start_link()
```

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

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

標準出力

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

実行結果

```elixir
7
```

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

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

```elixir
BlinkCounter.count_expansions(0, 6)
```

実行結果

```elixir
7
```

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

```elixir
:ets.tab2list(:blink_count_cache)
```

実行結果

```elixir
[
  {{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 回実行してみます

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

実行結果

```elixir
7
```

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

```elixir
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)
```

</details>

## まとめ

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

![aoc2024_day11_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/a81d7a87-4b7d-469b-6f64-4527f436f7dc.png)

やはり、 ETS は偉大ですね