2009-02-26

UTF-9への道のりと教訓

golf c

anarchy golf でやっているショートコーディングのお題のUTF-9 でようやくC言語でトップが取れたのでその道のりを公開。
かなり69バイトをさまよっていますｗｗｗ

ポイント

変数iで連結したビット数をカウント
0の場合は次の１バイトを連結しても出力はできないので、
出力条件は"!i"のみで行える。

成果物（68バイト）

結局三項演算子の順序の問題でした。

c,i;main(x){for(;~scanf("%x",&x);!i--?i=8:putchar(c>>=9))c|=x<<i+9;}

教訓

三項演算子で代入文を使いたい場合は、条件を否定してでも２項目で代入すべし！

要するに

a?b:(c=1);

をやりたくば、条件を否定して

!a?c=1:b;

とするだけで、1バイト削れる！

迷い道(全て69バイト・・・)

c,i;main(x){
	for(;~scanf("%x",&x);i--?putchar(c),c>>=9:(i=8))c|=x<<i;
}

c,i;main(x){
	for(;~scanf("%x",&x);i--?putchar(c>>=9):(i=8))c|=x<<i+9;
}

c,i;main(x){
	for(;~scanf("%x",&x);i+=i?putchar(c),c>>=9,-1:8)c|=x<<i;
}

c,i;main(x){
	for(;~scanf("%x",&x);i+=i?putchar(c>>=9),-1:8)c|=x<<i+9;
}

c,i;main(x){
	for(;~scanf("%x",&x);i-=i?putchar(c>>=9),1:-8)c|=x<<i+9;
}

c,i;main(x){
	for(;~scanf("%x",&x);i=i?putchar(c),c>>=9,i-1:8)c|=x<<i;
}

c,i;main(x){
	for(;~scanf("%x",&x);i=i?putchar(c>>=9),i-1:8)c|=x<<i+9;
}

c,i;main(x){
	for(;~scanf("%x",&x);i--?putchar(c>>=9):(i=8))c|=x<<i+9;
}

最大の迷い道（main再帰www)

main再帰というのは普通にプログラム組んでいる人にとってはパラレルワールド位別世界で考えられないことだろう。。。

c,i;main(x){
	~scanf("%x",&x)?c|=x<<i+9,i=i?putchar(c>>=9),i-1:8,main(x):0;
}

c,i;main(x){
	~scanf("%x",&x)?c|=x<<i+9,!i--?i=8:putchar(c>>=9),main(x):0;
}

2009-02-26

Rubyで2^x以上で最小の素数

Ruby programing

ちょと必要だったので、そのときのプログラムをメモ。

なぜ計算したかったのか？

xが1〜32までの時の2^x以上で最小の素数が欲しかったんです
ハッシュテーブルの大きさとかによく使うでしょ（そうそれ！

ソース

require 'mathn'

(1..32).each{|x| puts lambda{|i|
    while true
      break if i.prime?
#     break if i.prime_division.size == 1 && i.prime_division[0][1] == 1
#     break if 'X' * i !~ /\A(XX+)\1+\z/
      i = i + 1
    end
    return i
  }.call(2**x)
}

出力

解説

素数を求めるためにInteger#prime_divisionを使っています。
prime_divisionは整数を素因数分解するためのメソッドです。
各素因数がいくつあるかを、2次元配列で返してくれます。

irb(main):391:0* (10..30).each{|x| p x.prime_division}
[[2, 1], [5, 1]]
[[11, 1]]
[[2, 2], [3, 1]]
[[13, 1]]
[[2, 1], [7, 1]]
[[3, 1], [5, 1]]
[[2, 4]]
[[17, 1]]
[[2, 1], [3, 2]]
[[19, 1]]
[[2, 2], [5, 1]]
[[3, 1], [7, 1]]
[[2, 1], [11, 1]]
[[23, 1]]
[[2, 3], [3, 1]]
[[5, 2]]
[[2, 1], [13, 1]]
[[3, 3]]
[[2, 2], [7, 1]]
[[29, 1]]
[[2, 1], [3, 1], [5, 1]]
=> 10..30

注意

prime_divisionを使うためにはmathnをrequireしておく必要があります。

require 'mathn'

ちなみに・・

      break if 'X' * i !~ /\A(XX+)\1+\z/

がコメントアウトされていますが、これ（正規表現）でも

      break if i.prime_division.size == 1 && i.prime_division[0][1] == 1

と、同じ動きをするようです。（激遅ですがｗｗｗ

とりあえず、メモ。。
参考：第28回 Ruby/Rails勉強会＠関西に行ってきたよ - はこべにっき ♨

追記

Prime#prime?

を使えば良かったんや。。