おじい研究所

主にプログラミングの話題です

0.00278%くらいの確率で通るコード

悪い意味で頭がおかしい

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回は超えると思います。

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

ついった

今更ながら、ついった始めてみた。
http://twitter.com/ozy4dm
ゴルフのことしか言わない。昼何食べたとか、そんな話はしない。ゴルフ中に鬱積したものだけを放出する。もうね、病気なんです。短いコードを書いてぎゃーぎゃー騒いでいないと死んでしまうんです、僕。すみません。

すごすぎるグレイコード

変態すぐる

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

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

続きを読む

グレイコードが熱い

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

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

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

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

問題いぱーい

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

postfix to infix

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

postfix to infix

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

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

z80は神(´ω`)


こっちは古い版