#!/usr/bin/perl -w
# neptune2.pl - Don Yang (uguu.org)
#
# 2014-03-15

# Program code
$code = q'
use constant WIDTH => 25;
use constant HEIGHT => 10;

use constant VISITED => 4;
use constant DOOR_RIGHT => 1;
use constant DOOR_BOTTOM => 2;

@cells = ();

# Initialize maze
unless( defined($lfsr) )
{
   if( $#ARGV != 0 )
   {
      print "$0 <seed>\n";
      exit 1;
   }
   $lfsr = $ARGV[0];
}

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

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

# Start marking cells at upper left corner
@visit = ([0, 1, 1, 1]);
while( scalar @visit )
{
   ($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;
   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;
      }
   }

   # Visit neighbors in random order
   @delta = ([-1, 0], [1, 0], [0, -1], [0, 1]);
   for($i = @delta; --$i;)
   {
      $lfsr = ($lfsr >> 1) ^ (0xd0000001 & -($lfsr & 1));
      $j = $lfsr % ($i + 1);
      next if $i == $j;
      @delta[$i, $j] = @delta[$j, $i];
   }

   while( scalar @delta )
   {
      ($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;

# Initialize position
if( defined($cx) )
{
   if( defined($dir) )
   {
      if( $dir == 0 && ($cells[$cy - 1][$cx] & DOOR_BOTTOM) )
      {
         # bash = up
         $cy--;
      }
      elsif( $dir == 1 && ($cells[$cy][$cx] & DOOR_BOTTOM) )
      {
         # python = down
         $cy++;
      }
      elsif( $cells[$cy][$cx] & DOOR_RIGHT )
      {
         # ruby = right
         $cx++;
      }
   }
   elsif( $cells[$cy][$cx - 1] & DOOR_RIGHT )
   {
      # perl = left
      $cx--;
   }
}
else
{
   $cx = $cy = 0;
}

# Output current state
if( $cx == WIDTH - 1 && $cy == HEIGHT - 1 )
{
   print "GOAL!\n";
}
else
{
   # Driver stub
   $Q = ($q = "\47") x 3;
   #XXX

   @lines = ();
   for($y = 0; $y <= HEIGHT; $y++)
   {
      # Vertical walls
      $output = "";
      for($x = 0; $x <= WIDTH; $x++)
      {
         $output .= ($cells[$y][$x] & DOOR_RIGHT) ? "   " : "  |";
      }
      push @lines, substr($output, 2) . "\n";

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

         # Corners
         #
         #        bit 2
         # bit 3         bit 1
         #        bit 0
         $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";
   }

   # Legend
   substr($lines[10], 36, 4) = "bash";
   substr($lines[11], 29, 18) = "perl          ruby";
   substr($lines[12], 35, 6) = "python";
   substr($lines[21], 71, 5) = "}#$Q";

   # Current position
   substr($lines[$cy * 2 + 2], $cx * 3 + 1, 2) = "<>";

   # Output lines
   print foreach @lines;
}
';


eval $code;