Zenn
🎅

Advent of Code 2024 Day 17: Chronospatial Computer

に公開
Python
Advent of Code
tech

このページは

2024 年の Advent of Code の Day17 の記事です。

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

Day16 の内容はこちら。

https://zenn.dev/yasuharu519/articles/9d1b6e56b115c5

Day 17: Chronospatial Computer

奇妙な装置のボタンが押されると、小型の端末装置が突然展開し、コンピュータになりました。このコンピュータは 3-bit のコンピュータで、A, B, C の 3 つのレジスタを持っています。ただしレジスタは 3-bit 以上の値を保持できます。

このコンピュータは 8 つの命令を持ち、命令のオペコードは 3-bit の整数で区別されます。またその直後の値をオペランドとして受け取ります。

命令ポインタは 0 から開始し、次に読むオペコードの値を指し示します。jump 命令を除いて通常の命令を実行した後は 2 だけ進みます。プログラムの末尾を読もうとすると停止します。

オペランドは 2 種類存在します。

  • リテラルオペランド: 0 から 7 の整数
  • コンボオペランド:
    • 0 から 2 の場合: その整数自身を表す
    • 4 の場合: レジスタ A の値
    • 5 の場合: レジスタ B の値
    • 6 の場合: レジスタ C の値
    • 7 については有効なプログラムには登場しません。

8 つの命令は以下の通りです。

  • adv (オペコード 0):
    • 割り算を実行します
    • 割られる数はレジスタ A の値で、割る数は、命令のコンボオペランドの 2 のべき乗です
    • 結果は整数に切り捨てられ、レジスタ A に格納されます
  • bxl (オペコード 1):
    • ビット XOR を実行します
    • レジスタ B の値と、命令のリテラルオペランドをとり、レジスタ B に格納します
  • bst (オペコード 2):
    • 命令のコンボオペランドの値を 8 で割った値 (下位 3 bit を取り出した値) をレジスタ B に書き込みます
  • jnz (オペコード 3):
    • レジスタ A が 0 の場合は何もしない
    • そうでない場合は、命令のリテラルオペランドの値を命令ポインタに設定する
    • この場合は実行後も命令ポインタを 2 進めない
  • bxc (オペコード 4):
    • レジスタ B と レジスタ C の ビット XOR を実行し、結果をレジスタ B に格納します
    • オペランドは無視されます
  • out (オペコード 5):
    • コンボオペランドの値を 8 で割った余りを出力します
  • bdv (オペコード 6):
    • adv 命令と同じですが、結果をレジスタ B に格納します
  • cdv (オペコード 7):
    • adv 命令と同じですが、結果をレジスタ C に格納します

Part1

Part1 では、与えられたプログラムの実行を行い、プログラムが終了するまでの out 命令の結果を求める問題です。

例えばサンプルとして与えられた以下のプログラムを見てみましょう。

Register A: 729
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0

Program をオペレーションとオペランドに分けて見てみると、以下のようなイメージになります。

(adv 2**1) (out RegA) (jnz 0)
  • レジスタ A の値を (2**1) で割った値を レジスタ A に格納
  • レジスタ A の値を 8 で割った余りを出力
  • 命令ポインタを 0 に戻す

基本的には与えられたプログラムを読み、命令ポインタにある命令を実行していけば良いです。
各命令がとるオペランドの種類が異なるため、間違えないように注意しましょう。 (自分は最初すべてコンボオペランドとして処理するというミスをしてしまった)

Part2

Part2 では、どうやら レジスタ A の値が間違っていたことがわかりました。 本来このプログラムはプログラムを実行した結果が、プログラムそのものになるといったものだったようです。
今回は本来の意図通りの動作となるようなレジスタ A の値を求める必要があります。

今回の入力を見て見ましょう

2,4,1,5,7,5,1,6,4,2,5,5,0,3,3,0
(bst RegA) (bxl 5) (cdv 2**RegB) (bxl 6) (bxc 2) (out RegB) (adv 2**3) (jnz 0)

このプログラムをよく見て後半の３つの命令に注目してみましょう。

  • (out RegB): レジスタ B の値を 8 で割った余りを出力
  • (adv 2**3): レジスタ A の値を 8 で割った値を レジスタ A に格納
  • (jnz 0): レジスタ A の値が 0 でない場合は、命令ポインタを 0 に戻す

つまり、前半はレジスタ A, B, C の値を操作し、後半は レジスタ B の値を出力した後、レジスタ A の値を 8 で割り、レジスタ A の値に応じてループ するものと読み取れます。
また、プログラムを停止させるためには、最終的にレジスタ A の値が 0 である必要があります。

そのため、 最終的に レジスタ A の値が 0 になるようにしながら、プログラムと同じ出力がでるようなレジスタ A の値 を逆順に求めていくことで問題を解くことが出来ます。

https://github.com/yasuharu519/advent-of-code-2024/blob/main/python/day17/part2.py#L4-L20

のように、再帰関数を作成することで、最初のレジスタ A の値を求めることが出来ます。

Day 18 に続きます。
https://zenn.dev/yasuharu519/articles/a1569d4b96c9a1

Discussion