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

use Compress::Zlib;

# 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($seed) )
{
   if( $#ARGV != 0 )
   {
      print "$0 <seed>\n";
      exit 1;
   }
   $seed = $ARGV[0];
}
$lfsr = $seed;

# 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;

# Debug info
print "#INPUT cx=", (defined($cx) ? $cx : "?"),
      " cy=", (defined($cy) ? $cy : "?"),
      " d=", (defined($d) ? $d : "?"), "\n";

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

print "#NEXT  cx=", (defined($cx) ? $cx : "?"),
      " cy=", (defined($cy) ? $cy : "?"),
      " d=", (defined($d) ? $d : "?"), "\n";

# Output current state
if( $cx == WIDTH && $cy == HEIGHT )
{
   print "GOAL!\n";
}
else
{
   # Driver stub
   $Q = ($q = "\47") x 3;
   $s = chr(92);
   if( $cx == 1 && $cy == 1 )
   {
      $code = "\$seed=$seed;$code";
   }
   $encoded = pack "u*", compress($code);
   eval "\$encoded =~ y/${s}40-${s}47${s}n\@$s$s/a-k/;";

   print <<"EOT";
q=$Q\$q=.0;use Compress::Zlib;\$cx=$cx;\$cy=$cy;\$code=uncompress(unpack"u*",("$encoded"=~y/a-k/${s}40-${s}47${s}12${s}100${s}134/r));eval\$code;__DATA__ $q+%{
perl<<z;exit 0
$s\$d=0;\$q
z
$Q
import subprocess
r=q.rfind($q/$q)
i=subprocess.Popen("perl",stdin=subprocess.PIPE)
i.stdin.write($q\$d=1;$q+q[0:q.rfind($q/$q,0,r)]+r$q/${s}40-${s}47${s}12${s}100${s}134$q+q[r:])
i.stdin.close()
i.wait()
$Q};IO.popen("perl","w"){|l|l.write($q\$d=2;$q+q);l.close_write};r=%{
EOT
   print "\n" x 5;

   @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], $cx * 3 - 2, 2) = "<>";

   # Output lines
   print foreach @lines;
}
';


eval $code;