Best solved puzzle

最高の解かれたパズル

Line wrap

Highlight

#include<stdint.h>//       4                                                
#include<stdio.h>/*      76.                               1                
                         ..2321     1       57             3                
                         21....     .       ..             .11         1   2
                    1  88..1321  2  33    5512      1      277        14   1
                    099..12....  .  ..    ....    1 4 11111...111 122 5.1  .
                  11...221.821112411123455676489  51.176543232666 902 .27  1
                  10111...1.....................11.417...........1...21..11.
                  ..2239921176566156225563322299887...6533233233182469196894
                  22...............................111......................
*///              3269548556987776665556662131223412347543332334543322223456
/*                                                                          
          13.3.37 */char C[120]  [60   ];int R[120][60],W,H,J,K,B[61][61],/*
          12.2.39 */r,i,j,c,*q  =&   H,t=7200,x,y,k;int64_t*U,T[28800],*S=/*
          11.2.40 */T,O[120],  Z[   120],v,z;void D(){for(k=-1;7200>++k;S[/*
            10.39 */k]=v)r=!         ~(v=U[k])&&*R[k/60]?2:S[k]-v?1:r;;;;}/*
             9.36 */void L(             ){for(r=1;r==1;){r=3;;for(i=0;120>/*
             9.31 */i;i++){                  for(k=z=1,j=0;v=R[i][j];j++)O/*
           8.3.32 */[i]|=(  1LL             <<v)-1<<k,k+=v,0,Z[i]=z|=1LL<</*
           7.3.30 */k++;;  v=~                (3LL<<k-2);for(j=-61;++j<60;/*
           5.3.29 */v=(   v|~                  z)&(j<0?v>>1:v<<1|1))v=S[60/*
       3.1.3.1.28 */*         i    +(j        < 0?~j:j)]|=j?v:~3;}for(z=0;/*
         1.2.4.31 ;         */    7200       >z;z++)i=z/60,j=z%60,(B[i<60?/*
           7.5.31     */i:j][   i<60?        j:i-60]=~S[z]&O[i]?~S[z]&Z[i]/*
         1.6.5.30 ;  */?r=0    :(U=O          ,1):(U=Z,2))?k=i<60?j+60:j,S/*
       5.10.12.16 */[i%    60+60*k]|=         ~U[k]:0;U=S;  S-=t*=-1;D();z/*
    5.11.5.4.12.4 */*9;  }}int main(          ){for  (;K=  scanf("%d",R [*/*
    15.2.4.4.11.5 */q+c*60]+j)<1?          q= &W,j  --,2   >++c:'\n';j =-K/*
   16.3.4.2.2.5.5 */+getchar()?j+1        :++ *q*0   );     L(   );;if (!r/*
         14.8.7.3 */)for(K=0;K<W          *60;K++)              if(K%60  </*
     12.1.4.1.6.2 */W&!B[K/60]          [ K%60 ]                  ){for(  /*
       11.3.4.6.1 */c=64;c--;         )if (!(1                     &S[K/*  ;
     10.1.8.8.5.1 */]>>c))U=        S ,000,S+=         J=14400,     D()/*  ;
         9.8.11.5 */,S[K]=~         (1LL<<c)         ,L(),S-=J,S    [K]/*   
    9.5.6.1.2.4.1 */|=r==2?          1LL<<          c:0;L(  ) ;}     q=/*  ;
        9.3.5.1.5 */&K;;for           (J=          K=i=0       ;    120/*   
        3.2.6.5.1 */>    i;                       Z[i]=k            --,/*  ;
        2.6.3.5.1 */                             i>59?q    =&J     :0,/*   ;
    2.1.2.6.3.6.1 */ *     q<                    k?*q=k    :0,    0,C[/*   ;
2.1.2.2.1.5.2.5.1 */ i  ++  ][                k  ]=' '     ){     j=k/*    ;
    2.1.2.5.5.6.3 */ =  0;  for(;         x=R[i  ][j++]            ;/*      
      4.1.9.7.5.1 */0)  k  +=sprintf   ((00,C[    i]+/*                    ;
       5.19.6.1.2 */k), "%d.",x);}i=~J;;r&1       ||puts        (         /*
         24.6.3.3 */r?"invalid":"failed");         for(;i      <H;       i/*
     24.1.2.9.7.4 */++,puts(""))for(j=~K;j  <  W;  )putchar( i<0?j<0    ||/*
        25.1.2.25 */(k=i+Z[j+60])<0?' ':C[j +  60  ][k]:j<00?(k=j+Z[i])<0?/*
          28.1.26 */' ':C[i][k]:"?X "[B[i][j]]  ) ,j++;return 0;} /* 2012 */

引用元：https://www.ioccc.org/2011/hamaji/hamaji.c

審査員・作者による説明：https://www.ioccc.org/2011/hamaji/hint.html

動作

お絵かきロジックのソルバ。

$ gcc -o hamaji hamaji.c

$ ./hamaji < dragon.nono
                           4
                         76.                               1
                         ..2321     1       57             3
                         21....     .       ..             .11         1   2
                    1  88..1321  2  33    5512      1      277        14   1
                    099..12....  .  ..    ....    1 4 11111...111 122 5.1  .
                  11...221.821112411123455676489  51.176543232666 902 .27  1
                  10111...1.....................11.417...........1...21..11.
                  ..2239921176566156225563322299887...6533233233182469196894
                  22...............................111......................
                  3269548556987776665556662131223412347543332334543322223456

          13.3.37 XXXXXXXXXXXXX  XXX   XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
          12.2.39 XXXXXXXXXXXX  XX   XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
          11.2.40 XXXXXXXXXXX  XX   XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
            10.39 XXXXXXXXXX         XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
             9.36 XXXXXXXXX             XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
             9.31 XXXXXXXXX                  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
           8.3.32 XXXXXXXX  XXX             XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
           7.3.30 XXXXXXX  XXX                XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
           5.3.29 XXXXX   XXX                  XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
       3.1.3.1.28 XXX         X    XXX        X XXXXXXXXXXXXXXXXXXXXXXXXXXXX
         1.2.4.31 X         XX    XXXX       XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
           7.5.31     XXXXXXX   XXXXX        XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
         1.6.5.30 X  XXXXXX    XXXXX          XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
       5.10.12.16 XXXXX    XXXXXXXXXX         XXXXXXXXXXXX  XXXXXXXXXXXXXXXX
    5.11.5.4.12.4 XXXXX  XXXXXXXXXXX          XXXXX  XXXX  XXXXXXXXXXXX XXXX
    15.2.4.4.11.5 XXXXXXXXXXXXXXX          XX XXXX  XXXX   XXXXXXXXXXX XXXXX
   16.3.4.2.2.5.5 XXXXXXXXXXXXXXXX        XXX XXXX   XX     XX   XXXXX XXXXX
         14.8.7.3 XXXXXXXXXXXXXX          XXXXXXXX              XXXXXXX  XXX
     12.1.4.1.6.2 XXXXXXXXXXXX          X XXXX X                  XXXXXX  XX
       11.3.4.6.1 XXXXXXXXXXX         XXX XXXX                     XXXXXX  X
     10.1.8.8.5.1 XXXXXXXXXX        X XXXXXXXX         XXXXXXXX     XXXXX  X
         9.8.11.5 XXXXXXXXX         XXXXXXXX         XXXXXXXXXXX    XXXXX
    9.5.6.1.2.4.1 XXXXXXXXX          XXXXX          XXXXXX  X XX     XXXX  X
        9.3.5.1.5 XXXXXXXXX           XXX          XXXXX       X    XXXXX
        3.2.6.5.1 XXX    XX                       XXXXXX            XXXXX  X
        2.6.3.5.1 XX                             XXXXXX    XXX     XXXXX   X
    2.1.2.6.3.6.1 XX X     XX                    XXXXXX    XXX    XXXXXX   X
2.1.2.2.1.5.2.5.1 XX X  XX  XX                X  XXXXX     XX     XXXXX    X
    2.1.2.5.5.6.3 XX X  XX  XXXXX         XXXXX  XXXXXX            XXX
      4.1.9.7.5.1 XXXX  X  XXXXXXXXX   XXXXXXX    XXXXX                    X
       5.19.6.1.2 XXXXX XXXXXXXXXXXXXXXXXXX       XXXXXX        X         XX
         24.6.3.3 XXXXXXXXXXXXXXXXXXXXXXXX         XXXXXX      XXX       XXX
     24.1.2.9.7.4 XXXXXXXXXXXXXXXXXXXXXXXX  X  XX  XXXXXXXXX XXXXXXX    XXXX
        25.1.2.25 XXXXXXXXXXXXXXXXXXXXXXXXX X  XX  XXXXXXXXXXXXXXXXXXXXXXXXX
          28.1.26 XXXXXXXXXXXXXXXXXXXXXXXXXXXX  X XXXXXXXXXXXXXXXXXXXXXXXXXX

解説

入力は問題データを表す。左側のヒントの数字をドット区切りで並べ、ハイフンの行で区切ったあと、上側のヒントの数字を並べる。最大サイズは60x60。解がない場合、解が一意に決まらない、解が求まらない場合は”invalid”と出力される。詳しくはhint.text参照のこと。

お絵かきロジックはNP困難なので、バックトラックでまじめに解くのは難しい（30x30程度が限界）。人間が行うヒューリスティクスを実装すれば、人間が解けるものは大体解けるが、プログラムが長くなりがち。このプログラムは第3の方法として、http://www.haskell.org/haskellwiki/Nonogramで紹介されている集合ベースのソルバを実装しているとのこと。人間のようなむずかしい推論はしないが、決定しないセルに対してバックトラックをしない推定を行う。

コードはお絵かきロジックでドラゴンの絵を示した形状。数字のヒントに多くの文字を消費するので、コード自体はだいぶ縮められている。ドラゴン形状とスピードとサイズから、しっかり難読化されたコードになっているとのこと。

ドラゴンを選んだのは、2012年が辰年だったからとのこと。 IOCCC 2011は募集期間が2011-11-12から2012-01-12だった。