Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/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.";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement