Bash
ProjectEuler
数学

Project Euler Q67 【最大経路の和 その2】

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