Best Abuse of Computation

計算の最高の悪用

受賞者:Christopher Night

引用元:https://www.ioccc.org/2006/night/night.c

審査員・作者による説明:https://www.ioccc.org/2006/night/hint.text

動作

パズルゲームの生成。 作者は迷路と言っている。

$ gcc -o night night.c -lncurses

$ ./night
起動直後の様子
図:起動直後の様子

4x4の矢印は、青と緑で市松模様に塗り分けられている(左上は青)。 初期盤面では左上の矢印が太字(少し明るい青)で描画されていて、これは現在地であることを表している。 wasdで上左下右の隣の矢印に移動できるが、現在地の矢印の方角にしか移動できない。 現在地が左上なら、左か下だが、左は画面端なので移動できない。 そして、青い矢印を離れるとき、その矢印は時計回りに90度回転する。 緑の矢印から離れると反時計回りに回転する。 これを繰り返して、左上矢印から右上矢印に到達するのが目的。

解説

迷路生成を遺伝的アルゴリズムで行っている。 遺伝子は32ビット整数で、交叉はなく突然変異のみ(ランダムに3ビット変える)、解答にもっとも長い手数がかかる盤面の遺伝子だけが生き残る、という設定で、手数が64以上になる盤面を生成するとのこと。

コードは遺伝子の形状。自己生成プログラムではない、とhint.textに書いてある。 識別子はAGTCのようなものばかり。DNAの塩基の4種類(アデニン、グアニン、チミン、シトシン)。 512回の繰り返し処理をループではなくマクロ展開で行っている。 プリプロセスをしたときに巨大になって解読しにくくするために意図的にそうしたとのこと。 そのためコンパイルに少し時間がかかる。


チート攻略方法。マクロCCCの定義をrand()から次に置き換える。

#define CCC 2461325420^7

これで、盤面を固定できる。

この盤面の攻略は次の通り。自分の環境ではペーストで動いた。

sdsdaadswdaddadsawaadswdaddwswsadswwwswsswsaaasddaadwswdaddswww

なお、この解は探索によって求めた。

これにより、次のような5フレームのアニメーションでメッセージが出てくる。

  C
  C        G
  C        G        T
  C        G        T        A
  C  O  N  G  R  A  T  U  L  A  T  I  O  N  S

ちなみにこのメッセージは、コード中のT(...)のマクロ内にあるAGTCの出現でエンコードされている。 デコード方法はmain関数(マクロGAT)の冒頭。GTTを(ポインタAGT経由で)破壊的に書き換えているあたり。 デコード方法はわかるが、該当メッセージが埋め込まれているあたりは普通に意味のあるコードに見えるので、どうやって作ったのかわからない。