commit 54e078e44e302e7bb0cb6dc0f406d22cd5a76cb3
parent 3a2d976a412563ae5209483d42622ed0f25b7fcd
Author: Samir Parikh <noreply@samirparikh.com>
Date: Fri, 13 Jan 2023 18:51:33 +0000
solve part 1 of day12
Diffstat:
2 files changed, 56 insertions(+), 34 deletions(-)
diff --git a/day12/Day12.pm b/day12/Day12.pm
@@ -11,6 +11,13 @@ our @EXPORT = qw( define_matrix define_graph find_path );
use Data::Dumper;
+use Log::Log4perl ();
+use Log::Log4perl::Level ();
+Log::Log4perl->easy_init(
+ Log::Log4perl::Level::to_priority( 'TRACE' )
+); # set to 'OFF', 'INFO', 'DEBUG' or 'TRACE' for successively more information
+my $logger = Log::Log4perl->get_logger();
+
my $LIMIT = ord ( 'z' ) + 10;
sub define_matrix ( $input )
@@ -32,7 +39,7 @@ sub define_graph ( $matrix_ref )
# my $start_col = '';
# my $end_row = '';
# my $end_col = '';
- my ( $start_row, $start_col, $end_row, $end_col ) = ( -1, -1, -1, -1 );
+# my ( $start_row, $start_col, $end_row, $end_col ) = ( -1, -1, -1, -1 );
my $r = scalar @mat;
my $c = scalar @{ $mat[ 0 ] };
foreach my $row ( 0 .. $r - 2 )
@@ -40,21 +47,21 @@ sub define_graph ( $matrix_ref )
foreach my $col ( 0 .. $c - 2 )
{
# default values
- my $key = "$row - $col";
+ my $key = "$row:$col";
my $value = $mat[ $row ][ $col ];
if ( $value == ord( 'S' ) )
{
- $key = "start";
+# $key = "start";
$value = ord( 'a' );
- $neighbors{ "start" } = $key;
+ push @{ $neighbors{ "start" } } => $key;
# $start_row = $row;
# $start_col = $col;
}
if ( $value == ord( 'E' ) )
{
- $key = "end";
+# $key = "end";
$value = ord( 'z' );
push @{ $neighbors{ $key } } => "end";
# $end_row = $row;
@@ -67,23 +74,29 @@ sub define_graph ( $matrix_ref )
{
my $n_row = $row + $neighbor->[0];
my $n_col = $col + $neighbor->[1];
- push @{ $neighbors{ $key } } => "$n_row - $n_col"
- unless ( $mat[ $n_row ][ $n_col ] > $value + 1 );
- if ( $mat[ $n_row ][ $n_col ] < $value + 1 )
- {
- if ( $n_row == $start_row && $n_col == $start_col )
- {
- push @{ $neighbors{ $key } } => "start";
- }
- elsif ( $n_row == $end_row && $n_col == $end_col )
- {
- push @{ $neighbors{ $key } } => "end";
- }
- else
- {
- push @{ $neighbors{ $key } } => "$n_row - $n_col";
- }
- }
+
+ my $neighbor_elevation = ( $mat[ $n_row ][ $n_col ] == ord( 'E' ) ) ?
+ ord( 'z' ) :
+ $mat[ $n_row ][ $n_col ];
+
+ push @{ $neighbors{ $key } } => "$n_row:$n_col"
+ #unless ( $mat[ $n_row ][ $n_col ] > $value + 1 );
+ unless ( $neighbor_elevation > $value + 1 );
+# if ( $mat[ $n_row ][ $n_col ] < $value + 1 )
+# {
+# if ( $n_row == $start_row && $n_col == $start_col )
+# {
+# push @{ $neighbors{ $key } } => "start";
+# }
+# elsif ( $n_row == $end_row && $n_col == $end_col )
+# {
+# push @{ $neighbors{ $key } } => "end";
+# }
+# else
+# {
+# push @{ $neighbors{ $key } } => "$n_row - $n_col";
+# }
+# }
}
}
}
@@ -115,31 +128,39 @@ sub find_path ( $n, $e )
#my @queue = @{ $neighbors{ $search } };
my @queue = ( $search );
-while ( @queue )
+ while ( @queue )
{
- say "queue is @queue";
+ $logger->debug( "queue is @queue" );
my $square = shift @queue;
- say "checking square at $square";
+ $logger->info( "checking $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;
+ $logger->info( "we found the end" );
+ $logger->info( "we got here via ",
+ ( join " > ", @{ $paths{ $square } }, $square ) );
+ # don't need "start" to first square or end square to "end"
+ return ( scalar @{ $paths{ $square } } ) - 2;
}
else
{
+ $logger->info( "$square is not the end" );
# 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;
+ unless ( $searched{ $neighbor } )
+ {
+ $logger->trace( "adding $square to $neighbor path" );
+ #push @{ $paths{ $neighbor } } => @{ $paths{ $square } }, $square;
+ @{ $paths{ $neighbor } } = ( @{ $paths{ $square } }, $square );
+ $logger->trace( "path to $neighbor is now ",
+ join "->", @{ $paths{ $neighbor } } );
+ $logger->trace( "adding $neighbor to the queue" );
+ push @queue => $neighbor;
+ }
}
# add the just searched $sqaure to the searched hash
$searched{ $square } = 1;
diff --git a/day12/day12.pl b/day12/day12.pl
@@ -12,4 +12,5 @@ chomp( my $input = do { local $/; <> } );
my $matrix = define_matrix( $input );
my ( $neighbors, $elevation ) = define_graph( $matrix );
-#find_path( $neighbors, $elevation );
+my $part_1 = find_path( $neighbors, $elevation );
+say $part_1;
