ショートコーディング：パスカルの△【解説】
本稿はCodeIQで2013年4月26日～2013年5月20日に出題された「ショートコーディング：パスカルの△」という問題の解法に関する記事です。
ショートコーディング：パスカルの△【解説】
◆注意
本問は「ショートコーディング」・「コードゴルフ」と呼ばれる、ソースコードをできるだけ短く書く遊びの一環として出題されたものですので、一般的なプログラミング解説とは少し異なります。
◆最短コードを生むアルゴリズム
パスカルの三角形を作る方法として一番簡単そうなのは、前の行の結果を単純に足し合わせて、次の行を生成する方法です。この方法での最短記録は、72バイトでした。十分短いのですが、配列アクセスで文字数が増えてしまうので、ややロスがありました。しかし、この方法の良い点は、単純な足し算しかしていません（途中掛け算をして32bitを超えることはありません）から、三角形のサイズがある程度大きくなっても対応できるということです。
今回は、三角形のサイズを「20行」と指定しました。神級コードに達するかどうかは、このサイズ指定を利用できたかどうかです。多倍長整数が宣言なしで扱えるような言語でのコードゴルフでは気にならないことですが、Cではint型の整数どうしの演算を行う場合に、扱うことのできる数の範囲を気にしなければなりません。
さて、最短記録を出しているアルゴリズムですが、これは足し算を行わずに直接計算しています。たとえば、5行目の
1 4 6 4 1
という並びを出力するのに、1からスタートして
1 * 4 / 1 = 4 4 * 3 / 2 = 6 6 * 2 / 3 = 4 4 * 1 / 4 = 1
のように、かける値を1ずつ減らし、割る値を1ずつ増やすことで求めることができます。高校の数学で習った、二項定理というやつですね。
ひとつの問題を解くのに、やり方が複数あることは少なくありません。もちろん自分のやり方を信じて、縮めまくるのも良いですが、煮詰まったところで他のやり方を検討するのも大切なことです。
◆上位ショートコーダーの超短いコード
1位
- rotary-oさんのコード（70バイト）
l;c;main(a){for(;a=c?a*c/(l-c):(c=++l)<21;printf(--c?"%d ":"1\n",a));}
- naoya_tさんのコード（70バイト）
i,n;main(a){for(;n+20;i?a=a*i/(n-++i):puts("",i=--n))printf("%d ",a);}
- climpetさんのコード（70バイト）
j,s;main(i){for(;i<21;)printf(!s?j=++i,"\n":"%d ",s=s?s*--j/(i-j):1);}
- robertさんのコード（70バイト）
i,j;main(c){for(;c=!i?i=j,j=j<20:c*i--/j++;)printf(i?"%d ":"%d\n",c);}
- UGさんのコード（70バイト）
n,k;main(C){for(;C=k?C*k/(n-k):(k=++n)<21;)printf("%d %c",C,!--k*10);}
2位
- ushshさんのコード（72バイト）
j;a[];main(i){while(*a=j<20)printf(j<0?j=i++,"1\n":"%d ",a[j]+=a[--j]);}
- mad_pさんのコード（72バイト）
n,k;main(v){n>19||main(v?v*(n-k)/++k:(k=0)<++n,printf(v?"%d ":"\n",v));}
3位
- UTOさんのコード（73バイト）
j,p[];main(i){for(;*p=i<21;)printf(!j--?j=i++,"1\n":"%d ",p[j]+=p[j-1]);}
4位
- hogeover30さんのコード（74バイト）
j,a[];main(i){for(*a=1;i<21;printf(j--<0?j=i++,"\n":"%d ",a[j]+=a[j-1]));}
- hirokazuさんのコード（74バイト）
i,j;main(c){for(;j=++i%21;puts("1"))for(;--j;c=c*j/(i-j))printf("%d ",c);}
- ayuzakさんのコード（74バイト）
j;a[];main(i){for(;*a=i<21;)printf(j--?"%d ":(j=i++,"1\n"),a[j]+=a[j-1]);}
- mbspさんのコード（74バイト）
i,j;main(o){for(;j=j?:++i,j<21;o=o*j/(i-j)|!j)printf("%d%c",o,--j?32:10);}
- simbelmynさんのコード（74バイト）
k[],a;main(p){for(;p<21;)printf(a--?"%d ":(a=p++,"1\n"),k[*k=a]+=k[a-1]);}
- debiruさんのコード（74バイト）
a,g[99];main(i){for(;*g=i<21;)printf(a<0?a=i++,"1\n":"%d ",g[a]+=g[--a]);}
5位
- SARUさんのコード（75バイト）
a[21],i;main(j){for(;i=i?:j++%21;printf(i?"%d ":"1\n",a[i]+=--i<2?:a[i]));}
- cielさんのコード（75バイト）
a[99]={1},i;main(T){for(;T<21;)printf(i<0?i=T++,"1\n":"%d ",a[i]+=a[--i]);}
- Azicoreさんのコード（75バイト）
p[]={1};main(i){20>--i&&printf("%d ",p[i]+=p[i-1])&main(i?:p[puts("")]+2);}
☆最短コード69バイト
配列を使わず直接計算する方法で縮めていくと、69バイトまで縮みます。1位の5名の中では、rotary-oさんとrobertさんが形的には一番近い…っていうか、robertさん、'%d\n'を'1\n'にするだけやん！！！惜しすぎますね…。
k,n;main(a){for(;a=!k?k=n,n=n<20:a*k--/n++;)printf(k?"%d ":"1\n",a);}
私自身、出題当初は「70バイトが最短かなぁ」と思っておりました。 69バイトのコードはrotary-oさんが70バイトの記録を出した後から考えたものですので、純粋に私の記録というわけではありません。皆さんから色々なコードを募った結果出来上がった、皆さんの情熱の結晶ですね。
☆オマケ―main再帰で70バイト
ショートコーディングテクニックの1つとして、main関数自体を繰り返し呼び出す、通常「main再帰」というテクニックがあります。今回の問題では全く利用する必要が無いのですが、『なんだか使えるとカッコイイ』という理由だけで使ったりもします。
k,n;main(a){n<21&&main(k--?printf("%d ",a),a*k/(n-k):puts("",k=++n));}
代入するための「=」を省くことと、これは実装依存なので通る環境が限られますが、putsの返り値を利用しています。puts関数の返り値は厳格に決められているわけではありませんが、最後に出力した文字コードや、出力した文字数が返ることが多いです。Ideone.comの環境では、文字数が返るようになっているので、puts("")と書くと、改行の'\n'を1文字だけ出力することになり、1が返ります。これを変数の初期化に使っているわけですね。
