/
ch-1.pl
executable file
·56 lines (40 loc) · 1.04 KB
/
ch-1.pl
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
#!/usr/bin/perl
# Perl Weekly Challenge - 064
#
# Task 1 - Minimum Sum Path
#
# Author: Niels 'PerlBoy' van Dijke
use strict;
use List::Util qw(min);
use Data::Dumper;
sub findMinSumPath($$\@\@);
my @msp;
my @matrix = ([qw(1 2 3)], [qw(4 5 6)], [qw(7 8 9)]);
print "Input:\n";
for my $x (0 .. 2) {
print join("\t",@{$matrix[$x]})."\n";
}
my $minSumPath = findMinSumPath(0, 0, @matrix, @msp);
printf "\nMinimum Sum Path: %d\n", $minSumPath;
printf "Path: %s\n", join(' => ', @msp);
sub findMinSumPath ($$\@\@) {
my ($x, $y, $arMatrix, $arMsp) = @_;
my $return;
my %mV;
my $mP;
if (defined $arMatrix->[$x+1]) {
$mV{findMinSumPath($x+1, $y, @$arMatrix, @{$mP->{x}})} = 'x';
}
if (defined $arMatrix->[$x][$y+1]) {
$mV{findMinSumPath($x, $y+1, @$arMatrix, @{$mP->{y}})} = 'y';
}
my $minV = min(keys %mV);
if ($minV) {
@$arMsp = ($arMatrix->[$x][$y], @{$mP->{$mV{$minV}}});
$return = $arMatrix->[$x][$y] + $minV;
} else {
@$arMsp = ($arMatrix->[$x][$y]);
$return = $arMatrix->[$x][$y];
}
return $return;
}