はじめに
Advent of code 2024 Day 13 の Part 2 を解きます
問題文はこちら
実装したノートブックはこちら
Part 1 はこちら
セットアップ
Kino AOC をインストールします
また、今回は行列演算を使いたいので、 Nx もインストールします
Mix.install([
{:kino_aoc, "~> 0.1"},
{:nx, "~> 0.9"}
])
Kino AOC の使い方はこちらを参照
入力の取得
"Advent of Code Helper" スマートセルを追加し、 Day 13 の入力を取得します
私の答え
私の答えです。
折りたたんでおきます。
▶を押して開いてください。
回答
Part 1 の回答のままでは、組み合わせの数が多くなりすぎて終わりません
組み合わせを探索するのではなく、以下の連立方程式を解く方針にしましょう
$$
n_aa_x + n_bb_x = p_x
$$
$$
n_aa_y + n_bb_y = p_y
$$
（$n_a$ は A ボタンを押す回数、 $n_b$ は B ボタンを押す回数）
この連立方程式は行列を使うと以下のように表現できます
$$
Ax=b
$$
sample_input =
"""
Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400
Button A: X+26, Y+66
Button B: X+67, Y+21
Prize: X=12748, Y=12176
Button A: X+17, Y+86
Button B: X+84, Y+37
Prize: X=7870, Y=6450
Button A: X+69, Y+23
Button B: X+27, Y+71
Prize: X=18641, Y=10279
"""
|> String.trim()
クレーンゲーム機を A と b の行列で表現するように読み込みます
また、桁数が大きいため、型を :f64 に指定します
parse_machines = fn input ->
input
|> String.split("\n\n")
|> Enum.map(fn machine_rows ->
Regex.named_captures(
~r/\+(?<ax>\d+).*\+(?<ay>\d+)\n.*\+(?<bx>\d+).*\+(?<by>\d+)\n.*=(?<px>\d+).*=(?<py>\d+)/,
machine_rows
)
end)
|> Enum.map(fn %{"ax" => ax, "ay" => ay, "bx" => bx, "by" => by, "px" => px, "py" => py} ->
%{
A: Nx.tensor([
[String.to_integer(ax), String.to_integer(bx)],
[String.to_integer(ay), String.to_integer(by)]
], type: :f64),
b: Nx.tensor([
String.to_integer(px) + 10000000000000,
String.to_integer(py) + 10000000000000
], type: :f64)
}
end)
end
machines = parse_machines.(sample_input)
実行結果
[
%{
b: #Nx.Tensor<
f64[2]
[10000000008400.0, 10000000005400.0]
>,
A: #Nx.Tensor<
f64[2][2]
[
[94.0, 22.0],
[34.0, 67.0]
]
>
},
%{
b: #Nx.Tensor<
f64[2]
[10000000012748.0, 10000000012176.0]
>,
A: #Nx.Tensor<
f64[2][2]
[
[26.0, 67.0],
[66.0, 21.0]
]
>
},
%{
b: #Nx.Tensor<
f64[2]
[10000000007870.0, 10000000006450.0]
>,
A: #Nx.Tensor<
f64[2][2]
[
[17.0, 84.0],
[86.0, 37.0]
]
>
},
%{
b: #Nx.Tensor<
f64[2]
[10000000018641.0, 10000000010279.0]
>,
A: #Nx.Tensor<
f64[2][2]
[
[69.0, 27.0],
[23.0, 71.0]
]
>
}
]
Nx には連立方程式を解くための関数が用意されています
Nx.LinAlg.solve(A, b) で x を求めることができます
Nx.LinAlg.solve(
Nx.tensor([[26, 67], [66, 21]], type: :f64),
Nx.tensor([10000000012748, 10000000012176], type: :f64)
)
実行結果
#Nx.Tensor<
f64[2]
[118679050709.00002, 103199174542.0]
>
誤差はありますが、答えがほぼ整数になっています
連立方程式が解けないケースを実行してみます
Nx.LinAlg.solve(
Nx.tensor([[94, 22], [34, 67]], type: :f64),
Nx.tensor([10000000008400, 10000000005400], type: :f64)
)
実行結果
#Nx.Tensor<
f64[2]
[81081081161.08109, 108108108148.10811]
>
結果が整数ではありません
このことを利用して、ある程度の誤差を許容しつつ、結果が整数であれば解けたと考えられます
get_prize = fn %{A: a, b: b} ->
x = Nx.LinAlg.solve(a, b)
if x |> Nx.to_list() |> Enum.all?(&(round(&1 * 100) == round(&1) * 100)) do
x |> Nx.to_list() |> Enum.map(&round(&1))
else
[0, 0]
end
end
Enum.map(machines, &get_prize.(&1))
実行結果
[[0, 0], [118679050709, 103199174542], [0, 0], [102851800151, 107526881786]]
この結果を使ってコストを計算します
get_cost = fn machines ->
machines
|> Enum.map(fn machine ->
machine
|> get_prize.()
|> then(fn [num_a, num_b] ->
num_a * 3 + num_b
end)
end)
|> Enum.sum()
end
get_cost.(machines)
実行結果
875318608908
実際の入力を使えば答えが出ます
puzzle_input
|> parse_machines.()
|> get_cost.()
まとめ
問題文から ChatGPT に画像を生成してもらいました
Nx に連立方程式を解いてもらいました
桁数が大きすぎる場合、考慮しないといけないことが色々ありますね