#!/usr/bin/env perl6

use v6.c;

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

class Pos
{
    has Int $.x;
    has Int $.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 $.width;
    has $.height;
    has @.grid;
    has @.target;
    has %.target-at;

    submethod BUILD(:@lines)
    {
        for @lines.kv -> $y, $line {
            @!grid.push: $line.comb.map({ when '#' { WALL }; when '.' { SPACE }; when '0'..'9' { TARGET }; });

            for $line.match(/ <[0..9]> /, :g) {
                my $pos = pos($_.from, $y);
                @!target[$_] = $pos;
                %!target-at{$pos} = +$_;
            }
        }

        $!width = +@!grid[0;*];
        $!height = +@!grid[*;0];
    }

    #| 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 $!width > $x >= 0 && $!height > $y >= 0;

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

        # Return the cell
        return @!grid[$y;$x];
    }

    #| 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
    method draw()
    {
        for ^$!height -> $y {
            say (^$!width).map({ self.cell($_, $y) }).join;
        }
    }

    #| Draw the maze with a given path
    method draw-path($path)
    {
        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;

            # 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]);
                    $visited{$new} = True;
                }
            }
        } 

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

sub MAIN(IO() $inputfile where *.f, Bool :v(:$verbose)=False)
{
    my $maze = Maze.new(:lines($inputfile.lines));
    $maze.draw if $verbose;
    say '' if $verbose;

    # Create a table of all distances between targets
    my @distance;
    for $maze.target.keys.combinations(2) -> ($t1, $t2) {
        my @path = $maze.find-path($maze.target[$t1], $maze.target[$t2]);
        say "Distance from target $t1 to target $t2: { @path - 1 } steps" if $verbose;
        @distance[$t1;$t2] = @distance[$t2;$t1] = @path-1;
    }

    # Calculate distance for all permutations of targets
    my %total-distance;
    my %return-distance;
    for $maze.target.keys[1..*].permutations -> @p {
        my $key = @p.join('-');
        %total-distance{$key} = (0,|@p).rotor(2=>-1).map({ @distance[$_[0];$_[1]] }).sum;
        %return-distance{$key} = %total-distance{$key} + @distance[@p[*-1];0];
    }

    # Find (one of) the best path(s), both without and with return to target 0
    my $best-total = %total-distance.keys.sort({ %total-distance{$_} })[0];
    my $best-return = %return-distance.keys.sort({ %return-distance{$_} })[0];

    say '' if $verbose;
    say "The shortest path without return is 0-{$best-total}; %total-distance{$best-total} steps.";
    say "The shortest path with return is 0-{$best-return}-0; %return-distance{$best-return} steps.";
}