algorithms

commit 888c793c53ef3aada8482d3a6028030963c99487
parent 9d74febec06192dcc2c00d296692afa91b306721
Author: Samir Parikh <noreply@samirparikh.com>
Date:   Mon,  3 Jan 2022 01:53:12 +0000

get initial refactoring to work again

Diffstat:
M
dijkstra_shortest_path.pl
 | 
55
++++++++++++++++++++++++++++++-------------------------

1 file changed, 30 insertions(+), 25 deletions(-)
diff --git a/dijkstra_shortest_path.pl b/dijkstra_shortest_path.pl
@@ -32,32 +32,34 @@ sub define_matrix {
 }
 
 sub init_graph_costs {
-    my ($matrix_ref, $graph_ref, $costs_ref) = @_;
-    my @matrix = @{ $matrix_ref };
-    my %graph = %{ $graph_ref };
-    my %costs = %{ $costs_ref };
-    my $rows  = scalar @matrix;
-    my $columns = scalar @{ $matrix[0] };
-    print Dumper (\@matrix);
-    foreach my $row (0 .. $rows - 2) {
-        foreach my $col (0 .. $columns - 2) {
-            $costs{$row, '-', $col} = 'inf';
+    #my ($matrix_ref, $graph_ref, $costs_ref) = @_;
+    my $matrix_ref = shift;
+    my @mat = @{ $matrix_ref };
+    my %grph;
+    my %csts;
+    my $r  = scalar @mat;
+    my $c = scalar @{ $mat[0] };
+    print Dumper (\@mat);
+    foreach my $row (0 .. $r - 2) {
+        foreach my $col (0 .. $c - 2) {
+            $csts{$row, '-', $col} = 'inf';
             foreach my $neighbor ([0, 1], [1, 0]) {
                 my $n_row = $row + $neighbor->[0];
                 my $n_col = $col + $neighbor->[1];
-                $graph{$row, '-', $col}{$n_row, '-', $n_col} = $matrix[$n_row][$n_col]
-                    unless ($matrix[$n_row][$n_col] == LIMIT);
+                $grph{$row, '-', $col}{$n_row, '-', $n_col} = $mat[$n_row][$n_col]
+                    unless ($mat[$n_row][$n_col] == LIMIT);
             }
         }
     }
-    $graph{'start'}{0, '-', 0} = $matrix[0][0]; # start node to 0, 0
-    $graph{2, '-', 2}{'end'}   = 0; # n, n node to end
-    $costs{0, '-', 0}          = $matrix[0][0];
-    $costs{'end'}              = 'inf';
+    $grph{'start'}{0, '-', 0} = $mat[0][0]; # start node to 0, 0
+    $grph{2, '-', 2}{'end'}   = 0; # n, n node to end
+    $csts{0, '-', 0}          = $mat[0][0];
+    $csts{'end'}              = 'inf';
     say "within the subroutine...";
-    print Dumper (\%graph);
-    print Dumper (\%costs);
+    print Dumper (\%grph);
+    print Dumper (\%csts);
     #$parents{0, '-', 0}        = 'start';
+    return (\%grph, \%csts);
 }
 
 my $filehandle  = get_filehandle();
@@ -68,13 +70,16 @@ my @matrix      = define_matrix($filehandle);
 #push @matrix => [ (LIMIT) x $columns ]; # add extra row of 9s
 #my $rows        =  @matrix;
 #my $columns = $rows;
-my %graph;
-my %costs;
+#my %graph;
+#my %costs;
 my %parents;
 $parents{0, '-', 0}        = 'start';
 # hash to track all of the nodes we have already processed
 my %processed;
-init_graph_costs(\@matrix, \%graph, \%costs);
+#init_graph_costs(\@matrix, \%graph, \%costs);
+my ($graph_ref, $costs_ref) = init_graph_costs(\@matrix);
+my %graph = %{ $graph_ref };
+my %costs = %{ $costs_ref };
 #my %parents;
 # hash to track all of the nodes we have already processed
 #my %processed;
@@ -155,7 +160,7 @@ while ($node ne 'None') {
 # parent ($parents{$path[0]}) to the FRONT of the array until we reach the
 # beginning ('start')
 my @path = ('end');
-#unshift @path => $parents{$path[0]} while ($path[0] ne 'start');
-#say "weight of shortest path is $costs{'end'}";
-#say "which is achieved by the following path:";
-#say join " -> " => @path;
+unshift @path => $parents{$path[0]} while ($path[0] ne 'start');
+say "weight of shortest path is $costs{'end'}";
+say "which is achieved by the following path:";
+say join " -> " => @path;