当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

Delicious Order【Turing Complete編】

はじめに

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

コースト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サブルーチンに関しては正常に動作すると判断できます。

入力データとRAM内データを比べると完全に一致する

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 _ _ _

4:テストする

[Run]ボタンを押してテストします。RAMコンポーネント内のデータが徐々にソートされていく様子を観察できるはずです。

入力される数列のパターンにもよりますが、1つのテストパターンを終えるまでに結構な時間がかかります。

テストパターンは全部で32個あります。1つ目のテストをパスできれば、ロジック的におそらく問題なさそうと判断できます。[Run faster]ボタンを押して早送りでテストしてもよいでしょう。

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