blob: 0da6ad52895840d566d1e8d453e5410d7cb81436 (
plain)
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
|
package Triangle;
use Moo;
use Data::Dumper;
$Data::Dumper::Sortkeys = 1;
sub min_path_sum {
my ( $self, $triangle ) = @_;
my $table = $self->triangle_to_table($triangle);
my $sum = $self->parse_table($table);
return $sum;
}
sub triangle_to_table {
my ( $self, $triangle ) = @_;
my $max = @$triangle - 1;
for my $row_index ( 0 .. $max ) {
for my $column_index ( 0 .. $max ) {
$triangle->[$row_index][$column_index] //= 0;
}
}
return $triangle;
}
sub parse_table {
my ( $self, $table ) = @_;
my $max = @$table - 1;
for my $row_index ( reverse( 0 .. $max - 1 ) ) {
for my $column_index ( 0 .. $max - 1 ) {
if ( $table->[ $row_index + 1 ][$column_index]
< $table->[ $row_index + 1 ][ $column_index + 1 ] )
{
$table->[$row_index][$column_index]
+= $table->[ $row_index + 1 ][$column_index];
}
else {
$table->[$row_index][$column_index]
+= $table->[ $row_index + 1 ][ $column_index + 1 ];
}
}
}
return $table->[0][0];
}
1;
|
