Water World【Turing Complete編】
目次
はじめに
いつもブログをご覧いただきありがとうございます。
FIRE生活中のIPUSIRONです😀
いよいよTuring Completeの最終ステージになります。
Water Worldステージ
地球をエキゾチックなウォーターパークに変えたいと考えているようです。ウォータースライダーを設置するよい場所を探して欲しいとのことです。具体的には水を大量に貯められる場所になります。
風景（landscape）の幅は16列になります。入力を16回読み取り、各列の高さを左から順に取得できます。LEGアーキテクチャーの力を借りて、その風景が運ぶことのできる水の総体積を答えとして出力してください。
Water Worldステージを解くためのアルゴリズム
両サイドから高さの最大値を調べていき、潜在的な水柱を計算します。
ただし、潜在的な水柱として2つの値が出てきた場合は、小さい方を採用します。
すべての列で水柱が確定したら、その合計値を出力します。
https://steamcommunity.com/sharedfiles/filedetails/?id=27984...Water Worldステージを解く
1：プログラムを設計する
アセンブリーエディターを開いて、右上のゲーム画面に注目します。
[Enter]キーを押すと、風景に水が貯まった状況が表示されます。凹みがあるところに水が貯まります。端は横に流れるので水が貯っていません。
“Total volume"に体積が表示されます。つまり、テストパターン1では28を出力すれば正解ということになります。
16列分の入力が与えられますが、水の量ではなく、高さであることに注意してください。
本ステージで一番難しいのは、水の量をカウントするアルゴリズムです。さらにアルゴリズムが確定しても、我々のLEGアーキテクチャーには6個のレジスターしかありません。しかも、うち1個はRAMのアドレス用で消費しています。実質的に自由に使えるレジスターは5個しかなく、その制限下でアルゴリズムを走らせなければならないことが、プログラムをより複雑化させてしまう要因になります。
今回は以下の記事内のプログラムを参考にしました。ありがとうございます。
※若干我々のLEGアーキテクチャーに合わせて調整しています。
https://steamcommunity.com/sharedfiles/filedetails/?id=26251...RAMにおいて、16d番地を水の量を記憶する場所とします。
2：プログラムを実装する
プログラムを作成すると次のようになりました。
const ROW_SIZE 16
label main
CALL save_values _ _
const current REG0
const edge_h REG1
const current_h REG2
const w_temp REG3
const WATER_ADDRESS 16
const water REG2
const max_h REG4
label LeftEdge
ADDi current 0 RAM
LOAD _ _ edge_h
label SearchL2R
ADDi current 1 current
IF_GT_EQi current ROW_SIZE RightEdge
ADDi current 0 RAM
LOAD _ _ current_h
IF_LESS_EQ edge_h current_h UpdateEdgeL
SUB edge_h current_h current_h
ADD w_temp current_h w_temp
IF_EQ _ _ SearchL2R
label UpdateEdgeL
ADDi current_h 0 edge_h
ADDii WATER_ADDRESS 0 RAM
LOAD _ _ water
ADD water w_temp water
SAVE water _ _
ADDii 0 0 w_temp
IF_EQ _ _ SearchL2R
label RightEdge
ADDi edge_h 0 max_h
SUBii ROW_SIZE 1 current
ADDi current 0 RAM
LOAD _ _ edge_h
IF_GT_EQ edge_h max_h OutputResult
ADDii 0 0 w_temp
label SearchR2L
SUBi current 1 current
IF_LESSi current 0 OutputResult
ADDi current 0 RAM
LOAD _ _ current_h
IF_LESS_EQ edge_h current_h UpdateEdgeR
SUB edge_h current_h current_h
ADD w_temp current_h w_temp
IF_EQ _ _ SearchR2L
label UpdateEdgeR
ADDi current_h 0 edge_h
ADDii WATER_ADDRESS 0 RAM
LOAD _ _ water
ADD water w_temp water
SAVE water _ _
ADDii 0 0 w_temp
IF_GT_EQ edge_h max_h OutputResult
IF_EQ _ _ SearchR2L
label OutputResult
ADDii WATER_ADDRESS 0 RAM
LOAD _ _ OUTPUT
IF_EQ _ _ main
# 入力をすべてRAMに保管する.
# REG0（破壊）
label save_values
XOR REG0 REG0 REG0 # カウンターをゼロクリア.
label save_values_loop
IF_GT_EQi REG0 ROW_SIZE save_values_ret
ADDi REG0 0 RAM
SAVE INPUT _ _
ADDi REG0 1 REG0
IF_EQ _ _ save_values_loop
label save_values_ret
XOR REG0 REG0 REG0
XOR RAM RAM RAM
RET _ _ _
※プログラムサイズは208バイトでした。
3：テストする
テストにパスすると、ステージクリアになります。
最終ステージを終えたので、ゲーム自体をクリアしたことになります。
スタックを使用するプログラムにする【別解】
水の量をRAMの16番地に格納するのではなく、スタックに格納することにします。
水の量という1つの変数のみを保存しているため、スタックの贅沢な使い方かもしれません。
const ROW_SIZE 16
label main
CALL save_values _ _
const current REG0
const edge_h REG1
const current_h REG2
const w_temp REG3
const water REG2
const max_h REG4
XOR REG0 REG0 REG0
PUSH REG0 _ _ # 水の量をスタックに保存.0で初期化.
label LeftEdge
ADDi current 0 RAM
LOAD _ _ edge_h
label SearchL2R
ADDi current 1 current
IF_GT_EQi current ROW_SIZE RightEdge
ADDi current 0 RAM
LOAD _ _ current_h
IF_LESS_EQ edge_h current_h UpdateEdgeL
SUB edge_h current_h current_h
ADD w_temp current_h w_temp
IF_EQ _ _ SearchL2R
label UpdateEdgeL
ADDi current_h 0 edge_h
POP _ _ water
ADD water w_temp water
PUSH water _ _
ADDii 0 0 w_temp
IF_EQ _ _ SearchL2R
label RightEdge
ADDi edge_h 0 max_h
SUBii ROW_SIZE 1 current
ADDi current 0 RAM
LOAD _ _ edge_h
IF_GT_EQ edge_h max_h OutputResult
ADDii 0 0 w_temp
label SearchR2L
SUBi current 1 current
IF_LESSi current 0 OutputResult
ADDi current 0 RAM
LOAD _ _ current_h
IF_LESS_EQ edge_h current_h UpdateEdgeR
SUB edge_h current_h current_h
ADD w_temp current_h w_temp
IF_EQ _ _ SearchR2L
label UpdateEdgeR
ADDi current_h 0 edge_h
POP _ _ water
ADD water w_temp water
PUSH water _ _
ADDii 0 0 w_temp
IF_GT_EQ edge_h max_h OutputResult
IF_EQ _ _ SearchR2L
label OutputResult
POP _ _ OUTPUT
IF_EQ _ _ main
# 入力をすべてRAMに保管する.
# REG0（破壊）
label save_values
XOR REG0 REG0 REG0 # カウンターをゼロクリア.
label save_values_loop
IF_GT_EQi REG0 ROW_SIZE save_values_ret
ADDi REG0 0 RAM
SAVE INPUT _ _
ADDi REG0 1 REG0
IF_EQ _ _ save_values_loop
label save_values_ret
XOR REG0 REG0 REG0
XOR RAM RAM RAM
RET _ _ _
プログラムサイズは204バイトになりました。先ほどと比べて4バイト節約できました。
レジスターを追加した回路で解く【別解】
レジスターを1つ追加して、それをREG 6とします。
REG 5はRAMのアドレス用に使っているので、あえてREG 6としました。
参考にしたロジックは次のページになります。
https://gameah.fr/turing-complete-guide-de-solution-complete...
const ROW_SIZE 16
label main
CALL save_values _ _
# 初期準備.
XOR REG0 REG0 REG0
PUSH REG0 _ _ # 水の量を記憶.今は0.
ADDii 1 0 REG0 # REG0は左から見ていくインデックス.
XOR RAM RAM RAM
LOAD _ _ REG1 # REG1は左端の高さ.
ADDii 14 0 REG2 # REG2は右から見ていくインデックス.
ADDii ROW_SIZE-1 0 RAM
LOAD _ _ REG3 # REG3は右端の高さ.
label main_loop
IF_GT REG0 REG2 finish
ADDi REG0 0 RAM
LOAD _ _ REG4 # REG4は左側の高さ.
ADDi REG2 0 RAM
LOAD _ _ REG6 # REG6は右側の高さ.
IF_GT REG4 REG6 first
IF_LESS_EQ REG4 REG1 second
ADDi REG4 1 REG1 # REG1を上書き.
label second
SUB REG1 REG4 REG4
POP _ _ REG6
ADD REG6 REG4 REG6
PUSH REG6 _ _
ADDi REG0 1 REG0
IF_EQ REG0 REG0 main_loop
label first
IF_LESS_EQ REG6 REG3 third
ADDi REG6 0 REG3
label third
SUB REG3 REG6 REG6
POP _ _ REG4
ADD REG4 REG6 REG4
PUSH REG4 _ _
SUBi REG2 1 REG2
IF_EQ REG0 REG0 main_loop
label finish
POP 0 0 OUTPUT
IF_EQ REG0 REG0 main
# main処理終了.
# 入力をすべてRAMに保管する.
# REG0（破壊）
label save_values
XOR REG0 REG0 REG0 # カウンターをゼロクリア.
label save_values_loop
IF_GT_EQi REG0 ROW_SIZE save_values_ret
ADDi REG0 0 RAM
SAVE INPUT _ _
ADDi REG0 1 REG0
IF_EQ REG0 REG0 save_values_loop
label save_values_ret
XOR REG0 REG0 REG0
RET _ _ _
テストはまだ実施していません。
おわりに
お疲れ様でした。
これで全ステージをクリアしたことになります。
ただし、実績は残っています。余裕がある方は挑戦してみるとよいでしょう。
また、The Sandbox（トップのメニューからアクセスできる）にて自作の回路を作って遊ぶこともできます。