ソニーのソフトウェアスペシャリスト認定コンテスト『申告制エレベータ』

広告

いよいよ明日帰国でどたばたしていますが、ちょっとだけ『申告制エレベータ』をやってみました。

申告制エレベータ

10F建てのオフィスビルがあります。事前に全ての利用者から申告を受けています。エレベータが最適に動作するアルゴリズムを考えてみましょう。

エレベータには下記の制約があります。

  1. エレベータが1つの階を移動するのに掛かる時間は2秒です。
  2. 一旦、エレベータの扉が開くと、閉まるまでに最低でも5秒掛かります。
  3. ※扉の開閉時間は、この5秒に含まれているものとします。

  4. エレベータの初期状態は1Fで扉が閉まっています。

エレベータの入力データと出力データのフォーマットは決まっています。下記ファイルを参照して下さい。

入出力ファイルについては

データフォーマット

入力データ

利用者の申告を下記のcsv形式で標準入力します。

--------------------------------
1,0,1,5
2,20,2,6
3,80,4,5
4,80,4,5
--------------------------------

入力形式

  • In1,In2,In3,In4
  • In1 – 入力データの識別番号です。(1-)
  • In2 – 申告者の乗車希望時刻です。開始してからの経過秒数で表します。(0-)
  • In3 – 申告者が乗車する階です。(1-10)
  • In4 – 申告者が降車する階です。(1-10)

出力データ

エレベータの動作履歴を下記のcsv形式で標準出力します。

--------------------------------
1,0,1,B,0,0,0,0,0
1,5,1,E,1,0,0,0,0
1,13,5,B,1,0,0,0,0
1,18,5,E,0,0,0,0,0
1,24,2,B,0,0,0,0,0
1,29,2,E,2,0,0,0,0
1,37,6,B,2,0,0,0,0
1,42,6,E,0,0,0,0,0
1,46,4,B,0,0,0,0,0
1,80,4,E,3,4,0,0,0
1,82,5,B,3,4,0,0,0
--------------------------------

出力形式

Out1,Out2,Out3,Out4,Out5,Out6,Out7,Out8,Out9

  • Out1 – エレベータの識別番号です。(1-)
  • Out2 – エレベータの動作時刻です。開始してからの経過秒数で表します。(0-)
  • Out3 – エレベータが動作した階です。(1-10)
  • Out4 – エレベータの動作です。(‘B’:開 ‘E’:閉)
  • Out5 – 入力データの識別番号1 ※1
  • Out6 – 入力データの識別番号2 ※1
  • Out7 – 入力データの識別番号3 ※1
  • Out8 – 入力データの識別番号4 ※1
  • Out9 – 入力データの識別番号5 ※1

※1 Out4がBの場合:降車させた入力データの識別番号が最大で5つ続きます。該当するデータが存在しない場合は0とします。(1,2,3,0,0)

Out4がEの場合:乗車させた入力データの識別番号が最大で5つ続きます。該当するデータが存在しない場合は0とします。(1,2,3,0,0)

問1

エレベータを1台、最大乗車人数を1人とします。単純に入力データの識別番号順に、利用者を運ぶプログラムを作成してください。入力データは下記ファイルとします。

1,226,3,4
2,263,2,3
3,282,1,8
4,466,5,3
5,499,10,6
6,544,7,1
7,593,1,10
8,663,10,2
9,678,3,5
10,803,4,9

たぶんウォーミングアップ。素直に書いてみる。

// ライセンスは修正BSDライセンス
#include < stdio.h>
#include < iostream>
#include < string>
#include < set>
#include < map>
#include < algorithm>
#include < stack>
#include < vector>

using namespace std;

struct data
{
    int id;
    int time;
    int getin;
    int getoff;
};

int main()
{
    FILE *in = fopen("input_i.csv","rt");
    if( in == NULL )
        return EXIT_FAILURE;
    
    vector<data> schedule;
    while( true )
    {
        data d;
        fscanf( in, "%d,%d,%d,%d", &d.id, &d.time, &d.getin, &d.getoff );
        printf( "%d %d %d %dn", d.id, d.time, d.getin, d.getoff );        
        schedule.push_back(d);

        if( feof(in) == true )
            break;
    }
    
    cout << endl;
    cout << "1,0,1,B,0,0,0,0,0" << endl;
    
    int time = 0;
    int currentfloor = 1;
    for( int i = 0; i < schedule.size(); i++ )
    {
        int nextfloor = schedule[i].getin;
        int t = (nextfloor - currentfloor) * 2;
        int id = schedule[i].id;
        time = max( schedule[i].time, time + t );
        currentfloor = nextfloor;
        printf("%d,%d,%d,%c,%d,%d,%d,%d,%d 移動して扉を開けるが下ろす人はいないn",1, time, currentfloor, 'B', 0, 0, 0, 0, 0 );
        time += 5;
        printf("%d,%d,%d,%c,%d,%d,%d,%d,%d 人を乗せて扉を閉める、+5秒n",1, time, currentfloor, 'E', id, 0, 0, 0, 0 );
        
        nextfloor = schedule[i].getoff;
        t = (nextfloor - currentfloor) * 2;
        time += t;
        currentfloor = nextfloor;
        printf("%d,%d,%d,%c,%d,%d,%d,%d,%d 乗せた人を下ろすn",1, time, currentfloor, 'B', id, 0, 0, 0, 0 );
        time += 5;
        printf("%d,%d,%d,%c,%d,%d,%d,%d,%d 扉を閉めて次に向かうn",1, time, currentfloor, 'E', 0, 0, 0, 0, 0 );
    }
    
    return EXIT_SUCCESS;
}

こういう理解でいいのかな。正解を示してくれれば理解のただしさを確認できるのだけど。

まず最初の出力は初期状態。これは決め打ち。

次にスケジュールを読んで、その通りに行動する。このサンプルでは全部の利用者に対して余裕を持って運行できるけど、間に合わない場合もある。人の乗り降りは瞬間的に行われるという前提。書いてないからね。1人1秒とか書いてあればそれも意識する。

問1ではエレベータは一人乗りだから、誰か乗っていれば他の人は乗れない。だから待っている人を迎えに行って下ろしての繰り返し。優先度も「単純に入力データの識別番号順に、利用者を運ぶ」だからそのまま素直に動かせばいい。

そのようなわけで、スケジュールから1行読む。次の階がどこか、現在の階がどこかを確認する。1フロア移動するのに2秒かかる。あと出力に「入力データの識別番号が最大で5つ続きます」とあるから、それを記録しておく。定員は1名だから

時刻の計算をする。予約の時間と、現在時刻に移動に要する時間を比較して大きい方に次の予約に向かう。この例題の場合は必ず間に合うようになっているけど、間に合わない場合もあるだろう。

時刻が決まったらcurrentfloorをnextfloorに置き換える。また出力データを生成する。まず扉を開けるから動作はBで、下ろす人はいないからidは0を出力。時刻とかどのフロアにいるかとかをずらずら書き出す。扉の開け閉めで5秒要するので時刻を足しておく。扉を閉めたら今度は動作Eを出力。

下ろす階に移動する。その際に跨ぐフロアの数 * 2分要する。その時間を足す。扉を開けるのでBを出力。下ろすのはさっき乗せた人。5秒後に扉を閉めて次の目的地に向かう。

出力

1,0,1,B,0,0,0,0,0
1,226,3,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,231,3,E,1,0,0,0,0 人を乗せて扉を閉める、+5秒
1,233,4,B,1,0,0,0,0 乗せた人を下ろす
1,238,4,E,0,0,0,0,0 扉を閉めて次に向かう
1,263,2,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,268,2,E,2,0,0,0,0 人を乗せて扉を閉める、+5秒
1,270,3,B,2,0,0,0,0 乗せた人を下ろす
1,275,3,E,0,0,0,0,0 扉を閉めて次に向かう
1,282,1,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,287,1,E,3,0,0,0,0 人を乗せて扉を閉める、+5秒
1,301,8,B,3,0,0,0,0 乗せた人を下ろす
1,306,8,E,0,0,0,0,0 扉を閉めて次に向かう
1,466,5,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,471,5,E,4,0,0,0,0 人を乗せて扉を閉める、+5秒
1,467,3,B,4,0,0,0,0 乗せた人を下ろす
1,472,3,E,0,0,0,0,0 扉を閉めて次に向かう
1,499,10,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,504,10,E,5,0,0,0,0 人を乗せて扉を閉める、+5秒
1,496,6,B,5,0,0,0,0 乗せた人を下ろす
1,501,6,E,0,0,0,0,0 扉を閉めて次に向かう
1,544,7,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,549,7,E,6,0,0,0,0 人を乗せて扉を閉める、+5秒
1,537,1,B,6,0,0,0,0 乗せた人を下ろす
1,542,1,E,0,0,0,0,0 扉を閉めて次に向かう
1,593,1,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,598,1,E,7,0,0,0,0 人を乗せて扉を閉める、+5秒
1,616,10,B,7,0,0,0,0 乗せた人を下ろす
1,621,10,E,0,0,0,0,0 扉を閉めて次に向かう
1,663,10,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,668,10,E,8,0,0,0,0 人を乗せて扉を閉める、+5秒
1,652,2,B,8,0,0,0,0 乗せた人を下ろす
1,657,2,E,0,0,0,0,0 扉を閉めて次に向かう
1,678,3,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,683,3,E,9,0,0,0,0 人を乗せて扉を閉める、+5秒
1,687,5,B,9,0,0,0,0 乗せた人を下ろす
1,692,5,E,0,0,0,0,0 扉を閉めて次に向かう
1,803,4,B,0,0,0,0,0 移動して扉を開けるが下ろす人はいない
1,808,4,E,10,0,0,0,0 人を乗せて扉を閉める、+5秒
1,818,9,B,10,0,0,0,0 乗せた人を下ろす
1,823,9,E,0,0,0,0,0 扉を閉めて次に向かう

こんな感じで破綻がなければOK。余分なデバッグ用文字列は消しておく。

残りはまた後で

残りの問は結構面倒臭い。本格的な実装が必要になりそう。適当に勘で書くと、貪欲法、A*アルゴリズムによる経路探索、オフラインアルゴリズム、並列機械スケジューリングあたりかなあ。

おそらくこの問題はかなり難しい。これを上手く解けたら、時計とかガンマ関数の問題よりもずっと格好いいだろうな。でもやることは比較的明確なので土日にでもじっくり取り組めばできそう。この問題をエレガントに解いた人はソニーどころかGoogleでも通用するんじゃないかな。Googleのインタビューで聞かれることよりもだいぶ難しいはずだ。

ゲームAIは複雑な敵の動きとかを記述するためのものだから多分役に立つ。おそらく単純にやるには貪欲に一番遠いところから巡回して人を回収していく、ありがちなエレベータの動作を実装すればいいのだろうけど、それが最適解であるかはわからない。貪欲法は上手くいくときは極めて強力かつシンプルにいけるけど、必ずしも最適解にはならない。

『実例で学ぶゲームAIプログラミング』は裁断&スキャン済みの本がPCの中に入っているはずだが、整理していないので見つからない。『ゲーム開発者のためのAI入門』は貸した友人が就職で関西に行ってしまったので戻ってこない。こちらの方がA*とか事細かに書いてあるのでよかったかも知れない。

『アルゴリズムクイックリファレンス』は手元にあった。オライリーだからPDFで買えるのもいい。電子書籍ばんざい。サンプルコードもどこかにあるらしいが、見つからなかった。