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;

use Log::Log4perl ();
use Log::Log4perl::Level ();
Log::Log4perl->easy_init(
    Log::Log4perl::Level::to_priority( 'OFF' )
); # 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 )
{
    my $matrix;

    push @$matrix => [ ( map{ ord( $_ ) } split // ), $LIMIT ] foreach (split /\n/, $input);
    push @$matrix => [ ( $LIMIT ) x scalar @{$matrix->[0]} ];

    return $matrix;
}

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' ) )
            {
                $value = ord( 'a' );
                push @{ $neighbors{ "start" } } => $key;
            }

            if ( $value == ord( 'E' ) )
            {
                $value = ord( 'z' );
                push @{ $neighbors{ $key } } => "end";
            }
            
            $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];

                # it's possible we have to add a neighbor which is the end square
                # but whose elevation needs to be set to ord( 'z' ), which is 122,
                # rather than ord( 'E' ), which is 69.
                my $neighbor_elevation = ( $mat[ $n_row ][ $n_col ] == ord( 'E' ) ) ?
                                         ord( 'z' ) :
                                         $mat[ $n_row ][ $n_col ];
                # we don't want to update the value of $mat[ $n_row ][ $n_col ] just
                # yet because we have to process the end node above

                push @{ $neighbors{ $key } } => "$n_row:$n_col"
                    unless ( $neighbor_elevation > $value + 1 );
            }
        }
    }
    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 = ( $search );

    while ( @queue )
    {
        $logger->debug( "queue is @queue" );
        my $square = shift @queue;
        $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" )
            {
                $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
                foreach my $neighbor ( @{ $neighbors{ $square } } )
                {
                    unless ( $searched{ $neighbor } )
                    {
                        $logger->trace( "adding $square to $neighbor path" );
                        @{ $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;
            }
        }
    }

    return 0; # end square not found
}

1;