ヒューマン・リソース・マシーン攻略入社41年目並べ替えよ

ついに最後の問題。後半は解説が適当になってきてた感があるので、質問があればお気軽にどうぞ(即答できるとは言っていない)

ここで解説している内容なりヒントなりはあくまで筆者の解法に基づいたものなので、別の考え方ももちろんあるよ。ってのは念頭に置いてください。

課題

0を終端とした文字列がいくつか流れてきます。
各文字列に対してソート(並べ替え)を行い、小さい順(昇順)に右側へ運んでください。

使用可能な命令

inbox
outbox
copyfrom
copyto
add
sub
bump+
bump-
jump
jump_if_zero
jump_if_neg

効率目標

サイズ：34行
スピード：714ステップ

ヒント

その1

全然ヒントになっていないけど、サイズ/スピードを気にしなければ、これまでの仕事を思い出せば出来るはず。
まずは思う通りにやってみよう。

その2

ソートの世界はアルゴリズムと呼ばれる手法が既にいっぱい確立されている。
「ソートアルゴリズム」でどんなアルゴリズムがあるか調べてみよう

その3

気に入ったアルゴリズムをこのゲームの命令に置き換えてみよう。
ただ、再帰系は基本無理なので、再帰系じゃないアルゴリズムを選択しよう。

回答例 + 解説

サイズ + スピード

回答例 + 解説

ラベル1：// 1セットの開始位置
1. copyfrom 24
2. copyto cnt
ラベル2：// パネルをカーペットに配置
3. inbox
4. jump_if_zero：ラベル3へ
5. copyto [cnt]
6. bump+ cnt
7. jump：ラベル2へ
ラベル3：// ソート開始
8. copyto minIdx // この時点では必ず手元が0になっているためそれを利用して初期化
ラベル4：// 初期化
9. copyto min
10. copyto i
11. bump+ i // 同じ位置で比較を行っても無駄なので、最小値(=min)の次から開始
12. sub cnt
13. jump_if_zero：ラベル5へ
ラベル6：// 最小値の判定
14. copyfrom [min]
15. sub [i]
16. jump_if_neg：ラベル7へ
// 最小値を更新
17. copyfrom i
18. copyto min
ラベル7：参照位置を更新
19. bump+ i
20. sub cnt
21. jump_if_neg：ラベル6
// 最小値を運ぶ
22. copyfrom [min]
23. outbox
24. copyfrom [minIdx]
25. copyto [min]
26. bump+ minIdx
27. jump：ラベル4へ
ラベル5：最終要素を運ぶ
28. copyfrom [minIdx]
29. outbox
30. jump：ラベル1へ

選択ソートを採用。
ただし最小値はカーペットには並べずに直接右側へ運ぶ

初期化用に0を取得(copyfrom 24)して、参照カウンタ(=cnt)を初期化(copyto)
まずは単語をカーペット上に並べる(inbox ~ jump)
並べ終わった(jump_if_zero)ら、最小値の格納予定位置(=minI),最小値(=min),参照位置(=i)を初期化(copyto)
この時、参照位置は最小値との比較に使用するため、最小値の次(bump+)から開始する。
最小値(copyfrom [min])と参照位置の値を比較(sub [i])し、参照位置の値の方が小さい場合は最小値を更新(copyfrom i -> copyto min)してから、参照位置の値の方が大きい(jump_if_neg)場合は、そのまま参照位置を更新(bump+ i)し、終端を参照するまで比較を繰り返す(sub cnt -> jump_if_neg)
終端まで比較が終わったら、最小値(copyfrom)を右側へ運び、最小値を格納する予定だった位置の値(copyfrom [minI])を最小値が格納されていた位置に移動(copyto [min])し
最小値を格納する位置を更新(bump+)した上で、終端に格納する値が確定する(bump+ i -> sub cnt -> jump_if_zero)まで処理を繰り返す(jump)
終端に格納する値が確定した場合は、それ(copyfrom [minIdx])を右側へ運び(outbox)、次の単語へ(jump)