#!/usr/bin/ruby

# Maze dimensions.
$height = [ARGV[0] && ARGV[0].to_i - 3 || 18, 14].max
$width = [ARGV[1] && ARGV[1].to_i - 2 || 64, 32].max
until $height % 4 == 2 do $height -= 1 end
until $width % 16 == 0 do $width -= 1 end
if ARGV[2]
   srand ARGV[2].to_i
end

# Parent pointers.
$parent = {}

# Output buffer.
$canvas = []

# Triangles that are used in middle boxes.
$reserved = {}

# Get the canonical parent for a particular cell.
def canonical_parent(y, x)
   k = [y, x]
   while $parent[k] && $parent[k] != k
      k = $parent[k]
   end
   return k
end

# Merge two adjacent cells.
def merge_cells(y1, x1, y2, x2)
   k1 = canonical_parent(y1, x1)
   k2 = canonical_parent(y2, x2)
   $parent[k1] = $parent[k2] = [k1, k2].min

   if y1 == y2
      #     ..;;;;;;..              ..;;'';;..
      # ..;;A'  ;;  B';;..      ..;;''      '';;..
      # '';;..  ;;  ..;;''  ->  '';;..      ..;;''
      #     '';;;;;;''              '';;..;;''
      $canvas[y1 - 1][x1 + 4, 2] = "''"
      $canvas[y1    ][x1 + 4, 2] = "  "
      $canvas[y1 + 1][x1 + 4, 2] = "  "
      $canvas[y1 + 2][x1 + 4, 2] = ".."
   else
      y = [y1, y2].max
      if $reserved[k1] && $reserved[k2]
         #     ..;;;;;;..                    ..;;;;;;..
         # ..;;''  ;;  A';;..            ..;;''  ;;  '';;..
         # '';;..  ;;  ..;;;;;;..    ->  '';;..  ;;      ;;;;..
         #     '';;;;;;B'  ;;  '';;..        '';;;;      ;;  '';;..
         #         '';;..  ;;  ..;;''            '';;..  ;;  ..;;''
         #             '';;;;;;''                    '';;;;;;''
         $canvas[y - 1][x1 - 2, 6] = "      "
         $canvas[y    ][x1 - 2, 6] = "      "
      else
         #     ..;;;;;;..                    ..;;;;;;..
         # ..;;''  ;;  A';;..            ..;;''  ;;  '';;..
         # '';;..  ;;  ..;;;;;;..    ->  '';;..  ;;   ,;;;;;;..
         #     '';;;;;;B'  ;;  '';;..        '';;;;;;    ;;  '';;..
         #         '';;..  ;;  ..;;''            '';;..  ;;  ..;;''
         #             '';;;;;;''                    '';;;;;;''
         if y % 4 > 2
            $canvas[y - 1][x1, 2] = x1 % 16 == 4 ? ", " : " ,"
            $canvas[y    ][x1, 2] = "  "
         else
            $canvas[y - 1][x1, 2] = x1 % 16 == 4 ? " ," : ", "
            $canvas[y    ][x1, 2] = "  "
         end
      end
   end
end

# Initialize canvas with all walls.
def init_canvas
   template =
   [
      ";;  ..;;;;;;..  ",
      ";;;;''  ;;  '';;",
      ";;;;..  ;;  ..;;",
      ";;  '';;;;;;''  ",
   ]
   $canvas = []
   (0..$height - 1).each{|y| $canvas += [template[y % 4] * ($width / 16)]}

   # Remove extraneous edges from top row.
   $canvas[0] = $canvas[0].gsub(/;; /, "   ")
   $canvas[1] = $canvas[1].gsub(/;;;;''/, "..;;''")

   # Add some padding to bottom row.
   suffix =
   [
      "'';;..  ;;  ..;;",
      "    '';;;;;;''  ",
      "        ''      ",
   ]
   (0..2).each{|y| $canvas += [suffix[y] * ($width / 16)]}

   # Pad right side edges.
   pad = [
      "  ",
      "..",
      "''",
      "  ",
   ]
   (0..$canvas.size - 1).each{|y| $canvas[y] += pad[y % 4]}

   # Initialize disjoint regions.
   (0..$height / 2 - 1).each{|i|
      (0..$width / 8 - 1).each{|j|
         k = [i * 2 + 1, j * 8 + 4]
         $parent[k] = k
      }
   }
end

# Check if a single group of cells are all free to be reserved.
def is_available(y, x)
   return (0..2).all?{|i| !$reserved[[y + i * 2, x]] &&
                          !$reserved[[y + i * 2, x + 8]]}
end

# Group some cells into isometric rectangles.
def reserve_boxes
   # Set initial position.
   y0 = rand(($height / 2) - 5) * 2 + 1
   x0 = (y0 % 4 < 2) ? rand(($width / 16) - 2) * 16 + 20
                     : rand(($width / 16) - 2) * 16 + 12

   # See if we can expand further right.
   size = 0
   dy = rand(2) > 0 ? +2 : -2
   while (size == 0 || rand(5) > 0) &&
         x0 + 8 + 8 * size < $width - 12 &&
         y0 + dy * size < $height - 6 &&
         y0 + dy * size > 2 &&
         is_available(y0 + dy * size, x0 + 8 * size)
      size += 1
   end
   if size == 0
      return
   end

   # Reserve cells.
   (0..size - 1).each{|i|
      (0..2).each{|j|
         $reserved[[y0 + i * dy + j * 2, x0 + i * 8]] = 1
         $reserved[[y0 + i * dy + j * 2, x0 + i * 8 + 8]] = 1
      }
   }

   # Remove walls.
   if dy > 0
      if rand(2) > 0
         # ;;  ..;;'';;..  ;;  ..;;;;;;..  ;;
         # ;;;;''      '';;;;;;''  ;;  '';;;;
         # ;;;;..          '';;..  ;;  ..;;;;
         # ;;  '';;..          '';;;;;;''  ;;
         # ;;      '';;..          '';;..  ;;
         # ;;          '';;..          '';;;;
         # ;;;;..          '';;..      ..;;;;
         # ;;  '';;..          '';;..;;''  ;;
         # ;;  ..;;;;;;..          ;;      ;;
         # ;;;;''  ;;  '';;..      ;;      ;;
         # ;;;;..  ;;  ..;;;;;;..  ;;  ..;;;;
         # ;;  '';;;;;;''  ;;  '';;;;;;''  ;;
         merge_cells(y0 + size * 2, x0 + size * 8,
                     y0 + size * 2 + 2, x0 + size * 8)
         (0..size - 1).each{|i|
            merge_cells(y0 + i * 2, x0 + i * 8,
                        y0 + i * 2, x0 + i * 8 + 8)
            merge_cells(y0 + i * 2 + 2, x0 + i * 8,
                        y0 + i * 2 + 4, x0 + i * 8)
         }
         (0..size - 2).each{|i|
            merge_cells(y0 + i * 2,     x0 + i * 8 + 8,
                        y0 + i * 2 + 2, x0 + i * 8 + 8)
            merge_cells(y0 + i * 2 + 4, x0 + i * 8,
                        y0 + i * 2 + 4, x0 + i * 8 + 8)
         }
      else
         # ;;  ..;;;;;;..  ;;  ..;;;;;;..  ;;
         # ;;;;''  ;;  '';;;;;;''  ;;  '';;;;
         # ;;      ;;      '';;..  ;;  ..;;;;
         # ;;      ;;          '';;;;;;''  ;;
         # ;;  ..;;'';;..          '';;..  ;;
         # ;;;;''      '';;..          '';;;;
         # ;;;;..          '';;..          ;;
         # ;;  '';;..          '';;..      ;;
         # ;;  ..;;;;;;..          '';;..  ;;
         # ;;;;''  ;;  '';;..          '';;;;
         # ;;;;..  ;;  ..;;;;;;..      ..;;;;
         # ;;  '';;;;;;''  ;;  '';;..;;''  ;;
         merge_cells(y0, x0,
                     y0 + 2, x0)
         (0..size - 1).each{|i|
            merge_cells(y0 + i * 2 + 4, x0 + i * 8,
                        y0 + i * 2 + 4, x0 + i * 8 + 8)
            merge_cells(y0 + i * 2,     x0 + i * 8 + 8,
                        y0 + i * 2 + 2, x0 + i * 8 + 8)
         }
         (0..size - 2).each{|i|
            merge_cells(y0 + i * 2 + 2, x0 + i * 8 + 8,
                        y0 + i * 2 + 2, x0 + i * 8 + 16)
            merge_cells(y0 + i * 2 + 4, x0 + i * 8 + 8,
                        y0 + i * 2 + 6, x0 + i * 8 + 8)
         }
      end
   else
      if rand(2) > 0
         # ;;  ..;;;;;;..  ;;  ..;;'';;..  ;;
         # ;;;;''  ;;  '';;;;;;''      '';;;;
         # ;;;;..  ;;  ..;;''          ..;;;;
         # ;;  '';;;;;;''          ..;;''  ;;
         # ;;  ..;;''          ..;;''      ;;
         # ;;;;''          ..;;''          ;;
         # ;;;;..      ..;;''          ..;;;;
         # ;;  '';;..;;''          ..;;''  ;;
         # ;;      ;;          ..;;;;;;..  ;;
         # ;;      ;;      ..;;''  ;;  '';;;;
         # ;;;;..  ;;  ..;;;;;;..  ;;  ..;;;;
         # ;;  '';;;;;;''  ;;  '';;;;;;''  ;;
         merge_cells(y0 + 2, x0,
                     y0 + 4, x0)
         (0..size - 1).each{|i|
            merge_cells(y0 - i * 2, x0 + i * 8,
                        y0 - i * 2, x0 + i * 8 + 8)
            merge_cells(y0 - i * 2 + 2, x0 + i * 8 + 8,
                        y0 - i * 2 + 4, x0 + i * 8 + 8)
         }
         (0..size - 2).each{|i|
            merge_cells(y0 - i * 2 + 2, x0 + i * 8 + 8,
                        y0 - i * 2 + 2, x0 + i * 8 + 16)
            merge_cells(y0 - i * 2,     x0 + i * 8 + 8,
                        y0 - i * 2 - 2, x0 + i * 8 + 8)
         }
      else
         # ;;  ..;;;;;;..  ;;  ..;;;;;;..  ;;
         # ;;;;''  ;;  '';;;;;;''  ;;  '';;;;
         # ;;;;..  ;;  ..;;''      ;;      ;;
         # ;;  '';;;;;;''          ;;      ;;
         # ;;  ..;;''          ..;;'';;..  ;;
         # ;;;;''          ..;;''      '';;;;
         # ;;          ..;;''          ..;;;;
         # ;;      ..;;''          ..;;''  ;;
         # ;;  ..;;''          ..;;;;;;..  ;;
         # ;;;;''          ..;;''  ;;  '';;;;
         # ;;;;..      ..;;;;;;..  ;;  ..;;;;
         # ;;  '';;..;;''  ;;  '';;;;;;''  ;;
         merge_cells(y0 - size * 2 + 2, x0 + size * 8,
                     y0 - size * 2 + 4, x0 + size * 8)
         (0..size - 1).each{|i|
            merge_cells(y0 - i * 2 + 4, x0 + i * 8,
                        y0 - i * 2 + 4, x0 + i * 8 + 8)
            merge_cells(y0 - i * 2,     x0 + i * 8,
                        y0 - i * 2 + 2, x0 + i * 8)
         }
         (0..size - 2).each{|i|
            merge_cells(y0 - i * 2, x0 + i * 8,
                        y0 - i * 2, x0 + i * 8 + 8)
            merge_cells(y0 - i * 2 + 2, x0 + i * 8 + 8,
                        y0 - i * 2 + 4, x0 + i * 8 + 8)
         }
      end
   end
end

# Reserve lots of boxes until we fulfill certain density requirement.
def reserve_enough_boxes
   max_reservable_boxes = ($width / 8) * ($height / 2)
   for i in 0..max_reservable_boxes
      reserve_boxes
      if $reserved.size > max_reservable_boxes * 0.4
         return
      end
   end
end

# Remove vertical walls that are not adjacent to reserved boxes.
def remove_vertical_walls
   for i in 0..$height / 2 - 1
      y = i * 2 + 1
      for j in 0..$width / 16 - 1
         x = j * 16 + (i % 2 > 0 ? -4 : 4)
         if !$reserved[[y, x]] && !$reserved[[y, x + 8]]
            merge_cells(y, x, y, x + 8)
         end
      end
   end
end

# Collect coordinates of triangle pairs that form removable walls.
def get_diagonal_walls
   walls = []
   for i in 1..$height / 2 - 1
      y = i * 2 + 1
      for j in 1..$width / 8 - 2
         x = j * 8 + 4
         walls += [[y, x, y - 2, x]]
      end
   end
   return walls.shuffle
end

# Join cells using walls that do not border reserved cells.
def join_cells(walls)
   walls.each{|y1, x1, y2, x2|
      if !$reserved[[y1, x1]] && !$reserved[[y2, x2]] &&
         canonical_parent(y1, x1) != canonical_parent(y2, x2)
         merge_cells(y1, x1, y2, x2)
      end
   }
end

# Make sure there is a path from entrance to exit.
def make_maze_solvable(walls)
   $reserved = {}

   walls.each{|y1, x1, y2, x2|
      if canonical_parent(1, 4) == canonical_parent($height - 1, $width - 4)
         return
      end
      if canonical_parent(y1, x1) != canonical_parent(y2, x2)
         merge_cells(y1, x1, y2, x2)
      end
   }
end

# Mark start and end of the maze.
def mark_start_and_end
   merge_cells(1, 4, -1, 4)
   merge_cells($height - 1, $width - 4, $height + 1, $width - 4)
end


init_canvas
reserve_enough_boxes
remove_vertical_walls
walls = get_diagonal_walls
join_cells(walls)
make_maze_solvable(walls)
mark_start_and_end

$canvas.each{|line| puts line}