Just another Ruby porter,


2月上旬の日記 | RDF

2016-02-04 (Thu)

Project Euler Problem 26 #シェル芸

Reciprocal cycles. 逆数の循環節。
d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ。

bcでscaleを適当に大きく設定すれば力ずくで解ける。
肝は繰り返しの正規表現でこればかりはRubyやPerlじゃないと面倒。

% time (seq -f 'scale=2000;1/%g' 999|BC_LINE_LENGTH=0 bc|ruby -pe 'sub(/.*(.+)\1+$/){"#$. #{$1.size}"}'|sort -k2n|tail -n1)
983 982
( seq -f 'scale=2000;1/%g' 999 | BC_LINE_LENGTH=0 bc | ruby -pe  | sort -k2n )  3.13s user 0.01s system 104% cpu 3.011 total

3秒かかる。

というわけでちゃんと計算してみる。
たとえば1/17を小数点以下40桁分計算するとこんな感じになる。

% echo 'r=1;for(i=0;i<40;i++){r*=10;print r/17;r%=17}'|bc;echo
0588235294117647058823529411764705882352

循環は商で考えてしまうと難しい。ここで重要なのは余りのほう。
同じ余りに戻ってきたときに1周したと考えればいい。
この方針だと瞬時に求まる。しかも短い。

% time (seq 999 | awk '{for(r=1;!a[r];r=10*r%$0)a[r]=1;print $0,length(a);delete a}'|sort -k2n|tail -n1)
983 982
( seq 999 | awk '{for(r=1;!a[r];r=10*r%$0)a[r]=1;print $0,length(a);delete a})  0.05s user 0.00s system 90% cpu 0.053 total

余りで考えると循環の長さは最大でも除数-1にしかならないことがわかる。
これを利用するとさらに高速化が可能となる。


2016-02-03 (Wed)

Project Euler Problem 25 #シェル芸

1000-digit Fibonacci number. 1000桁のフィボナッチ数。
ひねりなし。

% echo 'b=1;l=10^999;for(;a<l;i++){a=b-a;b+=a}; i' | bc
4782

最初の1000桁は10^999なので豪快にこれと比較する。

cf: Project Eulerをシェル芸で解いてみる(Problem 25) #シェル芸 - Qiita


2016-02-02 (Tue)

Project Euler Problem 24 #シェル芸

Lexicographic permutations. 辞書式順列。
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目。
順列ということは10!通りの数がある。
1桁目は10通り。ということはそれぞれ9!(362880)のブロックになる。
1000000/362880が2.7ぐらいなので、1桁目は0,1,2の2になる。
1000000%362880=274240ということで、今度は8!(40320)で同じように進めると、
274240/40320が6.8ぐらいなので、2桁目は0,1,3,4,5,6,7の7になる。
これをシェル芸で表現する。

% echo 0123456789 | sed -r "$(echo 'n=999999;f=3628800;for(i=10;i>0;--i){f/=i;n/f;n%=f}'|bc|sed 's/./s,(.{&})(.)(.*),\\1\\3\\2,/')"
2783915460

まず、3628800は10!。階乗の値は9!,8!と必要になるのでつぎつぎと割ってあげればいい。

% echo 'n=999999;f=3628800;for(i=10;i>0;--i){f/=i;n/f;n%=f}'|bc
2
6
6
2
5
1
2
1
1
0

これを使って0123456789から抜き出すわけだけど、抜き出す代わりに並び換える。
次々と最後へ10回繰り返して移動させれば抜き出すのと同じことになる。

% echo 2662512110|sed 's/./s,(.{&})(.)(.*),\\1\\3\\2,\n/g'
s,(.{2})(.)(.*),\1\3\2,
s,(.{6})(.)(.*),\1\3\2,
s,(.{6})(.)(.*),\1\3\2,
s,(.{2})(.)(.*),\1\3\2,
s,(.{5})(.)(.*),\1\3\2,
s,(.{1})(.)(.*),\1\3\2,
s,(.{2})(.)(.*),\1\3\2,
s,(.{1})(.)(.*),\1\3\2,
s,(.{1})(.)(.*),\1\3\2,
s,(.{0})(.)(.*),\1\3\2,

このsed scriptを通してあげれば並び換え完成。
backslashがうっとうしいので-rオプションを使っている。

cf: Project Eulerをシェル芸で解いてみる(Problem 24) #シェル芸 - Qiita

やってることは基本同じ。


2016-02-01 (Mon)

Project Euler Problem 23 #シェル芸

Non-abundant sums. 非過剰数の総和。
真の約数の和が出てくるのでProblem 21の方法が使える。

% time seq 28123 | gawk 'i=$0{n[i]=i;for(j=i*2;j<=28123; j+=i)a[j]+=i;if(i<a[i])b[++k]=i}END{for(i in b)for(j=i;(sum=b[i]+b[j])<=28123;j++)n[sum]=0;for(i in n)s+=n[i];print s}'
4179871
seq 28123  0.00s user 0.00s system 0% cpu 0.066 total
gawk   4.41s user 0.00s system 99% cpu 4.416 total

aに真の約数の和、bに過剰数をいれて、それを使って過剰数の和を削除している。
n[sum]=0はdelete n[sum]でいいんだけど遅い。
それとjはfor(j in b)とできるんだけどやはり遅い。

mawkはgawkよりやはり速い。

% time seq 28123 | mawk 'i=$0{n[i]=i;for(j=i*2;j<=28123; j+=i)a[j]+=i;if(i<a[i])b[++k]=i}END{for(i in b)for(j=i;(sum=b[i]+b[j])<=28123;j++)n[sum]=0;for(i in n)s+=n[i];print s}'
4179871
seq 28123  0.00s user 0.00s system 0% cpu 0.077 total
mawk   3.30s user 0.00s system 99% cpu 3.300 total

cf: Project Eulerをシェル芸で解いてみる(Problem 23) #シェル芸 - Qiita


2016-01-31 (Sun)

N!の最下位桁から続く0をすべて除いた値の下位9桁を出力 #シェル芸

1<=N<=1000000で。
【解説】プログラミングでかわいい彼女をつくって水着を着てもらう方法 - paiza開発日誌
なんちゅうタイトルだ。
Pythonでの解説が書いてあるが、なんか結構まどろっこしい。
awkだと9桁×1000000は問題なく扱えるので2と5に分ける必要はない。

% mawk 'BEGIN{printf "%.f\n", 999999999*1000000}'
999999999000000

というわけでこれで十分。

% time seq 1000000|mawk '{m*=$0; while(m%10==0)m/=10; m%=1e9}END{print m}' m=1
58412544
seq 1000000  0.00s user 0.05s system 24% cpu 0.214 total
mawk '{m*=$0; while(m%10==0)m/=10; m%=1e9}END{print m}' m=1  0.21s user 0.00s system 98% cpu 0.215 total

2月上旬の日記 | RDF


WWW を検索 jarp.does.notwork.org を検索

わたなべひろふみ
Key fingerprint = C456 1350 085F A320 C6C8 8A36 0F15 9B2E EB12 3885
Valid HTML 4.01!