http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036
$ seq 999999 | paste - <(seq 999999|rev) | awk '$1==$2{a="";b="";p=$1;while(p){q=p%2;a=q""a;b=b""q;p=int(p/2)}print $1,a,b}' | awk '$2==$3{a+=$1;print $1,$2}END{print "answer:",a}'
1 1 3 11 5 101 7 111 9 1001 33 100001 99 1100011 313 100111001 585 1001001001 717 1011001101 7447 1110100010111 9009 10001100110001 15351 11101111110111 32223 111110111011111 39993 1001110000111001 53235 1100111111110011 53835 1101001001001011 73737 10010000000001001 585585 10001110111101110001 answer: 872187 real 0m0.593s user 0m0.490s sys 0m0.100s
awk の中から外部コマンド(bc, rev)を呼ぶと遅いので、なるべくawkで済ませます。これだけで劇的に処理時間が短縮されます。
# 100万未満の数を生成
seq 999999 |
# ひっくり返してくっつける
paste - <(seq 999999|rev) |
# 回文数ならば、、、
awk '$1==$2{
# 2進数表記(a)と、逆にひっくり返したもの(b)を生成
a="";
b="";
p=$1;
# ひたすら2で割り、余りを結合していく
while(p){
q=p%2;
a=q""a; # 2で割った余りを上位桁へくっつける
b=b""q; # 上記と反対に、下位桁へくっつける
p=int(p/2)
}
# 結果を表示
print $1,a,b
}' |
# 2進数表記が回文数ならば、、、
awk '$2==$3{
# 合計値を求める
a+=$1;
# (おまけ)回文数を表示する
print $1,$2
}END{
# 答えを表示する
print "answer:",a
}'
$ time seq 999999 | paste - <(seq 999999|rev) | awk '$1==$2{print $1}' | sed 's/[0-9]*/& obase=2;ibase=10;&/' | awk '{"echo \047"$2"\047|bc"|getline f;print $1,f}' | awk '{"echo "$2"|rev"|getline f;print $0,f}' | awk '$2==$3{print $1,$2}' | awk '{a+=$1}END{print a}'
872187 real 0m10.554s user 0m5.628s sys 0m12.919s
10秒ちょいだからまぁいいか。
# 100万未満の整数
seq 999999 |
# 回文を作って並べる
paste - <(seq 999999|rev) |
# 10進数で回文のものを抽出
awk '$1==$2{print $1}' |
# bcで2進数を作るためのコマンド生成
sed 's/[0-9]*/& obase=2;ibase=10;&/' |
# bcで2進数に変換
awk '{"echo \047"$2"\047|bc"|getline f;print $1,f}' |
# 2進数の回文を作って並べる
awk '{"echo "$2"|rev"|getline f;print $0,f}' |
# 2進数で回文のものを抽出
awk '$2==$3{print $1,$2}' |
# 答えを計算
awk '{a+=$1}END{print a}'
こんな時にしか輝けない rev に愛の手を!