kdoo

書いてる人: ょゎ
hatena:id:yowa, Twitter/yowa, Gmail:yowaken
«前3日分 追記

2010-07-14 [長年日記]

>> TopCoder はじめました このエントリを含むはてなブックマーク

まだ practice やってるだけだけどなー。

日記はこちら → yowa の TopCoder 日記 - TopCoder部 (http://topcoder.g.hatena.ne.jp/yowa/)

本日のツッコミ(全1件) [ツッコミを入れる]

>> warsitanterve [Getting an instant height boost from heel Lifts isn’t just..]


2010-06-22 [長年日記]

>> ICFPC 2010 おわったよー! このエントリを含むはてなブックマーク

まとめ: 比較的早い段階で最初の一歩を踏み出して、そこから身動きが取れないまま終了だった。

問題文はこちらmr_konn さんによる日本語訳*1)。

実際の作業の流れは、みんなこんな感じだったんだと思う。

  • 問題文を読む。
  • 燃料出力回路("19L: 12R13R0#1R12R, ... "みたいなやつ)の syntax を推測する。
  • 自分で回路を構成し、#219の車の fuel として投入し、その出力からゲートの機能を推測する。
  • 燃料出力回路に入ってくる input stream を推測する。(場合によっては不要)
  • key prefix を出力する回路を作る。
  • 狙った出力が得られる回路を作る方法を構成する。
    • ↑ ここまでできた
  • 数の列...の列を表現する、三進ストリーム(122000010 みたいなやつ)の syntax を推測する。
  • 数の列...の列を、車としてどう解釈するのかを推測する。
  • 数の列...の列を、燃料としてどう解釈するのかを推測する。
  • 特定の車にたいして、それに適合する燃料を作る。
  • 自分で車を作り、それに適合する燃料を作る。
  • 燃料をゴルフする(コードが短い方がスコアが高い)。

以下、答えネタバレがあるので、注意する人は注意。

(期日終了後もゼロからチャレンジできるんだっけ?)


燃料出力回路の syntax を推測する

これは素直だった。2入力2出力のゲートを使ってるってことが分かってたので、 L, R が端子で 前の数値はゲート番号(= 行番号できまる)、区切りの左が入力元、 右が出力先と。

0L: X0R0#X0R: 0L

だったらこんな感じ。

       ┌─┐ 
入力→──→│ゲ│→───→出力
      │││         
    ┌→│ト│→┐
    │ └─┘ │
    └─────┘

ゲート機能を推測

とりあえず

回路: 0L:X0R0#X0R:0L -> 出力: 02120112100002120

みたいなのが得られるようになったので、 ゲート数の少ないシンプルな回路をいくつか投入し、出力をメモる。

ゲートの左出力をL(x,y)、右出力をR(x,y)、(未知の) 入力文字列を i0, i1, i2, ... とすると、上の出力例では

時刻 t
  0   L(i0, 0) == 0        
  1   L(i1, R(i0, 0)) == 2
  2   L(i2, R(i1, R(i0, 0))) == 1        
  :

みたいな関係がわかる。

ゲートの出力を、前の入力に戻す形(上の図の下部みたいな)だと、 時刻 0 の出力は不定になりそうだけど、とりあえず 時刻 0 では 0 が入ると 仮定した(この仮定は当たった)。

また

0L:X0L0#0RX:0R -> 22120221022022120

から、

時刻 t
  0   R(i0, 0) == 2
  1   R(i1, L(i0, 0)) == 2
  2   R(i2, L(i1, L(i0, 0))) == 1        
  :

が分かって、最初の t=1 と次の t=0 を合わせると

L(i1, 2) = 2

が得られる。みたいなパターンマッチを(Ruby で)やることで、 ゲートの出力パターン 3x3x2 が全て埋まった。

      L(x, y)            R(x, y)

       y=0 1 2            y=0 1 2
  x=0    0 2 1       x=0    2 2 2
    1    1 0 2         1    2 0 1
    2    2 1 0         2    2 1 0 

input stream を推測する。

これは上の、パターンマッチの延長。

L(i0, 0) = 0

で、L(x, 0) = 0 になるのは x = 0 のときだけだから、i0 = 0 がわかり、 それを使ってさらに次の推測へ(実際はゲート推測と並行して行っていた)。

input stream: 01202101210201202...

key prefix を出力する回路を作る。

問題文に書いてあるサンプル回路と入力を動かすと、

key prefix: 11021210112101221

が分かるので、次にやるのは input stream をもらって、key prefix を出す回路の作成。

だが、特定の出力を 17 文字も出すような回路、どうやって設計したもんだか わからぬ。 三進の17文字だから 3**17 パターン。1.3億くらいか。

…… 1.3億分の1 くらいなら、ランダムでも現実的な時間で引き当てられるんじゃね?

とゆーことで、(最初は Ruby でやってたけど、さすがに1億 iteration はムリなので)C で書く。ゲート数は(なんとなく) 20 に決め打って、 41個(入力端子 20x2 + 回路の出力)をランダムな相手につないで走らせる、 の繰り返し。

3000万 iterate くらいであっさりと解が求まり、それをサーバにうp。

Congratulations!

キタコレ!

この時点で「既に解いてる人: 7人」とか表示されたので、 「うひょ〜、はやいんじゃね?」とか思いながら、初日はここで寝る。

この時のメモ

まあ、これが通っても全く発展性がないんだけどね……。[2010-06-19 05:22:40]

迷走

起きる。

スコアテーブルの上のほうに

0.664 yowa

とあって「おお!」とか思う。

そして迷走。

「ゲート数 20 で通ったけど、もっと少なく出来るんじゃね?」 (ゲート数が少ない方が高得点なので)と思い、ゲート数 15 の解を見つけたり、

「3**17 < (7*2+1)! だから、ゲート数 7 でも行けるんじゃね?」と、 ゲート数 7 の解を見つけたり、

「(6*2+1)! くらいなら、総当たりでいけるんじゃね?」と ゲート数 6 の解を見つけたり(ゲート数 5 以下に解がないことも確認したり)。

もしも時が戻るのなら、この時のオレに、寝る前に書いた 「まあ、これが通っても全く発展性がないんだけどね……」というメモを 100遍音読させたい。

三進文字列の syntax の解読……したいなあ

車も、燃料(の key prefix 以降)も、syntax が同じ三進文字列になっている。 ので、車のコードを見れば syntax が何かわかるんじゃないかと思い、 その時点でうpされていた車のコード(10種くらい?)を並べてにらめっこ。

(これは終了後の感想だけど、(問題文にもあるように)ここでは、 「サーバにデータを送って出力を得る」をとにかく繰り返して、 syntax error を元に推測しておくべきだった。 ゲート推定が少なめのサンプル数でいけたので、 こっちもなんとかなると思い込んでたっぽい。)

んで、「なんか "22" が多いなあ。これ区切り?」みたいな思いつきはあるものの、 そこからどうしていいかがよく分からず。 key prefix を出力する燃料を用意して、車として思いつきの三進文字列を 投げてみるけど、 「syntax は合ってるけど、車の条件を満たしてない」的なことばかり言われて どう読み取っていいかが分からない。 (だから、syntax が合わない入力でもっと挑戦しなさいって。)

やることを見失ってる。 [2010-06-19 17:26:49](残り 51時間半)

鯖不調の間ぷよるつもりが1時間以上。 [2010-06-20 03:07:32](残り42時間)

もう、やるきないよ! [2010-06-21 00:41:00](残り21時間)

半歩進む

ここで Twitter で #icfpc とかを検索してたら、 「定数出力を行う回路」的な発言を複数の人がしてるのをみかけた。

じゃあオレもやってみるかと思い、(ゲート出力の割り当て的に一番簡単そうな) 2 を出力し続ける回路に挑戦。……もちろん総当たりで。

サイズ 4 以下では見つからず、サイズ 5 で発見。あとは

L(2, 2) = 0
L(0, 2) = 1

を使えば、0 と 1 の定数出力もできる。

ここらで 「『最初の一文字は左入力、残りは右入力をそのまま出力』という回路と、 『入力を一文字遅らせる(最初に何かいらないやつをつける)』という回路を 組み合わせれば、任意の出力いけるんじゃね?」的な思いつき。

まずは「入力を一文字遅らせる」を(もちろん総当たりで)見つけた。 頭に 0 がつくらしい。

ここで初めて「あと『最初に 1 をつける』『最初に 2 をつける』 が揃ったら、出力側から順に直列つなぎすれば、好きな文字列が作れるじゃん!」と 気づいた。 (たぶん、ほとんどの参加者は key prefix を通す前に、これに気づいてる)

ということで、

NUM0 = Circuit.parse("1R:2R1L0#X2R,2LX0#0R2L,1R0R0#1L0L:0L")
NUM1 = Circuit.parse("2L:1R2R0#2R1R,2L0R0#X0L,X0L0#1L0R:1L")
NUM2 = Circuit.parse("2R:1R2R0#2L1L,0R2L0#X0L,0LX0#1R0R:1L")

を(総当(ry)見つけた。これが半歩前進。

これでサーバでできることがかなり増えたので、いろいろ作業ができる…… と思ったが、この頃になるとサーバが 503→使えるようになる→また 503 みたいな繰り返しに。 単純作業の繰り返しなら、機械的に(503 なら待って retry とか)できるん だろうけど、まだ「入力をあたえる→結果を得る→いろいろ考える→ 次の入力を決める」の段階なので、結果が得られないとストレスがたまるで ござるよ。

一年ぶりに pixiv に絵をうpしたり 不貞寝したりしながら終了時刻を迎えた。

振り返り

Ternary Streams

This wasn't the ICFP contest if it was that easy.

ICFPcontest - Task(問題文)

The circuit design, and the ternary coding, were really there just for the fun of obfuscation. On the other hand, with Cars and Fuels, there’s a real story: (後略)

What’s this thing with Cars and Fuels? -- The 2010 ICFP Programming Contest Blog(公式ブログの、終了後エントリ)

上にあるように、今回の大会において(回路設計と)三進コーディングは 「ICFP 的なお楽しみ」要素で、本題はその先だったのだが、 私はみごとに obfuscated だった。

やはり迷走が悔やまれる。 回路設計を先にやってれば、(サーバの混んでない)早い段階で試行錯誤を できるチャンスがあったわけで、三進文字列の解読もできたかもしれない (できなかったかもしれない)。

Twitter がきっかけで半歩進むことができたように、 ハマりからの方向転換を容易にするためにもチームを組むのは有用なんだろうな、 とか思った。

まあ来年も(やるなら)1人でやるけど (だって、チームメンバーにおもしろいトコ先に取られたらイヤじゃん!)

今年の問題について

それを語れるほど、解けてません!

鯖重

中盤以降、サーバが断続的に落ちていたのは残念だったが仕方ないっちゃ 仕方ないんだろうな。

「お楽しみ」部分がリバースエンジニアリング系なので、 試行錯誤が多数発生し、サーバが重くなるのは不可避だけれども、 (やはり、問題がリバースエンジニアリング系なので) 去年の仮想VMの実装・コードのペアのように、 ローカルで動く環境を用意するのが難しかったんだろう (コード読まれたら、リバースエンジニアリングがより簡単になるので)。

また本題の方も、上位になるには多数の回答を機械的に送ることが必須 なので、やっぱり重くなる。

あとスコアが人数割りなので「自分の回答が通った後は、 DoS って他の回答者を妨害した方が有利になる」なんて黒い話もあったり なかったり。

*1 ありがたや。期間中に問題文が微修正されてるので、多少訳が異なる部分もある


2010-06-17 [長年日記]

>> 今年の ICFPC は (日本時間)6/18 21:00〜 このエントリを含むはてなブックマーク

年に一度の ICFP プログラミングコンテストですよー。明日ですよー。


去年は最後の課題まで到達できなかったので、今年はそれを目標にしよう。 問題の構成によっては「最後の課題」なんて無いかもしんないけど。

2008年が火星探査機で、2009年が衛星軌道操作と、モノを動かす系のが続いたので、今年は全く違う方面の課題になるんじゃないかなあ。

期間中、途中経過を Twitter でつぶやくのはマズいと思うので(ネタバレ的な意味で)、なんかタイムスタンプ付きで気軽にメモれる環境を用意しておこうっと。

そういえば、去年の開催後に shinh さんが提案してた 「期間中にルール議論と馴れ合いができる場があったらいいね」みたいな話は実現するのかな?


«前3日分 追記
2005|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|09|
2010|01|02|03|04|06|07|

最近のコメント

あわせて読みたい