Skip to content
This repository has been archived by the owner on Jan 8, 2019. It is now read-only.

Latest commit

 

History

History
273 lines (234 loc) · 10.7 KB

README.ja.md

File metadata and controls

273 lines (234 loc) · 10.7 KB
Raw

Elevator Saga の解答

下記サイトで公開されているElevator Sagaに対する解答です。

最終的な解答コードは elevator-saga.js となります。

以降は実装の経緯になります。

バージョン1: 基本動作

まずはAPIを読んで、普段乗っているエレベータの動作を考えてみて、下記のように実装しました。

  • フロアのボタンが押下された情報はフロア×方向(上/下)として保持(各フロアのボタン押下状態を取るAPIが無いのが不親切だが、そこが今回の肝なのかもしれない)
    • 停止中のエレベータで、近くにあるものを向かわせる
    • そのフロアに止まったら、該当の情報をクリア
    • フロアを通過前に情報をチェックし、進行方向と同じボタンが押下されていて、かつ乗客がまだ乗れる場合には、該当フロアに止まる
    • 行き先フロアが無くなったら、ボタンが押下されたフロアで現フロアから一番近いフロアに移動＋進行方向を設定
  • エレベータ内の行き先フロアボタンが押下されたら、現在フロアから進行方向の順でソートしてフロアに止まる順番をリセットする

各Challengeを50回実行した結果は下記の通りです。(クリアできるかどうかは乱数によるぶれ幅が広い感じ)

All         :  49.11 (442/900)
Challenge  1: 100.00 (50/50)
Challenge  2:  88.00 (44/50)
Challenge  3:  94.00 (47/50)
Challenge  4:  94.00 (47/50)
Challenge  5:  50.00 (25/50)
Challenge  6:   2.00 (1/50)
Challenge  7:  16.00 (8/50)
Challenge  8:  84.00 (42/50)
Challenge  9:  94.00 (47/50)
Challenge 10:  16.00 (8/50)
Challenge 11:  62.00 (31/50)
Challenge 12:  14.00 (7/50)
Challenge 13:   0.00 (0/50)
Challenge 14:   4.00 (2/50)
Challenge 15:  32.00 (16/50)
Challenge 16: 100.00 (50/50)
Challenge 17:  30.00 (15/50)
Challenge 18:   4.00 (2/50)

バージョン2: 効率的な動作へ

バージョン1での実際の動作を見て、下記の考慮を追加しました。

  • 移動先候補の決定に、他のエレベータが次に移動しようとしている箇所を除外する処理を追加。
    • 同じフロアの乗客を拾おうとして空振りしないように
  • フロアを通過するタイミングで、乗客が0の場合(最初の乗客を乗せるための移動時)には、最新の情報で移動先を再決定。
    • 移動中に近いフロアで新たな乗客が発生する場合があるため、その都度最新の情報で判断するように

大きく性能向上し、回数は少ないですが、全ての面がクリアできるようになりました。

All         :  66.89 (602/900)
Challenge  1: 100.00 (50/50)
Challenge  2:  82.00 (41/50)
Challenge  3:  96.00 (48/50)
Challenge  4:  98.00 (49/50)
Challenge  5:  84.00 (42/50)
Challenge  6:   6.00 (3/50)
Challenge  7:  28.00 (14/50)
Challenge  8: 100.00 (50/50)
Challenge  9:  94.00 (47/50)
Challenge 10:  26.00 (13/50)
Challenge 11:  90.00 (45/50)
Challenge 12:  70.00 (35/50)
Challenge 13:  16.00 (8/50)
Challenge 14:  42.00 (21/50)
Challenge 15:  96.00 (48/50)
Challenge 16: 100.00 (50/50)
Challenge 17:  66.00 (33/50)
Challenge 18:  10.00 (5/50)

バージョン3: 移動回数への対応

移動回数が条件の場合(Challenge#6,#7)、スループットを優先するとクリア率がどうしても低くなってしまうため、移動回数を考慮した実装を追加しました。

Challenge#6,#7の場合のみ、なるべく多くの人を乗せてから移動するような対応です。(ボタンが押下されても、人が一定数乗っていないと移動しない)

該当Challengeのクリア率をあげることができました。

All         :  76.78 (691/900)
Challenge  1: 100.00 (50/50)
Challenge  2:  86.00 (43/50)
Challenge  3:  98.00 (49/50)
Challenge  4:  98.00 (49/50)
Challenge  5:  82.00 (41/50)
Challenge  6: 100.00 (50/50)
Challenge  7:  98.00 (49/50)
Challenge  8:  94.00 (47/50)
Challenge  9:  98.00 (49/50)
Challenge 10:  14.00 (7/50)
Challenge 11:  88.00 (44/50)
Challenge 12:  82.00 (41/50)
Challenge 13:  16.00 (8/50)
Challenge 14:  44.00 (22/50)
Challenge 15:  98.00 (49/50)
Challenge 16: 100.00 (50/50)
Challenge 17:  62.00 (31/50)
Challenge 18:  24.00 (12/50)

バージョン4: フロア通過時に追加で人を乗せる条件の見直し

クリア率が低いChallenge#10を見ていると、フロアに止まるが乗客を乗せないことが多々見受けられたため、フロア通過時に追加で乗客を乗せる条件を loadFactor < 1 からもう少し余裕を持たせた形の loadFactor < 0.5 に変更しました。これによりフロアに止まっても乗客を乗せないといった現象が無くなりました。

All         :  81.11 (730/900)
Challenge  1: 100.00 (50/50)
Challenge  2:  86.00 (43/50)
Challenge  3:  90.00 (45/50)
Challenge  4: 100.00 (50/50)
Challenge  5:  96.00 (48/50)
Challenge  6: 100.00 (50/50)
Challenge  7:  98.00 (49/50)
Challenge  8:  96.00 (48/50)
Challenge  9:  98.00 (49/50)
Challenge 10:  56.00 (28/50)
Challenge 11:  86.00 (43/50)
Challenge 12:  62.00 (31/50)
Challenge 13:  30.00 (15/50)
Challenge 14:  44.00 (22/50)
Challenge 15: 100.00 (50/50)
Challenge 16: 100.00 (50/50)
Challenge 17:  86.00 (43/50)
Challenge 18:  32.00 (16/50)

回数を200まで増やした結果です。

All         :  81.03 (2917/3600)
Challenge  1: 100.00 (200/200)
Challenge  2:  82.50 (165/200)
Challenge  3:  96.50 (193/200)
Challenge  4:  99.00 (198/200)
Challenge  5:  90.50 (181/200)
Challenge  6: 100.00 (200/200)
Challenge  7:  96.00 (192/200)
Challenge  8:  98.50 (197/200)
Challenge  9:  96.50 (193/200)
Challenge 10:  53.50 (107/200)
Challenge 11:  92.50 (185/200)
Challenge 12:  69.00 (138/200)
Challenge 13:  29.00 (58/200)
Challenge 14:  43.00 (86/200)
Challenge 15:  98.50 (197/200)
Challenge 16: 100.00 (200/200)
Challenge 17:  87.50 (175/200)
Challenge 18:  26.00 (52/200)

バージョン5: 次の移動先決定の精度向上

次の移動先を決定する際に、下記の考慮を入れことによって、より効率の良く移動先を決めるようにしました。

  • その他のエレベータの移動先取得において、そのエレベータの最後の移動先の場合には、その次の動きを考慮した移動先となるように
    • 最終停止フロアで押されているボタンの方向の乗客をそのまま乗せるので、フロアのボタン押下状態を反映する形
  • その他のエレベータが移動先としているフロア＋方向は選択しないようにしていたが、その他のエレベータより近い場合(2フロア以上近い位置にいるとき)には、候補とするように
    • 他のエレベータに任せることによって時間がかかりすぎる場合もあるので、差が大きいときには近いほうで処理してしまう

多少良くなりましたが、数パーセントの差なので、誤差の範囲かもしれません。少なくとも悪くはなってはいないので、この考慮をいれたまま進めます。

All         :  84.11 (757/900)
Challenge  1: 100.00 (50/50)
Challenge  2:  92.00 (46/50)
Challenge  3:  94.00 (47/50)
Challenge  4: 100.00 (50/50)
Challenge  5:  90.00 (45/50)
Challenge  6: 100.00 (50/50)
Challenge  7:  94.00 (47/50)
Challenge  8:  94.00 (47/50)
Challenge  9:  98.00 (49/50)
Challenge 10:  62.00 (31/50)
Challenge 11: 100.00 (50/50)
Challenge 12:  84.00 (42/50)
Challenge 13:  40.00 (20/50)
Challenge 14:  54.00 (27/50)
Challenge 15:  92.00 (46/50)
Challenge 16: 100.00 (50/50)
Challenge 17:  90.00 (45/50)
Challenge 18:  30.00 (15/50)

回数を200まで増やした結果です。

All         :  83.03 (2989/3600)
Challenge  1: 100.00 (200/200)
Challenge  2:  86.50 (173/200)
Challenge  3:  96.00 (192/200)
Challenge  4:  98.50 (197/200)
Challenge  5:  95.50 (191/200)
Challenge  6: 100.00 (200/200)
Challenge  7:  98.00 (196/200)
Challenge  8:  98.50 (197/200)
Challenge  9:  99.00 (198/200)
Challenge 10:  52.00 (104/200)
Challenge 11:  95.50 (191/200)
Challenge 12:  77.50 (155/200)
Challenge 13:  41.50 (83/200)
Challenge 14:  53.50 (107/200)
Challenge 15:  96.00 (192/200)
Challenge 16: 100.00 (200/200)
Challenge 17:  86.50 (173/200)
Challenge 18:  20.00 (40/200)

バージョン6: 次の移動先決定の精度向上 その2

一番近い移動先フロアで押下されている方向が、今いるフロアの方向だった場合、さらに1つ離れたフロアで今いるフロアの方向のものがあれば、離れたフロアに移動して、まとめて拾えるようにしてみました。

例：現在フロアが1で、一番近い移動先フロアが2で下向きの場合、3で下向きがあればそれを選択

Challenge#18の勝率がかなりあがりましたが、Challenge#13,#14が落ちる結果(とはいえ、誤差の範囲)となりました。

All         :  84.56 (761/900)
Challenge  1: 100.00 (50/50)
Challenge  2:  90.00 (45/50)
Challenge  3:  94.00 (47/50)
Challenge  4: 100.00 (50/50)
Challenge  5:  94.00 (47/50)
Challenge  6: 100.00 (50/50)
Challenge  7:  94.00 (47/50)
Challenge  8:  96.00 (48/50)
Challenge  9:  98.00 (49/50)
Challenge 10:  60.00 (30/50)
Challenge 11:  94.00 (47/50)
Challenge 12:  84.00 (42/50)
Challenge 13:  34.00 (17/50)
Challenge 14:  48.00 (24/50)
Challenge 15:  92.00 (46/50)
Challenge 16: 100.00 (50/50)
Challenge 17:  90.00 (45/50)
Challenge 18:  54.00 (27/50)

回数を200まで増やした結果です。やはりChallenge#18には効果が出ているようです。

All         :  84.03 (3025/3600)
Challenge  1: 100.00 (200/200)
Challenge  2:  83.50 (167/200)
Challenge  3:  96.50 (193/200)
Challenge  4: 100.00 (200/200)
Challenge  5:  93.00 (186/200)
Challenge  6: 100.00 (200/200)
Challenge  7:  95.00 (190/200)
Challenge  8:  99.00 (198/200)
Challenge  9:  99.50 (199/200)
Challenge 10:  58.50 (117/200)
Challenge 11:  97.00 (194/200)
Challenge 12:  86.50 (173/200)
Challenge 13:  37.50 (75/200)
Challenge 14:  45.00 (90/200)
Challenge 15:  95.00 (190/200)
Challenge 16: 100.00 (200/200)
Challenge 17:  86.50 (173/200)
Challenge 18:  40.00 (80/200)

[おまけ] Elevator Sage の自動実行

Elevator Sageを自動実行するツールを作成しました。

これを使うとベンチマークが計測できますので、ぜひご利用ください。