-
Notifications
You must be signed in to change notification settings - Fork 319
/
ch-1.pl
executable file
·135 lines (112 loc) · 3.31 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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#!/usr/bin/perl
# Use Dijkstra's algorithm to find a minimum weighted path
# through a matrix.
# The algorithm is provided by the "Graph" package.
# To make use of this implementation, the given matrix has to
# be transformed into a directed, weighted graph with the
# matrix elements as vertices and the valid moves as edges.
# Each edge is assigned a weight that is the move's target matrix
# element.
# Assigning weights to the vertices is not necessary but it
# simplifies the calculation of minimum path's weight.
use Test2::V0;
use Graph;
use List::Util qw(reduce);
# Set to true to display intermediate variables
my $verbose;
# Find minimum path from top left to bottom right in given matrix.
sub minpath {
my $matrix = shift;
my $graph = graph($matrix);
# Get minimum weighted path using Dijkstra's algorithm
# from start to end vertex.
my @path = $graph->SP_Dijkstra(vertex(0,0),
vertex($#$matrix, $#{$matrix->[-1]}));
print
join(' -> ', map "$_:" . $graph->get_vertex_weight($_), @path),
"\n" if $verbose;
# Sum vertex weights in path.
reduce {$a + $graph->get_vertex_weight($b)} 0, @path;
}
# Create a directed weighted graph, allowing only
# right or down moves in given matrix.
sub graph {
my $matrix = shift;
my $out_edges = edges($matrix);
my $graph = Graph->new;
for my $row (0 .. $#$matrix) {
for my $col (0 .. $#{$matrix->[$row]}) {
next unless defined $matrix->[$row][$col];
$graph->add_weighted_edges(&$out_edges($row, $col));
$graph->set_vertex_weight(vertex($row, $col),
$matrix->[$row][$col]);
}
print "[",
join(', ', map {defined $_ ? sprintf('%2d', $_) : ' '}
@{$matrix->[$row]}),
"]\n" if $verbose;
}
$graph;
}
# Generate sub that returns outgoing weighted edges from given vertex
# for this matrix.
sub edges {
my $matrix = shift;
sub {
my ($row, $col) = @_;
my $vertex = vertex($row, $col);
# Create argument list for "add_weighted_edges" method.
# Add edge only if right/down neighbor vertex exists.
((defined $matrix->[$row][$col + 1] ?
($vertex, vertex($row, $col + 1),
$matrix->[$row][$col + 1]) : ()),
(defined $matrix->[$row + 1] && defined $matrix->[$row + 1][$col] ?
($vertex, vertex($row + 1, $col),
$matrix->[$row + 1][$col]) : ()));
}
}
# Create vertex name.
sub vertex {
local $" = ',';
"(@_)";
}
# For testing only:
# Generate matrix from sub
sub narray {
my $size = shift;
my $val = pop;
my $na;
for my $i (0 .. $size - 1) {
$na->[$i] = @_ ? narray(@_, sub {&$val($i, @_)}) : &$val($i);
}
$na;
}
# main
$verbose = 1;
# example from challenge
my $example = narray(3, 3, sub {3 * $_[0] + $_[1] + 1});
is minpath($example), 21, 'example from challenge';
print "\n";
# walk around a hill
my $hill = narray(5, 5, sub {$_[0] * (4 - $_[0]) + $_[1] * (4 - $_[1])});
is minpath($hill), 20, 'around the hill';
print "\n";
# walk though a valley
my $valley = narray(5, 5, sub {abs($_[0] - $_[1])}
);
is minpath($valley), 4, 'through the valley';
print "\n";
# walk around holes
my $hole = narray(5, 5, sub {
1 - ($_[1] == 2 ||
($_[0] == 0 && $_[1] < 2) ||
($_[0] == 4 && $_[1] > 2))
});
undef $hole->[2][2];
is minpath($hole), 3, 'avoid holes';
done_testing;
#srand;
# random matrix
my $rand = narray(3 + int(rand(4)), 3 + int(rand(4)), sub {int(rand(6))});
print "\nToday's random matrix\n";
print "minimum sum: ", minpath($rand), "\n";