#!/usr/bin/env perl6

use v6.c;

constant WALL = '█' but False;
constant SPACE = '░' but True;
constant PATH = '·' but True;

class Pos
{
    has $.x;
    has $.y;

    method Str { "<$!x,$!y>" }
    method gist { self.Str }

    method infix:<eq>(Pos $a, Pos $b) { $a.x == $b.x && $a.y == $b.y }

    method WHICH { "Pos|$!x|$!y" }
}

sub pos($x,$y) { Pos.new(:$x,:$y) }

class Maze
{
    has $.id;
    has @!grid;

    #| Determine the contents of cell <$x,$y> with an optional path
    multi method cell(Int $x, Int $y, $path=())
    {
        # Don't go outside the boundaries
        return WALL unless $x >= 0 && $y >= 0;

        # Check if we're on the path
        return PATH if $path.elems && pos($x,$y) eq any(@$path);

        # Calculate cell value if not yet cached, and return it
        @!grid[$x;$y] //= ($x*$x + 3*$x +2*$x*$y + $y + $y*$y + $!id)\
                            .base(2).comb('1').elems %% 2 ?? SPACE !! WALL;
        return @!grid[$x;$y];
    }

    #| Determine the contents of cell $p in the maze with an optional $path
    multi method cell(Pos $p, $path=()) { self.cell($p.x, $p.y, $path); }

    #| Draw the maze up to a given width and height
    method draw(Int $width, Int $height)
    {
        for ^$height -> $y {
            say (^$width).map({ self.cell($_, $y) }).join;
        }
    }

    #| Draw the maze with a given path
    method draw-path($path)
    {
        my $width = $path».x.max + 2;
        my $height = $path».y.max + 2;

        for ^$height -> $y {
            say (^$width).map({ self.cell($_, $y, $path) }).join;
        }
    }

    #| Find a path from $from to $to
    method find-path(Pos $from, Pos $to)
    {
        my $visited = SetHash.new;
        my @moves = [[$from, [],],];

        while @moves {
            # Try the next move in the queue
            my ($pos, $path0) = @moves.shift;
            my @path = |$path0[*], $pos;
            $visited{$pos} = True;

            # Are we there yet?
            return @path if $pos eq $to;

            # Add possible moves from this location
            for pos($pos.x+1,$pos.y), pos($pos.x,$pos.y+1),
                        pos($pos.x-1,$pos.y), pos($pos.x,$pos.y-1) -> $new {
                if self.cell($new) && $new ∉ $visited {
                    @moves.push([$new, @path]);
                }
            }
        } 

        # No moves remailing, give up.
        return ();
    }

    #| Find all positions that can be reached from $from in $max-moves moves
    method find-positions(Pos $from, Int $max-moves)
    {
        my $visited = SetHash.new;
        my @moves = [[$from, [],],];

        while @moves {
            # Try the next move in the queue
            my ($pos, $path0) = @moves.shift;
            my @path = |$path0[*], $pos;
            $visited{$pos} = True;

            # Are we done yet?
            next if @path.elems - 1 == $max-moves;

            # Add possible moves from this location
            for pos($pos.x+1,$pos.y), pos($pos.x,$pos.y+1),
                        pos($pos.x-1,$pos.y), pos($pos.x,$pos.y-1) -> $new {
                if self.cell($new) && $new ∉ $visited {
                    @moves.push([$new, @path]);
                }
            }
        } 

        # Return all visited positions
        return $visited.keys;
    }
}

#| Solve maze with ID from input file
multi sub MAIN(IO() $inputfile where *.f,
               Int :$x = 31, Int :$y = 39,
               Int :$max-moves = 50)
{
    my ($maze-id) = $inputfile.words;
    MAIN($maze-id, :$x, :$y, :$max-moves);
}

#| Solve maze with ID on command line
multi sub MAIN(Str $maze-id where !*.IO.f,
               Int :$x = 31, Int :$y = 39,
               Int :$max-moves = 50)
{
    my $maze = Maze.new(:id($maze-id));

    say '';
    say 'Part 1:';

    my $from = pos(1,1);
    my $to = pos($x,$y);
    my @path = $maze.find-path($from, $to);
    if @path {
        say "Shortest path from $from to $to: {@path.elems-1} moves.";
        say "";
        $maze.draw-path(@path);
    }
    else {
        say "Sorry, can't find a path from $from to $to!";
    }

    say '';
    say 'Part 2:';

    my @pos = $maze.find-positions($from, $max-moves);
    if @pos {
        say "Number of reachable positions in $max-moves moves: @pos.elems().";
        say "";
        $maze.draw-path(@pos);
    }
    else {
        say "Sorry, can't find any positions from $from in $max-moves moves!";
    }
}