Delicious Order【Turing Complete編】

2023年9月12日

1 はじめに
2 Delicious Orderステージ
3 Delicious Orderステージを解く

はじめに

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

FIRE生活中のIPUSIRONです😀

IPUSIRONのプロフィールを見る

Delicious Orderステージ

Delicious Orderステージのゴールは、15個の数列をソートすることです。

クルーたちは銀河の食べ物百科事典を更新しており、人間の食べ物を追加しようとしています。アルファベットがないため、百科事典の項目はおいしさのスコア順に並べられています。

本ステージでは、15個のおいしさスコアが順に与えられます。これらを昇順ソート（小さい値から大きい値へと並べること）して、順に出力しなければなりません。

Level screenには、おいしさスコアが振られた料理が並んでいます。これらをソートするわけです。

Delicious Orderステージを解く

1：プログラムの設計方針を決める

プログラムはざっくりと次の流れになります。

①15回連続で入力を読み込み、それらをRAMに登録する。

②ソートアルゴリズムを使って、RAM内の15個の数を並び替える。ソートアルゴリズムはもっともシンプルなバブルソートを採用する。

③ソートが終わったら、RAMから1つずつ、計15個を出力する。

2：入力処理と出力処理を実装する

const MAX_ITEMS 15

label main
CALL SaveValues _ _
# TODO ソート処理.
CALL LoadValues _ _
# メイン処理終了.

# 入力を次々にRAMに保存する.
label SaveValues
XOR RAM RAM RAM
label save
IF_GT_EQi RAM MAX_ITEMS exit_save 
SAVE INPUT _ _
ADDi RAM 1 RAM
IF_EQ REG0 REG0 save # 強制ジャンプ.
label exit_save
RET _ _ _

# RAM内のデータを次々に出力する.
label LoadValues
XOR RAM RAM RAM
label load
IF_GT_EQi RAM MAX_ITEMS exit_load 
LOAD _ _ OUTPUT
ADDi RAM 1 RAM
IF_EQ REG0 REG0 load # 強制ジャンプ.
label exit_load
RET _ _ _

この時点でテストして、RAMコンポーネントに15個のデータが登録するのを確認します。ただし、出力の段階でテストはエラーになります（これは想定済み）。期待通りにRAMに格納されたら、少なくともSaveValuesサブルーチンに関しては正常に動作すると判断できます。

3：バブルソートの処理を組み込む

配列上でのソートであれば実装は楽ですが、今回はRAM上でのソートになります。RAMから隣接するペアを取り出して、必要があればスワップして保存し直します。次は隣のペアでも同一の操作を実施します。これを繰り返していきます。

const MAX_ITEMS 15
const INDEX REG0
const SORTED_INDEX REG1

label main
CALL SaveValues _ _
CALL Sort _ _
CALL LoadValues _ _
# メイン処理終了.

# 入力を次々にRAMに保存する.
label SaveValues
XOR RAM RAM RAM
label save
IF_GT_EQi RAM MAX_ITEMS exit_save 
SAVE INPUT _ _
ADDi RAM 1 RAM
IF_EQ REG0 REG0 save # 強制ジャンプ.
label exit_save
RET _ _ _

# 昇順ソートする.
label Sort
SUBii MAX_ITEMS 1 SORTED_INDEX
label sort_main
IF_EQi SORTED_INDEX 0 ret
IF_GT_EQ INDEX SORTED_INDEX end_1loop
ADDi INDEX 0 RAM
LOAD _ _ REG2
ADDi INDEX 1 RAM
LOAD _ _ REG3
IF_LESS REG2 REG3 next
# スワップして格納し直す.
SAVE REG2 _ _ # インデックス大のほう.
SUBi RAM 1 RAM
SAVE REG3 _ _ # インデックス小のほう.
label next
ADDi INDEX 1 INDEX
IF_EQ REG0 REG0 sort_main # 強制ジャンプ.
label end_1loop
XOR INDEX INDEX INDEX # インデックスの初期化.
SUBi SORTED_INDEX 1 SORTED_INDEX
IF_EQ REG0 REG0 sort_main # 強制ジャンプ.
label ret
RET _ _ _

# RAM内のデータを次々に出力する.
label LoadValues
XOR RAM RAM RAM
label load
IF_GT_EQi RAM MAX_ITEMS exit_load 
LOAD _ _ OUTPUT
ADDi RAM 1 RAM
IF_EQ REG0 REG0 load # 強制ジャンプ.
label exit_load
RET _ _ _