「ヒューマン・リソース・マシーン」YEAR 21 ~ YEAR 30 の考え方と解答例(サイズ、スピード目標達成)。 ネタバレになるので、解答例は折りたたんでいます。
YEAR 21 ゼロが区切り
課題が少々分かりにくい。
0 が連続して現れたときには、0 個の数値のグループ(空のグループ)が存在することに注意。
例えば、左のレーンから 1、2、0、0 の順でデータが流れてきたとき、1、2 のグループの和と、一個目とニ個目の 0 の間に存在する空のグループの和(すなわち 0)の二つのデータを右のレーンにわたす必要がある。
このように、課題の解答が分かりにくい場合には上司の解答例が参考になるので、どの課題でも一度は目を通しておくと良い。
効率化目標を達成するためには、空のグループの処理がポイント。
サイズ目標を達成するためには、空のグループとそれ以外のグループの処理をできるだけまとめる必要がある。
そのためには、各グループの和を計算する前に、和の値を 0 で初期化すると良い。
スピード目標を達成するためには、空のグループとそれ以外のグループの処理を場合分けして、余分な命令の実行を削る必要がある。
空のグループであると分かった時点で、右のレーンに 0 を渡せば良い。
▼ 解答
// サイズ目標達成 1: jump // (2) へジャンプ (1) 2: copyfrom sum 3: outbox (2) 4: copyfrom 5 5: copyto sum (3) 6: inbox 7: jump if zero // (1) へジャンプ 8: add sum 9: copyto sum 10: jump // (3) へジャンプ
サイズ:10 行(目標 10 行)、スピード:88 ステップ(目標 72 ステップ)
// スピード目標達成 1: jump // (2) へジャンプ (1) 2: copyfrom sum 3: outbox (2) 4: inbox 5: copyto sum 6: jump if zero // (1) へジャンプ (3) 7: inbox 8: jump if zero // (1) へジャンプ 9: add sum 10: copyto sum 11: jump // (3) へジャンプ
サイズ:11 行(目標 10 行)、スピード:72 ステップ(目標 72 ステップ)
YEAR 22 フィボナッチ数列
フィボナッチ数列は、f(0) = 1、f(1) = 1 としたとき、f(n+2) = f(n+1) + f(n)(n は自然数)を満たす数列。
フィボナッチ数列を計算し、右のレーンに渡すためには、最低限 f(n)、f(n+1) をカーペット上に残しておけば良い。
効率化目標を達成するためには、これまで使ったテクニックを駆使すれば OK。
強いてポイントを挙げるのなら、スピード目標の達成のためには f(0) と f(1) 以降の処理を場合分けすると良い。
▼ 解答
// サイズ目標達成 1: bump+ 9 (1) 2: copyfrom 9 3: copyto prev 4: copyto next 5: inbox 6: copyto thr (2) 7: sub prev 8: jump if neg // (1) へジャンプ 9: copyfrom prev 10: copyto tmp 11: outbox 12: copyfrom next 13: copyto prev 14: add tmp 15: copyto next 16: copyfrom thr 17: jump // (2) へジャンプ
サイズ:17 行(目標 19 行)、スピード:158 ステップ(目標 156 ステップ)
// スピード目標達成 1: bump+ 9 (1) 2: copyfrom 9 3: copyto prev 4: copyto next 5: inbox 6: copyto thr 7: copyfrom prev 8: outbox (2) 9: copyfrom thr 10: sub next 11: jump if neg // (1) へジャンプ 12: copyfrom next 13: copyto tmp 14: outbox 15: copyfrom tmp 16: add prev 17: copyto next 18: copyfrom tmp 19: copyto prev 20: jump // (2) へジャンプ
サイズ:20 行(目標 19 行)、スピード:152 ステップ(目標 156 ステップ)
サイズもスピードも、もっと詰められそうな気がします。
YEAR 23 一番小さいのは?
最も小さい数字がどれか確認するため、最初の数字をカーペット上に保管。 新しい数字を左側のレーンから受け取ったときに、カーペット上の数字と比較を行い、新しい数字の方が小さければカーペット上の数字を上書きをする。 左側のレーンから受け取った数字が 0 となるまでこれを繰り返し、最終的にカーペット上に保管されている数字を右側のレーンに渡す。
▼ 解答
1: jump // (2) へジャンプ (1) 2: copy from min 3: outbox (2) 4: inbox 5: copyto min (3) 6: inbox 7: jump if zero // (1) へジャンプ 8: sub min 9: jump if neg // (4) へジャンプ 10: jump // (3) へジャンプ (4) 11: add min 12: copyto min 13: jump // (3) へジャンプ
サイズ:13 行(目標 13 行)、スピード:73 ステップ(目標 73 ステップ)
YEAR 24 あまりはいくつ?
A を B で割った余り C は、A から B を 0 より小さくならないように繰り返し引いていくことで求められる。 実際には、0 以下にならないように引くのは無理なので、A から B を繰り返し引いていって、0 より小さくなった時点で B を一度だけ足す。
▼ 解答
1: jump // (2) へジャンプ (1) 2: add B 3: outbox (2) 4: inbox 5: copyto A 6: inbox 7: copyto B 8: copyfrom A (3) 9: sub B 10: jump if neg // (1) へ移動 11: jump // (3) へ移動
サイズ:11行(目標 12 行)、スピード:50 ステップ(目標 57 ステップ)
YEAR 25 ゼロまで足して
左側のレーンから受け取った数字をカーペット上に保存し、bump- 命令で 1 ずつ数字を減らしながら足していく。
▼ 解答
1: jump // (x) へジャンプ (1) 2: copyfrom sum (2) 3: outbox (3) 4: inbox 5: jump if zero // (2) へジャンプ 6: copyto tmp 7: copyto sum (4) 8: bump- tmp 9: jump if zero // (1) へジャンプ 10: add sum 11: copyto sum 12: jump // (4) へジャンプ
サイズ:12 行(目標 12 行)、スピード:79 ステップ(目標 82 ステップ)
YEAR 26 割り算のしかた
YEAR 24 の応用。 A から B を 0 より小さくならないように繰り返し引いていきながら、引いた回数を数える。
▼ 解答
1: jump // (2) へジャンプ (1) 2: copyfrom ans 3: outbox (2) 4: inbox 5: copyto A 6: inbox 7: copyto B 8: copyfrom 9 9: copyto ans (3) 10: copyfrom A 11: sub B 12: jump if neg // (1) へジャンプ 13: copyto A 14: bump+ ans 15: jump // (3) へジャンプ
サイズ:15 行(目標 15 行)、スピード:71 ステップ(目標 76 ステップ)
YEAR 28 小から大へ
単純にクリアするだけならば、左側のレーンから受け取った 3 つの数字をカーペット a, b, c 上に保管し、a>b>c となるようにバブルソートで並べ替え、c, b, a の順で右側のレーンに渡す。
サイズ目標をクリアする場合には、はじめの 2 つの数字を a>b となるようにカーペット上に配置し、3 つ目の数字と a, b との大小関係によってどの順番で右側のレーンに渡すか場合分けを行う(バブルソートによる並び替えの回数を減らしつつ、a が必ず b より後に右のレーンに渡されることが確定しているため、コードの圧縮が可能)。
スピード目標をクリアする場合には、3 つの数字を左のレーンから受け取った順にカーペット a, b, c 上に配置し、それぞれの数字の大小を比較して a, b, c をどの順番で右側のレーンに渡すか一つ一つ場合分けを行う(カーペット上での並び替えなどは一切しない)。
▼ 解答
// サイズ目標達成 1: jump // (3) へジャンプ (1) 2: add b 3: outbox (2) 4: copyfrom b 5: outbox 6: copyfrom a 7: outbox (3) 8: inbox 9: copyto a 10: inbox 11: copyto tmp 12: copyto b 13: sub a 14: jump if neg // (4) へジャンプ 15: copyfrom a 16: copyto b 17: copyfrom tmp 18: copyto a (4) 19: inbox 20: sub b 21: jump if neg // (1) へジャンプ 22: add b 23: copyto tmp 24: copyfrom b 25: outbox 26: copyfrom tmp 27: copyto b 28: sub a 29: jump if neg // (2) へジャンプ 30: copyfrom a 31: outbox 32: copyfrom b 33: outbox 34: jump // (3) へジャンプ
サイズ:34 行(目標 34 行)、スピード:89 ステップ(目標 78 ステップ)
// スピード目標達成 (1) 1: inbox 2: copyto a 3: inbox 4: copyto b 5: sub a 6: jump if neg // (4) へジャンプ // b>=a の場合 7: inbox 8: copyto c 9: sub b 10: jump if neg // (2) へジャンプ // c>=b>a の場合 11: copyfrom a 12: outbox 13: copyfrom b 14: outbox 15: copyfrom c 16: outbox 17: jump // (1) へジャンプ // b>=a, b>c へジャンプ (2) 18: copyfrom c 19: sub a 20: jump if neg // (3) へジャンプ // b>c>=a の場合 21: copyfrom a 22: outbox 23: copyfrom c 24: outbox 25: copyfrom b 26: outbox 27: jump // (1) へジャンプ // b>=a>c の場合 (3) 28: copyfrom c 29: outbox 30: copyfrom a 31: outbox 32: copyfrom b 33: outbox 34: jump // (1) へジャンプ // a>b の場合 (4) 35: inbox 36: copyto c 37: sub b 38: jump if neg // (6) へジャンプ // a>b, c>=b の場合 39: copyfrom b 40: outbox 41: copyfrom c 42: sub a 43: jump if neg // (5) へジャンプ // c>=a>b の場合 44: copyfrom a 45: outbox 46: copyfrom c 47: outbox 48: jump // (1) へジャンプ // a>c>=b の場合 (5) 49: copyfrom c 50: outbox 51: copyfrom a 52: outbox 53: jump // (1) へジャンプ // a>B>c の場合 (6) 54: copyfrom c 55: outbox 56: copyfrom b 57: outbox 58: copyfrom a 59: outbox 60: jump // (1) へジャンプ
サイズ:60 行(目標 34 行)、スピード:72 ステップ(目標 78 ステップ)
YEAR 29 間接的な指定
アドレス(参照すべきカーペットの番号)を用いた処理。
▼ 解答
(1) 1: inbox 2: copyto adr 3: copyfrom [adr] 4: outbox 5: jump // (1) へジャンプ
サイズ:5 行(目標 5 行)、スピード:25 ステップ(目標 25 ステップ)
YEAR 30 隠された暗号
YEAR 30 の応用。 左側から受け取った数字(参照すべきカーペットの番号)をカーペット上に保管し、1 ずつ加算しながら目的の文字をコピーし右側のレーンに渡す。
▼ 解答
(1) 1: inbox 2: copyto adr (2) 3: copyfrom [adr] 4: jump if zero // (1) へジャンプ 5: outbox 6: bump+ adr 7: jump // (2) へ移動
サイズ:7 行(目標 7 行)、スピード:203 ステップ(目標 203 ステップ)