algorithms

commit 9d74febec06192dcc2c00d296692afa91b306721
parent 68a678d5708957f8d3d949c439b0f5e4722293c0
Author: Samir Parikh <noreply@samirparikh.com>
Date:   Mon,  3 Jan 2022 01:46:24 +0000

trying to refactor code into subroutines

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

1 file changed, 80 insertions(+), 26 deletions(-)
diff --git a/dijkstra_shortest_path.pl b/dijkstra_shortest_path.pl
@@ -3,6 +3,13 @@
 use strict;
 use warnings;
 use v5.22;
+
+# declare our constants
+# program assumes that the graph (matrix) we want to traverse is composed only
+# of values between 0 and 9, inclusive.  Therefore, we'll be defining both a
+# boundary column and row composed of values equal to LIMIT which we can safely
+# ignore when we are processing the neighbors of a node during our graph
+# traversal
 use constant LIMIT => 10;
 use Data::Dumper;
 
@@ -16,35 +23,82 @@ sub get_filehandle {
   return $filehandle;
 }
 
-my $filehandle  =  get_filehandle();
-my @matrix   =  map{ [m/\d/g, LIMIT] } <$filehandle>; # add extra column of 9s
-my $columns     =  @{$matrix[0]};
-push @matrix => [ (LIMIT) x $columns ]; # add extra row of 9s
-my $rows        =  @matrix;
+sub define_matrix {
+    my $filehandle = shift;
+    my @matrix     =  map{ [m/\d/g, LIMIT] } <$filehandle>; # add boundary column
+    my $columns    =  @{$matrix[0]};
+    push @matrix   => [ (LIMIT) x $columns ];               # add boundary row 
+    return @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';
+            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);
+            }
+        }
+    }
+    $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';
+    say "within the subroutine...";
+    print Dumper (\%graph);
+    print Dumper (\%costs);
+    #$parents{0, '-', 0}        = 'start';
+}
+
+my $filehandle  = get_filehandle();
+my @matrix      = define_matrix($filehandle); 
+#print Dumper (\@matrix);
+#my @matrix   =  map{ [m/\d/g, LIMIT] } <$filehandle>; # add extra column of 9s
+#my $columns     =  @{$matrix[0]};
+#push @matrix => [ (LIMIT) x $columns ]; # add extra row of 9s
+#my $rows        =  @matrix;
+#my $columns = $rows;
 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);
+#my %parents;
+# hash to track all of the nodes we have already processed
+#my %processed;
 
-print Dumper (\@matrix);
-foreach my $row (0 .. $rows - 2) {
-    foreach my $col (0 .. $columns - 2) {
-        $costs{$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);
-        }
-    }
-}
-$graph{'start'}{0, '-', 0} = $matrix[0][0]; # start node to 0, 0
-$graph{2, '-', 2}{'end'}   = 0; # end node to n, n
-$costs{0, '-', 0}          = $matrix[0][0];
-$costs{'end'}              = 'inf';
-$parents{0, '-', 0}        = 'start';
+#print Dumper (\@matrix);
+#foreach my $row (0 .. $rows - 2) {
+#    foreach my $col (0 .. $columns - 2) {
+#        $costs{$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);
+#        }
+#    }
+#}
+#$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';
+#$parents{0, '-', 0}        = 'start';
+say "after the subroutine...";
 print Dumper (\%graph);
+print Dumper (\%costs);
 
 sub find_lowest_cost_node {
     # set lowest cost to infinity for initial comparison
@@ -101,7 +155,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;