ICFP Programming Contest 2010

色々な問題の集合のコンテストなので、とても一人では参加できる能力もないし、他の人が大半やっているのですが、取り敢えず一部の問題だけ比較的に良いものができたのでメモしておきます。

部分問題

0#という名前の2入力2出力のゲートを使って、特定の出力を構成せよ、という問題。ゲートは一直線にならべ、評価はその順番に行われる。逆に戻るような信号線は次のサイクルで評価される。信号線を分岐させることはできない。

ゲート仕様

左入力Xと右入力Yがあって、左出力には(X-Y)%3が、右出力には(X*Y-1)%3が出てくる。細かいことはさておき、以下で重要になるのは右出力は入力のどちらかが0だと2になってしまうために使い勝手が悪い半面、左出力は片方の入力を固定できればもう一方の入力を操作することで任意の出力が可能であるということ。また、ゲートの初期値は0なので、それを利用する。

解法の流れ

各サイクルごとに出力を決定させていく。信号線のつなぎ変えは副作用があるので、前向きの線(同一サイクルで評価される)は変更しないように構築していく。初期値が0であることを利用している部分については、後ろ向きの線でつなぎ変えれば少なくとも1サイクルは安定に動作する。つまり、出力のN桁目を決定する回路を順次組んでいくことを考える。

このような回路として1入力1出力の回路を組むことにする。この入力に対して出力がセンシティブにならなくてはいけないので、0#ゲートを多段に挟むわけにはいかない。また、出力は右出力とはできない。以上は右出力が全射ではないことによる。つまり、原則的に右出力が役に立たないので、左出力を工夫して使うということ。

全体としての出力も固定になっているので、1サイクル目の出力を作成する回路の出力が全体としての出力になる。2サイクル目の出力を作成する回路は、後ろ向きの信号線を使って遅延させれば、同様に作成できる。つまり、2サイクル目の回路の出力を1サイクル目の入力につなぐ。以下同様にNサイクル目の出力を作成する回路をN-1サイクル目の回路につないでいく。

具体的に信号を制御する方法としては、1サイクル目の出力は自前で作れる。2サイクル目の出力は入力信号にセンシティブな出力であるので、自分の内部の他の信号線の値を計算しておくと、必要な(作りたい)出力に合わせて入力を決定できる。つまり後ろ向きの信号線で届けられる信号の値として何を要求するか決定できる。Nサイクル目の出力は、最初の回路が2番目の回路に値を要求し、同様に3番目の回路...N番目の回路(新規に作成する)に値を要求することになる。

つまり、初期値0を持つ回路で、特定の出力を作ることを考えれば良い。出力は左出力である。これはテンプレートを三つ用意しておけばいいことを意味する。0を出力する場合、これは簡単で、0#ゲート一つで良い。後は右出力を自分の入力に戻してやれば、もう一本外部入力を取ることで、次に作る値を外部入力から決定できる。1を出力する場合、0#ゲートを二つ並べる必要がある。0#ゲートの間は左出力は戻し、右出力を直結する。2を出力する場合も、0#ゲートを二つ並べる必要があるが、手前の右出力を後ろの左出力に入れる。後ろの右入力が外部入力である。いずれも一番後ろの0#ゲートの左出力が回路全体の出力になり、そのゲートに外部入力を入れることで、外部入力に対してセンシティブにしてある。(テンプレートのサイズは1,2,2である。)細かい配線については割愛するが、記載していない部分はどうつないでも、外部入力に期待する値を計算する際に内部回路の状態を計算する作業が変更になるだけ。

ちなみに、今回の問題では全体に対する入力の最初の値が0(回路の初期値と一致)なので、最後の値を決定する回路を作成すれば、入力と直結するだけでいいが、そうでない場合には入力の遅延を考慮する必要がある。