http://shinh.skr.jp/dat_dir/icfpc-2010/factory/genkey6.rb
任意の要求出力に対して、出力数 + 7 で回路を作れるコードです。とりあえず key prefix と Car #10060 への答えくらいは動いてることを確認したので、まぁ動いてるんじゃないかと。
説明を試みる。
ICFPC の問題の回路をどの程度短い回路で作れるか、っていう話があって、1入力ごとに遅延した回路を1つ増やして…っていう話がありました。言葉で説明できる気がしないので手順を書いてみます。
最初、 0 ターン目は 1 が欲しいです。
+------+ | | v v--+ | +---+ | | | 0 | | | +---+ | | | | | | +---+ | | | 1 | | | +---+ | | | +--|-+ | | v v--|----- 3より大きい番号の回路からの入力 +---+ | | 2 | | +---+ | | | | X-+ +--+
これで初手に 1 は出るはずです。 2 の右入力は 3 より大きい番号につないであるので、 3 以降の回路によらず、初手に入ってくるのは初期値である 0 です。
さて次のターン、 1 ターン目もまた 1 が欲しいです。ゲート 0 と ゲート 1 は 0-2 にしか依っていないので、 2 に入ってくる左入力は計算できます。実際計算すると 0 なんじゃないかと思います。
さて、ここで 2 の左出力が出力になってるのがポイントで、左出力は入力のうち片方を任意に選べるなら、好きな値が出せるようになっています。今回の場合 1 が欲しいらしくて左入力は 0 なので、「3 より大きい番号の」と書いた回路の 0 ターン目が 2 を出力してくれていればいいことになります。
じゃあ 2 を 0 ターン目に出す回路をつないでやればいいじゃん、と、
+--+ +--+
| v v |
+------+ | +---+ |
| | | | 4 | |
v v--+ | | +---+ |
+---+ | | +--+ | |
| 0 | | | | |
+---+ | | +-+ |
| | | | | |
+---+ | | v v------ 5より大きい番号の回路からの入力
| 1 | | | +---+ |
+---+ | | | 3 | |
| +--|-+ +---+ |
| | | | |
v v--|-------+ +--+
+---+ |
| 2 | |
+---+ |
| | |
X-+ +--+ で、次、 2ターン目に欲しい数字は 0 です。 0-2 の回路の状態を覚えておいてやれば、 3 から 2 に何を入力してもらえれば 0 を出力できるかは計算できるはずです。実際はどうも 0 をもらえばいいようです。つまりゲート 3 の 1 ターン目 (1ターン遅れてることに注意)が 0 を出力してくれればいい。で、次の 3-4 の回路を見てやると、これも同じく、何を 5 からもらえれば 0 を出力できるかは計算できるはずです。実際は 2 のようで、「5より大きい番号の回路からの入力」と書いた部分の 0 ターン目の出力が 2 であればいい。 0 ターン目の出力が 2 である回路はさっきと同じで簡単に書けるので…
という具合に、 1 ターンずつ遅延した回路を置いていく、っていうのが私が ICFPC 期間中に考えた方法でした。
この方法だと、 0 が要求された回数 a 、 1 が要求された回数 b 、 2 が要求された回数 c とすると、 a + 3*b + 2*c のゲートが必要になる計算になります。これはざっくり出力数 * 2 くらいのゲートが必要だということになります。
で、同じく ICFPC 中に考えたのは、 1 が要求された時の回路やら 2 が要求された時の回路のサイズが大きくなってしまうのは、初手に使える入力が 0 しか無いからで、どっっかから別の値が持って来れればもっと短くなるのになぁ、ということです。
で、上の図で言うところの 2 とか 3 ってヤツは初手では必ず右から 2 が出力されるような形になっているので、この出力をうまく使えないかなぁと考えました。その 2 を使ってしまうと自分の回路への入力が一つ余ってしまうので、 2 を送った先から返してもらえればいいかなぁ、と。
具体的には、
+------+ | | v v----|----------+ +---+ | | | 0 | | | +---+ | | | | | | +---+ +-|-----v v------ 5より大きい番号の回路からの入力 | 1 | | | +---+ | +---+ | | | 3 | | | +--|-+ +---+ | | | | | | v v--|-------+ +--+ +---+ | | 2 | | +---+ | | | | X-+ +--+
こういう形。これはうまくいきそうに思って、実際に実装してみたのですが、結局うまくいかないことがわかりました。図で言うと 3 => 0 の配線ができてしまっているので、 N ターン目にゲート 2 からゲート 3 に X をくれと言う時に、ゲート 3 の N-1 ターン目の出力が判明してない段階で特定の値を要求できないからです。
でまぁ、あれこれ考えるに、どうも戻る方向の配線があるのはダメっぽい。右出力の出力 2 は使うけど、常に図で言うところの右っかわに送るだけで、右から左のリンクは作らない、という方針で書いてみたのが冒頭のコードです。この方法だと一番左端の回路の入力がどこからも入ってこないので、どんな入力に対しても 0 を出力する回路をつないでおきました。これを作るのに私のやり方では 6 回路かかるのと、 0 を二つ入力として初手に 1 を出す回路に 2 回路かかるので、 8 + (N-1) 回路の N + 7 回路となったわけです。
具体的には、初手に 1 を出す一番左の回路は、 AA 描くのめんどいので…
22R2R0#1R1L, 0R0L0#2L2R, 1L1R0#3L0R, 2L5L0#4R4L, 3R3L0#5R5L, 4R4L0#3R6R, 6L5R0#6L7R, 8L6R0#X10R,
という形 (ただし 22R は一番右の回路の右出力) で、後は 0, 1, 2 をそれぞれ初手に出力する回路は、
0
初手の 2 は使わず次以降で使う
---------->
+------ Nより大きい回路からの入力
|
+----+
v | |
+---+ |
| N | |
+---+ |
| | |
X-+ +--+1
初手の 2 がここから入る
----+
|
+------- Nより大きい回路からの入力
| |
v v
+---+
| N |
+---+
| |
X-+ +-------->
ここは初手 2 が出るので次以降で使う2
初手の 2 がここから入る
--+
|
| +------- Nより大きい回路からの入力
| |
v v
+---+
| N |
+---+
| |
X-+ +-------->
ここは初手 2 が出るので次以降で使うとかでいいので、これをつないで行けば OK です。
これ以上短くするのは、一番左端の回路作るコストがやたらでかいので、ここの定数項を落とせればいいのかな、と思います。できるかどうかは知りません。