ヒューマン・リソース・マシーン攻略入社28年目小から大へ

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

課題

左側の数値3つごとに対して、小さい順に並べ替え、右側へ運んでください。

使用可能な命令

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

効率目標

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

ヒント

その1

ただ愚直に場合分けをすればよい。

その2(サイズ目標)

最初の1回分を並び変えて共通化するだけで、場合分けが1ケース分削れる。

その3(サイズ目標)

Aを初めから2箇所に設定しておくと並び替え用に一時保持する必要がなくなる。

回答例 + 解説

スピード

回答例 + 解説

1. jump：ラベル1へ
ラベル2：// 手元のパネルを運んでからAを右に運ぶ
2. outbox
3. copyfrom A
ラベル3:// 右に運ぶ
4. outbox
ラベル1：// 1セットの開始位置
5. inbox
6. copyto A
7. inbox
8. copyto B
9. sub A
10. jump_if_neg：ラベル4へ
// A < B
11. inbox
12. copyto C
13. sub A
14. jump_if_neg：ラベル5へ
// Aが最小
15. copyfrom A
16. outbox
17. copyfrom C
18. sub B
19. jump_if_neg：ラベル6へ
// A < B < C
20. copyfrom B
21. outbox
22. copyfrom C
23. jump：ラベル3へ
ラベル6：// A < C < B
24. copyfrom C
25. outbox
26. copyfrom B
27. jump：ラベル3へ
ラベル5：// C < A < B
28. copyfrom C
29. outbox
30. copyfrom A
31. outbox
32. copyfrom B
33. jump：ラベル3へ
ラベル4：// B < A
34. inbox
35. copyto C
36. sub B
37. jump_if_neg：ラベル7へ
// Bが最小
38. copyfrom B
39. outbox
40. copyfrom C
41. sub A
42. jump_if_neg：ラベル8へ
// B < A < C
43. copyfrom A
44. outbox
45. copyfrom C
46. jump：ラベル3へ
ラベル8：// B < C < A
47. copyfrom C
48. jump：ラベル2へ
ラベル7：// C < B < A
49. copyfrom C
50. outbox
51. copyfrom B
52. jump：ラベル2へ

ただただ愚直に場合分けして組むだけ。

左のパネルを取って(inbox)、Aとして保持(copyto)
次のパネルを取って(inbox)、Bとして保持(copyto)
AとBを比較(sub)して、Aの方が大きければ(jump_if_neg)B < Aへ
そうじゃなければA < Bへ * A < B 次のパネルを取って(inbox)、Cとして保持(copyto) AとCを比較(sub)して、Aの方が大きければ(jump_if_neg)、C < A < Bが確定なので、その順番で運ぶ(copyfrom -> outbox)
そうじゃなければ、Aが最小であることは確定なので、まずA(copyfrom)を運ぶ(outbox)
その後、BとCを比較してBの方が大きければ(jump_if_neg)、C < B、そうじゃなければB < Cで確定なので、それぞれその順番で運ぶ(copyfrom -> outbox)
* B < A 上記[A < B]のAとBを入れ替えて同じ処理を実施

上記例はサイズ目標を見越して同じ処理は極力まとめてしまっているから分かり難いかも。。

サイズ

回答例 + 解説

1. jump：ラベル1へ
ラベル2：// 手元のパネルを運んでからBを右に運ぶ
2. outbox
3. copyfrom B
ラベル3:// 右に運ぶ
4. outbox
ラベル1：// 1セットの開始位置
5. inbox
6. copyto A
7. copyto B
8. inbox
9. sub A
10. jump_if_neg：ラベル4へ
// A < B
11. add A
12. copyto B
13. jump：ラベル4へ
14. add A
15. copyto A
ラベル4：AとCの比較
16. inbox
17. copyto C
18. sub A
19. jump_if_neg：ラベル5へ
// Aが最小
20. copyfrom A
21. outbox
22. copyfrom C
23. sub B
24. jump_if_neg：ラベル6へ
// A < B < C
25. copyfrom B
26. outbox
27. copyfrom C
28. jump：ラベル3へ
ラベル6：// A < C < B
29. copyfrom C
30. jump：ラベル2へ
ラベル5：// C < A < B
31. copyfrom C
32. outbox
33. copyfrom A
34. jump：ラベル2へ

上記解法でスピード目標を満たしている前提。
最初の1回分を並び替えて共通化することで、B < Aの場合分けをごっそり削除。
この時、Aを2箇所に設定しておくことで、いざB < Aとなったときに並び替え用に一時領域にAを保持。といったことをする必要がなくなる。

また、A < Bの形に整形することに伴って、処理最初の方で、inboxに繋げるoutboxに不随するcopyfromはBに変更。
※A < Bの形に整形した場合、パターンとしてC < A < B / A < C < B / A < B < Cの3パターンのみとなり、最終項がBになるケースが最多となるため

左のパネルを取って(inbox)、AとBに保持(copyto) 次のパネルを取って(inbox)、前に取ったパネルと比較(sub)し、前のパネルの方が大きければ(jump_if_neg)、Aとして保持(copyto)
そうじゃなければBとして保持(copyto)する。
この時、手元のパネル自体は計算結果となっているため、減算していた値を加算(add)することで元の値を復元してから保持する。

あとは上記スピード目標のA < Bのケースと同様