Cozy Ozy このページをアンテナに追加 RSSフィード

2009-06-22 0.00278%くらいの確率で通るコード

[][]0.00278%くらいの確率で通るコード 0.00278%くらいの確率で通るコード - Cozy Ozy を含むブックマーク

悪い意味で頭がおかしい

http://golf.shinh.org/p.rb?simple+octagon+tesselation

参戦者が少なくて寂しかったのですが、1人2人でも手を抜かずに!


というわけで、CとRubyで酷いことをやってしまいました。

C(119B)
i,j,k;
main(a,n)
{
  for( n%=33u; i<n;
   putchar(
    ++j+a>n-fmax(k=n%4*3-(i>9?n+~i:i)/3*3,0) ?
     j=!++i,10 : " #"[j>k&&a^j%3&1]
   )
  )a=i%3<1;
}
Ruby(105B)
i=0;eval'(1..n-[k=n%4-[i,n-i+=1].min/3,0].max*3-a=i%3&1).map{|j|putc" #"[j>k*3?a^j%3&1:0]};puts;'*n=id%33

グレイコードの時も使われた、乱数を利用する方法を用いたわけですが、普通は10未満の小さな値でやります。でないと確率がバカみたいに低いからです。0〜4を出すだけで5×5×5=125分の1で、100回前後postしなければならないわけですが、今回は33×33×33=35937分の1という確率のコードを通しました。しかもCとRubyで2回も(;´Д`)

最初に通したときは、34000回くらいで通りました。2回目は22000回くらい。もちろん100回程度で通るバージョンは何度も通してるので、post回数は軽く60000回は超えると思います。

f:id:Ozy:20090622203531j:image

shinhさんゴメンナサイもうしません(´ω`)

hogehoge 2009/06/24 01:57 ここまでくるともう針の穴ですな!

2009-06-14 ついった

[][][]ついった ついった - Cozy Ozy を含むブックマーク

今更ながら、ついった始めてみた。

http://twitter.com/ozy4dm

ゴルフのことしか言わない。昼何食べたとか、そんな話はしない。ゴルフ中に鬱積したものだけを放出する。もうね、病気なんです。短いコードを書いてぎゃーぎゃー騒いでいないと死んでしまうんです、僕。すみません。

2009-06-10 すごすぎるグレイコード

[][]すごすぎるグレイコード すごすぎるグレイコード - Cozy Ozy を含むブックマーク

変態すぐる

Gray codeが終了しました。私は結局8位でfinish。ナンバー1は*yuko*さんという方。唯一知らない(;´д`)ざざっとコードを見た感じ、*yuko*さんとkurimuraさんのを合わせたら90B切れますね。Top10の7名は、謎の3乗*1をやって大幅短縮しているみたいです。私も10進数でまとめて出力できないかなーと一瞬思って難しそうなので諦めたのですが、そうか8進数ならOKですよねー…。というわけで、今回のグレイコード祭りを通して得たアイデアをドドーンとまとめておきたいと思います。


素直なグレイコード

i番目のグレイコード

i ^ (i>>1)

で簡単に変換できることが知られています。私は色々と悩んだ結果、素直にこの方法で目一杯縮めることにしました。たぶん30回くらい書きました(笑)で、確実に通るので104B

i,k,v;
main(n)
{
  for(gets(&n);printf(i?&v:"Gray code  n=%c",n);)
    v=k?(i^i>>1)>>--k&1|48:~--i>>(k=n%8)?0:10;
}

iが正の整数だと(i^i/2)で大丈夫だったのだけど、負の数だとうまくいかなかったので諦めて普通にシフトした。nバイトのグレイコードを2進表示するためには、改行も含めて(n+1)回のループが必要になるので変数が増えるし、カウンタのリセットが必要になるのでここら辺が限界かなぁ。

kurimuraさんの1B短縮テクニック

Cで確実に通らないコードといえばargvを利用する方法が割と有名で、nをmain関数の第2引数にして

n=~n%9

みたいな使い方をします。最短を狙うなら、この辺の方法でごにょごにょするしかないと思うんですが、kurimuraさんのコードを見てみると、

n%=9u

となっています。そかそか、unsignedにしてやれば良いのね…。これでkurimuraさんに1B負けたのかorz

8進表示のグレイコード

これが思いつかなかった時点で完全に負けたかんじがします。とりあえず以下のコードを実行。

i,j,k;
main()
{
  for(i=0;++i<=32;)
  {
    printf("%o\n",k^=j*j*j);
    j=-i&i;
  }
}

実行結果

0
1
11
10
110
111
101
100
1100
1101
1111
1110
1010
1011
1001
1000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000

SU・GO・I☆

グレイコードとハノイの塔というのは密接に関わっていて、(ハノイで)移動させる円盤の番号と対応するビットを反転していくことでグレイコードになります。円盤の番号は2進で1が現れる最右のビット数と対応しているので、最右の1を得るビット演算

i & -i

を使って短くかけるのでハノイ方式は多分皆が思いつく方法だと思うのですが、8進表示でというところまでにはなかなか考えが至らない。思いついた人カシコー(゜Д゜)

感想

何度となく紹介してますが、

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

は必読だなぁと思っておりますが、正直今回はこれを読んだ程度じゃ全然アカンのだと痛感しました。2年前にショートコーディング本を書いたとき、たくさんあるアイデアを厳選して厳選して厳選して、気が狂いそうになったのを思い出しますが、当時このアイデアを知っていたなら、絶対コードゴルフのページに書いてただろうナァと思います。ん〜む、奥が深い。

とまあ、色々ありますが、何より今回は参加者が30人超もいてそこそこ盛り上がっていたのが一番ですね。ふぃづばづのときみたく100人以上参加したらもっと面白かっただろうけど^^

*1:testというのは私が名前を間違ってpostしちゃったやつです。スマソ^^;

kurimurakurimura 2009/06/10 11:58 正直小手先でがんばってもアルゴリズムで根本的に負けててうきーって感じですw

OzyOzy 2009/06/10 13:53 その気持ちは痛いほどわかります(>_<)
が、やっぱり99Bと100Bの差は大きいですよ〜!!

letterletter 2009/06/13 00:47 お疲れ様でした。
FizzBuzzのときは乗り遅れてしまったのですが、今回のgray codeやpostfix to infixでは競争できて面白かったです。
main関数の第2引数を使う不確実な方法も106Bくらいのときに試してみましたが、すごくめんどくさいですね;-)

OzyOzy 2009/06/14 09:46 お疲れ様です!letterさんとかkikさんとかkinabaさんあたりは運任せなコードをpostしないだろうなぁと思ってたので、100B切ってるのを見たとき絶望的な気分になりました^^;

2009-06-01 グレイコードが熱い

[][]グレイコードが熱い グレイコードが熱い - Cozy Ozy を含むブックマーク

あなごるのGray codeが熱い。

問題内容はいたってシンプルで、入力値nに対してnバイトのグレイコードを列挙するというものです。

n=3なら

Gray code  n=3
000
001
011
010
110
111
101
100

みたいな感じで出力します。Cのprintfには"%03b"みたいな書式が無いので、グレイコードへの変換と出力を無駄なく美しく書けるかが勝負のポイントでしょう。Cゴルファーは是非参加すべし!

締め切りまで1週間以上あるので、まだまだ縮むゾ!

letterletter 2009/06/01 23:47 単純ですけど書き方色々ありそうなんで限界が見えないですね。
Cゴルフ的には入力なし(n固定)の方がいいのにーと思ったり。

RobeRobe 2009/06/02 00:02 トップはまるで "%0*b" のような書式が存在しているかのような短さだ・・・。

OzyOzy 2009/06/02 22:15 なかなか閃きませぬ(´ω`)
最終的に入力を読み込む部分をXXして数バイト短縮して…ってなるんでしょうけど、なんかヤな感じですよねー。たしかにletterさんの仰るとおり、そこそこ大きめのn固定が良いと思います。

nanagyounanagyou 2009/06/03 01:01 しまった出遅れたと思ったときには 100B 未満とか!

OzyOzy 2009/06/04 22:43 なんかレベル高すぎて、TOP10に入れるかも微妙な感じですねー^^;とにかく締め切りまでに100B切りを目指さねば(>_<)

2008-02-07 なんじゃこれー

Ozy2008-02-07

[]Language Rankingが Language Rankingが - Cozy Ozy を含むブックマーク

表示されなくなってるるる

メールが面倒なのでトラバじゃ

id:shinichiro_h

shinichiro_hshinichiro_h 2008/02/07 23:29 適当に修正しました。ありがとうございます。

fkmfkm 2008/02/08 00:54 C#グループ 登録申請完了(`・ω・´)

2008-01-29 POJ3298

[][]問題いぱーい 問題いぱーい - Cozy Ozy を含むブックマーク

http://golf.shinh.org/

何問かインチキコードを通しておいたけど、まあ中途半端というかほとんど抜かれてますなー。Cゴルフはkurimuraさんとかhinoeさんが参戦するとあっというまにやられちまうゼ。Rubyのsum inputはそこそこ自信あったのになー。13Bスゴス。

2008-01-22 postfix to infix

[][]postfix to infix postfix to infix  - Cozy Ozy を含むブックマーク

忘れてた!!!とりあえず急いで縮めたけど、上位にはぜんぜん届いてないなぁ(´ω`)演算子の優先度をスタックに積むところをどうにかできるような気がしつつ、結局良い方法が思いつきませんでした。これから仕事に戻らないといけないので、今回は186Bでfinish。かな〜り悔しい。仕事に戻ったときに何か思いついたらもっと悔しい、きっと。

追記:

っちゅうわけで、締め切りになりました。上位はアルゴリズムが違うんだろなーと思ってましたが、なるほど後ろからやっつけるわけですね。後ろから…というのはちょっとやりかけて、難しそうなのでやめた記憶が^^;私はひたすら普通にスタックを使う方法でやってました。sprintfの書式文字列が一つにまとまったのと、括弧をつけるかどうかの判定がそこそこ簡単にできたので、なかなかよろしいかなーと思いましたが、配列を2つ使わないといけないのと文字列をpushする際にsprintfなりstrcpyなんかで一旦別のバッファに置かねばならない部分が痛い。まあ完敗ですねー。ちぇっっ

w[99],t[99][99],c,i,k;

main(n,s)
{
  for(;
    read(0,&c,1);
    k=w[i]=n>9?*t[++i]=c,0:n>0?
      sprintf(s,
        "%s%c%s%c(%s)"+k*4,
        !sprintf(t,n/5*w[i]%5?""-4:s,s=t+i)+t,
        c,t+i--,k&=k<n+c/45
      ),n:puts(s)
  )n=c-42?:5;
}

2008-01-11 postfix to infix

[][]postfix to infix postfix to infix - Cozy Ozy を含むブックマーク

http://golf.shinh.org/p.rb?postfix+to+infix

後置記法から中置記法に書き換える問題です。一見簡単そうなのですが、余計な括弧は除かなければならないので短く書くのは至難の業。期限までまだ11日以上あるにもかかわらずCゴルファーは燃えています。私のコードはそろそろ限界に近づいていますが、見た目が美しくないのでアルゴリズムに問題がありそうです。ということは200Bは切れるんじゃないかと思います。Cのキモいコードを愛する人は是非チャレンジを。

あと、Rubyで100Bちょっとというのは凄過ぎるのではないかと思うのですが、こんなときPerlゴルファーはどんなコードを繰り出すのか。興味深いです。

z80は神(´ω`)

hinoehinoe 2008/01/14 13:38 あけましてお久しぶりぶりです。ぶりぶり。
なんかこれまた久しぶりにOzyさん気合入ってるぽかったので、嬉しくなってむきになって対抗してみました。funnythingさんもすごいし、まだ気はぬけんね。
考えてみりゃショートコード本以来カキコするの初めてですね。ひどいな俺。
しばらくはゴルフをもって生存報告にかえさせていただきます、って状態が続くと思いますが、ShortCodingブログのほうにも何か書いていきたいですね。

OzyOzy 2008/01/14 15:39 おおーどもども、お久しぶりです!190B台はイメージできるものの、うまく書けません(´ω`)まだ時間があるので、ちょっと息抜きしてからまたチャレンジするつもりです。今年もよろしくでーす^^

2008-01-04 新しい、年

[]うるう年 うるう年 - Cozy Ozy を含むブックマーク

http://golf.shinh.org/p.rb?leap+year

うるう年かどうかを判定するプログラムです。さっきとりあえず書いてみたら、Cで91Bのコードになりましたが、Rubyだと70Bくらいでしか書けません。なので、Cはもっと縮むんでないかなーと思うのですがどうでしょうか。それなりにテストケースは多いですが、入力依存のコードを書くことは可能なので、ビット演算とか剰余とかを工夫すれば…と思ったりします。ヒマな人はレッツちゃれんじですよ!

nanagyounanagyou 2008/01/05 17:00 おめでとうございます。

職場などで話を聞いていると、誰しもだいたい10年から12年に1回死ぬほど忙しかったりする人生のピークが訪れているようですね。18歳〜20歳で1回目、そして30歳前後で2回目と。
特に30歳は仕事が調子に乗っているにもかかわらず、まだまだのつもりの体力が衰え始めているので、体を壊してしまう人が多いとか。
Ozyさんは同年代なので他人事ではない私です。

健康に気をつけつつ、仕事にショートコーディングに精を出していきたいですね(`ω´)

OzyOzy 2008/01/07 10:06 そうですねー。極端に体力が落ちているわけではないので、ついつい無理しがちになってます。微妙な体質の変化を掴んでおかないと、今後大きなミスをしてしまうような気がしました。長くプログラミングを楽しむためには、やはり体調管理ですね^^

2007-12-05 z80か!

[]z80か! z80か! - Cozy Ozy を含むブックマーク

http://golf.shinh.org/

added Z80 as a language.

z80が使えるようになっているとは(笑)

とりあえずサンプルを参考に"Hello, world!"を。

これで28バイト。トップは24バイトか…。

#PUTCHAR EQU 8000H
#GETCHAR EQU 8003H

 LD B,0DH
 LD HL,DATA

LOOP:
 JR Z,LOOP
 LD A,(HL)
 CALL #PUTCHAR
 INC HL
 DJNZ LOOP
 HALT

DATA:
 DB 'Hello, world!'