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

use Compress::Zlib;

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

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

@c = ();

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

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

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

# Start marking cells at upper left corner
@b = ([0, 1, 1, 1]);
while( scalar @b )
{
   ($m, $n, $o, $p) = @{pop @b};

   next if (($c[$p][$o] & VISITED) != 0);

   # Mark path between current cell and previous cell
   $c[$p][$o] |= VISITED;
   if( $m < $o )
   {
      $c[$p][$m] |= DOOR_RIGHT;
   }
   elsif( $m > $o )
   {
      $c[$p][$o] |= DOOR_RIGHT;
   }
   else
   {
      if( $n < $p )
      {
         $c[$n][$o] |= DOOR_BOTTOM;
      }
      else
      {
         $c[$p][$o] |= DOOR_BOTTOM;
      }
   }

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

   while( scalar @m )
   {
      ($i, $j) = @{pop @m};
      push @b, [$o, $p, $o + $i, $p + $j];
   }
}

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

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

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

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

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

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

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

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

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

   # Current position
   substr($m[$v * 2], $u * 3 - 2, 2) = "<>";

   # Output lines
   print foreach @m;
}
';


eval $q;