この記事は、mae616 Advent of Code Advent Calendar 2024 の13日目の記事です。

このアドベントカレンダーは皆勤賞のQiitaくんのぬいぐるみに惹かれて挑戦している大変ゆるい挑戦のものです。そんな感じで読んでいただければ幸いです。

Advent of Code が10周年っぽいので、やっぱり 10 なんですかね ٩( ᐛ )و

前の日: [Advent of Code 2024] Day 12: Garden Groups
次の日: [Advent of Code 2024] Day 14: Restroom Redoubt

今日のお題

13日目の物語

■ 13日目: クレーン装置
次は、熱帯の島にあるリゾートの『ロビー』です。歴史学者たちは六角形の床タイルをちょっと眺めた後、散らばり始めます。

『ロビー』も Advent of Code 2020 と繋がってるみたいですね。

幸いなことに、このリゾートには新しいアーケード(ゲーム機)があります！クレーンゲームで何か景品を獲れるかもしれませんね。

ここにあるクレーンゲームはちょっと変わっています。ジョイスティックや方向ボタンでクレーンを操作するのではなく、A ボタンと B ボタンという2つのボタンが付いています。さらに悪いことに、トークンを入れたらすぐにプレイできるわけではなく、A ボタンを押すには3 『トークン』、B ボタンを押すには 1 『トークン』が必要です。

少し試してみると、各マシンのボタンは、それぞれクレーンを X 軸方向に特定の距離だけ右に、Y 軸方向に特定の距離だけ前に動かすことがわかります。

各マシンには1つの景品があり、クレーンを景品の真上に正確に位置させないといけません。X 軸と Y 軸の両方でピッタリと重ねる必要があります。

さて、最小のトークン数で、できるだけ多くの景品を獲得するにはどうすればよいでしょうか？あなたは、各マシンのボタン動作と景品の位置（あなたのパズルの入力）をリストにまとめました。

お金の代わりに『トークン』っていうのが必要なんですね٩( ᐛ )و

なんかこんな感じのクレーンゲームがいっぱいあるところなんですかね ٩( ᐛ )و
(画像生成AIにて生成)

1問目

例1:

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

※ Prize は日本語訳で賞品🎁 です。賞品は1つのクレーンゲームに1つか入ってないらしいので、賞品の位置が書いてあるみたいですね。

このリストは、4台の異なるクレーンマシンのボタン設定と賞品の位置を示しています。

まず、リストの最初のクレーンマシンを見てみましょう：
このマシンで

ボタン A を押すと、クレーンは X 軸方向に 94、Y 軸方向に 34 だけ動きます

ボタン B を押すと、クレーンは X 軸方向に 22、Y 軸方向に 67 だけ動きます

賞品は X=8400, Y=5400 にあります

つまり、クレーンの 初期位置 から、X 軸で 8400、Y 軸で 5400 だけ動かす必要があります。

このマシンで賞品🎁 を獲得するための最小コストの方法は、ボタン A を 80 回、ボタン B を 40 回押すことです。
これで、クレーンが

X 軸 A: 80 回 * 94 = 7520, B: 40 回 * 22 = 880, 7520 + 880 = が 8400 (賞品の X の位置)

Y 軸 A: 80 回 * 34 = 2720, B: 40 回 * 67 = 2680, 2720 + 2680 = が 5400 (賞品の Y の位置)

で賞品の位置にぴったり合います。
この方法でかかる『トークン』は、

ボタン A を 80 回押すのに 80 * 3 = 240 トークン

ボタン B を 40 回押すのに 40 * 1 = 40 トークン

合計 280 トークンです。

※ 最初の物語部分にあったように、A ボタンを 1 回押すには3 トークン、B ボタンを 1 回押すには 1 トークンが必要です

2台目と4台目のクレーンマシンでは、ボタン A と B を押すどんな組み合わせでも賞品を獲得することはできません。

3台目のクレーンマシンでは、最小コストの方法は

ボタン A を 38回

ボタン B を 86 回

押すことです。これで、かかるトークンは合計 200 トークンです。

つまり、最も多く獲得できる賞品は 2 つ(1台目と3台目)で、そのために必要な最小トークン数は 480 トークン(1台目 280 + 3台目 200 = 480 )です。

各ボタンは賞品を獲得するために100回以上押す必要はないと見積もっている。

A ボタンも押すのは最大100回まで、B ボタンも押すのは最大100回までですね٩( ᐛ )و

できるだけ多くの賞品を獲得する方法を考え、すべての賞品を獲得するために最も少ないトークン数を求めてください。

やってみましょう٩( ᐛ )و

解いたコード

なんかすごいDP(動的計画法)の気がしてるんですが、わからないのでとりあえず総当たりしました ꉂꉂ( ᐛ )

./day13_1/main.js

function main(input) {
  const args = input.split("\n");

  // 読み込みと解析
  const claws = [];

  const clawMapping = [
    { prefix: "Button A", key: "a" },
    { prefix: "Button B", key: "b" },
    { prefix: "Prize", key: "prize" },
  ];

  let clawCount = 0;
  let claw = {};
  for (const arg of args) {
    if (arg === "") {
      claws.push(claw);
      clawCount++;
      claw = {};
      continue;
    }

    const [prefix, value] = arg.split(": ");
    const mapping = clawMapping.find((m) => prefix === m.prefix);
    const [x, y] = value.match(/\d+/g);
    claw[mapping.key] = { x: parseInt(x), y: parseInt(y) };
  }

  // クレーンの操作
  const tokenA = 3; // Aボタンを1回押すのに消費するトークンの数
  const tokenB = 1; // Bボタンを1回押すのに消費するトークンの数

  let sum = 0;
  for (const claw of claws) {
    const { a, b, prize } = claw;

    let minToken = Infinity;
    for (let countB = 0; countB <= 100; countB++) {
      for (let countA = 0; countA <= 100; countA++) {
        if (
          countA * a.x + countB * b.x === prize.x &&
          countA * a.y + countB * b.y === prize.y
        ) {
          minToken = Math.min(minToken, countA * tokenA + countB * tokenB);
        }
      }
    }

    // トークンの消費量
    if (minToken !== Infinity) {
      sum += minToken;
    }
  }
  console.log(sum);
}
main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));

下記で実行できます。

$ cd day13_1
$ node main.js

1問目(2)

2問目にいくにあたり、ちょっと1問目をDP(動的計画法)に変えてみました٩( ᐛ )و
正直、DP(動的計画法)は何度も本で解説を読んでもなかなか知識に出来ず、苦戦しております。なので、この記事を1日寝かして、昨夜ChatGPTさんにDPについてコーチしてもらいました ꉂꉂ( ᐛ )
賢くなりたいですね ꉂꉂ( ᐛ )

さて、いきましょう٩( ᐛ )و

解いたコード

./day13_1_dp/main.js

function main(input) {
  const args = input.split("\n");

  // 読み込みと解析
  const claws = [];

  const clawMapping = [
    { prefix: "Button A", key: "a" },
    { prefix: "Button B", key: "b" },
    { prefix: "Prize", key: "prize" },
  ];

  let clawCount = 0;
  let claw = {};
  for (const arg of args) {
    if (arg === "") {
      claws.push(claw);
      clawCount++;
      claw = {};
      continue;
    }

    const [prefix, value] = arg.split(": ");
    const mapping = clawMapping.find((m) => prefix === m.prefix);
    const [x, y] = value.match(/\d+/g);
    claw[mapping.key] = { x: parseInt(x), y: parseInt(y) };
  }

  // クレーンの操作
  const tokenA = 3; // Aボタンを1回押すのに消費するトークンの数
  const tokenB = 1; // Bボタンを1回押すのに消費するトークンの数

  let sum = 0;
  for (const claw of claws) {
    const { a, b, prize } = claw;

    const queue = [{ x: 0, y: 0 }];
    const point = new Array(prize.x + 1)
      .fill()
      .map(() => new Array(prize.y + 1).fill(Infinity));
    while (queue.some((p) => p.x < prize.x || p.y < prize.y)) {
      const { x, y } = queue.shift();

      if (x > prize.x || y > prize.y) {
        continue;
      }

      point[x + a.x][y + a.y] = Math.min(
        point[x + a.x][y + a.y],
        point[x][y] + tokenA
      );
      point[x + b.x][y + b.y] = Math.min(
        point[x + b.x][y + b.y],
        point[x][y] + tokenB
      );

      queue.push({ x: x + a.x, y: y + a.y });
      queue.push({ x: x + b.x, y: y + b.y });
    }

    // トークンの消費量
    if (point[prize.x][prize.y] !== Infinity) {
      sum += point[prize.x][prize.y];
    }
  }
  console.log(sum);
}
main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));

2問目

最初の賞品を取ろうとしたところ、　クレーンが予想していた位置には全くないことに気付きます。測定時の単位換算ミスにより、すべての賞品の位置が実際には X 軸と Y 軸それぞれで 10000000000000 だけ高くなっているのです！

各賞品の X 座標と Y 座標に 10000000000000 を加えてください。この変更を加えると、上記の例は次のようになります：
Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=10000000008400, Y=10000000005400

Button A: X+26, Y+66
Button B: X+67, Y+21
Prize: X=10000000012748, Y=10000000012176

Button A: X+17, Y+86
Button B: X+84, Y+37
Prize: X=10000000007870, Y=10000000006450

Button A: X+69, Y+23
Button B: X+27, Y+71
Prize: X=10000000018641, Y=10000000010279

今、賞品を獲得できるのは2番目と4番目のクレーンマシンだけです。残念ながら、それを達成するには100回以上の操作が必要になるでしょう。

修正された賞品の座標を使って、できるだけ多くの賞品を獲得する方法を考えてください。すべての賞品を獲得するために必要な最少のトークン数は何ですか？

また、すごい問題がきた ꉂꉂ( ᐛ )
エグいですねぇ ꉂꉂ( ᐛ )

いってみましょう٩( ᐛ )و

解くアプローチ

いろいろ試したのですがどれも処理時間が長すぎて、すっかり分からずChatGPTさんに解き方聞いちゃいました ꉂꉂ( ᐛ )

どうも線形方程式というのであらわせるみたいですね٩( ᐛ )و
線形方程式ってなんだろう。まあ、今はそこまで調べるとキャパシティオーバーするので飛ばしましょう ꉂꉂ( ᐛ )

\begin{flalign}
&\left\{
\begin{array}{ll}
Aボタンを押す回数 \times AボタンによるX軸の移動量 + Bボタンを押す回数 \times BボタンによるX軸の移動量 = 目標X座標\\
Aボタンを押す回数 \times AボタンによるY軸の移動量 + Bボタンを押す回数 \times BボタンによるY軸の移動量 = 目標Y座標\\
\end{array}
\right.&
\end{flalign}

なので、変数名を当てはめると
※ $pushCountA$ ... Aボタンを押す回数, $pushCountB$ ... Bボタンを押す回数

\begin{flalign}
&\left\{ 
\begin{array}{l} 
pushCountA \times a.x + pushCountB \times b.x = Prize.x\\
pushCountA \times a.y + pushCountB \times b.y = Prize.y\\
\end{array}
\right.&
\end{flalign}

を解けばいいことになりますね ٩( ᐛ )و

🐸
　
解き方はこれかな？

ああ、線形代数。すごい大学で苦しみながらやりました ꉂꉂ( ᐛ )
ここで出会うとは ꉂꉂ( ᐛ )
線形代数と同じ意味の線形ですかね(よく分かってません) ꉂꉂ( ᐛ )

数学のトラウマが思い出されたところでいきましょう。レッツゴー٩( ᐛ )و

🐸 🐸 🐸
　
1台目のクレーンマシーンの値を試しに当てはめてみましょう。

Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=10000000008400, Y=10000000005400

だから、

\begin{flalign}
&\left\{ 
\begin{array}{l} 
pushCountA \times 94 + pushCountB \times 22 = 10000000008400\\
pushCountA \times 34 + pushCountB \times 67 = 10000000005400\\
\end{array}
\right.&
\end{flalign}

線形代数にすると...

\begin{flalign}
&\left(
\begin{array}{ll} 
94 & 22\\
34 & 67\\
\end{array}
\right)
\times
\left(
\begin{array}{l} 
pushCountA\\
pushCountB\\
\end{array}
\right)
=
\left(
\begin{array}{l} 
10000000008400\\
10000000005400\\
\end{array}
\right)&
\end{flalign}

になる。
もうすごくいや ꉂꉂ( ᐛ )

<解があるかの確認>
で、これを解くと...
もうChatGPTさん頼りです ꉂꉂ( ᐛ )

行列 $A$ を定義します。

\begin{flalign}
&A=\left(
\begin{array}{ll} 
94 & 22\\
34 & 67\\
\end{array}
\right)&
\end{flalign}

計算して $det(A)$ というのを求めます。
たすき掛けみたいに計算してますね。

\begin{flalign}
&det(A)=(94×67)−(34×22)&
\end{flalign}

計算してみましょう。

\begin{flalign}
&det(A)=(94×67)−(34×22) = 6298 - 748 = 5550&
\end{flalign}

答えが $5550$ で $0$ でないので「この線形方程式に解はある」ということがわかります。

<解を求める>
(1)　まず逆行列 $A^{-1}$ というのを求めます。

\begin{flalign}
&A^{-1}=
\frac{1}{det(A)}
\times
\left(
\begin{array}{rr} 
67 & -22\\
-34 & 94\\
\end{array}
\right)&
\end{flalign}

※ 逆行列の求め方

\begin{flalign}
&A=
\left(
\begin{array}{rr} 
a & b\\
c & d\\
\end{array}
\right)
\hspace{20pt}
A^{-1}=
\frac{1}{det(A)}
\times
\left(
\begin{array}{rr} 
d & -b\\
-c & a\\
\end{array}
\right)&
\end{flalign}

$det(A)$ はすでに $5550$ と求めたので、

\begin{flalign}
&A^{-1}=
\frac{1}{5550}
\times
\left(
\begin{array}{rr} 
67 & -22\\
-34 & 94\\
\end{array}
\right)&
\end{flalign}

になります。

(2)　逆行列 $A^{-1}$ を使って方程式を解く。
問題の行列方程式は

\begin{flalign}
&\left(
\begin{array}{ll} 
94 & 22\\
34 & 67\\
\end{array}
\right)
\times
\left(
\begin{array}{l} 
pushCountA\\
pushCountB\\
\end{array}
\right)
=
\left(
\begin{array}{l} 
10000000008400\\
10000000005400\\
\end{array}
\right)&
\end{flalign}

で、

\begin{flalign}
&A
\times
\left(
\begin{array}{l} 
pushCountA\\
pushCountB\\
\end{array}
\right)
=
\left(
\begin{array}{l} 
10000000008400\\
10000000005400\\
\end{array}
\right)&
\end{flalign}

と書くことができる。

　　
これの両辺に逆行列 $A^{-1}$ をかける。

\begin{flalign}
&A^{-1}
\times
A
\times
\left(
\begin{array}{l} 
pushCountA\\
pushCountB\\
\end{array}
\right)
=
A^{-1}
\times
\left(
\begin{array}{l} 
10000000008400\\
10000000005400\\
\end{array}
\right)&
\end{flalign}

　
$A^{-1} \times A = 1$ になるので、

\begin{flalign}
&\left(
\begin{array}{l} 
pushCountA\\
pushCountB\\
\end{array}
\right)
=
A^{-1}
\times
\left(
\begin{array}{l} 
10000000008400\\
10000000005400\\
\end{array}
\right)&
\end{flalign}

になる。

　　
逆行列 $A^{-1}$ を当てはめてみましょう。

\begin{flalign}
&\left(
\begin{array}{l} 
pushCountA\\
pushCountB\\
\end{array}
\right)
=
\frac{1}{5550}
\times
\left(
\begin{array}{rr} 
67 & -22\\
-34 & 94\\
\end{array}
\right)
\times
\left(
\begin{array}{l} 
10000000008400\\
10000000005400\\
\end{array}
\right)&
\end{flalign}

これを解きましょう。

　　
下記になります。

\begin{flalign}
&\begin{array}{l} 
pushCountA = 
\frac{1}{5550}
\times
(67 \times 10000000008400 + (-22) \times 10000000005400) \\
pushCountB = 
\frac{1}{5550}
\times
(-34 \times 10000000008400 + 94 \times 10000000005400)
\end{array}&
\end{flalign}

これを計算すると $pushCountA$ と $pushCountB$ が求められます。

(3) 最小トークンの計算

\begin{flalign}
&最小トークン数 = pushCountA \times 3 + pushCountB \times 1&
\end{flalign}

です。

🐸 🐸 🐸

整理してみましょう

Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=10000000008400, Y=10000000005400

で求めました。

　
　
要は...

\begin{flalign}
&det(A)=(a.x \times b.y)−(a.y \times b.x)&
\end{flalign}

が $0$ でなければ「解がある」、つまり「賞品🎁 の座標にクレーンがたどり着ける」ことになります。

　
A ボタン、B ボタンを押す回数は...

\begin{flalign}
&\begin{array}{l} 
pushCountA = 
\frac{1}{det(A)}
\times
(b.y \times prize.x + (-1 \times b.x) \times prize.y) \\
pushCountB = 
\frac{1}{det(A)}
\times
((-1 \times a.y )\times prize.x + a.x \times prize.y)
\end{array}&
\end{flalign}

で求められる。

　
最小トークンは...

\begin{flalign}
&最小トークン数 = pushCountA \times 3 + pushCountB \times 1&
\end{flalign}

です。

もし理解できなくても大丈夫です。私も理解してません ꉂꉂ( ᐛ )
もう解き方は教えてもらって、コードを書くのをがんばりましょう。
ここまで読むのお疲れさまでした٩( ᐛ )و

解いたコード

./day13_2/main.js

function main(input) {
  const args = input.split("\n");

  // 読み込みと解析
  const claws = [];

  const clawMapping = [
    { prefix: "Button A", key: "a" },
    { prefix: "Button B", key: "b" },
    { prefix: "Prize", key: "prize" },
  ];

  let clawCount = 0;
  let claw = {};
  for (const arg of args) {
    if (arg === "") {
      claws.push(claw);
      clawCount++;
      claw = {};
      continue;
    }

    const [prefix, value] = arg.split(": ");
    const mapping = clawMapping.find((m) => prefix === m.prefix);
    const [x, y] = value.match(/\d+/g);
    claw[mapping.key] = { x: parseInt(x), y: parseInt(y) };
  }

  // 10000000000000 を足す
  const add = 10000000000000;
  for (const claw of claws) {
    claw.prize.x += add;
    claw.prize.y += add;
  }

  // クレーンの操作
  const tokenA = 3; // Aボタンを1回押すのに消費するトークンの数
  const tokenB = 1; // Bボタンを1回押すのに消費するトークンの数

  let sum = 0;
  for (const claw of claws) {
    const { a, b, prize } = claw;

    // det(A) を求める
    const detA = a.x * b.y - a.y * b.x;

    if (detA === 0) {
      // クレーンが賞品に到達できない
      continue;
    }

    // ボタン A とボタン B を押す回数を求める
    const pushCountA = (b.y * prize.x + -1 * b.x * prize.y) / detA;
    const pushCountB = (-1 * a.y * prize.x + a.x * prize.y) / detA;

    // ボタン A とボタン B を押す回数が整数でない場合
    if (!Number.isInteger(pushCountA) || !Number.isInteger(pushCountB)) {
      // クレーンが賞品に到達できない
      continue;
    }

    // 最小のトークン数を求める
    const token = pushCountA * tokenA + pushCountB * tokenB;
    sum += token;
  }
  console.log(sum);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));

もうすごいがんばりました。2日くらいすごい悩んでました ꉂꉂ( ᐛ )

終わり！

すっかり海外の人に置いてかれてしまいました...
https://www.reddit.com/r/adventofcode/
数学に強い人うらやましい ꉂꉂ( ᐛ )

では、また٩( ᐛ )و