commit f43ed2a46a7615e3c51d506c83c2b7bfda921630
parent 57d851b9ce3c419e041b1bd6bcaeca8f9db032a0
Author: Samir Parikh <noreply@samirparikh.com>
Date: Thu, 12 Jan 2023 20:40:54 +0000
start to solve part 1 of day12
Diffstat:
A | day12/Day12.pm | | | 160 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
A | day12/day12.pl | | | 23 | +++++++++++++++++++++++ |
2 files changed, 183 insertions(+), 0 deletions(-)
diff --git a/day12/Day12.pm b/day12/Day12.pm
@@ -0,0 +1,160 @@
+package Day12;
+
+use strict;
+use warnings;
+use v5.32;
+use feature qw( signatures );
+no warnings qw( experimental::signatures );
+
+use Exporter qw( import );
+our @EXPORT = qw( define_matrix define_graph find_path );
+
+use Data::Dumper;
+
+my $LIMIT = ord ( 'z' ) + 10;
+
+sub define_matrix ( $input )
+{
+ my $matrix;
+
+ push @$matrix => [ ( map{ ord( $_ ) } split // ), $LIMIT ] foreach (split /\n/, $input);
+ push @$matrix => [ ( $LIMIT ) x scalar @{$matrix->[0]} ];
+
+ return $matrix;
+}
+
+sub init_graph_costs {
+ my $matrix_ref = shift;
+ my @mat = @{ $matrix_ref };
+ my %grph;
+# my %csts;
+ my $r = scalar @mat;
+ my $c = scalar @{ $mat[0] };
+ foreach my $row (0 .. $r - 2) {
+ foreach my $col (0 .. $c - 2) {
+# $csts{$row, '-', $col} = 'inf';
+ foreach my $neighbor ([0, 1], [1, 0], [0, -1], [-1, 0]) {
+ my $n_row = $row + $neighbor->[0];
+ my $n_col = $col + $neighbor->[1];
+ $grph{$row, '-', $col}{$n_row, '-', $n_col} = $mat[$n_row][$n_col]
+ unless ($mat[$n_row][$n_col] == $LIMIT);
+ }
+ }
+ }
+ $grph{'start'}{0, '-', 0} = $mat[0][0]; # start node to 0, 0
+ $grph{$r - 2, '-', $c - 2}{'end'} = 0; # n, n node to end
+# $csts{0, '-', 0} = $mat[0][0];
+# $csts{'end'} = 'inf';
+ say Dumper \%grph;
+# return (\%grph, \%csts);
+ return ( \%grph );
+}
+
+sub define_graph ( $matrix_ref )
+{
+ my @mat = @{ $matrix_ref };
+ my %neighbors;
+ my %elevation;
+ my $r = scalar @mat;
+ my $c = scalar @{ $mat[ 0 ] };
+ foreach my $row ( 0 .. $r - 2 )
+ {
+ foreach my $col ( 0 .. $c - 2 )
+ {
+ # default values
+ my $key = "$row - $col";
+ my $value = $mat[ $row ][ $col ];
+
+ if ( $value == ord( 'S' ) )
+ {
+ $key = "start";
+ $value = ord( 'a' );
+ }
+
+ if ( $value == ord( 'E' ) )
+ {
+ $key = "end";
+ $value = ord( 'z' );
+ }
+
+ $elevation{ $key } = $value;
+
+ foreach my $neighbor ( [0, 1], [1, 0], [0, -1], [-1, 0] )
+ {
+ my $n_row = $row + $neighbor->[0];
+ my $n_col = $col + $neighbor->[1];
+# $grph{$row, '-', $col}{$n_row, '-', $n_col} = $mat[$n_row][$n_col]
+# unless ($mat[$n_row][$n_col] == $LIMIT);
+# push @{ $neighbors{ $key } } => [ $n_row, $n_col ]
+ push @{ $neighbors{ $key } } => "$n_row - $n_col"
+ unless ( $mat[ $n_row ][ $n_col ] > $value + 1 );
+ }
+ }
+ }
+ #say Dumper \%neighbors;
+ return ( \%neighbors, \%elevation );
+}
+
+# arguments are reference to hash containing neighbors and reference to hash
+# containing elevations
+sub find_path ( $n, $e )
+{
+ # hash that stores reference to array that contains the square's neighbors
+ my %neighbors = %{ $n };
+
+ # hash that stores square's elevation
+ my %elevation = %{ $e };
+
+ # hash that stores whether or not the square has already been searched
+ my %searched;
+
+ my $search = "start";
+
+ # hash that stores reference to array that contains squares visited to
+ # reach current squaure
+ my %paths;
+ $paths{ $search } = [ ];
+
+ # array that stores list of squares to be searched
+ my @queue = @{ $neighbors{ $search } };
+# foreach (@queue)
+# {
+# say "@{ $_ }";
+# }
+ while ( @queue )
+ {
+ say "queue is @queue";
+ my $square = shift @queue;
+# my $key = "$square->[0] - $square->[1]";
+ say "checking square at $square";
+ # unless we've already searched this square
+ unless ( $searched{ $square } )
+ {
+ # check if we've found the "end" square
+ if ( $square eq "end" )
+ {
+ say "we found the end";
+ say "we got here via ", ( join " > ", @{ $paths{ $square } }, $square );
+ return;
+ }
+ else
+ {
+ # add all of $square's neighbors to the queue
+ say "$square is not the end";
+ foreach my $neighbor ( @{ $neighbors{ $square } } )
+ {
+ say "adding $square to {$neighbor}'s path";
+ push @{ $paths{ $neighbor } } => @{ $paths{ $square } }, $square;
+ say "adding $neighbor to the queue";
+ push @queue => $neighbor;
+ }
+ # add the just searched $sqaure to the searched hash
+ $searched{ $square } = 1;
+ }
+ }
+ }
+
+ return 0; # end square not found
+}
+
+1;
diff --git a/day12/day12.pl b/day12/day12.pl
@@ -0,0 +1,23 @@
+#!/usr/local/bin/perl
+# day 2022-12
+
+use strict;
+use warnings;
+use v5.32;
+use lib '.';
+use Day12 qw( define_matrix define_graph find_path );
+
+@ARGV = "input" unless @ARGV;
+chomp( my $input = do { local $/; <> } );
+
+#say $input;
+my $matrix = define_matrix( $input );
+#foreach ( @{ $matrix } )
+#{
+# say " @{$_} ";
+#}
+
+#my ($graph, $costs) = init_graph_costs( $matrix );
+#my $graph = init_graph_costs($matrix);
+my ( $neighbors, $elevation ) = define_graph( $matrix );
+find_path( $neighbors, $elevation );