このページは
2024 年の Advent of Code の Day13 の記事です。 Day12 はこちら。
https://zenn.dev/yasuharu519/articles/cc3311c131327b
Day 13: Claw Contraption
舞台は南国の島のリゾート地となりました。ここにはゲームセンターがあり、その中のクレーンゲームをプレイすることになりました。
クレーンゲームにはコントローラがなく、 A ボタンと B ボタンの二つのボタンしかありません。また、A ボタンを押すには 3 つのトークン、B ボタンを押すには 1 つのトークンを支払う必要があります。
商品が置かれている X, Y 座標があり、クレーンをちょうどその位置に移動させることが出来れば商品を取ることが出来ます。ボタン A, ボタン B を押したときに X, Y 座標がどの程度移動するかが与えられるので、商品をとるのに必要な最小のトークンを求めるといった問題です。
Part1
Part1 では、商品をとるまでにそれぞれのボタンについて押す回数は 100 以下であることが保証されています。
それぞれ 100 回ずつ試しても 10000 回程度となるため、単純に全探索を行っても問題なさそうです。
https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day13/part1.py#L20-L25
のように全パターンを試して見て、最小のコストになるものを探し出します。
Part2
Part2 では、クレーンの場所が商品の場所とは遠く離れたところにあることが判明しました。実際の商品の場所は、与えられた座標から X, Y それぞれ 10000000000000 ずつ離れた場所にあることがわかりました。
結果、ボタンの数もそれぞれ 100 回以上押す必要があることが判明し、これでは Part1 のようにすべてのボタンの押し方を試して探し出すことは難しそうです。
最終的にボタン A を何回押す必要があるか、ボタン B を何回押す必要があるかわかれば良さそうで、ボタン A は a 回、ボタン B は b 回押すものとしましょう。
例えば
- ボタン A を押すと X 座標が +94, Y 座標が +34 移動
- ボタン B を押すと X 座標が +22, Y 座標が +67 移動
- 商品は X 座標が 10000000008400, Y 座標が 10000000005400 にある
とするとき、式にすると
\begin{align}
94a + 22b &= 10000000008400 \notag \\
22a + 67b &= 10000000005400 \notag
\end{align}
を満たすような a, b を求めれれば良さそうで、こちらは
\begin{pmatrix}
94 & 22 \\
22 & 67
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
\begin{pmatrix}
10000000008400 \\
10000000005400
\end{pmatrix}
というような連立方程式を解くことで求めることが出来そうです。
逆行列を用いて解こうとすると
\begin{align}
\begin{pmatrix}
a \\
b
\end{pmatrix}
&=
\begin{pmatrix}
94 & 22 \\
22 & 67
\end{pmatrix}^{-1}
\begin{pmatrix}
10000000008400 \\
10000000005400
\end{pmatrix}
\notag \\
&=
\frac{1}{94 \times 67 - 22 \times 22}
\begin{pmatrix}
67 & -22 \\
-22 & 94
\end{pmatrix}
\begin{pmatrix}
10000000008400 \\
10000000005400
\end{pmatrix}
\notag \\
&=
\frac{1}{94 \times 67 - 22 \times 22}
\begin{pmatrix}
67 \times 10000000008400 - 22 \times 10000000005400 \\
-22 \times 10000000008400 + 94 \times 10000000005400
\end{pmatrix}
\notag
\end{align}
となります。
A ボタンを押したときの X, Y の移動する距離を dx_a, dy_a、B ボタンを押したときの X, Y の移動する距離を dx_b, dy_b とするし、商品の座標を X, Y とすると、上記の式は
\begin{align}
\begin{pmatrix}
a \\ b
\end{pmatrix}
=
\frac{1}{dx_a \times dy_b - dx_b \times dy_a}
\begin{pmatrix}
dy_b \times X & -dx_b \times Y \\
-dy_a \times X & dx_a \times Y
\end{pmatrix}
\end{align}
となります。こちらの連立方程式の解の求め方は クラメルの公式 としても知られているようです。
https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day13/part2.py#L19-L28
実際の計算の際には、逆行列が存在するかどうかの確認も忘れないようにしましょう。
Day 14 に続きます。
https://zenn.dev/yasuharu519/articles/e3f21bd7a556e9
Discussion