#!/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)
   if k1 != k2
      $parent[k1] = $parent[k2] = [k1, k2].min

      if y1 == y2
         # A   ..;;B;;;..              ..;;'';;..
         # ..;;''  ;;  '';;..      ..;;''      '';;..
         # '';;..  ;;  ..;;''  ->  '';;..      ..;;''
         #     '';;;;;;''              '';;..;;''
         (0..3).each{|i| $canvas[y1 + i][x1 + 8, 2] = "'  ."[i] * 2}
      else
         y = [y1, y2].max
         if $reserved[k1] && $reserved[k2]
            #     ..;;A;;;..                    ..;;;;;;..
            # ..;;''  ;;  '';;..            ..;;''  ;;  '';;..
            # '';;..  B;  ..;;;;;;..    ->  '';;..  ;;      ;;;;..
            #     '';;;;;;''  ;;  '';;..        '';;;;      ;;  '';;..
            #         '';;..  ;;  ..;;''            '';;..  ;;  ..;;''
            #             '';;;;;;''                    '';;;;;;''
            [y, y + 1].each{|i| $canvas[i][x1 + 2, 6] = " " * 6}
         else
            #     ..;;A;;;..                    ..;;;;;;..
            # ..;;''  ;;  '';;..            ..;;''  ;;  '';;..
            # '';;..  B;  ..;;;;;;..    ->  '';;..  ;;   ,;;;;;;..
            #     '';;;;;;''  ;;  '';;..        '';;;;;;    ;;  '';;..
            #         '';;..  ;;  ..;;''            '';;..  ;;  ..;;''
            #             '';;;;;;''                    '';;;;;;''
            $canvas[y][x1 + 4, 2] =
               " , "[(x1 % 16 > 0) ^ (y % 4 > 1) ? 1 : 0, 2]
            $canvas[y + 1][x1 + 4, 2] = "  "
         end
      end
   end
end

# Initialize canvas with all walls.
def init_canvas
   template =
   [
      # Template
      "; .;;;. ",
      ";;' ; ';",
      ";;. ; .;",
      "; ';;;' ",
      # Suffix
      "';. ; .;",
      "  ';;;' ",
      "    '   "
   ].map{|i| i.split(//).map{|j| j * 2}.join}
   $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.
   (4..6).each{|y| $canvas += [template[y] * ($width / 16)]}

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

   # Initialize disjoint regions.
   (0..$height / 2 - 1).each{|i|
      (0..$width / 8 - 1).each{|j|
         k = [i * 2, j * 8]
         $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
   x0 = (y0 % 4 < 2) ? rand(($width / 16) - 2) * 16 + 16
                     : rand(($width / 16) - 2) * 16 + 8

   # 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 - 16 &&
         y0 + dy * size < $height - 7 &&
         y0 + dy * size > 1 &&
         is_available(y0 + dy * size, x0 + 8 * size)
      size += 1
   end
   if size > 0
      # Reserve cells.
      (0..size - 1).each{|i|
         (0..2).each{|j|
            [0, 8].each{|k|
               $reserved[[y0 + i * dy + j * 2, x0 + i * 8 + k]] = 1
            }
         }
      }

      # Remove walls.
      # dy > 0, dx > 0                       dy > 0, dx < 0
      # ;;  ..;;'';;..  ;;  ..;;;;;;..  ;;   ;;  ..;;;;;;..  ;;  ..;;;;;;..  ;;
      # ;;;;A'      B';;;;;;''  ;;  '';;;;   ;;;;H'  ;;  D';;;;;;''  ;;  '';;;;
      # ;;;;..          '';;..  ;;  ..;;;;   ;;      ;;      '';;..  ;;  ..;;;;
      # ;;  D';;..  C       '';;;;;;''  ;;   ;;  G   ;;  E       F';;;;;;''  ;;
      # ;;      '';;..          '';;..  ;;   ;;  ..;;'';;..          '';;..  ;;
      # ;;  E       F';;..          '';;;;   ;;;;A'      B';;..          '';;;;
      # ;;;;..          '';;..      ..;;;;   ;;;;..          '';;..          ;;
      # ;;  '';;..          '';;..;;H'  ;;   ;;  '';;..  C       '';;..      ;;
      # ;;  ..;;;;;;..          ;;      ;;   ;;  ..;;;;;;..          '';;..  ;;
      # ;;;;''  ;;  '';;..      ;;  G   ;;   ;;;;''  ;;  '';;..          '';;;;
      # ;;;;..  ;;  ..;;;;;;..  ;;  ..;;;;   ;;;;..  ;;  ..;;;;;;..      ..;;;;
      # ;;  '';;;;;;''  ;;  '';;;;;;''  ;;   ;;  '';;;;;;''  ;;  '';;..;;''  ;;
      #
      # dy < 0, dx > 0                       dy < 0, dx < 0
      # ;;  ..;;;;;;..  ;;  ..;;'';;..  ;;   ;;  ..;;;;;;..  ;;  ..;;;;;;..  ;;
      # ;;;;''  ;;  '';;;;;;''      '';;;;   ;;;;''  ;;  '';;;;;;''  ;;  G';;;;
      # ;;;;..  ;;  ..;;''          ..;;;;   ;;;;..  ;;  ..;;''      ;;      ;;
      # ;;  '';;;;;;C'          ..;;''  ;;   ;;  '';;;;;;''          ;;  H   ;;
      # ;;  ..;;''          ..;;''      ;;   ;;  ..;;''          ..;;'';;..  ;;
      # ;;;;A'      B   ..;;''          ;;   ;;;;E'      F   ..;;''      '';;;;
      # ;;;;..      ..;;''          ..;;;;   ;;          ..;;''          ..;;;;
      # ;;  G';;..;;E'      F   ..;;''  ;;   ;;  D   ..;;C'          ..;;''  ;;
      # ;;      ;;          ..;;;;;;..  ;;   ;;  ..;;''          ..;;;;;;..  ;;
      # ;;  H   ;;  D   ..;;''  ;;  '';;;;   ;;;;A'      B   ..;;''  ;;  '';;;;
      # ;;;;..  ;;  ..;;;;;;..  ;;  ..;;;;   ;;;;..      ..;;;;;;..  ;;  ..;;;;
      # ;;  '';;;;;;''  ;;  '';;;;;;''  ;;   ;;  '';;..;;''  ;;  '';;;;;;''  ;;
      dx = rand(2) > 0 ? 8 : -8
      py1 = px1 = py2 = px2 = nil
      (0..size - 1).each{|i|
         # Merge A+B
         merge_cells(cy1 = y0 + i * dy + (dx > 0 ? 0 : 4),
                     cx1 = x0 + i * 8,
                     ny1 = y0 + i * dy + (dx > 0 ? 0 : 4),
                     nx1 = x0 + i * 8 + 8)
         # Merge D+E
         cy2 = cy1 + ((dx > 0) ^ (dy > 0) ? -2 * dy : dy)
         cx2 = cx1 + ((dx > 0) ^ (dy > 0) ? 8 : 0)
         merge_cells(cy2,
                     cx2,
                     ny2 = cy2 + dy,
                     nx2 = cx2)

         if py1
            # Merge B+C
            merge_cells(py1, px1, cy1, cx1)
            # Merge E+F
            merge_cells(py2, px2, cy2, cx2)
         end
         py1 = ny1
         px1 = nx1
         py2 = ny2
         px2 = nx2
      }
      # Merge G+H
      cy = dx > 0 == dy > 0 ? py2 : y0 + 2
      cx = dx > 0 == dy > 0 ? px2 + 8 : x0
      merge_cells(cy,
                  cx,
                  cy - dy,
                  cx)
   end
end

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

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

# Collect coordinates of triangle pairs that form removable walls.
def get_diagonal_walls
   walls = []
   (1..$height / 2 - 1).each{|i|
      y = i * 2
      (1..$width / 8 - 2).each{|j|
         x = j * 8
         walls += [[y - 2, x, y, x]]
      }
   }
   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]]
         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(0, 0) != canonical_parent($height - 2, $width - 8)
         merge_cells(y1, x1, y2, x2)
      end
   }
end

# Mark start and end of the maze.
def mark_start_and_end
   merge_cells(-2, 0, 0, 0)
   merge_cells($height - 2, $width - 8, $height, $width - 8)
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}