最大路径和 I

作者：Felix Herrmann

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

    Pod::FormattingCode<94304264456112>
    Pod::FormattingCode<94304264456048> 4
    2 Pod::FormattingCode<94304264455984> 6
    8 5 Pod::FormattingCode<94304264455920> 3

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

求出以下三角形从顶部到底部的最大总和

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注意：由于只有 16384 条路径，可以通过尝试每条路径来解决此问题。但是，问题 67 是相同的挑战，但三角形包含一百行；它不能通过蛮力解决，需要一个巧妙的方法！ ;o)

源代码： prob018-felher.pl

use v6;

my $triangle =
    '75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23';

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 });
}