最大路径和 II

作者：Felix Herrmann

https://projecteuler.net/problem=67

从下面三角形的顶部开始，每次移动到下一行中相邻的数字，从顶部到底部的最大总和为 23。

   Pod::FormattingCode<94304264470448>
  Pod::FormattingCode<94304264470384> 4
 2 Pod::FormattingCode<94304264470320> 6
8 5 Pod::FormattingCode<94304264470256> 3

即，3 + 7 + 4 + 9 = 23。

在 triangle.txt 文件中找到从顶部到底部的最大总和，该文件是一个 15K 的文本文件，包含一个有一百行的三角形。

注意：这是问题 18 的一个更难的版本。不可能尝试每条路线来解决这个问题，因为总共有 299 条路线！如果你能每秒检查一万亿 (1012) 条路线，那么检查所有路线将需要超过两百亿年。有一种有效的算法可以解决它。;o)

源代码：prob067-felher.pl

use v6;

my $triangle = slurp($*SPEC.catdir($*PROGRAM-NAME.IO.dirname, '/triangle.txt'));
my @lines = string-to-array($triangle).reverse;

# reduce the triangle by adding up the lines until only one line with one
# element is left; then print it.
say "{@lines.reduce: &add-maxima}";

# this function assumes the shorter and longer array to be consecutive lines
# in an reversed triangle. It then adds each of the maxima of consecutive fields
# of the longer array to their shared diagonal neighbour in the shorter array.
sub add-maxima(@longer, @shorter is copy) {
    for 0 .. @longer - 2 -> $i {
        @shorter[$i] += max @longer[$i], @longer[$i + 1];
    }
    return @shorter;
}

sub string-to-array($string) {
    my @lines = $string.lines;
    @lines .= map(-> $line { $line.comb(/\d+/).item });
}