〜2016年1月下旬〜
Lattice paths.
パスカルの三角形ということで、40!/(20!*20!)を求める問題となる。
% seq 40 | gawk '{m*=$0}NR==20{r=m}END{print m/r/r}' m=1
137846528820
gawkだとこのくらいの桁なら問題なく計算できる。
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 15) - Qiita
Power digit sum
% gawk 'BEGIN{split(2^1000,a,"");for(i in a)s+=a[i];print s}'
1366
なんでオーバーフローしないのかよくわからんけど、gawkだと計算できちゃう。
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 16) - Qiita
Number letter counts. andはイギリススタイルらしいよ。
かなりチートだが、bsdgamesパッケージにはnumberというコマンドが存在する。
% number 100 123 1000 one hundred. ... one hundred twenty-three. ... one thousand.
後はandの処理を加えるだけ。
% seq 1000 | number | sed '/red /aand' | tr -cd a-z | wc -c 21124
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 17) - Qiita
マニュアルに
# Evaluate the resulting words as numeric expressions and output the characters corresponding to the
resulting integer. Note that this form is entirely distinct from use of the # without parentheses.
と書いてあって、いまいち使い方がよくわかなかったけど、やっと意味がわかった。
% s=A; echo $[#s] 65
as numeric expressionsってこういうことか。
If the MULTIBYTE option is set and the number is greater than 127 (i.e. not an ASCII character) it is treated as a Unicode character.
ってことなので
% s=あ; echo $[#s] 12354
日本語もokと。
slと打ち間違えたらまさかのSLが走り始めた。
そんなのPATHに通ってるところに入れた覚えはないのになと調べてみたら、
なんとbsdgamesに入っていた。
% dpkg -L sl | grep 'sl$' /usr/games/sl /usr/share/doc/sl
そうか。最近はそんなものまで。
Maximum path sum I. 経路問題。
bottomから解くのがいいようだけど、topから解いてみる。
3 7 4 2 4 6 8 5 9 3 10 7 2 4 6 8 5 9 3 12 14 13 8 5 9 3 20 19 23 16
のように足し込んで最終的に一番大きいのが答えになる。
% gawk '{for(i=1;i<=NF;i++){print a[NR,i]=$i+((x=a[NR-1,i-1])>(y=a[NR-1,i])?x:y)}}' p18.txt | sort -nr | head -n1
1074
めんどくさいので途中に出てくる数値も表示してsortに任せている。
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 18) - Qiita
Counting Sundays. 1901年から2000年まで1日が日曜日なのは何日あるか。
まずはdateで。1901-01-01という形式をdateに渡す。
ロケールに依存しないように%uか%wを使うといい。
% echo {1901..2000}-{01..12}-01$'\n' | date -f- +%w | grep -c 0
171
つづいてcal。calに年を渡すと1年分3列まとめて表示する。
1ヶ月は22バイトになっている。
% cal -3h -m2
2016
January February March
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 2 1 2 3 4 5 6 1 2 3 4 5
3 4 5 6 7 8 9 7 8 9 10 11 12 13 6 7 8 9 10 11 12
10 11 12 13 14 15 16 14 15 16 17 18 19 20 13 14 15 16 17 18 19
17 18 19 20 21 22 23 21 22 23 24 25 26 27 20 21 22 23 24 25 26
24 25 26 27 28 29 30 28 29 27 28 29 30 31
31
fold -22で整形すればあとはgrepでいける。
% seq 1901 2000 | xargs -n1 cal | fold -22 | grep -c '^ 1 ' 171
cal 1 1901という形式で1ヶ月ごとにやらせる方法もあるが、それなりに時間がかかる。
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 19) #シェル芸 - Qiita
この方針ならこんな方法も。
% seq 1901 2000 | xargs -n1 env LANG=C cal | grep -A1 Su | tr -cd 7 | wc -c 171
Factorial digit sum. 100!の各桁の総和。
何個か考えてみた。
% seq 100 | gawk -M '{m*=$0}END{print m}' m=1 | grep -o . | jq -s add
648
% seq 100 | gawk -M '{m*=$0}END{split(m,a,"");for(i in a)s+=a[i];print s}' m=1
648
% seq 100 | gawk -M '{$0=m*=$0}END{for(i=1;i<=NF;i++)s+=$i;print s}' m=1 FS=
648
% seq -s '*' 100 | bc | grep -Po '\d' | jq -s add
648
この問題の場合は-Mがないとオーバーフローする。このあたりの加減がよくわからない。
jq -s addでいい感じに総和が求まる。
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 20) #シェル芸 - Qiita
Amicable numbers. 10000未満の友愛数の総和。
これもまじめに計算しなくてもその辺りに転がってるので拾ってくればいい。
% curl -Ls https://en.wikipedia.org/wiki/Amicable_numbers | awk -F'[^0-9]+' '/are:/{for(i=3;$i<1e4;i++)s+=$i;print s}'
31626
ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 21) #シェル芸 - Qiita
を参考に計算するとこんな感じ。
% seq 9999 | awk '{p=1;for(i=2; i*i<=$0; i++){if($0%i==0)p+=i+$0/i*(i!=$0/i)};if($0!=p)print $0,p"\n"p,$0}'|sort -n|uniq -d|jq -s add/2
31626
jq -s addだと2倍になるので2で割っている。
約数といえばfactorが使える。
約数は素因数分解したときの各々の素数の組み合わせであり、
約数の総和ということならもっと簡単に計算できる。
たとえば12なら2^2*3なので (1+2^1+2^2)(1+3^1)
と表わせる。展開すれば 1+2+3+4+6+12 になる。
この方針で実装すると
% seq 10000|factor|tr ' ' '\n'|uniq -c|awk '/:/{if(t!=m-=t)print t,m"\n"m,t;t=+$2;m=1;next}{s=0;for(i=0;i<=$1;i++){s+=$2^i};m*=s}'|sort|uniq -d|jq -s add/2
となる。真の約数は自身を含まないのでその分を引いている。
さらに等比数列の和は(p^(i+1)-1)/(p-1)と表わせるのでこれを利用できる。
% seq 10000|factor|tr ' ' '\n'|uniq -c|awk '/:/{if(t!=m-=t)print t,m"\n"m,t;t=+$2;m=1;next}{m*=($2^($1+1)-1)/($2-1)}'|sort|uniq -d|jq -s add/2
もろもろ整理するとこうなった。
% seq 10000|factor|tr ' ' '\n'|uniq -c|awk '/:/{if((t!=m-=t)&&a[t,m]++*a[m,t]++==1)s+=t+m;t=+$2;m=1;next}{m*=($2^++$1-1)/--$2}END{print s}'
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 21) #シェル芸 - Qiita
かなりシンプルな別解を思い付いてしまったので記す。
真の約数の総和はこう書くとかなり規則的だ。
2: 1 3: 1 4: 1+2 5: 1 6: 1+2+3 7: 1 8: 1+2 +4 9: 1 +3 10: 1+2 +5 11: 1 12: 1+2+3+4 +6 13: 1 14: 1+2 +7 15: 1 +3 +5 16: 1+2 +4 +8 ...
つまり2の倍数には2を3の倍数には3をというように足し込んでいけばいいわけだ。
この方針だと真の約数の総和を計算するだけならこう書ける。
% seq 9999 | awk '{for(i=$0*2; i<=9999; i+=$0)a[i]+=$0}'
実にシンプルだ。あとは友愛数の条件に合う組み合わせを抜き出して総和を計算すればいい。
% seq 9999 | awk '{for(i=$0*2; i<=9999; i+=$0)a[i]+=$0}END{for(i in a)if(i!=a[i]&&i==a[a[i]])s+=i;print s}'
31626
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 21) #シェル芸 - Qiita
Names scores. 5000個以上の名前をソートしてスコアを計算し合計を求める。
ascii codeを利用する方法がすぐに思い付く。sumを使う方法だとこんな感じ。
% tr -sc A-Z '\n' p022_names.txt | sort | xargs -I@ echo "echo -n '@ ';echo -n @ | sum -s" | sh | awk '{s+=($2-length($1)*64)*NR}END{print s}'
871198282
しかしこれはsumを5000回ほど呼び出すことになり5秒ぐらいかかる。あまりよろしくない。
そこで、odを使う。
% sed 'y/,/\n/;s/"//g' p022_names.txt | sort | head -2 | od -An -vtu1 65 65 82 79 78 10 65 66 66 69 89 10
改行である10を区切りにすれば名前単位がレコードになる。
awkならRSで指定可能だ。
% sed 'y/,/\n/;s/"//g' p022_names.txt | sort | od -An -vtu1 | gawk '{for(i=1;i<=NF;i++)s+=($i-64)*NR}END{print s}' RS='\\<10\\>'
ascii codeを使わない方法もある。愚直ではあるが、AからZまで並べてしまえばいいわけだ。
indexで何番目にあるか調べれば代用できるというか、こっちのほうが題意に沿っている。
% tr , '\n' < p022_names.txt | sort | awk '{for(i=2;i<NF;i++)s+=index("ABCDEFGHIJKLMNOPQRSTUVWXYZ",$i)*NR}END{print s}' FS=
意外にも結構短い。AからZまでの文字列生成を工夫するともうちょっと短くなる。
% tr , '\n' < p022_names.txt | sort | awk '{for(i=2;i<NF;i++)s+=index(A,$i)*NR}END{print s}' FS= A=$(printf %s {A..Z})
あとこんな方法も。
% tr , '\n' < p022_names.txt | sort | awk '{for(i=2;i<NF;i++)s+=index(A,$i)*NR/2}END{print s}' FS= A=" $(echo {A..Z})"
cf: ProjectEuler - Project Eulerをシェル芸で解いてみる(Problem 22) #シェル芸 - Qiita
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