##コードゴルフとは
コードゴルフはコンピュータプログラミング・コンテストの一種。参加者は与えられたアルゴリズムを、可能な限りもっとも短いソースコードで記述することを競う[1]。バイナリサイズではなく、ソースコードの文字数がスコアとなる。(Wikipediaより)
ショートコーディングという名前でも知られているかと思います。
発端
2001年から2ちゃんねるで「七行プログラミング」という名前でコードゴルフが行われていました。
ルールは「1行79字以内7行」というもので、
- 倉庫番
- レイトレ
- テトリス
など、様々な作品が投稿されていました。
そんな中トリッキーの１氏によってされたのが対戦オセロで、
#include <stdio.h>
int p,t,a,d,c,v,i,m[90]={0},s,r[]={-10,-9,-8,-1,1,8,9,10};void k(){if(m[p]==0)
for(i=0;i<8;i++){for(c=0,v=p+r[i];m[v]==3-t;v+=r[i])c++;if(c&&m[v]==t){a+=c;v=
p;if(d)do m[v]=t,v+=r[i];while(m[v]!=t);}}}char*h="・○●\n";int main(){for(i=
1,m[41]=m[49]=2;i<10;m[i++*9]=3)m[40]=m[50]=t=s=1;for(;;a=d=0){for(p=9;p<82;++
p)k(),printf("%.2s",&h[m[p]*2]);if(a)for(d=a=s=p=8;a==8;k())t-2?(scanf("%d %d"
,&p,&i),p+=i*9):++p;else if(s)s=0,printf("pass");else break;t=3-t;}return 0;}
というものでした。
私がこのコードを知ったのは2001年当時ではなくもっと後になってからでしたが、もっと短くかける予感がしたため挑戦を始めた次第です。
※こちらのコードの詳しい解説はこちらで紹介されています。
ここまでたどり着くのに5年ほどかかっており、知人の助言をもとに進めた部分もあるのでまだ改善の余地はあるかもしれません。
実行環境
- 言語：C
- コンパイラ：gcc version 8.2.0
VisualStudioで実行する場合はプリプロセッサに_CRT_SECURE_NO_WARNINGSを追加し、必ず使用されるincludeファイルにstdio.hを追加してください。
制約
- プレイヤーの入力は1~8までの数値二つ
- 例：
3 4 - 範囲外の入力は無いものとする
- プレイヤーが置けない場所に置こうとすることは考慮する
- 例：
- 盤面と盤面は改行を挟んで表示する
- 敵を実装し、対戦を実現する
- 石を置けない場合は
PASSを表示する - プレイヤー的ともに置けなくなった場合はゲームを終了する
完成コード
b[91],X=90,x,Y,t,a,f,d;C(i,j){for(i=b[X]/3*9;i--;){for(d=i+i/3*6-10,j=1;b[Y=X+d
*j++]==!t;);if(2<j&b[Y]==t)for(x=X;j--&&f;a++)b[X+d*j]=t;}}main(p){for(;X--;b[X
]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x?1?X=x:scanf("%d%d",&Y,&
X),f=X+=!1*Y*9,C(),p=!a?t=!t,p:2:puts("PASS")&p--,t=!t,x=f=0)for(X=7;81>X++;a=!
putchar("0@\n-"[b[X]]))C();}
これで352byteです。
解説
まずは適度に改行とコメントを挟んでみましょう。
// 変数宣言
b[91],// 盤面 0:白石 1:黒石 2:番兵 3:空きマス
X=90,// 石を置く場所
x,// 石を置ける場所
Y,// C()内：操作場所の一時保存 main()内：プレイヤーのY軸の設置場所
t,// ターン 0:プレイヤー 1:敵
a,// ひっくりかえせる枚数
f,// 石をひっくり返すフラグ
d;// 走査方向
// 盤面探索(石が置けるかの判定とひっくりかえす処理を兼ねています)
C(i,j){
// 8方向走査
for(i=b[X]/3*9;i--;){
// いくつ置けるか調べる
for(d=i+i/3*6-10,j=1;b[Y=X+d*j++]==!t;);
// 走査終了地点が自分の石なら
if(2<j&b[Y]==t)
// ひっくりかえすフラグfが立っているならひっくりかえす
for(x=X;j--&&f;a++)
b[X+d*j]=t;
}
}
// エントリ
// pはパスできる残り回数
main(p){
// 盤面初期化
for(;X--;b[X]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);
// メインループ
for(;p;x?t?X=x:scanf("%d%d",&Y,&X),f=X+=!t*Y*9,C(),p=!a?t=!t,p:2:puts("PASS")&p--,t=!t,x=f=0)
// 盤面の表示と敵の置く場所の決定
for(X=7;81>X++;a=!putchar("0@\n-"[b[X]]))
C();
}
main関数から見ていきましょう。
main(p){}
これはよくある書き方に直すと
int main(int p){return 0;}
になります。C言語では型がない場合に自動でintをつけたしてくれます。またpにはコマンドライン引数の数1が入ります。pはパスできる残り回数ですが、後ほど石を置いた際に2でリセットするため0でなければなんでもいいです。returnも省略できます。
for(;X--;b[X]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);
盤面の初期化は難しいことはしていません。下の図のような2次元配列を1次元に圧縮し、if分の代わりに三項演算子を使っています。
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 3 | 3 | 3 | 1 | 0 | 3 | 3 | 3 |
| 2 | 3 | 3 | 3 | 0 | 1 | 3 | 3 | 3 |
| 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 |
一つ工夫点を挙げるとすれば番兵の判定X%9&&X>8&X<81で、X>8とX<81は0か1なので&&ではなく&が使えます。あと基本的なことですが、for分の再初期化式で行うインクリメント/デクリメントは継続条件式に入れると数バイト削れます。
for(;p;x?Y=0,t?X=x:scanf("%d%d",&Y,&X),f=X+=Y*9,C(),p=!a?t=!t,p:2:puts("PASS")&p--,t=!t,x=f=0)
for(X=7;81>X++;a=!putchar("0@\n-"[b[X]]))C();
メインループは複雑すぎるので、再初期化式を外に出してコメントを付けます。
// プレイヤーと敵が続けてパスする(誰も置けない)までループ
for(;p;){
// 改行用の8と盤面領域9～80を表示
for(X=7;81>X++;)
C(),// ついでに石が置ける場所があるかを調べる(最後の置ける場所はxに格納)
a=!putchar("0@\n-"[b[X]]);//表示と、putcharの戻り値を使ってaを0に初期化
// xが0でない⇒おける場所がある
x?
// 敵のターンかどうか
t?
X=x// とにかく置けるところに置く
:
scanf("%d%d",&Y,&X),//標準入力から決定
f=X+=!t*Y*9,// プレイヤーのターンの時はXにX+Y*9を入れる & ひっくりかえすフラグをたてる
C(),//ひっくりかえす
p= !a?t=!t,p:2// ひっくりかえした数aが0ならターンが変わらないようtを調整
// 0<aならpを2にリセット
:
puts("PASS")&p--,// おける場所がなければPASSを表示してpを減らす
t=!t,// ターン切替
x=f=0;// x(おける場所)とf(ひっくりかえすフラグ)を0にリセット
}
アルゴリズムの説明はコメントの通りです。
使ってる小技としては、
- putcharで表示する文字を引数内で定義
- aを0にするのにputcharの戻り値を使用
- putsとp--を参考演算子の中で行うために左結合の&で結合
があります。
C(i,j){}
C()の引数にiとjを宣言することで、, がひとつ削れます。
for(i=b[X]/3*9;i--;){
i=b[X]/3*9をわかりやすく書くとi=b[X]==3?9:0です。b[X]は0,1,2,3のいずれかなのでこのように圧縮できます。
つまりやってることとしては、b[X]が空きマスの時は8方向走査します。実際は9回ループしてますが、アルゴリズム上は問題ありません。
for(d=i+i/3*6-10,j=1;b[Y=X+d*j++]==!t;);
d=i+i/3*6-10は、-9,-8,1,10,9,8,-1,-10という数字の集合を表現しています。この集合は、自分のマスの周囲8マスへのオフセットを示しています。2次元配列であれば(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)で表現されるやつです。X+d*jのようにjを変えることで指定マス先が調べられます。つまり条件式のb[Y=X+d*j++]==!tは、jマス先に相手の石が置いている間ループする、という意味です。
if(2<j&b[Y]==t)
先ほどのforの終了条件は「マスが相手の石でないとき」なので、「マスが自分の石」で終わっているかを確認しています。その際間に石が挟まれていない場合(j==2)があるので除外しています。
for(x=X;j--&&f;a++)
b[X+d*j]=t;
ひっくりかえす石があった場合はその座標をxに記録し、ひっくりかえすフラグが立っているときのみ石をひっくり返していきます。
歴史
せっかくなのでここまでの軌跡を残しておきます。
残っている最古のコード(2014/11/19) (469バイト)
#include <stdio.h>
int b[81],x,X,Y,t,a,c,i,j,f,p,d[]={-9,-8,1,10,9,8,-1,-10};int C(){a=0;if(b[X]==
2)for(i=8;i--;){for(j=0,Y=X+d[i];b[Y%81]==!t;Y+=d[i])j++;if(j&&b[Y]==t)for(;j--
+2;Y-=d[i],a++)f?b[Y]=t:0;}return a;}int main(){for(x=81;x--;b[x]=x%9-8&&x>8?2:
3);b[39]=b[49]=0;p=t=b[40]=b[48]=1;for(;p+1;){x=f=0;for(X=7;X++<80;printf(" %c"
,"O@-\n"[b[X]]))C()?x=X:0;if(x)Y=0,t?scanf("%d%d",&X,&Y):X=x+1,f=X+=Y*9-1,t=C()
?t:!t;else puts("pass"),p--;t=!t;}return 0;}
いろいろあって (469バイト)
#include <stdio.h>
int b[81],x,X,Y,t,a,c,i,j,f,p,d[]={-9,-8,1,10,9,8,-1,-10};int C(){a=0;if(b[X]==
2)for(i=8;i--;){for(j=0,Y=X+d[i];b[Y%81]==!t;Y+=d[i])j++;if(j&&b[Y]==t)for(;j--
+2;Y-=d[i],a++)f?b[Y]=t:0;}return a;}int main(){for(x=81;x--;b[x]=x%9-8&&x>8?2:
3);b[39]=b[49]=0;p=t=b[40]=b[48]=1;for(;p+1;){x=f=0;for(X=7;X++<80;printf(" %c"
,"O@-\n"[b[X]]))C()?x=X:0;if(x)Y=0,t?scanf("%d%d",&X,&Y):X=x+1,f=X+=Y*9-1,t=C()
?t:!t;else puts("pass"),p--;t=!t;}return 0;}
d配列の初期化を変更 (427バイト)
#include <stdio.h>
int b[91],X=90,x,Y,t,a,i,j,f,p,d[]{-9,-8,1,10,9,8,-1,-10};void C(){a=0;for(i=b[
X]-3?0:8;i--;){for(j=1;b[Y=X+d[i]*j]==!t;)j++;if(1<j&&b[Y]==t)for(;j--;a++)f?b[
X+d[i]*j]=t:0;}}int main(){for(;X--;p=b[X]=X%9&&X>8&&X<81?X-40&&X-50?X-41&&X-49
?3:0:1:2);for(;p;x=f=0){for(X=7;X++<81;putchar("0@\n-"[b[X]]))C(),a?x=X:0;x?Y=0
,t?X=x:scanf_s("%d%d",&Y,&X),f=X+=Y*9,C(),t=a?p=2,t:!t:(puts("PASS"),p--);t=!t;
}}
scanfをcinに変更 (423バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d[]{-9,-8,1,10,9,8,-1,-10};void C(){a=0;for(i=b[
X]-3?0:8;i--;){for(j=1;b[Y=X+d[i]*j]==!t;)j++;if(1<j&&b[Y]==t)for(;j--;a++)f?b[
X+d[i]*j]=t:0;}}int main(){for(;X--;p=b[X]=X%9&&X>8&&X<81?X-40&&X-50?X-41&&X-49
?3:0:1:2);for(;p;x=f=0){for(X=7;X++<81;putchar("0@\n-"[b[X]]))C(),a?x=X:0;x?Y=0
,t?X=x:(std::cin>>Y>>X,0),f=X+=Y*9,C(),t=a?p=2,t:!t:(puts("PASS"),p--);t=!t;}}
パス判定を変更 (421バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d[]{-9,-8,1,10,9,8,-1,-10};void C(){a=0;for(i=b[
X]-3?0:8;i--;){for(j=1;b[Y=X+d[i]*j]==!t;)j++;if(1<j&&b[Y]==t)for(;j--;a++)f?b[
X+d[i]*j]=t:0;}}int main(){for(;X--;p=b[X]=X%9&&X>8&&X<81?X-40&&X-50?X-41&&X-49
?3:0:1:2);for(;p;x=f=0){for(X=7;X++<81;putchar("0@\n-"[b[X]]))C(),a?x=X:0;x?Y=0
,t?X=x:(std::cin>>Y>>X,0),f=X+=Y*9,C(),a?p=2:t=!t:(puts("PASS"),p--);t=!t;}}
C()内のaの初期化をputcharのところに変更 (420バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d[]{-9,-8,1,10,9,8,-1,-10};void C(){for(i=b[X]-3
?0:8;i--;){for(j=1;b[Y=X+d[i]*j]==!t;)j++;if(1<j&&b[Y]==t)for(;j--;a++)f?b[X+d[
i]*j]=t:0;}}int main(){for(;X--;p=b[X]=X%9&&X>8&&X<81?X-40&&X-50?X-41&&X-49?3:0
:1:2);for(;p;x=f=0){for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C(),a?x=X:0;x?Y=0,
t?X=x:(std::cin>>Y>>X,0),f=X+=Y*9,C(),a?p=2:t=!t:(puts("PASS"),p--);t=!t;}}
d[]を削除して数式に変更 (401バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d;void C(){for(i=b[X]-3?0:9;i--;){d=i+i/3*6-10;
for(j=1;b[Y=X+d*j]==!t;)j++;if(1<j&&b[Y]==t)for(;j--;a++)f?b[X+d*j]=t:0;}}int
main(){for(;X--;p=b[X]=X%9&&X>8&&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x=f
=0){for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C(),a?x=X:0;x?Y=0,t?X=x:(std::cin
>>Y>>X,0),f=X+=Y*9,C(),a?p=2:t=!t:(puts("PASS"),p--);t=!t;}}
敵の置ける場所の更新位置を変更 (397バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d;void C(){for(i=b[X]-3?0:9;i--;){d=i+i/3*6-10;
for(j=1;b[Y=X+d*j]==!t;)j++;if(1<j&&b[Y]==t)for(x=X;j--;a++)f?b[X+d*j]=t:0;}}
int main(){for(;X--;p=b[X]=X%9&&X>8&&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p
;x=f=0){for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C();x?Y=0,t?X=x:(std::cin>>Y>>
X,0),f=X+=Y*9,C(),a?p=2:t=!t:(puts("PASS"),p--);t=!t;}}
putsとp--を&で結合 (394バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d;void C(){for(i=b[X]-3?0:9;i--;){for(d=i+i/3*6-
10,j=1;b[Y=X+d*j]==!t;)j++;if(1<j&&b[Y]==t)for(x=X;j--;a++)f?b[X+d*j]=t:0;}}int
main(){for(;X--;p=b[X]=X%9&&X>8&&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x=f
=0){for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C();x?Y=0,t?X=x:(std::cin>>Y>>X,0)
,f=X+=Y*9,C(),a?p=2:t=!t:puts("PASS")&p--;t=!t;}}
条件式の&&を&に置き換え (392バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d;void C(){for(i=b[X]-3?0:9;i--;){for(d=i+i/3*6-
10,j=1;b[Y=X+d*j]==!t;)j++;if(1<j&b[Y]==t)for(x=X;j--;a++)f?b[X+d*j]=t:0;}}int
main(){for(;X--;p=b[X]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x=f=
0){for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C();x?Y=0,t?X=x:(std::cin>>Y>>X,0),
f=X+=Y*9,C(),a?p=2:t=!t:puts("PASS")&p--;t=!t;}}
変数YにX+d*j++を入れて使いまわし (391バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d;void C(){for(i=b[X]-3?0:9;i--;){for(d=i+i/3*6-
10,j=1;b[Y=X+d*j++]==!t;);if(2<j&b[Y]==t)for(x=X;j--;a++)f?b[X+d*j]=t:0;}}int
main(){for(;X--;p=b[X]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x=f=
0){for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C();x?Y=0,1?X=x:(std::cin>>Y>>X,0),
f=X+=Y*9,C(),a?p=2:t=!t:puts("PASS")&p--;t=!t;}}
fの判定をforに埋め込み (390バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d;void C(){for(i=b[X]-3?0:9;i--;){for(d=i+i/3*6-
10,j=1;b[Y=X+d*j++]==!t;);if(2<j&b[Y]==t)for(x=X;j--&&f;a++)b[X+d*j]=t;}}int
main(){for(;X--;p=b[X]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x=f=
0){for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C();x?Y=0,1?X=x:(std::cin>>Y>>X,0),
f=X+=Y*9,C(),a?p=2:t=!t:puts("PASS")&p--;t=!t;}}
b[X]-3?0:9をb[X]/3*9で表現 (389バイト)
#include <iostream>
int b[91],X=90,x,Y,t,a,i,j,f,p,d;void C(){for(i=b[X]/3*9;i--;){for(d=i+i/3*6-10
,j=1;b[Y=X+d*j++]==!t;);if(2<j&b[Y]==t)for(x=X;j--&&f;a++)b[X+d*j]=t;}}int main
(){for(;X--;p=b[X]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x=f=0){
for(X=7;X++<81;a=!putchar("0@\n-"[b[X]]))C();x?Y=0,1?X=x:(std::cin>>Y>>X,0),f=X
+=Y*9,C(),a?p=2:t=!t:puts("PASS")&p--;t=!t;}}
助言によりC++からCに変更。includeやvoid、intを削除、p,i,jの宣言位置を変更、Yの初期化方法を変更 (352バイト)
b[91],X=90,x,Y,t,a,f,d;C(i,j){for(i=b[X]/3*9;i--;){for(d=i+i/3*6-10,j=1;b[Y=X+d
*j++]==!t;);if(2<j&b[Y]==t)for(x=X;j--&&f;a++)b[X+d*j]=t;}}main(p){for(;X--;b[X
]=X%9&&X>8&X<81?X-40&&X-50?X-41&&X-49?3:0:1:2);for(;p;x?1?X=x:scanf("%d%d",&Y,&
X),f=X+=!1*Y*9,C(),p=!a?t=!t,p:2:puts("PASS")&p--,t=!t,x=f=0)for(X=7;81>X++;a=!
putchar("0@\n-"[b[X]]))C();}