CodeIQで「ショートコーディング：パスカルの△」に挑戦してみた話

CodeIQで、Ozyさんの問題「ショートコーディング：パスカルの△」に挑戦してみた話。

問題（要約）

パスカルの三角形の最初の20行

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1

を出力するCプログラムを可能な限り短く記述する。出力の行末に１つスペースがあっても可。

提出コード（５投分全公開）

最初、配列を使ってごにょごにょやってみたけれど（自分の力量では）思うほど縮まなかったので、二項係数 $a = _nC_k$ を1つずつ求める方針に変更。

anarchy golfで出題されている類題で73バイトが出ているが、Ozyさんの問題は制約が少しゆるいのでもっと縮まるのではという憶測あり。

1投目（76バイト）4/29 22:20

forループを用い、処理を愚直に実装。

a,k;main(n){for(a=k=1;n--;a=a*n/k++)printf("%d%c",a,n?32:10);k<21&&main(k);}

2投目（75バイト）4/30 19:52

試しにmain再帰にしてみたら1バイト縮んだ。

i,n=1;main(a){n>20?:main(i?printf("%d ",a),a*i/(n-i--):!!puts("1",i=n++));}

`a ?: b` はGCC拡張で、`a ? a : b` と同義。

`puts()`の返り値（ローカルでは10）から1を生み出すために`!!`を利用している。
`i=n++`を`puts()`の第二引数（本来そんなものはない）の位置に置くことで括弧を節約。
※ここでやりたい処理は`(i = n++, puts("1"), 1)`

3投目（73バイト）4/30 20:05

iとnを負数（というか非負整数）でカウントするようにして2バイト短縮。

i,n;main(a){n+20&&main(i?printf("%d ",a),a*i/(n-++i):!!puts("1",i=--n));}

`n+20&&...` は `if (n != -20) ...` と同義。

4投目（72バイト）4/30 22:07

ちょっと並び替えることでanarchy golfの73バイトの壁を破ることができた。

i,n;main(a){n+20&&main(i?a*i/(n-++i):!!puts("",i=--n),printf("%d ",a));}

最終提出コード（70バイト）5/2 21:22

試しにmain再帰をやめてみたら2バイト縮んだww

i,n;main(a){for(;n+20;i?a=a*i/(n-++i):puts("",i=--n))printf("%d ",a);}

出題者ozyさんの69バイトコードには及ばないものの、1位（神級）の5人に入ることができた。
70バイトの中ではrotary-oさんに次いで2番目の提出らしい。

解説

解説気味に書き直すと、

int i=0, n=0;

main (int a) {
  // aに最初に1が入っているのは説明不要だよね？
  while (n != -20) {
    // 現在のaの値（と空白）を表示
    printf("%d ", a);

    if (i != 0) {
      // 行が終わっていなければ
      a = a * i / (n - ++i); // 次のaを求める
    } else {
      // 行が終わっていれば
      i = --n; // 次の行へ (i = n = n-1)
      puts(""); // 改行
    }
  }
}

初期値: _i=0, n=0, a=1_

a=1になるのは解説不要だと思うけれど一応書いておくと、`main()`の本当の引数は

int main(int argc, char *argv[])

で、argcにプログラム名を含む引数の総数が渡されるので、引数なしで呼ばれた場合argcには1が入る。

その後の処理はこんな感じ。

1. まず現在の`a`を表示。
2. 行の終わりに来たか？

`i`が0の時：行の終わり

　2.1. `n`をデクリメント。`i`に`n`の値をセットして改行して次の行へ。
　注意点
　　`n`は0から始まり-20まで1つずつ減っていく。
　　`i`もその`n`（負数）から0へ向かって増えていく。
　　というわけで`n`も`i`も常に非正整数である。

`i`>0の時：行の途中

　次の`a`を求め、次の項のために`i`をインクリメント。
　注意点
　　`n---i`と書くと`n-- - i`と扱われてしまうので、意図通りにするには`n-(--i)`のように括弧が必要になってしまう。
　　非正整数を用いることで`n-++i`と書ける。

3. `n`が-20になるまで繰り返す

追記（自作69バイトコード）

ideoneだとputs("")が1を返すと聞いて

i,n;main(a){for(;n+20;a=a*i/(n-++i)?:puts("",i=--n))printf("%d ",a);}

naoya_t@hatenablog

いわゆるチラシノウラであります