炬燵の中でゲーム三昧

ゲームのプレイ雑記やあれこれ

ヒューマン・リソース・マシーン 攻略メモ#3 効率化目標達成(YEAR 21 ~ YEAR 30)

 「ヒューマン・リソース・マシーン」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 ステップ)