Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は$23$になる.
3
7 4
2 4 6
8 5 9 3
この例では $3 + 7 + 4 + 9 = 23$
$100$列の三角形を含んでいる$15K$のテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけよ.
注：これは, Problem 18のずっと難しいバージョンです.
全部で$2^{99}$ 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません！
あなたが毎秒$1$兆本の$(10^{12})$ルートをチェックすることができたとしても, 全てをチェックするために$200$億年以上かかるでしょう.
解決するための効率的なアルゴリズムがあります. ;o)
解答
time cat triangle.txt |
awk '{for(i=1;i<=NF;i++){if(a[NR-1][i]<a[NR-1][i-1]){a[NR][i]=$i+a[NR-1][i-1]}else{a[NR][i]=$i+a[NR-1][i]}}} END{for(i=1;i<=NF;i++){print a[NR][i]}}' |
sort -n |
tail -1
7273
real 0m0.033s
user 0m0.030s
sys 0m0.007s
Problem 18と全く同じ方法で解けた。
しかも処理速度も問題ない。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/067.html