2011-08 << 2011-09 >> 2011-10

2011-09-12 (月)

*GDD2011 DevQuiz

TODO:最後に提出したスライドパズルのコード貼る．

今年も，Google Developer Day 2011 Japanに参加しようと思ったので，DevQuizやりました．

Top Favorites 枠で当選してしまったので，参加権を得るという意味は無いのですが，GDDの参加目的の半分くらいはDevQuizにあるので，やるしかないです．

ただ，真面目コード書いたりできたのは始めた１日と，最後の１時間だけでした．

結局136.6点．ちょっと残念…．

Web Game

神経衰弱．

こんな感じ．ゴルフしていたわけではなくて，普通に書いたらこうなりました．

(function(){var f=[],c=eval($("script")[2].innerHTML.match(/\[.*\]/)[0]);
for(var i=0;i<c.length;i++){if(!f[i]){f[i]=1;for(var j=i;j<c.length;j++)
{ if(!f[j]&&c[i]==c[j]){f[j]=1;conc.flip(i);conc.flip(j)}}}}})()

Chromeエクステンション作る問題のようだけど，デバッグ面倒くさそうだし，ワンライナーで．

以前はアドレスバーでjsのデバッグしてたのだけど，Chromeがアドレスバーにjavascript:から始まるURLを貼り付けられなくなってしまったのでコンソール使う．ウインドウを開くことを我慢できるならこっちのほうが断然便利ですね．

問題の画面を開いたら，JavaScriptのコンソール画面に上のコードを64回ペーストするだけ．64回ペーストする作業が結構苦痛だったけど心を無にしてやった．

Go!

pngをデコードして色を数えるだけ．特に何も考えずに素直に．

import (
    "fmt"
    "io"
    "strings"
    "image/png"
)

func CountColor(pngdata io.Reader) int {
    img,_  := png.Decode(pngdata)
    rect := img.Bounds()
    colormap := map[uint32] bool {}
    numcolors := 0
    for y:=rect.Min.Y; y<rect.Max.Y;y++ {
        for x:=rect.Min.X; x<rect.Max.X; x++ {
            r,g,b,a := img.At(x,y).RGBA()
            if !colormap[r+(g<<8)+(b<<16)+(a<<24)] {
                numcolors++
                colormap[r+(g<<8)+(b<<16)+(a<<24)] = true
            }
        }
    }
    return numcolors
}

スライドパズル

とくに深く考えずに，手っ取り早く解が出そうな方法で実装してみる．

  • 全探索で一瞬で最適解が出たのが200問くらいだった
  • いい加減な評価関数で枝刈りするようにして3000問くらいに
  • その状態で，探索範囲を無理やり広げて数時間計算させる
  • 調子よさげ…っと思ったら3500くらいで移動回数の制限超えてしまう
  • 2週間ほどHDDの奥で熟成させて，締め切り前の1時間で書き直して，+150個くらい追加

どうせ何度も中断・再開するし，複数のアルゴリズム使いたくなる気がしたので，結果をマージしたりチェックしたりするコードも書いておく．最後に役に立った．

前日のうちにプログラム書いて実行しておくはずが寝てしまったので，30分ぐらいで場当たり的な改良をして，残りの30分くらい２台のノートPCで実行して，途中までの結果を古い結果とマージして提出するという酷い最後．

実際にはもう少し解けてたけど，移動回数をオーバーしてて使えなかったりで結局3662個．

幅優先だとメモリつらそうだなと思ったので，基本は深さ優先で．反復深化深さ優先探索？して，それでだめそうなら，途中結果で良さそうだったところから，再度同じアルゴリズムで繰り返す．

最新版が手元に無いので，一旦ちょっと古いやつを．すごくいい加減な感じが漂ってるし，よく覚えてないけど，きっと3600個くらい解ける？

puzzle_0828.cpp

たぶん後で最新版を少し読みやすいように整形してから貼ります．

2011-08 << 2011-09 >> 2011-10