C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[24]: 趣味の質問たかが3目並べされど三目並べ

(過去ログ 102 を表示中)

[トピック内 36 記事 (1 - 20 表示)]　 << 0 | 1 >>

■60636 / inTopicNo.1)

　趣味の質問たかが3目並べされど三目並べ

▼■

□投稿者/ 堀江伸一 (31回)-(2011/07/13(Wed) 09:13:46)

分類:[C/C++]　

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
リンク先は三目並べの勝敗を求めよという非常に簡単なプログラムの問題です。
この問題、コードを短くしようと下記のようなコードを書きました。
277バイトのコードで結構短く書いたつもりです。
しかしこの問題166バイトで書けるらしいのです。
もっと短くできるようなのですが、私には自分のコードをこれ以上短くする方法を思いつきません。
そこで質問です、もしこの問題を出来るだけ短いコードで解くなら皆さんはどのようなコードを書きますか？

私のコード。
#include<stdio.h>
int main(){
char m[10],k,t;
int s[]={0,1,2,0,3,6,0,2},d[]={3,3,3,1,1,1,4,2};
while(scanf("%s",m)!=EOF){
k='d';
for(int i=0;i<8;i++){
t=m[s[i]]&m[s[i]+d[i]]&m[s[i]+2*d[i]];
if(t=='o' || t=='x'){
k=t;
break;
}
}
printf("%c\n",k);
}
}

引用返信 編集キー/

■60637 / inTopicNo.2)

　Re[1]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ 774RR (600回)-(2011/07/13(Wed) 10:40:28)

166バイトって何が166なのか？
ソースコードのバイト数？

C はインデントや改行文字が無くても問題ない言語なので、単純にソース短縮するなら
・改行文字を入れない
・ ISO C (ANSI C) より古い文法でいうところの、暗黙の int を活用する
・ ISO C (ANSI C) より古い文法でいうところの、暗黙の関数宣言を活用する
などすれば短く＋汚く＋読みにくくなる。

提示コードのロジックのまま単純に汚く短くしたら以下のような感じ
int s[]={0,1,2,0,3,6,0,2},d[]={3,3,3,1,1,1,4,2};main(i,k,t){char m[10];while(gets(m)){k='d';for(i=0;i<8;i++){t=m[s[i]]&m[s[i]+d[i]]&m[s[i]+2*d[i]];if(t=='o'||t=='x'){k=t;break;}}printf("%c\n",k);}}
１９９バイト＋お勧めできない度ＵＰ
# もっと短くしようとするとロジック変更が必要だと思うが興味なし

引用返信 編集キー/

■60640 / inTopicNo.3)

　Re[1]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ shu (846回)-(2011/07/13(Wed) 11:13:30)

■No60636 (堀江伸一さん) に返信
kには一回しか設定されるはずがないのでbreakをしなければ8byte稼げます。(ブロックにする必要がないので)

引用返信 編集キー/

■60645 / inTopicNo.4)

　Re[2]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ 堀江伸一 (32回)-(2011/07/13(Wed) 13:35:07)

166バイトというのはソースコードのバイト数です。

ギリギリまで削って191バイト、どうもありがとうございます。
この先根本的な発想の転換が必要なのかそれともコード短縮の単純なテクニックがもう少しあるのか少し興味がわきます。
文字通り趣味の問題ですが。

個人的な感想ですが、コロンブスの卵的な根本的な発想の転換というのが答えならうれしいです。
もし最善手にコード圧縮テクニックしかないなら嬉しさが半減する感じです。
短縮するとしてポインタ演算やビット演算を駆使するのかそれとももっとほかの方法なのか、少し興味があります。

引用返信 編集キー/

■60736 / inTopicNo.5)

　Re[3]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ 堀江伸一 (33回)-(2011/07/16(Sat) 17:39:46)

返答も集まらないみたいですしこのスレはこれで閉じます。

引用返信 編集キー/

■60737 / inTopicNo.6)

　Re[4]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ 堀江伸一 (34回)-(2011/07/16(Sat) 17:39:49)

■No60736 (堀江伸一さん) に返信
> 返答も集まらないみたいですしこのスレはこれで閉じます。

引用返信 編集キー/

■60738 / inTopicNo.7)

　Re[5]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ やじゅ (1931回)-(2011/07/16(Sat) 20:20:09)

■No60737 (堀江伸一さん) に返信

C言語でのコードを短くするというなら、下記の本が参考になると思います。
Short Coding ~職人達の技法~
http://www.amazon.co.jp/dp/4839925232

引用返信 編集キー/

■60743 / inTopicNo.8)

　Re[6]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ ミキオ爺 (1回)-(2011/07/16(Sat) 21:48:58)

そこで質問です、もしこの問題を出来るだけ短いコードで解くなら皆さんはどのようなコードを書きますか？＞＞ぷっ。

高級言語の価値が下るだけですよ。
意味もない。

引用返信 編集キー/

■60744 / inTopicNo.9)

　Re[6]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ 逆運の覇者 (37回)-(2011/07/16(Sat) 21:59:04)

774RRさんのソースから1バイト削減。
しょうもないことですが。

while(gets(m)){k='d';
を
for(;gets(m);k='d'){
で置き換えます。
さらにshuさんの「breakをしない」を加えてこうなります。

int s[]={0,1,2,0,3,6,0,2},d[]={3,3,3,1,1,1,4,2};main(i,k,t){char m[10];for(;gets(m);k='d'){for(i=0;i<8;i++){t=m[s[i]]&m[s[i]+d[i]]&m[s[i]+2*d[i]];if(t=='o'||t=='x')k=t;}printf("%c\n",k);}}

ところで、774RRさんのソースは197バイトですよ。
なのでこれで188バイトです。

引用返信 編集キー/

■60746 / inTopicNo.10)

　Re[5]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ ピーター (19回)-(2011/07/17(Sun) 00:09:33)

おそらく、正解はいかにコード記述を短くするかではなくて、アルゴリズムで手順を短くするところに本質があるのだろう。
何度も言うようだが、ここの掲示板でアルゴリズム論を問い合わせても、回答を得るのは難しいだろう。

ところで、この問題でいうところの「ありえない局面」は考慮に入っているのだろうか？
この条件が提示コードのどの個所に該当するのかが分からなかったので。
おそらく、この条件を使わないと手順短縮が出来ないのであろう。
あとは、問題を見るにあたり、先手が○であることに注目すべきであろう。
小生ならば、これらに注目してアルゴリズムを考えるが、如何か？

引用返信 編集キー/

■60747 / inTopicNo.11)

　Re[7]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ shu (863回)-(2011/07/17(Sun) 00:12:19)

■No60744 (逆運の覇者さん) に返信
> 774RRさんのソースから1バイト削減。
> しょうもないことですが。
>
> while(gets(m)){k='d';
> を
> for(;gets(m);k='d'){
> で置き換えます。
> さらにshuさんの「breakをしない」を加えてこうなります。
>
> int s[]={0,1,2,0,3,6,0,2},d[]={3,3,3,1,1,1,4,2};main(i,k,t){char m[10];for(;gets(m);k='d'){for(i=0;i<8;i++){t=m[s[i]]&m[s[i]+d[i]]&m[s[i]+2*d[i]];if(t=='o'||t=='x')k=t;}printf("%c\n",k);}}
>
さらにごちゃごちゃにしてsとtをくっつけて、もう一つ変数bを用意して最初のs[i]をbに代入してみます。

int s[]={0,1,2,0,3,6,0,2,3,3,3,1,1,1,4,2};main(i,k,t,b){char m[10];for(;gets(m);k='d'){for(i=0;i<8;i++){t=m[b=s[i]]&m[b+s[i+8]]&m[b+2*s[i+8]];if(t=='o'||t=='x')k=t;}printf("%c\n",k);}} => 184bytes

さらにsとdの並びを入れ替えると

int s[]={3,3,3,1,1,1,4,2,0,1,2,0,3,6,0,2};main(i,k,t,b){char m[10];for(;gets(m);k='d'){for(i=0;i<8;i++){t=m[b=s[i+8]]&m[b+s[i]]&m[b+2*s[i]];if(t=='o'||t=='x')k=t;}printf("%c\n",k);}} => 182bytes

引用返信 編集キー/

■60748 / inTopicNo.12)

　Re[8]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ ピーター (20回)-(2011/07/17(Sun) 00:22:14)

■No60747 (shu さん) に返信

この問題は、上記で述べたように、アルゴリズムの考え方に本質がありそうです。
質問者のアルゴリズムそのままの単なるコード圧縮は無意味な議論だと思います。

引用返信 編集キー/

■60757 / inTopicNo.13)

　Re[6]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ 774RR (601回)-(2011/07/17(Sun) 08:48:39)

俺もう興味ないからこれ以上ツッコむ気無かったんだけど
そこまで言うなら自分でアルゴリズム考えてみたら？

当初提示コードのアルゴリズムは洗練されていてると思う。
そう簡単に「もっと良い」ものは出てこないと思うぞ。

引用返信 編集キー/

■60761 / inTopicNo.14)

　Re[7]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ flied onion (2回)-(2011/07/17(Sun) 10:48:57)

> int s[]={3,3,3,1,1,1,4,2,0,1,2,0,3,6,0,2};main(i,k,t,b){char m[10];for(;gets(m);k='d'){for(i=0;i<8;i++){t=m[b=s[i+8]]&m[b+s[i]]&m[b+2*s[i]];if(t=='o'||t=='x')k=t;}printf("%c\n",k);}} => 182bytes
int s[]={3,3,3,1,1,1,4,2,0,1,2,0,3,6,0,2};main(i,k,t,b){char m[10];for(;gets(m);k='d'){for(i=0;i<8;i++){t=m[b=s[i+8]]&m[b+s[i]]&m[b+2*s[i]];if(t=='o'||t=='x')k=t;}printf("%c\n",k);}}

kをその位置で初期化すると初回が引き分けだと私の環境では表示がおかしくなります。

sをcharにしてkの初期化位置を変えてみました。
main(i,t,b){char s[]={3,3,3,1,1,1,4,2,0,1,2,0,3,6,0,2},m[10],k='d';for(;gets(m);){for(i=0;i<8;i++){t=m[b=s[i+8]]&m[b+s[i]]&m[b+2*s[i]];if(t=='o'||t=='x')k=t;}printf("%c\n",k);}} => 177Bytes

引用返信 編集キー/

■60762 / inTopicNo.15)

　Re[7]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ ピーター (21回)-(2011/07/17(Sun) 11:29:25)

2011/07/17(Sun) 12:47:41 編集(投稿者)

■No60757 (774RR さん) に返信

> そこまで言うなら自分でアルゴリズム考えてみたら？

考えついているから、先の発言をしたまでである。

> 当初提示コードのアルゴリズムは洗練されていてると思う。

何を以て洗練されているというのか理解できないが、最初のアルゴリズムは単純に縦・横・斜めを
ビンゴが検出されるまでチェックしている点に注目すると、これはありきたりのアルゴリズムで、
洗練されているとは思わない。
なぜならば、小生が指摘した「ありえない局面」という条件、および先手が○であることに注目すれば、
縦・横・斜めのビンゴチェックは不要のはずである。
（少なくとも、問題では「ありえない局面」という条件を明示してあるので、洗練されたアルゴリズムであれば
まずこの点を見逃すわけがないはずである。）

もう質問者がここを見に来るかどうか不明だし、小生のアルゴリズムが正解かどうかも不明であるが、
（少なくとも質問者のアルゴリズムよりは洗練されていると自負できるが）
本件に関して興味ある方のために小生のアルゴリズムについてヒントを出すと、

・マスがすべて埋まっていない場合、埋まったマスの数が奇数か偶数か（あるいは、空のマスが偶数か奇数か）
　で○と×の勝者は判定できる。
・マスがすべて埋まった場合はドローもしくは○の勝ちであるが、この場合、あるマスが○の場合は○の勝ちと判定できる。
　逆にいえば、あるマスが×の場合はドローと判定できる。
　（これはシミュレーションしてみれば分かる。当然、「ありえない局面」が発生しないようにしなければならぬ。）

このアルゴリズムのコード化は、興味をお持ちの他の方にお任せすることとする。
小生はC言語は得意ではないし、ビジネスロジックをコード化するときは、必ず概要をコメントとして書き込むので、
結果、ソースのバイト数が増えてしまうのであるｗ

質問者には何度も言いたいが、ここでアルゴリズムの質問をしても、回答は期待しない方がいい。
このスレッドのレスを見れば一目瞭然である。

引用返信 編集キー/

■60763 / inTopicNo.16)

　Re[8]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ επιστημη (2655回)-(2011/07/17(Sun) 13:29:50)

このコンテキストにおいて"洗練されている"は"賢い"の意味じゃないよね。"コンパクトに記述できる"よね。
ピーターさんの挙げたアルゴリズムは"コンパクトに記述できる"んだろうか。

引用返信 編集キー/

■60764 / inTopicNo.17)

　Re[9]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ flied onion (3回)-(2011/07/17(Sun) 14:33:28)

επιστημηさんが指摘されてるように目指してる問題解決の方向性が違うようですが、一応指摘というか補足。

> ところで、この問題でいうところの「ありえない局面」は考慮に入っているのだろうか？

リンク先の問題に「ありえない局面が入力されることはありません。」と書いてあります。

> マスがすべて埋まっていない場合
> マスがすべて埋まっている場合
マスがすべて埋まっていない場合か、マスがすべて埋まった場合かは全てのマスをみないとわかりません。
(入力は常に全マス分であり、oかxか空白を表すsです。ループするとか全部ANDして'h'になるかとかなにかしら判断が必要でしょう）

引用返信 編集キー/

■60765 / inTopicNo.18)

　Re[9]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ ピーター (22回)-(2011/07/17(Sun) 14:45:39)

■No60763 (επιστημη さん) に返信
> このコンテキストにおいて"洗練されている"は"賢い"の意味じゃないよね。"コンパクトに記述できる"よね。
> ピーターさんの挙げたアルゴリズムは"コンパクトに記述できる"んだろうか。

例えば、誤差が小さい・動作が安定であるという"賢さ"であれば、いくら賢いアルゴリズムでもコードがコンパクトでない場合もあろうが、
同じ結果を返すのであれば、"賢い"と仰るアルゴリズムは手順が少ないので、コードはコンパクトになるはずであるが、違うだろうか。
（ちなみに、コンパクトなコードの定義を、空欄や改行等、省けるものを省いたコードのことを指すのであれば、
それは小生が指摘しているとおり、論点がずれていると申し上げたい。）

例を挙げてみよう。
仕様に、1からnまでの合計を計算するロジックがあったとする。
貴殿ならば、1からnまでをループを使って加算し続けるだろうか？
結果としては正解を得られるが、賢くもないし、コンパクトでもない。
計算はご存じの通り(1+n)*n/2でいいはずである。
（これは数学で習う公式なのだろうが、少し考えれば導き出せるレベルの式なので、この公式を暗記した覚えはない。）

また、仮に、質問者が提示されたコードが洗練されているとしよう。
しかし、問題掲載サイトに「ありえない局面」という条件を、わざわざ、大きく図示して明示してあるのにもかかわらず、
これをアルゴリズムに考慮していないというのは「洗練されている」以前の問題ではないだろうか？
少なくとも、結果は正しいのだろうが、回答としては不正解ではないか？
（そもそも、これは解答の必ずある問題なので、問題文にある条件は必ず解答に結びつくはずである。）
まぁ、システム設計をしたことのないものには理解できないのだろうが、「ありえない局面」という仕様を見逃すとは
設計者にとっては初歩的なミスであり、重篤な結果を招く恐れがあるということは、重々理解できるはずである。

さて、小生のアルゴリズムでは、縦・横・斜めのビンゴチェックが不要のため、

> int s[]={0,1,2,0,3,6,0,2},d[]={3,3,3,1,1,1,4,2};

のマトリックスは不要になる。これで記載コードが減ったのではないか？
あとは空マスを数えて単純な比較で処理は終わる。
以上だ。

引用返信 編集キー/

■60766 / inTopicNo.19)

　Re[10]: 趣味の質問たかが3目並べされど三目並べ

▲▼■

□投稿者/ ピーター (23回)-(2011/07/17(Sun) 14:57:13)

■No60764 (flied onion さん) に返信

>>ところで、この問題でいうところの「ありえない局面」は考慮に入っているのだろうか？
>
> リンク先の問題に「ありえない局面が入力されることはありません。」と書いてあります。

これは小生に対する意見であろうか？

>>ところで、この問題でいうところの「ありえない局面」は考慮に入っているのだろうか？

とは、「ありえない局面が入力されることはありません。」という条件が質問者の提示コードには考慮されているのかどうか
（つまり、ありえない局面がインプットされないことを前提に設計されたものなのかどうか）という疑問であるのだが、

> リンク先の問題に「ありえない局面が入力されることはありません。」と書いてあります。

これは小生に何を伝えたいのか、分かりやすく説明して貰えないだろうか。

>
>>マスがすべて埋まっていない場合
>>マスがすべて埋まっている場合
> マスがすべて埋まっていない場合か、マスがすべて埋まった場合かは全てのマスをみないとわかりません。
> (入力は常に全マス分であり、oかxか空白を表すsです。ループするとか全部ANDして'h'になるかとかなにかしら判断が必要でしょう）

この判断は必要である。
このレスのひとつ前のレスに、アルゴリズムのコンパクトさを記述したので見て頂きたい。

引用返信 編集キー/

■60767 / inTopicNo.20)

　Re[11]: 趣味の質問たかが3目並べされど三目並べ

▲　■

□投稿者/ flied onion (4回)-(2011/07/17(Sun) 16:00:11)

2011/07/17(Sun) 16:06:43 編集(投稿者)

* 返信部分修正

とりあえず書いてみました。

#include<stdio.h>
int main(){
char m[10],t=0,i,k;
for(;gets(m);){
for(i=0;i<9;i++)
if(m[i]=='s')t++;
if(t==0){
k='o';
if(m[4]=='x')k='d';
}else{
k='x';
if(t%2==0)k='o';
}
printf("%c\n",k);
}
}

すべて埋まった場合の「あるマス」はひとまず中央としましたが、
oox
xoo
oxx
で○の勝ちと判断されるため、中央とした私の間違いでしょう。
あるマスが特定の 1マスであれば改行その他けずれば結構短くなりそうですね。

■No60766 (ピーターさん) に返信
>>> ところで、この問題でいうところの「ありえない局面」は考慮に入っているのだろうか？
>> リンク先の問題に「ありえない局面が入力されることはありません。」と書いてあります。
> これは小生に何を伝えたいのか、分かりやすく説明して貰えないだろうか。

「ありえない局面がきたらどうするのか」という意味の発言かと思ったからです。
ガード条件や不整合チェックをしていないので私には「ありえない局面が来ない」仕様は考慮しているようにみえましたので。

ただ全体を読めばそういう意図ではないことはわかりますので私の勘違いですね。

引用返信 編集キー/

次の20件＞
トピック内ページ移動 / << 0 | 1 >>

- Child Tree -