ヒューマン・リソース・マシーン攻略入社40年目素因数に分解せよ

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

課題

左側のパネルの数値に対し、素因数分解を行い、答えを右側に運んで下さい。
答えは昇順、すなわち小さい順に運んで下さい。

使用可能な命令

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

効率目標

サイズ：28行
スピード：399ステップ

ヒント

その1

試しに割ってみて、割り切れたら因数
2から順番にやることで必然的に素因数になる
※これは試し割り法というアルゴリズム(手法)

その2(スピード目標)

2以外の偶数を試し割するのは無駄

その3(スピード目標)

試し割る数字を2(初項)の次だけ+1、それ以降は+2していけば偶数は飛ばせる

その4(スピード目標)

今回は最初だけ、+1したくない状況。このゲームでは条件ジャンプが0とマイナスなので、最初だけ0かマイナスになるような判定値を用意すれば良い

回答例 + 解説

サイズ

回答例 + 解説

ラベル1：// 1セットの開始位置
1. copyfrom 24
2. copyto B
3. bump+ B
4. bump+ B
5. inbox
ラベル3：// Aを更新
6. copyto A
ラベル4：// 試し割り開始
7. copyfrom 24
8. copyto cnt
9. copyfrom A
ラベル5：// 割り算
10. sub B
11. jump_if_zero：ラべル2へ
12. jump_if_neg：ラベル6へ
// 商を更新して割り算を継続
13. copyto temp
14. bump+ cnt
15. copyfrom temp
16. jump：ラベル5へ
ラベル6：// Bを更新して試し割りを継続
17. bump+ B
18. jump：ラベル4へ
ラベル2：// 因数を運ぶ
19. copyfrom B
20. outbox
21. copyfrom cnt
22. jump_if_zero：ラベル1へ
// Aを更新して試し割りを継続
23. bump+ cnt // 余りに対する判定を行ってからcntを更新するため、この時点ではcnt=商-1なので+1してからAを更新する
24. jump：ラベル3へ

2から順番に試しに割ってみて、割り切れたら素因数として運ぶ。これを割れなくなるまで繰り返す。 ※試し割り法というアルゴリズム(手法)

初期化用に0を取得(copyfrom 24)し、一旦割る数(=B)として設定(copyto)。
割る数の初項は2のため2になるまで加算(bump+)

左のパネルを拾って(inbox)、割られる数(=A)として設定(copyto)
0を拾って(copyfrom)、商用のカウンタ(=cnt)を初期化(copyto)
割れなくなる(jump_if_zero|jump_if_neg)まで割り算を繰り返す(sub B ~ jump)
この時、割り切れなかった場合は割る数だけ更新する必要があるため、Aとは別に計算過程用のカーペット(temp)を用意して、計算過程についてはそちらに保持(copyto)する

割り切れた(jump_if_zero)場合 Bを因数として運ぶ(copyfrom -> outbox)。cntが0なら(jump_if_zero)割り算を終了し次のパネルへ
0じゃないならば、cntを+1(bump+)してAを更新(copyto)し、同じBで再度試し割りを行う(jump)
割り切れなかった(jump_if_neg)場合 Bを更新(bump+)し、再度試し割りを行う(jump)

サイズ + スピード

回答例 + 解説

ラベル1：// 1セットの開始位置
1. copyfrom 24
2. copyto B
3. bump+ B
4. copyto flg // 手元に1がある状態なのでflgの初期設定に利用する
5. bump+ B
6. inbox
ラベル3：// Aを更新
7. copyto A
ラベル4：// 試し割り開始
8. copyfrom 24
0. copyto cnt
10. copyfrom A
ラベル5：// 割り算
11. sub B
12. jump_if_zero：ラべル2へ
13. jump_if_neg：ラベル6へ
// 商を更新して割り算を継続
14. copyto temp
15. bump+ cnt
16. copyfrom temp
17. jump：ラベル5へ
ラベル6：// Bを更新して試し割りを継続
18. bump- flg
19. jump_if_zero：ラベル7へ
// B+1
20. bump+ B
ラベル7：B+1
21. bump+ B
22. jump：ラベル4へ
ラベル2：// 因数を運ぶ
23. copyfrom B
24. outbox
25. copyfrom cnt
26. jump_if_zero：ラベル1へ
// Aを更新して試し割りを継続
27. bump+ cnt // 余りに対する判定を行ってからcntを更新するため、この時点ではcnt=商-1なので+1してからAを更新する
28. jump：ラベル3へ

サイズ目標を満たしている前提で、そこからの変更点を

素因数で考えると、2以外の偶数を試し割するのは無駄
試し割る数字を2(初項)の次だけ+1、それ以降は+2することで偶数の試し割りを飛ばす

そのため、Bを更新する際は基本的には+2になるようにbump+を2回実施するように変更する。ただし、初回だけは+1としたいため、bump+を1回分飛ばせるようにフラグ(flag)を用意し、初回分についてカバーする。
※今回のように特定の状況を示すための概念をフラグ(flag)と言う。特に覚える必要はない

フラグの考え方としては、「初期値=0として、jump_if_zeroで飛んだ先でbump+ flg」もしくは「初期値=1として、jump_if_zeroで飛ばなかったケースでbump- flg」と
ON/OFFで管理するのが正しい考え方だが、
サイズ/スピードの節約のため、値の取得/更新をまとめて実施出来る「初期値=1として、bump- flgしてからjump_if_zero」を採用
※なので厳密にはフラグとは違うけど、細かいことは気にしない。