#!/usr/bin/perl
# maze.pl - Don Yang (uguu.org)
#
# 2014-02-17

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

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

# Create door between two cells
sub ConnectCells($$$$$)
{
   my ($cells, $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 = int(rand($i + 1));
      next if $i == $j;
      @delta[$i, $j] = @delta[$j, $i];
   }
   return @delta;
}

# Generate maze with padded cells
sub GenerateMaze($$$)
{
   my ($cells, $width, $height) = @_;

   # Initialize maze with walls
   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;
      ConnectCells($cells, $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;
}

# Serialize maze as a string
sub OutputMaze($)
{
   my ($cells) = @_;
   my $height = @$cells - 1;
   my $width = @{$$cells[0]} - 1;

   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";
   }
   substr($lines[10], 28, 20) = '        bash        ';
   substr($lines[11], 28, 20) = 'perl            ruby';
   substr($lines[12], 28, 20) = '       python       ';
   substr($lines[21], 71, 5) = "}#'''";
   return join '', @lines;
}


my @cells = ();
GenerateMaze(\@cells, WIDTH, HEIGHT);
print OutputMaze(\@cells);