カテゴリー
General

ICFP 2011 速報

今年は @ohkura 君と2人で参加していました。チーム名は Mox Caml です。タップするとコンビネーターが出てきます。
まず、problem description をちゃんと読んでいなかったので、example に書いてある関数適用の方法と再帰呼び出しの方法に無駄に悩んでいたことは反省すべき。ohkura くんが自力で気づいたときは無駄に感動しあい、後ほどおもいっきり脱力しました。
1日目は simulator を書きながら attack や dec の使い方を考えていました。関数適用回数制限をチェックしない AI で invalid になりまくっていたが、理由を長い間理解できず。
2日目には attack も help をホイミにするのも慣れて結構上位に来る。このころの AI は最初に help ホイミを無限ループでうって HP 65535 のスロットでただただ敵を殴るものでした。そのうちゾンビに手をつけていき、夜ごろに使っていた AI は dead slot を 1 個作って、あとは敵の生きている slot に zombie + help でギアスをかけて2匹ずつ処分するもの。Help の引数には copy を仕込んで自分の 0 1 2 … 番スロットを読ませるようにするとゾンビで送りつける命令を造り直さなくても済むことに気づいてちょっと高速化。なにもしない npc なら1500 step ぐらいで倒せるようになる。
70時間目ぐらいのころ、やっと変数を increment できる loop を書いて dec で敵全体にイオをうってみるが、最終版には活かせず。結局2日目のやつに revive や Help heal の微調整、スロット番号の調整など小手先でいろいろ頑張ったものを提出しました。
今年も楽しかったです。運営のみなさまありがとうございました。

カテゴリー
NHC

ICFP 2010

与えられた問題を72時間かけてプログラミングで解く ICFP contest が今年も開催されました。今年は日本時間6月18日金曜21時から月曜21時までで、去年と同じく月曜日には有給を取りました。1人チーム (チーム名 riesz) で挑戦です。
スタート時間ちょうどに帰宅して問題を読みはじめ。あたえられたものは以下の3つ。
ルール http://icfpcontest.org/2010/
問題 http://icfpcontest.org/2010/task/
解答送信サーバ http://icfpcontest.org/icfp10/
問題文はところどころあやふやだったり、はっきり書いていなかったりして謎解きが必要になっています。
o 車の設計と燃料の設計が課題
o 車は upper と lower の2つの燃焼室をもっている
o 各燃焼室の途中で燃料と空気を混ぜ、空気の成分を変化させていく
o 燃焼室の廃棄がある条件を満たすと車は動く
o 参加者が提出するのは新しい車の設計図とその燃料、または他の参加者が提出した車に適した燃料
o 参加者は提出した燃料にあわせて報酬を貰える。燃料の供給者が少ないほど高い報酬
だいたいこんな感じです。個人的には 2007 年の Endo さんと同じぐらい面白かったです。みなさんも是非トライしてみてください!
ここまでかいて面倒になったので、以下、参加者にしかわからない適当な tweet 集をもって write up とさせていただきます。
ソース http://gulfweed.starlancer.org/gem/icfp2010/
問題読み終わったものの、なんだかわからない。とっつきやすそうな回路図の解読を試みる。
上が in で下が out かな。なんで ‘,’ だけじゃなくて ‘:’ が delimiter になっているんだろう。あぁ、最初と最後という以上の意味はないか。外部ゲートかな。
# の前の数字は何?あー、ゲートの種類か何かかな。3日目にゲートの種類が増えたりするのかな。
とりあえずサンプルや自分で作った最小限の回路を提出サーバに食わせてみよう
真理値表なんとかわからないかな・・・どうも、分析に使えるのは backward wire (要はラッチ入り wire) のみ。ラッチの初期出力が 0 と仮定して

外部入力 -> 0のL
0 ->外部出力 0のR

てな回路の出力を使えば分かりそう。
真理値表できたー
さすがに手で生の circuit descriptor 書いてるとつらいな。graphviz 的なフォーマットが使えるようにツールを作ろう。C++ でコーディング開始。
https://twitter.com/riesz/status/16492370314
全部0, 全部1, 全部2 の回路をゲットした
4:20 AM Jun 19th
使えそうな回路ができてくる。でも、こういうパーツができたところで、external input は分岐できないから、そう簡単には組み合わせられない。1つの回路にした時点で external input ではない何かを入力する必要が出てくる。
あー、入力ストリームもわからんし、どうしたらいいんだ
モンテカルロ、モンテカルロ、・・・無駄に時間 (現実も CPU 時間も) が過ぎてゆく
3 ゲートで identity できるじゃん。これに食わせれば入力ストリームが・・・
https://twitter.com/riesz/status/16517120895
やっと input がわかった #icfpc
12:02 PM Jun 19th
求めた入力ストリームのことはすっかり忘れて、一方

外部入力 -> nのL
0 -> 外部出力 nのR
1 -> 0のL 0のR
2 -> 1のL 1のR

n -> n-1のL n-1のR

みたいな回路 (通称 数珠) を使えば入力に関係なくきまったストリームが作れることに気づく。
and its input [0,2,2,2,2,2,2,0,2,1,0,1,1,0,0,1,1] これは結局何?・・・あぁ、これをサンプル回路に食わせると prefix が出てくるのか。なるほど、prefix はこれね。
でも出てくるストリームを調整する方法がわからない。どうにかして permutation 回路が作れないかと頑張るが無理。
数珠をたくさん作ってツリーにすればいいのかな・・・いや、わけがわからない
ねじればいいのかな。あれ、最後の方 0 と 1 しかでなくなった。だめじゃん
あー、もうわからん。とりあえず forward wire でノードを追加して permutation を試みてみよう・・・お、うまくいった!
https://twitter.com/riesz/status/16532449649
key できたあああああああああああああああああ #icfpc #icfp
5:32 PM Jun 19th
prefix のみの circuit は 35 nodes

% ./circuit_console.exe [~]
target> 11021210112101221
Circuit: 34L:3L3R0#1L1R,0L0R0#X34R,4L4R0#3L3R,2L2R0#0L0R,7L7R0#2L2R,
8L8R0#6L6R,5L5R0#7L7R,6L6R0#4L4R,12L12R0#5L5R,13L13R0#10L10R,
9L9R0#11L11R,10L10R0#12L12R,11L11R0#8L8R,14L14R0#9L9R,16L16R0#13L13R,
18L18R0#16L16R,15L15R0#14L14R,22L22R0#18L18R,17L17R0#15L15R,23L23R0#20L20R,
19L19R0#21L21R,20L20R0#22L22R,21L21R0#17L17R,24L24R0#19L19R,26L26R0#23L23R,
27L27R0#26L26R,25L25R0#24L24R,32L32R0#25L25R,33L33R0#29L29R,28L28R0#30L30R,
29L29R0#31L31R,30L30R0#32L32R,31L31R0#27L27R,34L34R0#28L28R,X1R0#33L33R:1L

さて、ここから先の input はどうなっているんだろう。周期12っぽいな。まぁ、このbackward wire 数珠使ってる分には関係ないんだけど
そもそも fuel の仕様はどうなっているんだろう・・・ためしにいろいろ作って submit してみよう。
有用なエラーメッセージがぽんぽん出てくるな。
なんか知らないけど2台目が通る。prefix + 1111111111… ってならべただけなのに
car submission では fuel submission みたいに複雑な回路 (少なくとも prefix が正しくないと有用なエラーが見られない) を造らなくても、適当に3進数をいれるだけでいろいろなエラーや対応する10進数値が帰ってくることがわかる。自然数エンコードの解析が楽になった
https://twitter.com/riesz/status/16540590740
Lightning division is over. 23rd place. No car submission. #icfpc #icfp
9:00 PM Jun 19th
でたらめな入力に対して 10那由他ぐらいの tank 番号が出てくる。表現力あるな・・・
会話しながらどんどん数値表現表とエンコード仕様を分析していく。
fuel フォーマットは大体理解。Car フォーマットもおおよそ理解。間に挟まっているのは main chamber フラグか。num_chamber や num_sections と fuel_id ではエンコードが違うんだな。罠
あきらかにとけていない問題に OK がかえってくる。あぁ、overflow か。多倍長整数にしなきゃだめだな。めんどくさい・・・
2次元行列の探索も冪零が必要な場面でうまいこと活躍してるみたいだ。
Chamber 0 : fuel0 > fuel1 の 665乗, Chamber 1 : fuel1 の 666乗 >= fuel0 みたいな条件の車に出くわす。2の666乗はさすがにでかすぎるだろう。いや、でも10那由他出たし・・・
線形な増加にしようと上三角行列なんかを駆使しようと試みるも、0行0列の要素はどうあがいても増えない。
いろんな人に追い抜かれて40位ぐらいになる。更新が止まっていたっぽいので、結構前からおちていたのかもしれない。
だらだらと 1chamber main upper = (0 0 0 0 0 0 0 0 … 0) lower = (1) 系の単純な車に手作業で燃料を入れ続ける。虚しい
666乗問題が解けなくてくやしいので、簡単な convert ツールだけでも Java で作ることに。
いろいろ分析して自然数 parser & formatter の if switch をまとめていくと綺麗な形に。一般化成功。あぁ、これ 2^666 ぐらい軽く入るじゃん!
https://twitter.com/riesz/status/16651760840
そしてにっくき 9748 を倒した #icfpc #icfp
多倍長さえ対応すれば解けそうな問題にしょっちゅう出くわすため、結局、もっとも無難な Java の BigInteger を使うべく、C++ からコードの大半を Java へ port。
https://twitter.com/riesz/status/16671437788
C++ -> Java porting おわったぁ。最低限必要な部分だけだけど。 #icfpc #icfp
fuel descriptor がわかっても回路生成器が遅くてどうにもならないケースがあるな・・・
回路生成器に小手先の最適化をいくらか施した。あんまりかわらない
https://twitter.com/riesz/status/16680948704
そろそろ自動化するか・・・570台も手で submit したわけか #icfpc #icfp
提出は LWP あたりで。Car descriptor を Java の solver に渡して結果を・・・えー、Perl の open + パイプって読み書きはできないの!IPC::Open2 を使えって?CPAN めんどい。一方ロシアは引数を使った
ログイン処理とか面倒そうだな。Chrome でログインしてから JSESSIONID を確認して、ハードコードしちゃおう。
あぁ、なんかどんどん submit できてるけど点数増えないな。あぁ、終わる・・・
結果

score: 356.684
others’ cars solved: 801
cars submitted: 3
46th place / 872 participants

眠い

カテゴリー
General

En Google modified by Gulfweed 0.08

とりあえず新しい UI に対応しました
インストール
正常に更新されない場合は一度 Greasemonkey を無効にして
上記リンクを開き、強制リロードをかけてください。

カテゴリー
General

Chrome 版 En Google

最新版 0.071 の Google Chrome extension パッケージ版を当サイトからも配布します。インストールはこちらからどうぞ。詳細は同ページの更新履歴を参照して下さい。

カテゴリー
General

En Google modified by Gulfweed 0.07

バグのせいで Firefox 2 で動作しなくなっていました。修正版です。
unnonouno さん報告ありがとうございました。
インストール
正常に更新されない場合は一度 Greasemonkey を無効にして
上記リンクを開き、強制リロードをかけてください。

カテゴリー
Programming

C# の文字列ソート

つい忘れてしまうのでメモっておきます。
.NET Framework の String.CompareTo(String) は Char.CompareTo(Char) と異なる基準で文字を比較します。List<String> と List<Char> に ASCII 文字をつっこんで List<T>.Sort() すると一目瞭然です。List<T>.Sort() はデフォルトで CompareTo 使うため、これで違いを確認できます。


using System;
using System.Collections.Generic;
...
List c_list = new List();
List s_list = new List();
for (int i = 0; ' ' + i <= '~'; i++) {
char c = (char)(' ' + i);
c_list.Add(c);
s_list.Add(new string(c, 1));
}
c_list.Sort();
foreach (char c in c_list) {
Console.Write(c);
}
Console.WriteLine();
s_list.Sort();
foreach (string s in s_list) {
Console.Write(s);
}
Console.WriteLine();

結果は以下です。


!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
'- !"#$%&()*,./:;?@[]^_`{|}~+<=>\0123456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ

List<Char> のほうは ASCII コード順にソートされていますが、List<String> のほうはなにやら愉快なことになっています。
String.CompareOrdinal() という Char.CompareTo(Char) と同じ基準で比較をするスタティックメソッドがあるので、これを delegate にして渡してやると同じ結果になります。


s_list.Sort(delegate(string a, string b) { return string.CompareOrdinal(a, b); });


!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

カテゴリー
General

En Google modified by Gulfweed 0.06

仕様変更に対応しました。
インストール
正常に更新されない場合は一度 Greasemonkey を無効にして
上記リンクを開き、強制リロードをかけてください。

カテゴリー
General

En Google modified by Gulfweed 0.05

日本語インターフェースの仕様が変わったので対応しました
En Google modified by Gulfweed
正常に更新されない場合は一度 Greasemonkey を無効にして
上記リンクを開き、強制リロードをかけてください
原作者: ユーザJavaScript – namespace gimite

カテゴリー
Programming

MinGW で64bit整数を printf するときの注意

MinGW は Windows の C Library (MSVCR) を使うので普通は %lld を解釈してくれません。Cygwin から開発をしていると、この事を忘れてはまり易いので注意。
(環境 : Windows 2000 + gcc 3.4.5 (mingw special))
VC++ と同じように %I64u, %I64d を使えば大丈夫です。C++ コードならストリームを使えばとりあえず問題ないとのこと。
Google:MinGW lld I64d で関連情報がたくさん出てきます。
これは使用するランタイムを選択することでも解決できます。最新の MinGW Runtime をインストールし、Wrapper として libmsvcr80.a をリンクすることで MSVCR 8.0 を使えば %lld も正常に解釈されます。libmsvcr71.a 以前はだめです。
printf の話題なのでついでに
%llf は多くの C Library で結果的に拡張倍精度長浮動小数点数 (long double) の format として機能しますが、本来 long double の変換修飾子は L です。日頃から %Lf を使うようにした方が無難かと思います。
これはたとえば GNU C Library なら vfprintf.c のソースから is_long_double 周辺を見ればよくわかります。
MSVCR は %Lf も解釈してくれませんが。(だめじゃん)

カテゴリー
General

ICFP 2007 延長戦

damaC# というチームで参加していましたが、
期間中はまともなスコアを出すことが出来ませんでした。
しばらく延長戦をやっていたので
その成果を公開してみます。
http://starlancer.org/~ysn/damacy/