Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

GDD2010 DevQuiz

会社の同僚に誘われてDevQuizに参加してみました。

Google Maps API

Google Maps APIのコードはJavaScriptという点がハードルでしたが,リファレンスを見ながらどうにかしました。
      「とほほのJavaScriptリファレンス

設問は最大で10地点の巡回セールスマン問題なので,解法は総当りで。順列の生成が必要となりますが,C++ではないのでnext_permutation()が使えない・・・ということで検索。
      「C#でSTLのnext_permutation的なものを

ラウンド2のもう一方の選択問題「2-legged OAuth」は,Rubyでやろうと「初めてのRuby」を買ってまで意気込んでいたのですが,結局は時間がとれずパスとなりました。後で読んでおこう。

Shiritori

単語セットが与えられた「しりとり」ゲーム。player側とcpu側の選択パターンをツリーで表せばOK。ツリーを辿るのはAND/OR木の考え方になります。辿るパスは,CPUの選択は全て負けパターン(AND),Playerの選択は一つでも勝ちがあればよい(OR)ことになります。

ツリーは,再帰を使ってこんな感じで。(実行効率は考慮せず)

int tree( set& words, char head, int bCPU )
{
    set selectable;
    set::iterator it;

    // next selection
    for( it = words.begin(); it != words.end(); it++ ){
        if( (*it)[0] == head ){
            selectable.insert(*it);
        }
    }
    if( selectable.empty() ){
        return bCPU;
    }

    int ret;
    int i = 0;
    for( it = selectable.begin(); it != selectable.end(); it++ ){
        char tail = (*it)[it->size()-1];
        words.erase(*it);
        ret = tree( words, tail, 1-bCPU );
        words.insert(*it);
        if( bCPU ){
            if( ret == 0 ) // 一つでも0なら0を返す
                return 0;
        }else{
            if( ret == 1 ) // 一つでも1なら1を返す
                return 1;
        }
        i++;
    }
    return bCPU;
}

単語セットが多い小問3はツリーが大きくなりすぎるため(処理が終わらない),twitterで流れていたこの論文を参照し,先頭文字と終端文字が巡回しているペア(例 axxxxb,bxxxa)を削除しました。
これだけで大きく処理時間が改善しました。設問の趣旨としてこの事に気づけるかが含まれていたのではないかなとも思います。

PAC-MAN

今回の一番の難敵であったPAC-MANは,Mrathon Match的な問題でかなり楽しめました。拠り所とした解法の考え方があまり宜しくなかったため,結果はあまり振るわず「41.0, 174.0, 358.0」でした。twitterを見てると,小問2は200点,小問3は500点越えが標準な感じで,若干敗北感が・・・

本問はプログラムで自動で解くものだろうと思い込んでましたが,期間途中で「手動による解法でも良い」と公式アナウンスが入り,若干気抜け。「Super Hacker」という名前であれば,自動解法に拘って欲しかったなぁと思います。例えば,Marathon Mathch的にサーバ側で隠された評価用問題を実行して得点を出すなど。

解法としては,局面の探索問題であるためDFSかBFSを基に考えることとしました。敵が移動することで局面の数が膨大となるため,BFSではメモリが足りなくなることは容易に想像つきます(ちょっと試してみましたが,すごい勢いでメモリ使用量が増えていきます)。そんなわけでDFSで進めます。

さらに局面を減らすため(これがまずかったのですが・・・),局面を自機が交差点にいる点だけに絞り込みました。通路では,次の交差点を一目散に目指す形となります。後ほど,手動で試して分かったことですが,敵V,Hを誘導するために通路では行ったり来たり・停止する等のトリッキーな動きが必要なようでした。

局面の数が膨大なためDFSでも全探索は無理だろうと,交差点で行き先の優先順位を決めて,良さそうな手から探索することとしています。(貪欲アルゴリズムで突き進み,ダメだったときに一手戻るという形です)

評価関数は次のような形にしてみました。(かなり場当たり的ですが)

int evaluate(移動先交差点)
{
    bonus = 0;
    if( ここまでの移動が初訪問 ){
        if(ここからの通路に未訪問が残っている)
            bonus = 100;
        eval = 0x40000000 + 交差点番号 + bonus;
    }else{
        moves    = 未訪問が残る通路への移動手数(何交差点先か)。 // 15手先まで見る
        dot_path = moves手先の交差点で,未訪問通路の数
        if(2手以内の範囲で,未訪問通路が単独で存在する)
            bonus = 100;
        eval = (1 << (15-moves)) + dot_path + bonus + 交差点番号*3;
    }
    return eval;
}

未訪問通路の通過が評価値最大,訪問済み通路の場合はここから周辺の未訪問通路への移動手数が少ない方が評価値大となります。交差点番号は,左上を0とし右下へ行くほど増える値です。行ったり来たりを繰り返さないように,右下方向を優先させるバイアスをかけてみました。

最終的には,小問1は手動で解いてしまい,小問2は自動,小問3は1個目の行き止まりまでは手動(50手弱)でその後は自動という半手動の形でやってみました。

スポンサーサイト

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。