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個)
もう少し時間がほしかった……
