Twitter: @kinaba
長い間、読もう読もうと思って忘れてる本があったような気がしてならなかったのです。 昨日、なにかからの連想でやっと思い出しました。笠原さんの本だ。さっそく購入。今度サインください（私信
Referrer を見ていると、Электрический гвоздодер さんによる ICFPC参加者まとめ がありました。素晴らしい！ Top 15 に名前のあった Begot や ryba も、画像を見ると相当進んでいるようですし、United Coding Team の人も、16位のスコアから考えるとかなりいい線行ってると思う、と書いておられる。 ここにさらに去年の入賞チームである Smartass と Awesome(たぶん) が加わるわけで、 すごい勝負だ…。
昨日の日記、いつもにも増してtypoが多くて俺疲れてるなぁと思った。それはともかく、 住井さんが 興味深い と書かれている点は自分も面白いなーと感じた点でした。
去年ちょっと物議を醸した 「ポインタと整数をキャストできる言語を使えば高速な処理系を簡単に書ける」 問題と違って、今年のは 「関数型データ構造を知ってれば高速な処理系を簡単に書ける」 問題 だったので、ICFP としては見事な出題だったと思います。全然 functional じゃないようを見ながら、いやいやHaskellなら瞬殺だよこれと思いつつSTLをデバッグしてた。
その <ext/rope> のリソース解放忘れもなかなか興味深い。
ropeの提案者は Boehm GC で有名なHans Boehm氏らで、当然ながら(?)、オリジナルの実装は GC の存在を前提としたものになっています （ソースを見ると #ifdef __GC だらけです。）それを GC が無い環境でも使えるようにするために、 参照カウンタを追加した結果がこのバグである、というのが一つ。
もう一つは、ropeが完全に全部C++で書かれてたら解放忘れなんて起きっこないのに…という こと （Mutex 周りは pthread と Win32 API を "C で" 薄くラップしたものでした）。 C++には RAII があって、C++で今の自分が書いたコードは絶対解放忘れを起こさないという自信が持てますので、 原因は rope 側にあると躊躇無く決めつけてデバッグすることができました。
Endoは endofunctor とか endomorphism が由来かと思ってました。ArrowとかMorphとか言ってますし…。
ほげー。終わりました。終了6分前にギリギリ15位圏内に滑り込んだのでたぶん15位です。 今年も凄い気合い入った出来だし、最後の方はかなり面白かったんですけど、 ヒントがわかりにくすぎて何をすればいいのか全くわからんのがキツかった。 というか、いまだに自分のした作業が出題側の想定した作業なのか疑問が。 他の人はどう解いたんだろう。
以下、時系列順の感想です。ネタバレ含んでますので注意。 ただ、正直、このくらいネタバレてないとスタートラインに 立つのすら難しい問題だと思うのだよなぁ…
問題読み始め。「（ ´_ゝ`）フーン星人の遠藤さんが困ってるので助けてあげよう」という問題らしい。
問題読み終わり。「Fuun 星人の DNA は、実は RNA を出力するプログラムなのである。 で、出力された RNA は、(題意はちょっと違うけど要するに) 画像を描画するプログラムなのである。 今の Endo さんの DNA にできるだけ短いコードを付け足して、目的の画像 target.png にできるだけ近い画像 を出力できるように頑張ろう」 という問題らしい。
とりあえず「DNAインタプリタ」も「RNAインタプリタ」も作らずに、 与えられたDNAは完全無視してお絵描きしまくるコードをいくつか書いてみた。 しかし考えるに、1ピクセル書くのに平均10バイトかかってしまうと点数にならないので、 こりゃー無理だろうという結論に。 まさか97984バイトでここまで描けるとは…!! すげーーーーー！！！！
DNAインタプリタの実装とりあえず完了。実装方法は懇切丁寧に問題文に書いてあるので直訳するだけ。 ただし、Section 6 に "文字列のappendは線形時間より速く動かないとキツいよ" と書いてあったので、rope を使うことにした。他の言語のライブラリはよく知らないので言語がここで自動的に C++ に決定。
が、なぜか文字列演算の最中に落ちる。なんでだ。眠くなってきたので typedef rope<chat> String; を typedef std::string String; に変えて実行。10時間くらい終わらなそうなので寝る。
起きたら、問題文に注記されている長さのちゃんとRNAが出力されてた。ということはミスがあるとすれば rope の使い方か rope の実装だ。デバッグ大会開始。
なんかバグ原因を切り分けてったら最終的に
(String("I...130文字...I").substr(0,129) + "I").find("IF");
の一行で落ちるんだけども。えーと STLPort のせいだ俺は悪くない。それともビルドでもミスったかなあ…。
VC++/STLPort をやめて g++の<ext/rope> でコンパイル。動いた。100秒でRNAも全部出た。うあー。
RNAインタプリタを書いた。こっちは D で。問題なく動いているみたい。
で、でも、与えられたDNAの動作を解析する手がかりが何もない。やっぱり全部自力で絵描くしかないの？
RNAインタプリタの要所要所で途中画像をダンプするようにしてみたら、最初の1000命令くらいで DNA文字列っぽい画像が描かれてすぐ黒塗りで消されているのを発見。 早速実行してみたら新たな画像が。
"FUUN FIELD REPAIR GUIDE"。与えられたDNAの使い方が描いてあるマニュアルらしい。これが手がかりか！ さらに「マニュアルのページを取り出すDNAコード」と「周りが暗くて困ったときのDNAコード」が書いてある。 すげー。これでやっと去年で言うumixにログインできた状態か。スタート遠すぎだろ！！
「周りが暗くて困ったときのDNAコード」を使うと28バイトで一気に20万点くらい稼げる。 ScoreBoardにやたら28バイトの人が多かったのはこれだったのか。
マニュアルのページは、"FUUN FIELD REPAIR GUIDE" を得たコード IIPIFFCPICFPPICIICCIICIPPPFIIC を書き換えたコードを実行することで 得られる。右のFをページ数の2進数表記(F=1,C=0,例えばpage.4ならCCF)で置き換え、左の Cは同じ個数のCで置き換える(page.4ならCCC) で置き換えるよろし。 まあこの置き換えにたどり着くのに5時間かかりました。
で、マニュアルのページを取り出しまくってどんどん読んでいく。役に立たない情報も多いけど、
などなど、だいぶDNAを解析する手がかりも揃ってきた。
さっきの「周りが暗くて困ったときのDNAコード」ってよく見たら無駄があるじゃん。27バイト。
関数のアドレス表 (Page 1/14) を参考に appletree 関数を呼んでみたら林檎の木が描画された。 すげー。あれか、こうやって色んな関数を探り当てて目的の画像を描画していくゲームなのかこれは！
と思ったけど、Page 2～14 がどこにも見あたらないのでどうしようもない。もう寝る。
起きた。ところで昨日から思ってたんだけど、自分のDNAインタプリタ、実行している間はOS全体で
のだけどなんだこれ。と思ってタスクマネージャで調べたら思いっきりリソースリークしてた。 デバッグ大会再開。
これで for(;;) { String x = "x"; } もリソースリークするんだけど。
えーと <ext/rope> のせいだ俺は悪くない。もうropeとか死ねばいいのに。
STLのソースを追っていったところ、「マルチスレッド環境で参照カウントするために、
ropeの各ノード毎にCreateMutexしてる。」「でもCloseしてない。」。こんにゃろう。
今とりあえずシングルスレッドで用は足りるので、mutex周り全部コメントアウト。直った。
快適快適。ついでにDNAインタプリタが倍速になった。
で、結局、どこに Page 2 ～ 14 が隠してあるのか、というかそもそもそんなページが存在するのか もわからなかった。やむを得ない。主催者側からのヒントなどに頼らず力業でバイナリ解析してやるわい！！
DNAを先頭からステップ実行していくことで、普通のアセンブラ/機械語の命令が どんな風にDNA語にエンコードされているかを探ることにした。
他色々、眺めているとやり方がだんだんわかってきた。
先頭からじゃなくて appletree 関数とか apple 関数をステップ実行してみるとどうだろう。 と思ってやってる最中に「林檎を緑に塗る」方法がわかった。これでちょっと点数アップ。27バイト帯を脱出。 でも眠いので寝る。
しかし、やっぱり、他に関数がわからないとどーにもこの先無理です。うーん。 でも、今の自分にはcall命令とret命令がどうDNAで表現されているかがわかっている！ この二命令のトレースをとって、関数のアドレス表を一気に全部ゲットだぜ！
アドレス表はとれても、それぞれの関数がなにやってるかわからない。しゃーない。それぞれ実行させてみて、 画像が出てきたらそれはなんか描画用の関数だ。ということで、必死に手作業で、アドレス⇔描かれるオブジェクト の対応表をつくっています。
なんか「色を変える」のが簡単なことに気づいたので、右下のマゼンタっぽい物体を描いてる関数の アドレスからステップ実行でコードを見てみました。これまた黄色に塗り替える方法がわかったのでsubmit。 でも、他には色変えで対処できる画像がない。
「実行トレースで関数アドレスを収集する法」の欠点は一度も呼び出されていない 関数のアドレスが集められないことです。つまり「元画像にないけどターゲット画像にあるオブジェクト」 を描画するのは今の自分ではできない。
やれるのは、「元画像にはあるけどターゲット画像にないオブジェクト」を消去することだけだ。
「消したいオブジェクトの描画関数を必死に探す」 → 「その関数の先頭をret命令で置き換える」 の繰り返しでチビチビとスコアを縮めている途中でタイムアップ。なんという Binary Hacking コンテスト。 みなさまお疲れ様でしたー！
終了後、kuma-- の人から「関数アドレス表 (Page 2 ～ 14)」の入手方法を教えてもらう。 Page 1 をよく見てちょっと実験してみればわかったとのこと。その発想はなかった…。 それがあれば全然作業効率が違ったよ！つーかそこが本当のスタート地点だな。 スタート遠すぎ！！
最終的な画像。遠藤さんはどっか行った。
ソースとメモのかたまり.zip。d2r.cppがDNAインタプリタで
r2p.dがRNAインタプリタ。fuun.dがprefix生成につかったDSL。
ニコニコ動画で笠原弘子で検索してみたら シンフォニック=レイン てのの曲が引っかかって、思わず衝動買いしてしまったりした今日この頃です。 なんでこんな暇な日記を書いてるかというと、ICFPC、次何をすればいいのかわからんまま 一日が過ぎてしまったのでした。力押し突撃するべきなんだろうか。うーん。 スコア 見た感じでは 自分含めた並の上位陣より遙かにshinhさんの方が先を行ってるように見える。流石だなあ。
あ、私のチーム名は kokorush です。今年は kuma-- と別だったりする。タイトルの "Morph Endo!" を読んだ瞬間には mame っちが 変形する様を想像して一人で吹いてました。
The 10th ICFP Programming Contest が迫って参りました。日本時間で 7/20(金) 19:00 ～ 7/23(月) 19:00 の３日間のコンテストです。 みなさま土日を潰して参加すべし。"Lightning Division" という部門もあって、こっちは最初の24時間 (～21(土) 19:00) の成績を競います。Rapid Programmingには自身がある方、忙しい方はそっち狙いで 参加するのが面白いかも。
あと、ICFPのコンテストといえば、去年の全システムのソースコード が公開されたらしいですよー。
キミならどう書く - その２。 出遅れたので parse と eval したら負けかなと思うことにしました。普通の優先順序なら：
from rational import Rational
def e(i,j): # e ::= t | e ('+'|'-') t
for x in t(i,j):
yield x
for m in range(i+1,j):
for x in e(i,m):
for y in t(m,j):
yield x+y
yield x-y
def t(i,j): # t ::= f | t ('*'|'/') f
for x in f(i,j):
yield x
for m in range(i+1,j):
for x in t(i,m):
for y in f(m,j):
yield x*y
yield x/y
def f(i,j): # f ::= number
yield Rational(reduce(lambda x,y:x*10+y, range(i,j)))
print '%d pattern(s) found' % list(e(1,10)).count(100) # ちなみに 101 と出ました
有理数演算は odz さんの Rational クラス をお借りして実験しました。整数演算にしたい場合、f で Rational 化しないでそのまま 整数を返して、あとtの最後で if y: yield x/y にすればＯＫです。電卓方式にするなら、 eの定義をこう変えます。
from rational import Rational
def e(i,j): # e ::= f | e ('+'|'-'|'*'|'/') f
for x in f(i,j):
yield x
for m in range(i+1,j):
for x in e(i,m):
for y in f(m,j):
yield x+y
yield x-y
yield x*y
yield x/y
def f(i,j): # f ::= number
yield Rational(reduce(lambda x,y:x*10+y, range(i,j)))
print '%d pattern(s) found' % list(e(1,10)).count(100) # ちなみに 68 と出ました
まあ要するに、式の文字列を生成するフェーズと、実際にその式を評価するフェーズを混ぜただけという。 "1□2□...□9" を非決定的にparseしていると言ってもいいかもしれません。 解の個数だけじゃなくて具体的な式も見たいときは、Rational の代わりにこんなんを突っ込めば 式文字列まで生成されるようになります。
class Expression(object):
def __init__(self, data, repr=None):
if isinstance(repr, str):
self.data = data
self.repr = repr
else:
self.data = Rational(data)
self.repr = str(data)
def __add__(self, other):
return Expression(self.data+other.data, self.repr+"+"+other.repr)
def __sub__(self, other):
return Expression(self.data-other.data, self.repr+"-"+other.repr)
def __mul__(self, other):
return Expression(self.data*other.data, self.repr+"*"+other.repr)
def __div__(self, other):
return Expression(self.data/other.data, self.repr+"/"+other.repr)
def __eq__(self, other):
return self.data == other
def __str__(self):
return self.repr
...
def f(i,j):
yield Expression(reduce(lambda x,y:x*10+y, range(i,j)))
...
for x in e(1,10):
if x == 100:
print x
shinhさんの Brainstuck のチューリング完全性について考えてみた。といっても、自分にはそのままだと足し算 [a,b] → [a+b] すら書けなかったので、ちょっとだけ拡張してみる方向で。 スタックトップしか書き換えられないのが辛いと思って最初に考えたのが、こんな感じの命令を入れたら
* => スタックトップと２番目の値を交換 {int t=x[xc-1]; x[xc-1]=x[xc]; x[xc]=t;}
0:[*+*-0:][0]
こう足し算書けるなあ、というの。んで、* を入れた状態で証明しばらく考えた結果、もっと単純な
" => スタックの２番目の値を削除 {x[xc-1]=x[xc]; xc--;}
00++:[0++:-0++:0+0++:]0+: 0+:["""+0+:] """ // 足し算
だけ増やせば行けるという結論になりました。
まず Bf実装法 という素晴らしい証明法を 実践しようとして即挫折。別の方法を考えよう。以下、スタックに入る１個１個の整数はどんな大きさの数でも入る 数学的な意味での整数ということにします。8ビットとか32ビットということにして、マジメに多倍長を 実装できるかどうかは不明。
チューリング完全な計算モデルとしてはチューリングマシンやλ計算が有名ですが、 帰納関数 / Recursive Function というのもあります。えーと要するに
zero = fun () -> 0
= 0
succ = fun x -> x+1
= +
proj[n,i] = fun x1 x2 ... xi ... xn -> xi
= [0][0]…[0][0]"""…"""
という関数が書けて、すでにある関数と関数を合成したのと同じ動作をする関数
comp[f,g1,...,gn] = fun x1 ... xn -> f( g1(x1...xn), g2(x1...xn), ..., gn(x1...xn) )
も書けて（"関数合成をする高階関数が書ける"が条件ではなく、なんか関数f,g1,...,gnがあるときに、 その合成と同じ働きをする関数が書ければＯＫ。例えば↓こんな風にhogehogeが書ければＯＫ
int f(int x, int y) { return x+y; }
int g1(int x, int y) { return x*y; }
int g2(int x, int y) { return x/y; }
int hogehoge(int x, int y) { return (x*y)+(x/y); }
// Brainstuckで、例えばf,g1,g2が全部2引数関数の場合は↓こんな）
comp[f,g1,g2] = 0+:0+: g1のソース 0++:0++: g2のソース fのソース ""
で、さらに帰納法ぽい再帰ぽい計算をする関数が書けて
pr[g,h] = fun x y1 ... yn -> if x==0 then g(y1,...,yn) else h(x-1,y1,…,yn,pr[g,h](x-1,y1,…,yn))
// Brainstuckで、例えば3引数関数(x,y,z)の場合は↓こんな感じ
// x y z 0 x-1 y z 1 x-2 y z 1 ... 1 y z 1 0 y z 1 g(y,z) という状態を作ってhで畳み込み
0 0+++:[0+++:- 0++:0++: 0+ 0+++:] 0+ 0++:0++: gのソース
0+: [ " hのソース 0+: ] """
で、最初に0になる引数を探す関数が書ければ
find[g] = fun x1 ... xn -> min [y | g(y,x1,...,xn)==0]
= 0 0+[+ 0: 0++: gのソース] " // 例えばgが2引数ならこんなん。普通にループで探すだけ
そのプログラミング言語はチューリング完全だよという話でした。おしまい。
問題 1 : 油売り算 を解いてみる。 Cでもできるようなことしかしてないですけど言語は適当にPythonで。 コード色々いじってたらいつの間にかpath_to の無駄さが酷いことになってしまったけどまあいいや。
from __future__ import division
# startからgoalまでのpathを探索
def search_path( start, is_goal, next ):
agenda = [start]
path_to = {start: []}
while agenda:
s = agenda.pop(0) # BFS (for DFS, change pop(0) to pop())
if is_goal(s):
return path_to[s]
for n,p in next(s):
if n not in path_to:
path_to[n] = path_to[s] + [p]
agenda.append(n)
# 油売り問題の場合
def aburauri( *oke ):
start = (oke[0],) + (0,)*(len(oke)-1)
def is_goal(s):
return list(s).count(oke[0]/2) == 2
def next(s):
for i,j in ((i,j) for i in range(len(oke)) for j in range(len(oke)) if i!=j):
a = min(s[i], oke[j]-s[j])
if a:
s2 = list(s)
s2[i] -= a
s2[j] += a
yield tuple(s2), "%c から %c に %d 升移す" % (97+i,97+j,a)
for p in search_path( start, is_goal, next ):
print p
aburauri(10, 7, 3)
# a から b に 7 升移す
# b から c に 3 升移す
# c から a に 3 升移す
# b から c に 3 升移す
# c から a に 3 升移す
# b から c に 1 升移す
# a から b に 7 升移す
# b から c に 2 升移す
# c から a に 3 升移す
いつ "に全部戻して" を出力すべきなのか問題文からよくわからんかったので、出力は適当です。 a に移すときだけ出せばいいのかな。問題文の出力例と同じ方法を求めるには、pop(0)をpop()に変えて 深さ優先探索します。つまり幅優先と深さ優先の違いなんてものはたった1バイトであるといいたかっただけなのでした。 agendaをqueueとして使えば幅優先、stackとして使えば深さ優先、なんか評価関数を定義して heap(priority_queue)にすれば最良優先とか。
で、そんなことはどうでもいいのですが、なんか思ったよりも全然綺麗に書けなくて難儀しました、next関数が。 タプルの要素を２カ所置き換えた新しいタプルを返す、ってもっとずっとマシに書けるような気がするのだけど…。 うーん。