これは圏です(はてな使ったら負けだとおもっていた)

きっと何者にもなれないつぎの読者につづく。

ICFP 2010 競技説明

ICFP 2010 Task description の非公式日本語訳を置いておきます。非公式でやっつけ仕事なので、誤訳などがあるかもしれません。見付けたらご指摘おねがいします。
また、訳文中の誤りによって何らかの損害を被っても何ら責任は負えませんので、悪しからず。


原文:http://icfpcontest.org/2010/task/
翻訳:石井大海

ICFP Contest 競技説明

今年のコンテストの目的は単純です:金を沢山儲けるのだ
国際的な自動車・燃料製造(International Car and Fuel Production)で!

自動車と燃料の市場

あなたは自動車産業に従事し、日々自動車と燃料の設計・製造を行っています。各自動車は微妙に仕様が異なり、それぞれ適合する燃料が異ります。燃料が自動車に合うかどうかは、コンテストサーバを利用して簡単に判定出来ます。自動車だけから最適な燃料を探しだすのは簡単なことではないでしょう。これこそがあなたの仕事です。自動車の仕様はオープンソースで誰でも読むことが出来ますが、燃料の調合は非公開なので、独力で考えなくてはなりません。

コンテストであなたが行うべきことは二つあります。即ち、

  • 自動車に合う燃料を計算・送信すること
  • 新車を専用の燃料と共に送信すること

です。

これがあなたの収入源です。得点は自動的に計算されすぐに表示されます。


すべての自動車は常に利益を産みます。それぞれの自動車から発生した利潤は、その自動車用の燃料を製造している全員で共有されます。勿論、自動車の製造者も含まれます。利益の配分は平等ではなく、より効率的な燃料を製造した人に多く配分されます。

つまり、あなたの目標は、他の参加者の自動車に適合する燃料を設計し、また、なるべく他の参加者が燃料を設計しにくい自動車を設計することにあります。

はじめの内から、既に何台かの自動車が既に市場に出回っています。コンテスト中、参加者・主催者の双方により沢山の自動車が製造され、出荷されるでしょう。

自分が燃料を設計した自動車の数より多くの自動車を製造することは出来ません。
最大で72台(コンテストの開催時間と同じです)の自動車を製造することが出来ます。

この制限は、あなたがどの部門に参加していても適用されます。特に、Lightning部門参加中に上限一杯まで製造してしまった場合、後のコンテストに参加することは出来ますが、もう製造できるのは燃料だけになります。

採点

どの車に対しても、配当はその自動車の燃料を供給したチームすべてに支給されます。燃料はサイズ順にソートされ、サイズが同じ場合は提出された時間の早い方が優先されます。つまり、サイズが小さく提出が早いほど良く、特に小さいことが重要になります。ひとつの車に対して nチーム が燃料を提出した場合、順に 1/n, 1/(n+1), ... 1/(2*n-1) 点をそれぞれ獲得します。

自動車を設計したチームが最初に提出した燃料も、この評価の対象になります。これは、自動車の設計者がより多くの利益を得られるための措置です。

配当は一定の期間ごとに支払われ、チームの口座に貯蓄されます。しかし悲しいことに、所得税が課せられています。どの期間も、一定割合の税金を払う必要があり、一日の間で50%を失う様になっています。

新車は提出された後、すぐに公開されます。利益が発生するのは、公開されてからちょうど一期間後からです。

各チームの得点は公開され、各期間の終了と同時に更新されます。しかし、上位5位までの得点はハイスコアの一覧から除かれています。上位者は点検のためソースコードを提出する様に要請され、勝者は9月のICFPカンファレンスで発表されます。

自動車の仕様

自動車のエンジンは燃焼室(chamber)の一覧によって与えられ、各燃焼室はアッパー・パイプ(Upper pipe)とロワー・パイプ(Lower Pipe)と云う二つのパイプを搭載しています。パイプは幾つかの区域(section)が並んだものです。パイプは外気を吸い込む機関です。外気は自由に使うことが出来、実際には何種類かの物質の混合気体です。

区間内では、左隣の区間からの物質と燃料タンクから直接供給される燃料による化学反応が起きていて、生成物は右隣の区間に供給されます。最終的に、両パイプの生成物は差動機関(Difference Engine)に運ばれ、機械の動力に変換されます。タンクから各区間への配管は自動車の製造者が設計したものになっています。


下の図を例にとると、ある自動車が0番, 1番の二つの燃料タンクを搭載していて、ただ一つの燃焼室だけから成ってい、パイプは二本あります。アッパーパイプは二つの区間から成り、両方ともタンク0と接続されていて、ロワーパイプは三つの区間から成っていて最初と最後の区間はタンク0、真ん中の区間はタンク1と接続されています。

      upper pipe:  -> section -> section ------------.
    /                   /          /                  \
   /         fuel 0  --<----------'--------.      difference      positive
 air                    \                   \       engine  --->  energy
   \                     \                   \        /
    \ lower pipe:  -> section -> section -> section -'
                                    /
             fuel 1 ---------------'
                        

正規の自動車

自動車は次の条件を満たす時だけ、公道を走ることが出来ます。

  • 燃料タンクの数は最大6つ
  • 標準化されている(normalized)こと
  • 結合的である(connected)こと

ある自動車を、燃焼室の順番の入れ替え・燃焼室の複製・燃料タンクの順番の入れ替えを経て別の自動車に変形出来た場合、その二つの自動車は等価(equivalent)なものであると見做します。自動車が『標準化されている(normalized)』とは、その三進表現(ternary encoding;下記参照)が、他の等価な自動車のものの中で最も小さい(辞書順で)ものである、と云う事です。


結合性(connectedness)の定義は次の通りです。
今、ある燃焼室Cのいずれかの区間(section)のアッパーパイプにタンクs が接続され、またある区間のロワーパイプにタンクt が接続されているとき(訳註:同じ区間でも違う区間でもいい)、タンクt は タンクs に依存している(depends on tank s)と云うことにします。また、s から依存性を辿っていって t へと辿り着けるとき、s は t に間接的に依存している(indirectly depends on t)と云うことにしましょう。
自動車が結合的(connected)である、とは、どんなタンクの組(s,t)についても、t が s に依存していると云うことです。上の節で例示した車は、タンク1からタンク0への依存性がないため、結合的ではありません。

燃料

どの区間でも、燃料は気体と反応し、それによって次の区間への気体の成分が変化します。この変化は線型です。つまり、タンクc と接続されている区間から出力される気体成分 k の量は、次の式で与えられます。

out(k) = c(1,k) * in(1) + .. + c(n,k) * in(n)
ただし、 in(i) は入力気体中の 気体成分 i の量

自動車に燃料を供給するにあたって、製造者は各タンクc について、中身の燃料を特徴づける c(i, k)の値を決定しなくてはなりません。

気体は多くの成分から成っていますが、そのタンクが扱う成分の数 n を選ぶことが出来ます。

各成分k について、アッパーパイプの出力に含まれるkの量が、ロワーパイプのそれと同じか上回ったときに限り、差動機関は作動します(訳註:駄洒落ではない)。この条件は、気体の状態に依らず、つまり吸入される気体の物質構成に依らず、常に成立していなくてはいけません。

気体の一番目の成分は特殊な役割を果します。吸入気体は常にその成分を含み、燃料との反応でその量が減少することはなく(つまり c(1,1)の係数は常に正であり)、そうでなければ差動機関は動作しません。


製造者は、燃焼室のうち幾つかをメイン燃焼室 (Main chamber)として指定します。メイン燃焼室のアッパーパイプから排出される第一成分の量は、ロワーパイプの排出量を厳格に上回っていなくてはいけません。それ以外の燃焼室は補助燃焼室となります。

三進ストリーム(Ternary Streams)

ICFPコンテストは、そんなに生易しいもんじゃありませんよ。


自動車も燃料も、その説明は構造的データとして与えられます。実際には、自然数のリスト(複数)、自然数のリストのタプルのタプルの…のタプルのリスト(複数)、そして自然数のタプル(複数)です。
自動車・燃料のデータは両方ともにトリット(trits; 三進数のビット)のストリームで表されます。さて、もう皆さんうすうすおわかりと思いますが、データについてはこれ以上の解説はここではしません。ストリームパーサのエラーメッセージから頑張って類推してください。


幾つかヒントを出しましょう。コードはどんなに大きな自然数も、どんな長さのリストも扱えます。リストはそれ自身境界を持ち(!!FIXME!! 原文:code is self-delimiting)、実際、燃料のデータのあとのゴミデータは無視しますが、自動車の後のゴミデータは無視しません。また、コードには冗長性(redundancy)がありますが(つまり全てのトリット列がコードの語(word)とは限りませんが)、そんなに多くはありません。


例えば、以下はある自動車を表わす三進コードです。

221022000022010112201010022001122011110220010

回路

まだ簡単そうだとおっしゃる?大丈夫!まだ他にも障害はあります。燃料のデータをそのまま数字で送信することは出来ません。その代わりに我々の与えるある入力列から目的のストリームに変換する工場(factory)の仕様書を与えなくてはいけないのです。


工場は、ゲートと導線から成る回路です。どのゲートも二つの入力と二つの出力を持ち、導線は出力と入力を繋ぎます。どの入出力端子とも、ちょうど一つだけの導線で繋がれていなくてはいけません。"前むきな(goes forward)"導線は情報を即座に伝達し、"後ろむきな(goes backward)"導線は遅れて伝達します。

また、外界とのやりとりのために、どの回路も入出力端子をひとつずつ持つ "外部(external)"ゲートを含んでいなくてはいけません。回路の入力ストリームは外部ゲートの出力から現れ、回路からの出力は外部ゲートの入力端子に送信します。

こうして、工場は燃料を表わすストリームを生成することになります。工場のサイズは内部のゲートの数であり、小さい工場ほどより効率的です。(これは採点に重要な点です。)


もうわかってると思いますけど、ゲートの意味論も回路の構文もここには書きませんよ。その代わり、鍵回路の例をここに書いておきますか。

19L:
12R13R0#1R12R,
14R0L0#4R9L,
9R10R0#3L8L,
2L17R0#5L9R,
15R1L0#10R13R,
3L18R0#6L15L,
5L11R0#13L12L,
19R16R0#11R8R,
2R7R0#11L10L,
1R3R0#18L2L,
8R4L0#16L2R,
8L7L0#15R6R,
6R0R0#14L0L,
6L4R0#14R0R,
12L13L0#17L1L,
5R11L0#16R4L,
10L15L0#17R7R,
14L16L0#18R3R,
9L17L0#19R5R,
X18L0#X7L:
19L

そして入力は:

[0,2,2,2,2,2,2,0,2,1,0,1,1,0,0,1,1]

出力に関しては、自分で頑張って見付けて下さい。最初の17個の出力は「鍵」と呼ばれ、解答をエンコードした三進ストリームの冒頭に必ずついていなければダメです。
どんな回路でもサーバに送信して、出力の最初のトリットを見ることが出来ます。

サーバーは上のストリームとは違う入力ストリームを使っているので、「鍵回路」をそのまま送信しても、直接的には役に立ちませんよ。

戦略上の注意

コンテストの初期には、回路を 自動車#0 (三進コードで "0")の解答として送信しましょう。この自動車は、燃焼室もなければ特別な燃料も必要としないという、一風変わった自動車です。この自動車は鍵接頭辞を特定するためだけにあります。

鍵接頭辞を出力する回路を送信した瞬間、最初の配当が支払われます。もちろん遅くなれば、取り分は小さくなるでしょう。


自動車を72台送信し終えても、他の自動車用の燃料を作ることで、よい利益を得ることが出来るでしょう。

Lightning部門での得点は、ちょうど24時間後に採点されます。