Best one-liner

引用元：https://www.ioccc.org/2004/kopczynski/kopczynski.orig.c

審査員・作者による説明：https://www.ioccc.org/2004/kopczynski/index.html

動作

8、9、10、11に特化したOCR、と称するプログラム。

8の例。

$ gcc -Dif=while -o kopczynski kopczynski.c

$ cat kopczynski-8a
 ####
######
##  ##
##  ##
 ####
##  ##
##  ##
######
 ####

$ ./kopczynski < kopczynski-8a
8

9の例。

$ cat kopczynski-9
###
# #
###
  #
###

$ ./kopczynski < kopczynski-9
9

10の例。

$ cat kopczynski-10
 #   ###
##  #   #
 #  #   #
 #  #   #
###  ###

$ ./kopczynski < kopczynski-10
10

11の例。

$ cat kopczynski-11
#  #
 #  #
  #  #
   #  #

$ ./kopczynski < kopczynski-11
11

8の他のパターン。

$ cat kopczynski-8b
#####
# # #
#####

$ ./kopczynski < kopczynski-8b
8

$ cat kopczynski-8c
 #
# #
 #
# #
 #

$ ./kopczynski < kopczynski-8c
8

6も9になる。

$ cat 6
###
#
###
# #
###

$ ./kopczynski < 6
9

解説

オイラー標数を求めるプログラム。

次のアスキーアートで考える。

+--+     +--+     +  +--+     +   +
|  |     |  |     |  |  |     |   |
+--+     +--+     |  |  |     |   |
|  |        |     |  |  |     |   |
+--+     +--+     +  +--+     +   +

オイラー標数とは、「頂点の数－辺の数＋面の数」という式で表される値。 上の各数字のオイラー標数は+の数（頂点の数）と--や|の数（辺の数）で決まる（いずれも面はゼロ）。

• 8は頂点6、辺7なのでオイラー標数は-1
• 9は頂点6、辺6なのでオイラー標数は0
• 10は頂点6、辺5なのでオイラー標数は1
• 11は頂点4、辺2なのでオイラー標数は2

このプログラムは、この数字を求めて9を足した数字を表示する。 これにより、見かけ上はOCRのように動く。

このプログラムの肝は、オイラー標数の求め方。 大筋としては、2x2のパターンごとにスコアを決めておき、2x2の窓をずらしながら足し合わせていくことで、標数が求まる仕組みになっている。

先にこのプログラムが使っているパターンごとのスコアを示す。

A    B    C    D    E    F    G    H    I    J    K    L    M    N    O    P

..   ..   ..   ..   .#   .#   .#   .#   #.   #.   #.   #.   ##   ##   ##   ##
..   .#   #.   ##   ..   .#   #.   ##   ..   .#   #.   ##   ..   .#   #.   ## 

 0    1   -1    0    0    1   -2    0    1    1   -1    0    0    1   -2    0

上は便宜上のパターンの名前、真ん中が2x2のパターン（.は空白を表す）、下がスコア。 パターンAは4マス全部空白で、0点。 パターンBは右下にだけ#がある場合で、1点。 パターンCは左下だけで、-1点。

これでうまくいくことを考えるために、全体で#が1つだけある図で考える。 これのオイラー標数は1。 2x2の窓を1マス分ずつずらしながらスコアを求めていくと、なにもないところはすべてパターンAで0点。 右下に#が来たら1点（パターンB）、左下に来たら-1点（パターンC）。 右上に#が来たら0点（パターンE）、左上に来たら1点（パターンI）。 足し合わせると、1-1+1 = 1で、1点となり、無事に正解が求まった。 他のパターンでも検算してみると良い。

なぜこれでうまく行くかと言うと、このテーブルは各マスを次のように分解し、重みを付けてオイラー標数のようなものを評価しているからである。

  a-----b
  |\   /.
  | \ / .
  |  e  .
  | / \ .
  |/   \.
  d . . c

頂点aの重み = 1
頂点bの重み = 0
頂点cの重み = 1
頂点dの重み = -1
頂点eの重み = 1

このマスのスコアを次のように計算する。

• 頂点aからeは、塗りつぶされているときは上に書かれた重みを足す（-1～3）
• 線について、実線になっているところが塗りつぶされている本数を引く（最大6本）
• 面は単純に塗りつぶされている数を足す（最大4面）

なぜ単純に足し合わせないかというと、頂点や辺は隣のマスと共有しているので重複カウントしてしまうため（面は共有しないので単純に足せばよい）。 2x2の窓をずらしながら足し合わせていけば、各頂点と各辺がそれぞれ1回ずつオイラー標数としてカウントされることがわかるはず。 頂点の重みはもっと単純に、aとeだけ1、bとcとdは0とすることもできるが、あえてややこしいものにしている（そうしなかった理由は後述）。

解釈の例をいくつか示す。

• パターンBは、頂点cが塗りつぶされているだけなので、1点。
• パターンCは、頂点dが塗りつぶされているので-1点。
• パターンKは、頂点aと頂点dを塗りつぶすので1点と-1点、そして左端の辺を塗りつぶすので1引き、合計-1点。
• パターンDは、頂点cと頂点dを塗りつぶすので1点と-1点、下の辺はこのマスでは考慮しないので、合計0点。
• パターンOは、頂点a、b、e、dを塗りつぶすと考え1+0+1-1 = 1点、線はab、ae、ad、be、edの5本、面はabeとaedの2面、合計すると1-5+2 = -2点。

他のパターンでも確かめてほしい。

実装のポイントは次の通り。

• -Dif=whileというオプションによって、while文をif文に見せかけている。
• 入力の各行を負の整数のビット列に変換している（変数lにビット列が入る）
• 1行読み終わったら変数Qが8になるように調整している（この値はパターン評価のときに使う）
• ビット列を6で初期化することで、暗黙的な領域を1つ増やして、オイラー標数を1大きくしている（よって最後に足すのは9ではなく8となっている）
• 前の列のビットパターンがI、次の列のビットパターンがlとして、テーブルを引きながら足し算していく
• テーブルは、文字列"has dirtiest IF"の下位2ビットに入っている（頂点の重みを複雑にした理由は、この文字列を意味ありげにするため）

審査員コメントにある数列クイズ「1, 0, 0, 0, 0, 0, 1, 0, 2, 1、の次の数字は？」は、これは数字の穴の数を表す。 0の穴は1つ、1から5の穴の数は0個、6は1つ、7は0個、8は2個、9は1個。 次の数字は10で、穴は1つなので、答えは1。 平面図形のオイラー標数は「連結成分の数 - 穴の数」なので、これに関連している。 （もしこの数列が「1 - オイラー標数」だとしたら、答えは0かもしれない）