「ヒューマン・リソース・マシーン」YEAR 11 ~ YEAR 20 の考え方と解答例(サイズ、スピード目標達成)。 ネタバレになるので、解答例は折りたたんでいます。
YEAR 11 引き算の結果
▼ 解答
(1) 1: inbox 2: copyto 0 3: inbox 4: copyto 1 5: sub 0 6: outbox 7: copyfrom 0 8: sub 1 9: outbox 10: jump // (1) へジャンプ
サイズ:10 行(目標 10 行)、スピード:40 ステップ(目標 40 ステップ)
YEAR 12 40 の作り方
YEAR 10 の応用。40 = 8 + 32 = 23 + 25 であることに注意。
▼ 解答
(1) 1: inbox // 左のレーンからデータ x を取得 2: copyto 0 3: add 0 4: copyto 0 5: add 0 6: copyto 0 7: add 0 8: copyto 0 // 8x を計算し、パネル 0 に一時保存 (a) 9: add 0 10: copyto 1 // 16x を計算し、パネル 1 に保存 (b) 11: add 0 // (a) + (b) で 24x を計算 (c) 12: add 1 // (b) + (c) で 40x を計算 13: outbox 14: jump // (1) へジャンプ
サイズ:14 行(目標 14 行)、スピード:56 ステップ(目標 56 ステップ)
40 = 23 + 25 なので、まず元のデータ x から 8x を計算して一時保存。 8x から 16x を計算して一時保存。 8x + (16x + 16x) = (23 + 25)x = 40x で目的の値を取得。
YEAR 13 同じかどうか
サイズ、スピード目標達成を目指す場合、YEAR 9 と同様に命令の順番を工夫して jump 命令の記述、実行回数を減らす必要がある。
▼ 解答
1: jump // (2) へジャンプ (1) 2: copyfrom 0 3: outbox (2) 4: inbox 5: copyto 0 6: inbox 7: sub 0 8: jump if zero // (1) へジャンプ 9: jump // (2) へジャンプ
サイズ:9 行(目標 9 行)、スピード:27 ステップ(目標 27 ステップ)
YEAR 14 大は小を兼ねる
クリア自体は難しくないが、素直にコードを組むとおそらく効率化目標が達成できない。
この課題の場合、一つの outbox 命令に対して copyto 命令が一つに抑えられる。つまり、A、B という二つのデータを比較して大きい方を右のレーンに渡すときに、A、B の両方をパネル上に残しておく必要がない。A と (B - A) の二つのデータがあれば、B は (B - A) + A で得られることに注意する。
▼ 解答
1: jump // (3) へジャンプ (1) 2: copyfrom 0 (2) 3: outbox (3) 4: inbox 5: copyto 0 6: inbox 7: sub 0 8: jump if neg // (1) へジャンプ 9: add 0 10: jump // (2) へジャンプ
サイズ:10 行(目標 10 行)、スピード:31 ステップ(目標 34 ステップ)
左のレーンから受け取る二つのデータを順番に A、B としする。 パネル上には、最初に受け取った A のみコピーし、B を受け取ったらそのまま A を引いて (B - A) を取得。 (B - A) が負、つまり B の方が大きい場合には、手元の (B - A) にパネル上の A を足して B を取得し、右のレーンに渡す。 (B - A) が 0 以上、つまり A が B 以上の場合には、パネル上の A を取得し、右のレーンに渡す。
YEAR 16 必ずポジティブに
- A から A を取得したい場合、- A から - A を二回引けば良い。- A - (- A) - (- A) = A である。
▼ 解答
1: jump // (3) へジャンプ (1) 2: copyto 0 3: sub 0 4: sub 0 (2) 5: outbox (3) 6: inbox 7: jump if neg // (1) へジャンプ 8: jump // (2) へジャンプ
サイズ:8 行(目標 8 行)、スピード:34 ステップ(目標 36 ステップ)
YEAR 17 同じならゼロ
1 個目のデータが負である場合、負でない場合で場合分けをする。
効率化目標を達成するためには、ジャンプの回数をできるだけ減らすことが重要(YEAR 9 や YEAR 13 と考え方は同じ)。
▼ 解答
1: jump // (4) へジャンプ // 2 個目のデータの処理(1 個目のデータが負の場合) (1) 2: inbox 3: jump if neg // (5) へジャンプ // 2 個のデータの符号が異なる場合 (2) 4: copyfrom 5 // 右のレーンへのデータの受け渡し (3) 5: outbox // 1 個目のデータの処理 (4) 6: inbox 7: jump if neg // (1) へジャンプ // 2 個目のデータの処理(1 個目のデータが負でない場合) 8: inbox 9: jump if neg // (2) へジャンプ // 2 個のデータの符号が等しい場合 (5) 10: copyfrom 4 11: jump // (3) へジャンプ
サイズ:11 行(目標 12 行)、スピード:27 ステップ(目標 28 ステップ)
YEAR 19 カウントダウン
課題のクリア自体は難しくないが、効率化目標を達成するためには少し工夫が必要。
サイズ目標を達成するためには、できるだけ同じ処理をまとめる。スピード目標を達成するためには、カウントダウンの終了時の処理(0 を右のレーンに渡す際の処理)を工夫して、できるだけ実行命令数を減らす。
サイズ目標とスピード目標を同時に達成するのは難しい(適切な解答を見つけられず)。
▼ 解答
// サイズ目標達成 (1) 1: inbox 2: copyto 0 (2) 3: outbox 4: copyfrom 0 5: jump if zero // (1) へジャンプ 6: jump if neg // (3) へジャンプ 7: bump- 0 8: jump // (2) へジャンプ (3) 9: bump+ 0 10: jump // (2) へジャンプ
サイズ:10 行(目標 10 行)、スピード:114 ステップ(目標 82 ステップ)
// スピード目標達成 1: jump // (2) へジャンプ (1) 2: outbox 3: bump+ 0 4: jump if neg // (1) へジャンプ 5: outbox (2) 6: inbox 7: copyto 0 8: jump if neg // (1) へジャンプ (3) 9: outbox 10: bump- 0 11: jump if neg // (2) へジャンプ 12: jump // (3) へジャンプ
サイズ:12 行(目標 10 行)、スピード:77 ステップ(目標 82 ステップ)
YEAR 20 掛け算のしかた
左のレーンから x、y の二つのデータを受け取ったとき、y を x 個だけ足し合わせた(加算した)値 z を右のレーンに渡せば良い。
サイズ目標を達成するのは比較的簡単。できるだけ同じ処理をまとめて記述すれば良い。
スピード目標を達成するには、大きく二つの工夫が必要。一つ目は掛け算のための加算の回数を減らすこと。x、y が異なる値ならば、y を x 個分加算するとき、y > x の場合の方が x > y の場合よりも加算の回数が少なくて済む。二つ目は x、y が 0 だった場合の処理を工夫すること。x、y の片方でも 0 であれば掛け算の結果は 0 となるので、最低限の処理以外を削ることで実行ステップ数を減らすことができる。
▼ 解答
// サイズ目標達成 1: jump // (3) へジャンプ (1) 2: copyfrom z (2) 3: outbox (3) 4: inbox 5: copyto x 6: inbox 7: copyto y (4) 8: copyto z 9: copyfrom x 10: jump if zero // (2) へジャンプ 11: bump- x 12: jump if zero // (1) へジャンプ 13: copyfrom z 14: add y 15: jump // (4) へジャンプ
サイズ:15 行(目標 15 行)、スピード:182 ステップ(目標 109 ステップ)
// スピード目標達成 1: jump // (4) へジャンプ // 1 個目のデータが 0 の場合の処理 (1) 2: inbox 3: copyfrom 9 4: outbox 5: jump // (4) へジャンプ // 掛け算の結果を右のレーンに渡す (2) 6: copyfrom z (3) 7: outbox // 左のレーンからのデータの受け取り (4) 8: inbox 9: jump if zero // (1) へジャンプ 10: copyto y 11: inbox 12: jump if zero // (3) へジャンプ 13: copyto x 14: sub y 15: jump if neg // (5) へジャンプ // x < y となるよう入れ替え(x > y であった場合) 16: copyfrom x 17: copyto tmp 18: copyfrom y 19: copyto x 20: copyfrom tmp 21: copyto y // 掛け算の処理 (5) 22: copyfrom y (6) 23: copyto z 24: bump- x 25: jump if zero // (2) へジャンプ 26: copyfrom z 27: add y 28: jump // (6) へジャンプ
サイズ:28 行(目標 15 行)、スピード:108 ステップ(目標 109 ステップ)