Best Flow Control

最高のフロー制御

受賞者:Mark Schnitzius

引用元:https://www.ioccc.org/1998/schnitzi.c

審査員・作者による説明:https://github.com/ioccc-src/winner/blob/main/1998/schnitzi.hint

動作

ソートをするC言語プログラムを出力する。

$ gcc -m32 -o schnitzi schnitzi.c

$ ./schnitzi 3 > sort.c

$ gcc -o sort sort.c

$ echo "2 3 1" | ./sort
1 2 3

解説

リポグラムがテーマになっている。 リポグラムとは文学界の用語で、特定の文字を使わないという制限のもとで文章を書くこと。 元のプログラムも、出力されたプログラムも、ある種のリポグラムになっているところが特徴。

出力されたプログラムから解説する。 これは、配列やループを一切使わないものになっている。 ソートアルゴリズムで配列もループも使わないのはちょっと驚くが、実際の出力を見ればすぐに納得できる。

$ ./schnitzi 3
main()
{
    int a,b,c;

    scanf("%d %d %d",&a,&b,&c);

    if (a<b)
        if (b<c)
            printf("%d %d %d ",a,b,c);
        else if (a<c)
            printf("%d %d %d ",a,c,b);
        else
            printf("%d %d %d ",c,a,b);
    else
        if (a<c)
            printf("%d %d %d ",b,a,c);
        else if (b<c)
            printf("%d %d %d ",b,c,a);
        else
            printf("%d %d %d ",c,b,a);
}

このように、入力サイズnに対して2n個の分岐を書き下したプログラムを生成する。


さて、元のプログラムのすごいところは、条件分岐を一切使っていないこと。 もちろん単にif文を使っていないという話ではなく、while文も?:&&も使っていない。 ついでに、関数の引数も返り値も使っていない。

基本的な構成は次の通り。 main関数はOという関数ポインタの入っている変数を繰り返し呼び出す。 呼び出された関数は、次に呼び出してほしい関数をOにセットする。 そのうちOexit関数が代入されるので正常終了する。

ただしこれでも、上記のような出力を出すためには条件分岐が必要である。 これを実現するのは次の4行。

void _j(){ O=_o; m=!m; h=h+m*(long)t; }
...
void _c(){ O=(e*)h; }
void  n(){ O=_j; t=w; _o=_c; }
void  p(){ O=_j; h=0; t=l; _o=n; }

pを呼び出すと、hを0に初期化し、その後_jn_j_cという順で呼び出され、最後にhに入っている関数が呼び出されることになる。 このときにhに何が入るかを考える。

ということで、mが0かどうかによって、lwを呼び分けるギミックになっている。


ポインタをintとして扱うので、-m32が必要。 intの変数宣言をlongにし、main関数の第2引数もlongに修正するのでもよい。