読者です 読者をやめる 読者になる 読者になる

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

「ショートコーディング:パスカルの△」最終ランキング~上位5位のコード公開+Ozyさんの解説付き #shortcoding #codegolf

CodeIQ中の人、millionsmileです。

お待ちかね、「ショートコーディング:パスカルの△」の
最終ランキングで上位5位までコード公開と、
出題者のOzyさんの解説です!

この解説記事を読めば、次はあなたも神になれるかも!?です。

===============================

解説と最短コード69バイト

最短コードを生むアルゴリズム

パスカルの三角形を作る方法として一番簡単そうなのは、前の行の結果を単純に足し合わせて、次の行を生成する方法です。この方法での最短記録は、72バイトでした。十分短いのですが、配列アクセスで文字数が増えてしまうので、ややロスがありました。しかし、この方法の良い点は、単純な足し算しかしていません(途中掛け算をして32bitを超えることはありません)から、三角形のサイズがある程度大きくなっても対応できるということです。

今回は、三角形のサイズを「20行」と指定しました。神級コードに達するかどうかは、このサイズ指定を利用できたかどうかです。JavaScriptコードゴルフでは気にならないことですが、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が返ります。これを変数の初期化に使っているわけですね。

===============================

最後に、問題文の掲載です。

今回のショートコーディングはとってもシンプルです。
パスカルの三角形を出力するコードを、Cで書いてください。
参照:wikipedia
http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2

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
・
・
・

入力データはありません。
出力は上記のように、各行の整数値を半角スペースで区切ったものを20行出力してください。
※正解のデータはこちらからダウンロードできます。
https://dl.dropboxusercontent.com/u/110505645/CodeIQ/201304/%E6%AD%A3%E8%A7%A3%E3%83%87%E3%83%BC%E3%82%BF.zip

☆注意
(1)出力の各行について、最後の整数の後ろに半角スペースが入っても「OK」とします。

(2)コンパイルは、"gcc -O0 -std=c99"で行います。
(Ideone.comでチェックする場合はCで通ればOKです)

(3)次の場合、締切日以前にフィードバックを行います(締切間際の提出分に関してはフィードバックが間に合わない場合もありますが、ご了承ください)。
・コンパイルエラー
・ランタイムエラー(メモリ違反・0除算等)
・出力に間違いがある

(4)通信によって外部から解答を得たり、system関数のような外部プロセスを実行するような解答など、出題者が不適切とみなしたコードは無効です(無効になった場合はその旨をフィードバックでお伝えします)。

ショートコーディング問題、いかがでしたか。
引き続き、おもしろい問題をだしていくのでCodeIQをよろしくお願いします!

f:id:codeiq:20130520152041j:plain