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

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

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

# Global data
my ($lfsr, $cx, $cy, $dir);
my @cells = ();

# Program entry
sub main()
{
   # Initialize maze
   if( $#ARGV != 0 )
   {
      die "$0 <seed>\n";
   }
   $lfsr = $ARGV[0];

   # 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[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
   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;
      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
      my @delta = ([-1, 0], [1, 0], [0, -1], [0, 1]);
      for(my $i = @delta; --$i;)
      {
         $lfsr = ($lfsr >> 1) ^ (0xd0000001 & -($lfsr & 1));
         my $j = $lfsr % ($i + 1);
         next if $i == $j;
         @delta[$i, $j] = @delta[$j, $i];
      }

      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;

   # 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 would go here

      my @lines = ();
      for(my $y = 0; $y <= HEIGHT; $y++)
      {
         # Vertical walls
         my $output = '';
         for(my $x = 0; $x <= WIDTH; $x++)
         {
            $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";
      }

      # 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) = "}#'''";

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

      # Output lines
      print foreach @lines;
   }
}


main();