1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#! /opt/local/bin/perl
#
# pyramid-power.pl
#
# Triangle Sum
# Submitted by: Mohammad S Anwar
# You are given triangle array.
#
# Write a script to find the minimum path sum from top to bottom.
#
# When you are on index i on the current row then you may move to either index i or index i + 1 on the next row.
#
# Example 1:
# Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
# Output: 8
#
# Explanation: The given triangle
#
# 1
# 2 4
# 6 4 9
# 5 1 7 2
#
# The minimum path sum from top to bottom: 1 + 2 + 4 + 1 = 8
#
# [1]
# [2] 4
# 6 [4] 9
# 5 [1] 7 2
#
# Example 2:
# Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
# Output: 7
#
# Explanation: The given triangle
#
# 3
# 3 1
# 5 2 3
# 4 3 1 3
#
# The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
#
# [3]
# 3 [1]
# 5 [2] 3
# 4 3 [1] 3
#
# © 2021 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
sub findpath ($arr) {
## the data structure: [ sum, [arr of values along path], last index ]
my $root = $arr->[0][0];
my @data = [$root, [$root], 0];
for my $depth ( 0..$#$arr-1 ) {
for my $pos ( 0..2**$depth-1 ) {
my $path = shift @data;
for (0,1) {
my ($sum, $trace, $last) = @$path;
my $value = $arr->[$depth+1][$last+$_];
my $newpath = [ $sum + $value,
[$trace->@*, $value],
$last + $_ ];
push @data, $newpath;
}
}
}
my $minpath = (sort {$a->[0] <=> $b->[0]} @data)[0];
say "minimum path sum: ", $minpath->[0];
say "path:";
say join ' -> ', $minpath->[1]->@*;
return $minpath->[0];
}
use Test::More;
is findpath( [[1], [2,4], [6,4,9], [5,1,7,2]] ), 8, 'ex-1';
is findpath( [[3], [3,1], [5,2,3], [4,3,1,3]] ), 7, 'ex-2';
done_testing();
|
