#!/usr/bin/env perl

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;

sub get_filehandle {
  if (@ARGV !=1) {
    die "Usage: $0 [input-filename]";
  }
  my $input_filename = $ARGV[0];
  open my $filehandle, '<', $input_filename or
    die "Could not open input file $input_filename: $!";
  return $filehandle;
}

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 = shift;
    my @mat = @{ $matrix_ref };
    my %grph;
    my %csts;
    my $r = scalar @mat;                # number of rows
    my $c = scalar @{ $mat[0] };        # number of columns
    foreach my $row (0 .. $r - 2) {
        foreach my $col (0 .. $c - 2) {
            $csts{$row, '-', $col} = 'inf'; # set initial costs to infinity
            foreach my $neighbor ([0, 1], [1, 0], [0, -1], [-1, 0]) {
                my $n_row = $row + $neighbor->[0];
                my $n_col = $col + $neighbor->[1];
                # here we set the weights of each edge between the nodes
                # the weight is equal to the "to" node unless we've hit a
                # boundary row or column
                $grph{$row, '-', $col}{$n_row, '-', $n_col} = $mat[$n_row][$n_col]
                    unless ($mat[$n_row][$n_col] == LIMIT);
            }
        }
    }
    # initialize the starting edge, from "start" to the first node (0, 0)
    $grph{'start'}{0, '-', 0} = $mat[0][0];
    # initialize the last edge, from the last node to "end"
    $grph{$r - 2, '-', $c - 2}{'end'}   = 0;
    # the "cost" to get to the first node is the value of the first node
    $csts{0, '-', 0}          = $mat[0][0];
    # set initial cost to get to the "end" node to infinity
    $csts{'end'}              = 'inf';
    return (\%grph, \%csts);
}

sub find_lowest_cost_node {
    my ($costs_ref, $processed_ref) = @_;
    my %csts = %{ $costs_ref };
    my %proc = %{ $processed_ref };
    # set lowest cost to infinity for initial comparison
    my $lowest_cost = 'inf';
    # set default lowest cost node to None in case none if sound
    my $lowest_cost_node = 'None';
    # for each node in our costs table
    foreach my $node (keys %csts) {
        my $cost = $csts{$node};
        # check if node is lowest cost so far AND
        # it has not yet been processed by our main while loop
        if ($cost < $lowest_cost && !exists $proc{$node}) {
            # if it is, update our $lowest_cost and $lowest_cost_node
            $lowest_cost      = $cost;
            $lowest_cost_node = $node;
        }
    }
    # will return None if all nodes have been processed
    return $lowest_cost_node;
}

# initialize variables
my $filehandle              = get_filehandle();
my @matrix                  = define_matrix($filehandle); 
my ($graph_ref, $costs_ref) = init_graph_costs(\@matrix);
my %graph                   = %{ $graph_ref };
my %costs                   = %{ $costs_ref };
my %parents;
# the parent of the first node will always be "start"
$parents{0, '-', 0}         = 'start';
# hash to track all of the nodes we have already processed
my %processed;
my $node                    = find_lowest_cost_node(\%costs, \%processed);

while ($node ne 'None') {
    my $cost = $costs{$node}; # cost to get to current node
    my @neighbors = keys %{$graph{$node}}; # neighbors of node
    # go through all neighbors of this node
    foreach my $neighbor (@neighbors) {
        # calculate new cost of getting to neighbor via this node
        my $new_cost = $cost + $graph{$node}{$neighbor};
        # if it's cheaper to get to this neighbor through this node
        if ($costs{$neighbor} > $new_cost) {
            # update new cost for the neighbor
            $costs{$neighbor} = $new_cost;
            # the current node becomes the parent of the neighbor
            $parents{$neighbor} = $node;
        }
    }
    # mark the node as processed
    $processed{$node} = 1;
    # find the next node to process
    $node = find_lowest_cost_node(\%costs, \%processed);
}

# @path is our array holding the shortest path
# we build it up starting from the end ('fin') and append the coresponding
# 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;