Sony「go for it」 問題5 申告制エレベータ

提出完了…毎日就活の合間を縫って作っていましたが、あと少し時間が足りませんでした。。
あと１日あればより充実した問題３，４と参考情報が記載出来ました。悔しい。
せっかくシミュレーターを作ったのだからもっとエレベーターのアルゴリズムをこね回したかった。


プログラムコード
こちらからダウンロードして下さい。

回答できた問題の出力
問題１(csvファイル)
問題１はIDの順番通り実行させるだけです。ちなみにこの理論最短時間は、「一人も待たすこと無く運んだ場合の合計時間」です。

問題２
問題２に関しては、各問題を実行後に自動で結果が出るようになっております。
アルゴリズムとしては、リフトごとに出力を振り分け、リフトの数分のスレッドで一気に処理します。スレッドを利用する理由は、入力を乗車した時点で一旦仮のリストに格納し、降車するタイミングでそれを解放するチェックアルゴリズムにおいて、リストの探索の回数を減らすことができるということです。
単独で動作させたい場合は、CsvManagerを初期化後、check(出力ファイルのパス)を実行することで可能です。また、この問題のルールではエレベーターが待機している場合の出力に関して明記されていなかったため、待機していたと思われる時間には注意文を出力させています。例えば２階先でドアを開いたのが６秒後だった場合、２秒待って４秒移動したのか[正解]、４秒待って２秒移動したのか[不正解]わかりません。

問題３(csvファイル)
ここからが本題なのですが…結果はかなり残念です。
なぜかというと、「申告制でなくても動作可能」なアルゴリズムだからです。
問題３，４のアルゴリズムは同じものを利用しています。
エレベーターが守っているルールは以下です。
・乗っている乗客と同じ方向の乗客しか乗せない
・お互いのエレベーターは極力異なる方向へ進もうとする

問題４(csvファイル)
アルゴリズムに関しては問題３と同じです。
ちなみにこの実行結果は提出期限１０分前に出たものです…
問題３と同じく「申告制でなくても動作可能」なアルゴリズムですが、倍以上の効率で作業をこなすことができたことは不幸中の幸いです。

アルゴリズムの簡単な説明
オブジェクトの構成
このようなクラス構成となっています。　※getter, setterは排除してあります

本プログラム内ではエレベーターをリフト[Lift]、入力データの各行をタスク[Task]と呼んでいます。
シミュレーター[Simulator]はビル[Building]と時計[Clock]を持っています。
ビル[Building]は以下のオブジェクトを持っています。
・各階[Floor]：それぞれにタスク[Task]が配置されている
・リフト[Lift]：目的[Aim]に従ってタスク[Task]を運ぶ
・リフトマネージャ[LiftManager]：リフト[Lift]に目的[Aim]を与える
極力現実世界と構成を似せてるので、その辺をイメージしながら見てもらえるとわかりやすいかと思います。
また、上記のオブジェクトとは別に以下のようなオブジェクトが存在しています。
・入出力管理オブジェクト[CvsManager]：データの入出力を管理します。チェックも行います。
・画面出力用ウィンドウ[Window]：アルゴリズムを考えやすくするために作成

シミュレーターのアルゴリズム
シミュレーターは以下のように動作しています。

リフトマネージャは抽象クラスですので、簡単にリフトの振る舞いを変えることが可能になります。
状態遷移に関しての詳細は、プログラム内にコメントで１行ごと記入していますので、そちらを参照して下さい。

エレベーターを制御するアルゴリズム
ここが問題のメインです(笑)
問題１に関してはID順に目的をこなすだけです。
問題３，４に関してはリフトが２つになるかしか違いが無いので、同じリフトマネージャで動かすことにしました。よってリフトが５台でも許容人数が１０人でも問題ありません。
※リフトの数を増やす場合、Windowクラスの99行目に増やした分のString.class,を記入しなくてはいけないことがわかりました。

経験的によい結果が出るであろうルールを根底に定義しました。

• 同じ方向の人しか乗せない

リフトに人を載せる場合、乗っている人間の方向が同じでなければいけない。人が乗っていない場合はどちらも載せることができる。これは途中で反対方向に向かうことは時間の無駄であり、行って帰ってきた時に載せた場合でも同じ移動時間になるため。またその間に片方のリフトが来る可能性、載せることができる人数に制限があることを考慮にいれると妥当である。

• リフトは極力対称的に動作すべき。

これは上記の根底と、リフトが人を待つことができる要素を含むとき、お互いがカバーできない状況を極力生まないことに繋がる。しかし次にどの階から最短で人を載せるかは事前にわかるため、常に1階と10階にいるべきというわけではない。

本来ならここから「申告制だからこそ出来る動作」を表現しようと考えていたのですが、時間が足りなくなってしまい、ここで断念しました。ちなみに自分の中で固まっているアイディアはページ末尾に載せておきます。

実行方法
実行環境
必要な環境として、JRE1.5以上がインストールされている必要があります。
また、ソースファイルはすべてShift-JISで記述されています。Windows以外で実行する場合は注意が必要です。

コンパイル(設定クラスを切り替えるたびに必要です)
各自コマンドプロンプトでsrcディレクトリをカレントディレクトリにしてください。以下のようにコマンドします。

実行
コンパイルが通りましたら以下のようにして実行して下さい。

問題の切り替え
Simulatorクラス内のmainメソッドで、実行したい問題のSettingクラスを宣言することで切り替え可能です。ですが、すでに必要な宣言は記入しコメントアウトしてあります。

上記の場合は問題３を実行することができます。
また、同mainメソッド内のrun(数字);の数字を大きくすればシミュレーションはゆっくり進み、小さくすると早く進みます。

感想・おまけ
感想
本プログラムを作る上で気をつけたことは、後から拡張・改変をしやすく、ということです。今回は最初から問題がすべて提示されていたので、最低限の抽象化で済ませました。個人でこれからどう拡張していくかわからないプログラムを作るときは、より抽象化したプログラムにすることで再利用性を高めています。

私はプログラミング、特にシステムの構成を考えている時が大好きなのですが、就活ではプログラミング能力を全面に出す企業は多くないように感じました。もちろん、他に大切なことがたくさんあるのは事実です。ですが「コードで世界は変えられる」、この言葉もまた重要であると思います。自身の技術力を高めてこそ、本当に良いものを自信をもって作ることができるのではないでしょうか。

就活で時間が取りにくく、満足した結果を出せなかったことは残念でしたが、せっかく作ったシミュレーターなので、問題３，４をこれからもっと賢いプログラムに変えていこうと思います！また機会があったら是非参加したいです。

おまけ
これからどのようにリフトマネージャを拡張するかのアイディアです。
アルゴリズムで挙げた２つのルールを守る場合、リフトの推論は 「載せるか、載せないか」と「どれだけ待つか」に絞ることができる。

• 【どれだけ待つか】

リフトがこれから向かう方向(乗っている人の方向) と同じ方向の人がn秒後に乗車可能になる場合、それまで待機する。これはn×(乗車中の人数+進行方向に存在する乗車待機中の乗車可能人数)分マイナスが発生する。その時間が、次に乗ることができるリフト(そのリフトかもしれないし、別のリフトかもしれない)が来るまでの待機時間を越えなければ待機する。

•  【載せるかどうか】 

リフトに人数制限がある以上、どの人間を載せていくかを考慮して選択していかなければならない。例えば同じ階層にすでに同じ方向で待機中の2人がいる場合、すぐに降りてくれる人の方が多くの人間を待たせない可能性が高い。また同じ階、または今後乗車する可能性のある人が多いか、その人が降りる階に同じ方向に乗る人が多いことが望ましい。しかし、それらの要素だけで決定してしまうと、ずっと待っている人ができてしまう。どうだろう(俺はそんなエレベーター乗りたくない)。

•  【下ろすかどうか】

リフト容量に余裕がある場合、乗り継ぎを利用することができる。これは他の人を同じ階に移すことでドアの開閉時間を押さえることが目的である。またそれが目的であるため、その階で下ろす人間がいる場合のみ利用可能である。また、この方法を利用した場合、タスクを変更することになり、検討が必要である。具体的には、タスクの開始時刻は変更せずに乗車階を下ろす際に変更し、フロアのタスクに再登録するというもの。これならばログ出力には影響しない。