GDD2011jp DevQuiz @sys1yagi編 149.0/150.0

全部やろうと思ったけどチャレンジクイズェ・・・にやられ手が出せなかった。

分野別クイズ Web Game

問題

神経衰弱のゲーム問題です。ウェブページにカードが表示され、カードをクリックすると裏返って色が表示される。
全ての色のペアを開けばクリア。全部で64問。

回答

最初は8枚とかなので手動でクリアできますが、後半1024枚の問題などがあって厳しいです。
Googleは「そういう時はChrome Extensionsを使えよな」と言っていたので使いました。
特定ドメインのページが開かれたらonload辺りで記述した処理を実行してくれるエクステンションがサンプルでついていたのでそれを改造しますた。
まずカードの要素配列を作成して、0番目とi+1番目をめくって、色が同じなら要素配列から削除し、要素配列がなくなったら完了、という直球な実装。Chrome Extensionsでやったので全自動で64問解いてくれました。bookmarklet的にも使えるはず。
めくった履歴とか保存してないので要素数によっては時間がすごくかかる、しかしマシンスペックのお陰で問題なし。
ありがとう現代。

(function(){
	var $ = function(id){return document.getElementById(id); }
	var es = [];
	for(var i = 0 ;; i++){
		var e = $("card"+i);
		if(e == null){ break; }
		es[i] = e;
	}
	var e = document.createEvent('MouseEvents');
	e.initEvent('click', false, true);
	var i = 0;
	while(es.length > 0){
		es[0].dispatchEvent(e);
		es[i+1].dispatchEvent(e);
		if(es[0].style.backgroundColor == es[i+1].style.backgroundColor){
			es.splice(0,1);	es.splice(i,1);
			i = 0;
		}
		else{
			i++;
		}
	}
})();

感想

Extensionsってonload的なのできるんだぁへぇ。

分野別クイズ Android

問題

AIDLとAndroidアプリを配布するんでそのアプリを端末なりエミュで立ち上げて指定のアカウントアドレスとパスコード入れ、配布AIDLからAndroidアプリのサービスに繋いでString getCode()で取り出せた値を答えろや。

回答

簡単。aidlとかサービスとかAndroidやってたら一瞬。

	IQuizService service;
	ServiceConnection conn = new ServiceConnection(){
		@Override
		public void onServiceConnected(ComponentName name, IBinder binder) {
			service = IQuizService.Stub.asInterface(binder);
			try{
				((TextView)findViewById(R.id.result)).setText(service.getCode());
			}catch(Exception e){
				e.printStackTrace();
			}
		}
		@Override
		public void onServiceDisconnected(ComponentName name) {
			service = null;
		}
	};
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);
        
        Intent intent = new Intent(IQuizService.class.getName());
        if ( this.bindService(intent, conn, Activity.BIND_AUTO_CREATE) ) {
        	
        }
    }

感想

簡単すぎﾜﾛｽ。Androidエンジニアならapkを解析して値を取り出すべきだったのだけど結局やらなかった。
dex2jarとかでいけたかなぁ。

チャレンジクイズ

問題

テキストにスライドパズルの定義が書かれていて、一行につき一問、以下のフォーマットで5000問。一問0.01点。3x3〜6x6まで。
幅,高さ,パズルの配列
例えば以下のようなやつ
5,5,806E91245K=3=AJ=7HIF=CMNO
"="は壁で移動できない。"0"は空白。5x5なので

806E9
1245K
=3=AJ
=7HUF
=CMNO

というパズルになる。それを操作して解法を出す。
操作はL,R,U,D(左右上下)。"0"を動かした手順を記録する。
上記問題だとゴールは

12345
6789A
=C=EF
=HIJK
=MNO0

になる。

回答

長くなるのでダイジェストで。8/30の夜から着手。問題に取り掛かった時は探索アルゴリズムなんて全く知らなかったです。
他の方々と違って？泥臭く、運の要素も強かった感があります。

1.
なにこれ余裕じゃね。サクっとランダムで回答導いて長さを最適化するべしだな

2.
フレームはできた、一発実行だな。→死亡

3.
あ、あかん、これはあかん。オライリーの「アルゴリズムクイックリファレンス」を引っ張り出す。
探索木とかいう所を読むが全然意味わかんねー。

4.
俺は、俺のやり方でやるんだ。

5.
謎ロジック完成。3x3は大体正解へ。(今にして思えば幅優先もどきのロジック)

6.
へへ、あとは全部回すだけ、勝ったな。

7.
4x4が、倒せない、だと・・・？ 199/5000

8.
「アルゴリズムクイックリファレンス」にごめんなさいして再入門。反復深化深さ優先探索がいいというので盲目的版をやってみる。ちょっと解けて来た。 471/5000

9.
下限値枝刈り法とかいうオシャレな方法があったので追加してみる。このへんで1000台には乗った。
下限値なんとかは単純に壁を考慮しないMDにした。 1011/5000

10.
色々深さとか調整しまくったりロジックを最適化してぶん回し1300くらいまでいった。 1378/5000

11.
まぁボーダー越えたやろ、という事で幅優先の時代に戻ってみよう、と実装を一からやってみた。
幅優先探索の場合深くなるとキューが爆発するので、キューサイズの限界値を設定し、ノードをMDのスコアでソートして、スコア上位ノードだけ次のノードを生成するという方法にしてみた。試しに最大キュー10000で深さ150まで、でやってみたら3000問解けた。 3542/5000

12.
この最大キューと深さを調整しまくる。実行時引数に取り、バッチにして様々な値で計算。4000台突入。 4002/5000

13.
処理最適化を行う。特にMDのスコア計算が毎回配列全ぶん回しだったのでそれをやめる。一回の操作でスコアは+1,-1しかしないのでその辺をいじったら早くなった。また移動後の盤面を保存し、以前の盤面に到達してしまったノードは無効にする様にしたら4900へ。

14.
伸び悩んで来たので最後のあがき。フィーリングカップルアルゴリズムという適当に考えた奴をやってみた。
最初の状態→ゴール、ゴール→最初の状態の２つの探索を走らせて、それぞれの盤面履歴を保存していく。相手の盤面履歴を参照して自分の現在の盤面と一致したら相手の履歴と自分の履歴を結合してFA。→メモリ食うし残った問題には歯が立たず。これってもしかして双方向のなんとかってやつなんだろうか。
次にMDをもうちょい賢くしてみる。壁が存在する場合最短手数が変わるのでそこを考慮した。でもあんまり意味なかった。

最終的には4902問。98問残り。となった。

感想

舐めてかかっていたが相当強かった。TwitterのTL上の他の方々の解法がレベル高すぎてついていけない。
でも色々調べてやってみる事は大事だなと。探索木なんて全く知らなかったが今回の問題によってIDDFSやBFS,A*とかMDとかいろいろ知った。完全に理解が出来ていないモノもあるし、まだまだ色々な方法があったりするけどとにかく面白くてﾜﾛﾀ。
4900に行くまでにユーティリティ的な部分以外は5回くらい1から作りなおした。
他にもHTML5でCanvas使って問題を読み込んで手作業で解くプログラムや、GAEにロジックを乗せてタスクキューで解かせたり色々した。
諦めず殴り続ける事が大事だと思った。

汚いソースはこちら->github
この提出版は結局いじり過ぎで結構重くなってます。ビルドして直下のlooper.batかlooper.shを叩けば4900は出るはず。多分。
まじ酷いソース。まじ参考になりません。

ソース整理はmasterブランチでやる予定。多分。