#!/usr/bin/perl -w
# path.pl - Don Yang (uguu.org)
#
# Find path to solve mazes generated by neptune.pl
#
# 2014-03-17

use strict;
use constant WIDTH => 25;
use constant HEIGHT => 8;

use constant SOLUTION_UP => 8;
use constant SOLUTION_DOWN => 16;
use constant SOLUTION_LEFT => 32;
use constant SOLUTION_RIGHT => 64;
use constant SOLUTION_GOAL => 128;
use constant VISITED => 4;
use constant DOOR_RIGHT => 1;
use constant DOOR_BOTTOM => 2;

my ($lfsr, @cells);

# Return the next random number using linear feedback shift register.
# We use our own random number generator to keep the mazes portable
# across different perl distributions.
sub Rand()
{
   $lfsr = (($lfsr >> 1) ^ (0x68000001 & -($lfsr & 1))) & 0x7fffffff;
   return $lfsr;
}

# Create a door between two cells
sub ConnectCells($$$$)
{
   my ($x0, $y0, $x1, $y1) = @_;

   if( $x0 < $x1 )
   {
      $cells[$y1][$x0] |= DOOR_RIGHT;
   }
   elsif( $x0 > $x1 )
   {
      $cells[$y1][$x1] |= DOOR_RIGHT;
   }
   else
   {
      if( $y0 < $y1 )
      {
         $cells[$y0][$x1] |= DOOR_BOTTOM;
      }
      else
      {
         $cells[$y1][$x1] |= DOOR_BOTTOM;
      }
   }
}

# Return 4 pairs of deltas in random order
sub GenerateDeltas()
{
   my @delta = ([-1, 0], [1, 0], [0, -1], [0, 1]);

   # Fisher-Yates shuffle
   for(my $i = @delta; --$i;)
   {
      my $j = Rand() % ($i + 1);
      next if $i == $j;
      @delta[$i, $j] = @delta[$j, $i];
   }
   return @delta;
}

# Generate maze
sub GenerateMaze()
{
   # Block off border cells
   for(my $x = 0; $x < WIDTH + 2; $x++)
   {
      $cells[0][$x] = $cells[HEIGHT + 1][$x] = VISITED | DOOR_RIGHT;
   }
   for(my $y = 1; $y <= HEIGHT; $y++)
   {
      $cells[$y][0] = $cells[$y][WIDTH + 1] = VISITED | DOOR_BOTTOM;
      for(my $x = 1; $x <= WIDTH; $x++)
      {
         $cells[$y][$x] = 0;
      }
   }

   # Reserve the middle area for instructions
   for(my $x = 10; $x < 16; $x++)
   {
      $cells[4][$x] = VISITED | DOOR_RIGHT | DOOR_BOTTOM;
      $cells[5][$x] = VISITED | DOOR_RIGHT;
   }
   $cells[4][16] = VISITED | DOOR_BOTTOM;
   $cells[5][16] = VISITED;

   # Start marking cells at upper left corner
   my @visit = ([0, 1, 1, 1]);
   while( scalar @visit )
   {
      my ($x0, $y0, $x1, $y1) = @{pop @visit};

      next if (($cells[$y1][$x1] & VISITED) != 0);

      # Mark path between current cell and previous cell
      $cells[$y1][$x1] |= VISITED;
      ConnectCells($x0, $y0, $x1, $y1);

      # Visit neighbors in random order
      my @delta = GenerateDeltas();
      while( scalar @delta )
      {
         my ($dx, $dy) = @{pop @delta};
         push @visit, [$x1, $y1, $x1 + $dx, $y1 + $dy];
      }
   }

   # Mark exit
   $cells[HEIGHT][WIDTH] |= DOOR_RIGHT;

   # Unmark entrance
   $cells[1][0] &= ~DOOR_RIGHT;
}

# Solve the maze recursively using flood fill.  This works because
# there are no loops in our maze.
sub Solve()
{
   my @path = ([0, 0, 0]);

   my %dead_end = ();
   $dead_end{0}{0} = 1;

   while( scalar @path )
   {
      my ($cx, $cy) = @{$path[$#path]};

      if( $cx == WIDTH - 1 && $cy == HEIGHT - 1 )
      {
         $path[$#path][2] = SOLUTION_GOAL;
         return @path;
      }
      $dead_end{$cx}{$cy} = 1;

      if( ($cells[$cy + 1][$cx + 1] & DOOR_RIGHT) != 0 &&
          not exists $dead_end{$cx + 1}{$cy} )
      {
         $path[$#path][2] = SOLUTION_RIGHT;
         push @path, [$cx + 1, $cy, 0];
         next;
      }
      if( ($cells[$cy + 1][$cx + 1] & DOOR_BOTTOM) != 0 &&
          not exists $dead_end{$cx}{$cy + 1} )
      {
         $path[$#path][2] = SOLUTION_DOWN;
         push @path, [$cx, $cy + 1, 0];
         next;
      }
      if( ($cells[$cy][$cx + 1] & DOOR_BOTTOM) != 0 &&
          not exists $dead_end{$cx}{$cy - 1} )
      {
         $path[$#path][2] = SOLUTION_UP;
         push @path, [$cx, $cy - 1, 0];
         next;
      }
      if( ($cells[$cy + 1][$cx] & DOOR_RIGHT) != 0 &&
          not exists $dead_end{$cx - 1}{$cy} )
      {
         $path[$#path][2] = SOLUTION_LEFT;
         push @path, [$cx - 1, $cy, 0];
         next;
      }
      pop @path;
   }
   return @path;
}

# Mark all entries along the solution path
sub MarkSolution($)
{
   my ($path) = @_;

   for(my $i = 0; $i <= $#$path; $i++)
   {
      my ($x, $y, $d) = @{$$path[$i]};
      $cells[$y + 1][$x + 1] |= $d;
   }
}

# Serialize solution commands to text
sub OutputSolution($)
{
   my ($path) = @_;

   my $solution = "";
   for(my $i = 0; $i <= $#$path; $i++)
   {
      my ($x, $y, $d) = @{$$path[$i]};
      if( $d == SOLUTION_UP )
      {
         $solution .= "| bash ";
      }
      elsif( $d == SOLUTION_DOWN )
      {
         $solution .= "| python ";
      }
      elsif( $d == SOLUTION_LEFT )
      {
         $solution .= "| ruby ";
      }
      elsif( $d == SOLUTION_RIGHT )
      {
         $solution .= "| perl ";
      }
   }
   $solution =~ s/\s*$//;
   return $solution;
}

# Serialize maze to text
sub OutputMaze()
{
   my @lines = ();
   for(my $y = 0; $y <= HEIGHT; $y++)
   {
      # Vertical walls
      my $output = '';
      for(my $x = 0; $x <= WIDTH; $x++)
      {
         if( $cells[$y][$x] & SOLUTION_UP )
         {
            $output .= '^^';
         }
         elsif( $cells[$y][$x] & SOLUTION_DOWN )
         {
            $output .= 'vv';
         }
         elsif( $cells[$y][$x] & SOLUTION_LEFT )
         {
            $output .= '<<';
         }
         elsif( $cells[$y][$x] & SOLUTION_RIGHT )
         {
            $output .= '>>';
         }
         elsif( $cells[$y][$x] & SOLUTION_GOAL )
         {
            $output .= '##';
         }
         else
         {
            $output .= '  ';
         }
         $output .= ($cells[$y][$x] & DOOR_RIGHT) ? ' ' : '|';
      }
      push @lines, substr($output, 2) . "\n";

      $output = '';
      for(my $x = 0; $x <= WIDTH; $x++)
      {
         # Horizontal walls
         $output .= ($cells[$y][$x] & DOOR_BOTTOM) ? '  ' : '--';

         # Corners
         #
         #        bit 2
         # bit 3         bit 1
         #        bit 0
         my $door_mask =
            (($cells[$y][$x] & (DOOR_RIGHT|DOOR_BOTTOM)) << 2) |
            ($cells[$y + 1][$x] & DOOR_RIGHT) |
            ($cells[$y][$x + 1] & DOOR_BOTTOM);
         $output .= substr('+++++-+-++||+-| ', $door_mask, 1);
      }
      push @lines, substr($output, 2) . "\n";
   }

   return join '', @lines;
}

# Program entry
sub main()
{
   # Initialize maze
   if( $#ARGV != 0 )
   {
      die "$0 <seed>\n";
   }
   $lfsr = $ARGV[0];
   GenerateMaze();
   my @path = Solve();
   #print OutputSolution(\@path), "\n";
   MarkSolution(\@path);
   print OutputMaze();
}


main();