Advent of code 2015 Day 25 を Livebook で楽しむ

はじめに

Advent of code 2024 の準備として、過去回の Advent of code 2015 を Livebook で楽しみます

本記事では Day 25 を解きます

問題文はこちら

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

Day 25 の Part 2 はエンディングになっていて、パズルはありませんでした

セットアップ

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

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

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

入力の取得

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

私の答え

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

回答

まず、行と列から「何番目のコードなのか」を取得します

斜めに増えていく数字は三角数です

https://ja.wikipedia.org/wiki/%E4%B8%89%E8%A7%92%E6%95%B0

$$
T_n = \frac{n(n+1)}{2}
$$

何番目の対角線なのか、は 行番号 + 列番号 - 1 で求めることができます

get_index = fn r, c ->
  k = r + c - 1
  div(k * (k - 1), 2) + c
end

例えば 3 行目、 2 列目を求めてみます

get_index.(3, 2)

実行結果

8

n 番目のコードは以下の式で求めることができます

$$
(20151125^{n-1}) mod 33554393
$$

しかし、 n が膨大な数字の場合、計算に時間がかかりすぎます

そこで、繰り返し二乗法を使用して計算量を抑えます

https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b

defmodule WeatherMachine do
  @initial 20_151_125
  @modulo 33_554_393
  @multiplier 252_533

  def get(r, c) do
    generate(get_index(r, c) - 1)
  end

  defp get_index(r, c) do
    k = r + c - 1
    div(k * (k - 1), 2) + c
  end

  defp generate(n) do
    power = mod_exp(@multiplier, n, @modulo)
    rem(@initial * power, @modulo)
  end

  defp mod_exp(_, 0, _), do: 1

  defp mod_exp(base, exp, mod) do
    if rem(exp, 2) == 0 do
      half = mod_exp(base, div(exp, 2), mod)
      rem(half * half, mod)
    else
      rem(base * mod_exp(base, exp - 1, mod), mod)
    end
  end
end

3 行目 1 列目で実行してみます

WeatherMachine.get(3, 1)

実行結果

16080970

実際の入力で実行します

WeatherMachine.get(2947, 3029)

まとめ

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

数学の勉強になりました

これで、 AOC 2015 はコンプリートです！

コンプリート達成後のカレンダーはなかなか見応えがありますね