カテゴリー: GDD11

DevQuizが無事及第点を突破していたということで、Google Devolper Day 2011 Japanに参加できることになりました。

想定されるボーダーからはだいぶ上だったとは言え
さらに高いスコアの方が（主にTwitter関連で）いっぱいいましたし、
Quizが終了してから一週間ほど悶々していたので、
テンションが一気にあがりましたよ！ヽ(´ー｀)ノ

とはいえ、今回のスライドクイズは力押しでスコアを上げてしまったので、
ちゃんとアルゴリズム組み立てて効率よく解かないとねえ……と反省はしきり。
仕事に直結はしないだろうけど、勉強して次回はもっといい立ち回りができるようにがんばる！

GDD2011JPのDevQuizの分野別クイズのうち、Web Gameの解答をさらします。

あまり捻くれたことはしていません。多少冗長なコードもありますが、まあ。
arrayElementColorIdのキーは、カードのindexでなく「色」の方をつっこんでます。

所要時間は、いま測定して62秒弱でした。
DevQuiz開催期間中は70〜80秒台だったので、ネットワーク負荷が軽くなったんですかね。

var i = 0; // カードのindex
var id; // "card" + i
var element; // idを元に取り出したオブジェクト
var color; // elementのcolor属性値
var latestId = null; // 前回2枚目で取り出した、既に配列上にあるid
var latestColor = null; // 同じくそのcolor
var arrayElementColorId = new Array(); // keyがcolor、valueがid

var clickEvent = document.createEvent('MouseEvents');
clickEvent.initEvent('click', false, true);

while (true) {
  // 前回の2枚目の処理でストアしたid/colorがあったら処理する
  if (latestId != null) {
    // 1枚目（前回ストアしたカード）
    element = document.getElementById(latestId);
    element.dispatchEvent(clickEvent);

    // 2枚目
    element = document.getElementById(arrayElementColorId[latestColor]);
    element.dispatchEvent(clickEvent); // これで2枚が処理済みになる
    delete arrayElementColorId[latestColor]; // 配列から削除

    latestId = null;
    latestColor = null;

    continue;
  }

  // 1枚目をめくる
  id = 'card' + i;
  element = document.getElementById(id);
//  if (element == null) {
//    break;
//  }

  i++; // インデックスを+1
  element.dispatchEvent(clickEvent);
  color = element.style.backgroundColor;

  if (color in arrayElementColorId) {
    // 色が一致する未処理のelementがある場合
    element = document.getElementById(arrayElementColorId[color]);
    element.dispatchEvent(clickEvent); // これで2枚が処理済みになる
    delete arrayElementColorId[color]; // 配列から削除
  } else {
    // ない場合は今取得したものを配列に格納する
    arrayElementColorId[color] = id;

    // 続けて2枚目をめくる
    id = 'card' + i;
      element = document.getElementById(id);

//    if (element == null) {
//      break;
//    }

    i++; // インデックスを+1
    element.dispatchEvent(clickEvent);
    color = element.style.backgroundColor;

    if (color in arrayElementColorId) {
      // 色が一致する未処理のelementがある場合
      // 次回の「1枚目をめくる」ときに処理する
      latestId = id;
      latestColor = color;
    } else {
      // ない場合は今取得したものを配列に格納する
      arrayElementColorId[color] = id;
    }
  }
}

もうひとつの選択問題は「Android」を選びましたが、こちらは単にbindServiceして叩いているだけなので省略します。

スライドパズルの結果は晒すのが憚られるコードなので、とりあえず作りだけ。

探索方法やパラメータをいろいろ弄くったあげく、最終的には
　・A*（評価関数は「そのボード状態に到達するまでのLRUD長」＋「ゴールまでのマンハッタン距離」）ベース
　・一定の探索回数で諦める＋探索用のキューを一定の割合で切り捨てて準最適解を導出
という方向でどんどこ回しました。

最適解を求めなかったので解への到達効率は上がりましたが「使えない子」が結構出ました。
（2392個の解に到達、使えたのは2209個）
もう少し時間がほしかった……