2008-02-07

Project Euler

が人気が出てきたみたいでかなり嬉しくてエントリーを書いちゃいます。

ちょっと前に検索したときは、そんなに目に付くサイトがなくて、まぁ日本人で登録してる参加者が40ちょいだからこんなもんかな、と思ってたんですが、最近、Connect Errorのemokenさんを発見したり、今しがた、k.inabaさん経由でid:ranha:20080205:1202202181を見つけたり。

ていうか、http://felicity.iiit.ac.in/~math/がすごい面白そうなんですが、知らない間に終わってました。

5x^2 + 14x + 1 が平方数になる自然数 x を小さい順に30個どうぞ

(from d.y.d.)
が、Project Eulerにも似たような(出てくる式は全く同じ)問題があって、一応解けたんですが、あまりに泥臭い手法なのでhttp://felicity.iiit.ac.in/~math/の解説を期待してたり。

誰かがhttp://felicity.iiit.ac.in/~math/の問題一覧を載っけてくれると凄く嬉しいです。私が。ログインしないと問題見れないっていう仕様はなんでなんだろう。

まぁ最近はあんまり手をつけてないんですが、このエントリー書いたらやる気でるんじゃないかな、っていう希望的予測。

2008-01-27

POJ3423 - Automaton optimization

3423 -- Automaton optimization

穴ゴルからの逃避でPOJを解いてみた。

一次元のセルオートマトンで、隣接するセル二つのうち一つのみが真のときにそのセルを真とするというルール(いわゆるルール90)で、初期状態として、真なセルのインデックスがn個与えられて、sステップ後のf〜f+lのセルの状態を表示せよ、という問題。
問題をざっと読んで、適当に書いて、サンプル通ったからいけるんじゃね? とか思ってsubmitしてみるとacceptされたパターン。こういうことやってるから適当なまんまなんじゃないかとは思わないでもない。というわけで以下適当な解説。というか思考過程。

2008-01-22

anarchy golf - postfix to infix(2)

deadlineが過ぎたので、初めて穴ゴルに参戦してみての感想などを。

まぁあれですよ。トップから28B差とかね。完敗ですよ完敗。というわけで以下のエントリは長い負け惜しみですw くっそぉぉぉ。

問題を読んで、最初に思い浮かんだのは素直にスタック使う方法と、うまく再帰を使っていけるのかな? 的なアイデアで、とりあえずスタックを使う方法でいってみたらそこそこ行けたのと、再帰を使う方法が、試し書きしてみてなんとも汚い感じのコードしか書けなかったので、スタックでごりごりと。
そのときのコードは以下。

c,p,f,u,s[99][99],m[99];
main(n){
  for(;read(0,&c,f=1);c-10?strcpy(s+n,c<48?n--,s:(n++,&c)):puts(s+n),m[n]=u)
    for(p=s,u=c/47+42/c;~f;)
      p+=sprintf(p,m[n-f]<u-c/45*--f?"(%s)%c":"%s%c",s+n-f,f*c);
}

id:Ozy:20080122さんが書いているように、sprintfとstrcpyがちょっと嫌だなとは思ったんですが(バッファは文字列スタックの最初を使用)、この問題のキモの一つである、括弧を付けるかどうかの判定は、まぁそこそこ短く書けたんじゃないかなぁとか、のほほんとしてたんですが、おもむろにletterさんとkinabaさんが20B以上短いコードをsubmitされてて鼻血が出そうになり。
ちょっと穴ゴル面白すぎじゃない? とか思いながらコードを書いては捨て書いては捨て、やっと最初の再帰のアイデアを思い出し。

再帰を使う方法を真面目に検討したときに、どうにかなりそうだったのが末尾から二分木を辿っていく感じで再帰かなぁと思い、書いてみたら案外いけるかな? ってレベルだったので、その線でがしがし縮めていって、できたコードが以下。

char*p,*q;
s[99];

F(g,a,f){
  for(a=*p--;g--;g?*--q=a:0)
    a<48?f=*p/47+42/ *p<a/47+42/a+a/45*g,f?*--q=41:0,F(2),f?*--q=40:0:0;
}
main(){
  for(;gets(s);puts(q))
    q=s+99,p=strchr(s,0)-1,F(2);
}

どう見ても括弧を付けるかの判定が汚いです。本当に(ry
って感じなんですが、なかなかこれ以上縮まずに、気がついたらIt's the end.

上位の方のコード雑感。
id:letterさん。149B。基本的なアイデアが似てるだけにすごい悔しい。完敗です。%を重ねて使うのは、たまに見たことあるけど使ったことがなかった、、%7までは全部考えたのになぁ、、、indexは知らなかったです。xor 1はすごいなぁ。
hinoeさん。154B。どう足掻いてもmain再帰だけは無理! って思ってたんですが、あれ、、、いけるんですねぇ。一回検討したんだけどなぁ、、、p+=read(0,p,s)がぱっと見理解できなかった。あぁ、なるほどなぁ。
kinabaさん。158B。19&86%qとか、、、敬意を込めて変態と呼ばせていただきますw

穴ゴルの感想。
puts()の返り値が0じゃないのに最初嵌りました。確認してないんですが、この処理系だとputs()の返り値は出力した文字列長なんですかね?
Unlambdaとかｽｺﾞｽ。
まぁしかし穴ゴルおもしろいですね。deadlineがあるとこんなに燃えるもんなのか。もはや萌えすら感じます。id:shinichiro_hさんにw
これからは面白そうな問題があったらガシガシ参加していきたいと、、、していけたらいいなぁ(弱気)

関係ないんですが、

ロベールのC++入門講座

作者: ロベール
出版社/メーカー: 毎日コミュニケーションズ
発売日: 2007/11/15
メディア: 単行本（ソフトカバー）
購入: 26人クリック: 25,357回
この商品を含むブログ (127件) を見る

を購入しました。
噂には聞いていましたが、本屋で見たときにちょっとニヤっとしてしまいましたw 殺人現場に落ちていたら凶器の候補に挙がることは間違いない分厚さ。
最近本を読む時間がなかなか取れないんですが、ぼちぼちと読ませていただこうと思います。

2008-01-14

POJ2273 - An Excel-lent Problem

2273 -- An Excel-lent Problem

中国の方から、メールで、「2273本気でチャレンジしてみてよ！」と言われたのでやってみた。

整数nをExcelの列の表記(1->A , 2->B , ... , 26->Z , 27->AA)に直すのがメインの問題。
ぱっと見、26進法でごにょごにょなんだけど、一工夫必要。

2008-01-11

anarchy golf - postfix to infix

穴ゴルは、最初の頃に手を出そうとして、気が付いたら問題数が増えてて、全部解くまとまった時間ができたらやろうと思ってたらずるずると放置になっていたんですが、今日早起きして、2008-01-11の、

Cのキモいコードを愛する人は是非チャレンジを。

の一文にグッと惹かれたので(w)、チャレンジしてみました。

真面目にショートコーディングするの久々やなぁ、とか思いつつガシュガシュ縮めていって、、、縮めていｔｔ、、、ちぢｍ、、、縮まねぇぇぇ、、、
トップと63B差とか、鈍ってるにしても大概ひどいもんです。まぁ頑張ります。

最近はめっきりProject Eulerにかかりきりなんですが、やっとTop100入りできたよ!
75% geniusからが長かった、、、
管理人さん曰く、easy-medium-easy-difficultの周期で問題を作ってるそうなので、ちょうどdifficultばっかりが残ってからが大変だったんですかね。
別に政治的イデオロギーとかは持ってないつもりですが、Top100に日本の国旗が表示されるとちょっと嬉しい。
現在87% genius。