Tower of Alloy【Turing Complete編】

2023年9月12日

1 はじめに
2 Tower of Alloyステージ
3 本ステージのハノイの塔
- 3.1 手動でハノイの塔を試す
4 ハノイの塔を解くアルゴリズム
5 Tower of Alloyステージを解く

はじめに

いつもブログをご覧いただきありがとうございます。

FIRE生活中のIPUSIRONです😀

IPUSIRONのプロフィールを見る

Tower of Alloyステージ

Tower of Alloyステージのゴールは、ハノイの塔を解くことです。

地下室の掃除を要請されます。具体的には、古い原子炉から放射性円盤の山を移動させます。小さな円盤の上に大きな円盤を置かないように注意しなければなりません。そうしないと、宇宙船が爆発してしまうからです。

本ステージのハノイの塔

円盤の山の移動は、ハノイの塔そのものです。

最初に4つの入力が与えられますが、それぞれのデータは順に次の意味を持ちます。

・disk_nr･･･円盤の最大番号（2～4）。つまり、最初の時点で少なくとも0,1,2の3枚は重なっている。

・source･･･移動元の場所（0～2）。

・destination･･･移動先の場所（0～2）。

・spare･･･移動元でも移動先でもない、3番目の場所（0～2）。

出力値でクレーンを制御します。

・0･･･スポット0に磁石を移動する。

・1･･･スポット1に磁石を移動する。

・2･･･スポット2に磁石を移動する。

・5･･･磁石^[1]磁力の放出をON・OFFできる電磁石だと思ってください。のON・OFFを切り替える。

手動でハノイの塔を試す

Level screenやアセンブリーエディターの右上にハノイの塔が表示されます。

左右キーで磁石を移動、[Enter]キーで磁石のON・OFFを切り替えられます。実際に試してみましょう。

わざと小さい数値の円盤の上に、大きい数値の円盤を重ねてみます。すると、爆発してゲームオーバーになります。

ハノイの塔を解くアルゴリズム

ハノイの塔を解くアルゴリズムは擬似コードの形で提示されています。これを参考に実装しましょう。

そして、レジスター値を変更する関数を呼び出す前は、レジスター値をスタックにPUSHして保存するとよいことがヒントとして与えられます。

Tower of Alloyステージを解く

1：プログラムの設計を検討する

ハノイの塔を解くアルゴリズムは提示されているので、我々のLEGアーキテクチャー、そして本ステージの仕様に合わせて、コードを追加・編集していきます。

2：プログラムを実装する

完成したプログラムは次の通りです。

const DISK_NR REG1
const SRC REG2
const DEST REG3
const SPARE REG4

label main
# 入力をレジスターに保存する.
ADDi INPUT 0 DISK_NR
ADDi INPUT 0 SRC
ADDi INPUT 0 DEST
ADDi INPUT 0 SPARE

CALL solve_hanoi _ _

# 次の問題を解く.
IF_EQ REG0 REG0 main # 強制ジャンプ.
# main処理終了.

# ハノイの塔を解く.
# REG 1【入力】：disk_nr
# REG 2【入力】：source
# REG 3【入力】：dest
# REG 4【入力】：spare
# REG 0（破壊）：一時保管用
label solve_hanoi
IF_EQi DISK_NR 0 disk_nr_0
PUSH DISK_NR _ _
PUSH SRC _ _
PUSH DEST _ _
PUSH SPARE _ _
# 引数をdisk_nr-1,source,spare,destとして、solve_hanoiを呼び出す.
SUBi DISK_NR 1 DISK_NR
#spareとdestをスワップ.
ADDi DEST 0 REG0
ADDi SPARE 0 DEST
ADDi REG0 0 SPARE
CALL solve_hanoi _ _
POP _ _ SPARE
POP _ _ DEST
POP _ _ SRC
POP _ _ DISK_NR
##
CALL move_disk _ _
##
PUSH DISK_NR _ _
PUSH SRC _ _
PUSH DEST _ _
PUSH SPARE _ _
# 引数をdisk_nr-1,spare,dest,sourceとして、solve_hanoiを呼び出す.
SUBi DISK_NR 1 DISK_NR
#spareとsourceをスワップ.
ADDi SRC 0 REG0
ADDi SPARE 0 SRC
ADDi REG0 0 SPARE
CALL solve_hanoi _ _
POP _ _ SPARE
POP _ _ DEST
POP _ _ SRC
POP _ _ DISK_NR
RET _ _ _
label disk_nr_0
CALL move_disk _ _
RET _ _ _

# 円盤を移動する.
# REG 2【入力】：移動元（0～2）
# REG 3【入力】：移動先（0～2）
label move_disk
# クレーンを移動元に合わせる.
ADDi REG2 0 OUTPUT
# 磁石をONにして円盤を持ち上げる.
ADDii 5 0 OUTPUT
# クレーンを移動先に合わせる.
ADDi REG3 0 OUTPUT
# 磁石をOFFにして円盤を下げる.
ADDii 5 0 OUTPUT
RET _ _ _

作ったプログラムでは、PUSH命令やPOP命令の実行後にありえない数値を出力して、エラーが発生していました。
十数分間悩みましたが、よく見たら「PUSH DISK_NR _ _ _」のように「_」が1つ多かったという単純なミスでした。
きちんとすべての命令が4バイトになっているかをチェックしましょう。

3：テストする

テストパターンは6つ用意されています。

テストにパスすると、ステージクリアになります。