ヒューマン・リソース・マシーン 入社41年目−並べ替えよ

目次

１）課題

０を終端とした文字列がいくつか流れてきます。各文字列に対してソート（並べ替え）を行い、小さい順（昇順）に右側へ運んでください。

２）状況の確認

この問題では, 予めコードが入っています. このコードを実行して, 何をするコードなのか確かめます. 

左のコンベアからパネルを取り出し, カーペットに配置しています. 終端を表す０を配置したところで終了しています. また, 使用したカーペットの最大値がカーペットの20番に記録してあります. 

３）考え方

カーペットに配置したパネルを小さい順に並べ替える方法を考えます. ここでは, 終端を表す０に近いカーペットから順に大きい数字のパネルを置くように考えていきます. アドレスの判定を簡単にするためです. 

ここで, 入社23年目の「一番小さいのは？」を振り返ります. この課題では, 一番小さいパネルを選びました. この課題を応用します. 

上の図では, カーペットの3番が０となっています. カーペットの2番に, 最大の数字を配置する方法を考えます. 

1. カーペットの2番をチャンピオンとします.
2. カーペットの1番をチャンピオンに挑ませます. 1番の方が大きければ, チャンピオンを交代します.
3. 同じようにしてカーペットの0番をチャンピオンに挑ませ, 大きければ交代します.

最大の数字が決まれば, カーペットの2番をチャンピオンとして同様に処理します. この操作を繰り返すことで, パネルを並び替えられます.

４）カーペットの名前

カーペットには, 並べ替えるパネル以外にも, 管理用のカーペットが必要です. 

次のように名前を付けました.

1. アドレス：処理中のカーペットを表します. チャンピオンを決定する時は, チャレンジャーの位置を表します.
2. チャンピオン：チャンピオンのいるカーペットの位置を表します.
3. SWAP：チャレンジャーが勝った場合, チャンピオンとチャレンジャーを入れ替えるために使います. 
4. ZERO：初期化用の０を置いておきます.

５）全体的な枠組み

カーペットの位置を示す「アドレス」と「チャンピオン」を書き換える処理を中心にコードを書いていきます.

8行目の時点で, 「アドレス」には終端を表す「0」を配置したカーペットの番号が入っています. 8行目から10行目で「チャンピオン」に反映します. 

11行目で, 「チャンピオン」が０になっているか判定しています. 「チャンピオン」が０なら, 並び替えが終わっているので, 運び出すだけです. 

12行目から「チャンピオン」の値を使って「アドレス」の値を「チャンピオン」の値－1としています. ここでの「アドレス」は「チャレンジャー」の意味です. 「アドレス（チャレンジャー）」がマイナスなら, 「チャンピオン」の防衛が決まったので, 10行目に戻り, 次の「チャンピオン」を決めます. 

15行目で「アドレス（チャレンジャー）」を取り出し, 「チャンピオン」に挑ませます. 

結果がマイナス, つまりチャンピオンの方が大きければ13行目に戻り, 次のチャレンジャーに挑ませます. 

結果がプラス, つまりチャレンジャーの方が大きければ, チャレンジャーとチャンピオンを入れ替えます. ここでは, 「SWAP」と書いたラベルを配置してあるだけで, コードの中身はこれから書きます.

「アドレス（チャレンジャー）」が「チャンピオン」より大きい場合, 「SWAP」を使って「アドレス（チャレンジャー）」を「チャンピオン」を入れ替えます. 入れ替え後に「アドレス（チャレンジャー）」を1減らし, 次のチャレンジャーに挑ませます.

11行目で「チャンピオン」がマイナスかを判定しています. マイナスの場合, すべてのパネルの順序が決まり, ソートが完了しました. パネルを小さい方から順に右のコンベアに運びます. 最初に左のコンベアから取り出したパネルをカーペットに配置しましたが, その逆のことをしています. 

クリアーできました. サイズ目標は3行も少なく達成できました. スピード目標を達成するには,もう少し工夫が必要です.

目次

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

目次

１）課題

右側のパネルの数値に対し、素因数分解を行い、答えを右側に運んで下さい。

答えは昇順、すなわち小さい順に運んで下さい。

２）考え方

カーペットが25枚とかなり広いので, 素数表を作る方法も考えましたが, 地道に割り算していくことにします. 

基本的な考え方として, 割るべき素数を2から始め, 割り切れれば割り算に使った素数を右のコンベアに運び, 割り算の結果の商を次の割られる数にします. 割り切れない場合は, 素数を1増やして割り切れるか試します. 

素数に入る数字は４など合成数になる時がありますが, 4で割り切れるなら2でも割り切れているので, 結果には影響しません. 効率は悪いですけれども. 

３）初期化

カーペットに名前を付けます.

1. ZERO：カーペットに配置してある０をコードでも識別しやすいように名前を付けます.
2. 入力：左のコンベアから取り出したパネルを保存しておきます. 素数で割り切れなかった時, 割り算をやり直すために使います.
3. 余り：引き算を繰り返して割り算をしますが, 引いた残りの値を記録します. 余りが０になれば, 割り切れたと判断できます.
4. 商：割り算の結果を記録します.
5. 素数：素因数分解するための素数の候補を記録します.

カーペットに名前を付け, 値を配置します. 「素数」には２を設定します.

４）割り算

「素数」で「余り」を割っていきます.

「余り」から「素数」を引き, 結果が０になれば「素数」で割り切れたたことになりますので, 「われた」に進みます. 

「余り」から「素数」を引いた結果がマイナスになった場合, 「素数」では割り切れなかったので, 次の素数で割ることを考えます.

５）割り切れなかった

割り切れなかった場合, 「素数」を1増やして割り算をやり直します.

「入力」に退避していた割られる数を「余」にコピーし, 8行目に戻ります. 8行目に戻る理由は, 「商」を０で初期化するためです.

６）割り切れた

割り切れた場合, 「素数」を右のコンベアに運び, 次の割り算に備えます.

割り切れた場合, 「素数」を右のコンベアに運びます. 忘れずに「商」を1増やしておきます. 

24行目で「商」と「素数」の大小を比較しています. 

「素数」の方が大きい場合は, 素因数分解が完了したと判断できるので, 先頭に戻ります. この時, 「商」は１になっているので, １との比較をした方が良いのでしょうが, この実装で進めます. 

「商」の方が大きければ, 5行目に戻り, 「商」の値を「余」と「入力」にコピーして, 「商」の素因数分解を試みます.

ここまでの内容を実行すると課題をクリアーできました. サイズ目標を達成できています. スピード目標はこの次に考えます.

目次

ヒューマン・リソース・マシーン 入社39年目−座標をもとめよ

目次

１）課題

右側の数字は、カーペット上の番号を表しています。各入力データに対し、その座標（X, Y）を右側に運んで下さい。

例えば左側の数字が６の場合、右に運び出してほしいのは２と１になります。

２）考え方

問題文では, 数字が６の場合, 座標はX=2, Y=1と書いてあります. XとYの求め方は次のようになります.

1. Xは数字６を４で割った余り
2. Yは数字６を４で割った商

入社26年目で割り算をしました. その結果を使えば良さそうです.

３）実装

入社26年目で作成したプログラムをコピーし貼り付けます.

ここからコードを修正していきます. 割る数Bは, カーペット15番の４となります. また, カーペット９番の「ZERO」はカーペット14番になります.

修正しました. カーペット1番にあったBをカーペット15番に付け替えました. またカーペット9番の「ZERO」をカーペット14番に移動しています. 当然, COPYFROMコマンドなどのアドレスも変更しています. 

また, コピー元のコードでは, 左のコンベアから2枚目のパネルを取り出し, カーペットに配置していましたが, これに関するコードは取り除いています.

左のコンベアから12を取り出し, 割り算をしました. 上司に怒られていますが, 割り算はできており, 「Q」と「A」のパネルを右のコンベアに運べば課題をクリアーできます. 

カーペットのラベルを問題の位置を反映し, 「A」を「X」に, 「Q」を「Y」に付け替えました. 割り算終了後に, 「X」と「Y」のパネルを右のコンベアに運んでいます. 

課題をクリアーできました. 

目次

ヒューマン・リソース・マシーン 入社38年目−数字をバラせ

目次

１）課題

左側のパネルの数字を桁ごとに分解して右側へ運んで下さい。

例えば数字が123だったら、答えは「1, 2, 3」となります。

２）考え方

一般的なプログラミング言語であれば, 10で割った商と余りを使って一の位から順に処理していきますが, ヒューマン・リソース・マシーンには割り算がありませんので工夫が必要です. 

カーペットには, 0, 10, 100と書いたパネルが置いてありますので, これらを使っていきます. アルゴリズムは次のようになります.

1. 100で割った結果を右のコンベアに運び, 余りをカーペットに置いておく. 
2. 余りを10で割った結果を右のコンベアに運び, 余りも右のコンベアに運ぶ.

この問題を解くときにもう一つ注意点があります. 上司に解答例を尋ねると, 3などの一桁の数は３のみを右のコンベアに運んでおり, 百の位の数が０の場合はコンベアに運びません. この条件が無ければ, もっと簡単なのですが.

３）初期化

初期化のためのコードを書きます.

カーペットの0番に「一の位」, 1番に「十の位」, 2番の「百の位」と名前を付けます. 元々, パネルを置いてあるカーペットにもパネルの値をカーペットの名前とします. 

続けて, 「百の位」と「十の位」に０を置きます. 「一の位」には左のコンベアから運んだパネルを置きます.

４）百の位

初期化が終わりましたので, 百の位を求めます.

「一の位」のパネルから「１００」を引きます. 結果がマイナスでない時, 「百の位」を1増やし, 結果がマイナスになるまで繰り返します. 結果がマイナスになれば, 「百の位」には百の位の値が入っています. その値が０でなければ右のコンベアに運びます. 

５）十の位

百の位と同様に十の位を求めます.

15行目から20行目までが十の位を求めるコードです. 百の位と処理内容は同等です.

６）十の位と一の位の出力

十の位の計算が終わると, 「十の位」と「一の位」に右のコンベアに運ぶべき値が入っています. 問題は, 「百の位」が０の時, 「十の位」の値も０であれば, 「一の位」だけを右のコンベアに運びます. それ以外の時は, 「十の位」に続けて「一の位」を出力します. 

21行目から「十の位」と「一の位」を出力するためのコードです.

21行目から, 「百の位」が０であるか判定しています. ０でなければ, 26行目にジャンプして, 「十の位」と「一の位」を出力します. 

「百の位」が０の場合, 「十の位」が０であるか判定しています. ０でなければ「十の位」を出力し, そのまま「一の位」を出力します. 「十の位」が０の場合, 28行目にジャンプして, 「一の位」を出力します. 最後に, 30行目で先頭に戻ります.

課題をクリアーできました. サイズ目標を達成できました. スピード目標は, どうしたものでしょう？

目次