2007-07-24

文字列追加は線形じゃないととか書いてあったっけ…と思ったら書いてあった。まぁそれ以前に GC 全メモリなめてるのが遅すぎたし書き直すのはめんどうだったというか、ひたすら絵を描く土木作業してるのが楽しかった。

まぁ予想通り私だけ全然違うゲームをやっていたようなのでそれについて少し書いておこうかと思います。

たしか k.inaba さんと同じように手書きは無理だと思ってたけど、最後までへたれた順位だと恥ずかしいので、と少し手で描いた。確か最初に描いた絵は横一直線と fill は少ない命令数でできるから、と

http://shinh.skr.jp/dat_dir/icfpc_yoko.png

遠藤さん生き返すつもりがあるとは思えません。

まぁこれでも空は割と得点が多かったので、もう少し頑張ることにしました。とりあえず命令を圧縮しよう、と move の連打とかは圧縮しておいて DNA で展開するためのロジックを書きました。この時書いたコードは最後まで使えた。

def week_compress(c, i)
  x = ''
  x += 'IIPIP'+asnat(c.size)+'IIFIIF'
  x += 'IFPP' * i + 'IIF'
  x += c
  x
end

def strong_compress(c, i)
  l = 0
  while (c + asnat(l) + 'IIPIP' + 'IIFFIIFIFPPIFPPIIF').size != l
    l += 1
  end
  x = ''
  x += 'IIPIP' + asnat(l) + 'IIFIIFIFPPIFPPIIF'
  x += (c + 'IIPIP' + asnat(l) + 'IIFFIIFIFPPIFPPIIF') + 'C' * (i - 2)
  x
end

week は1つの繰り返し文字列を4文字に圧縮する。要は sub(/HOGEHOGE/,'\1\1\1\1') っていう話。 strong は1文字まで圧縮する、けどなんかバグ入りなのと、あとイニシャルコストが高いので繰り返し数の多いコードの圧縮に。 strong の方は quine の書きかたに似てたのでスラスラ書けた。

でまぁ、空はともかく草原をなんとかしようと思ったのです。草原をよく見ると単純な方法で描かれてるではありませんか。

と、そのころやっと prefix 無し DNA が終わった。ということは RNA が手に入ったーということでその描画っぷりを見て、草原を描くロジックを丸ぱくりすることに。

丸ぱくりしたら恐ろしいことに点数が増えた。しかも圧縮のおかげで prefix は全然使わない。 28B とかわからんなーと他で拾った DNA を適当にインタプリタにかけつつ(ヘボ実装なので当時は5時間かかる)さらに土木工事。

で、一番重要なところなのですが、まぁ target.png 見てりゃすぐに気付くのですが、全体にノイズが乗りまくりで、単色で塗ったりしてもそこらじゅうに不一致の点ができてしまうのです。まぁそりゃそうで、要は私みたいな土木作業野郎に高得点取らせたらまずいわけですね。

でもまぁ DNA 遅すぎて(その上高速化しようとしてバグ埋めたりしてた)やること無いので適当にノイズをせっせと解析していた。

でなんか数時間くらいノイズと格闘した結果だったか、割と簡単な方法でノイズは乗せられてることがわかってきたので、自前でノイズを乗せていったらそれなりにうまくいった。

したら点数がすごく増えて、もう一押ししたら大量発生していた 28B の記録を追い抜かすことができた。

と思ったら 28B の DNA の実行が終わって、そこで方針についてうーんと考えたけど、まぁ DNA 遅いので他の実験をしつつ土木工事も続けることに。そもそもどうせ負けるにしても「ずっと問題の趣旨無視してゴルフしてました!」の方がネタになって良いよね。

後はまぁ…サポートツール(得点計算とか一致してない部分黒くするとか色を作る方法を調べるとか)を使いつつひたすら進めていった。あとまぁ案外難しいことには、 target.png はノイズが乗ってるのでどの色を使えば同じ色になるかわからないことがあったけど、まぁ自分でノイズ乗せる方法調べたわけだし、そこはまぁカンとかそのへんで案外なんとかなった。

あと川とか灯台とかはグラデかかってたり、森は半透明使ってたりするのでどうすればいいかわかりにくいんだけど、そのへんも草原と同じくオリジナルの RNA 調べてなんとかした。で、苦しかったというかできなかったのは後ろの電車っぽいヤツとか吹き出しとかだった。

まぁ今回書いたコードとか。黒魔法とその場の思いつきと眠気とコピペでいっぱいの mk_prefix.rb が力作すぎて D より行数多くなってしまった。 goto とか chdir とかにバグ無かったのは奇跡だよな。

http://shinh.skr.jp/dat_dir/icfpc2007.zip

まぁ私は基本的に頭冴えてる系じゃなくてドロドロ時間使うだけが得意なのですが特技が生かせてよかったです。でも今度正攻法でもやってみようと思います。あとまじめにやってた人ごめんなさい。

あ、あと RNA はまともな色指定できないので found_col.rb もお役立ちだった。バグってるけど。しかしなんで found とか過去形なのかな。

兼雑記

今回のコンテストのメンバー画像？

睡眠コントロールできないので記録