#!/usr/bin/ruby

# Maze dimensions.
i = ARGV
height = [i[0] && i[0].to_i - 3 || 18, 14].max
width = [i[1] && i[1].to_i - 2 || 64, 32].max
height = (height - (height + 2) % 4) / 2
width /= 16
if i[2]
   srand i[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;;;..              ..;;'';;..
         # ..;;''  ;;  '';;..      ..;;''      '';;..
         # '';;..  ;;  ..;;''  ->  '';;..      ..;;''
         #     '';;;;;;''              '';;..;;''
         4.times{|i| $canvas[y1 + i][x1 + 8, 2] = "'  ."[i] * 2}
      else
         y = [y1, y2].max
         if $reserved[k1] && $reserved[k2]
            #     ..;;A;;;..                    ..;;;;;;..
            # ..;;''  ;;  '';;..            ..;;''  ;;  '';;..
            # '';;..  B;  ..;;;;;;..    ->  '';;..  ;;      ;;;;..
            #     '';;;;;;''  ;;  '';;..        '';;;;      ;;  '';;..
            #         '';;..  ;;  ..;;''            '';;..  ;;  ..;;''
            #             '';;;;;;''                    '';;;;;;''
            2.times{|i| $canvas[y + i][x1 + 2, 6] = " " * 6}
         else
            #     ..;;A;;;..                    ..;;;;;;..
            # ..;;''  ;;  '';;..            ..;;''  ;;  '';;..
            # '';;..  B;  ..;;;;;;..    ->  '';;..  ;;   ,;;;;;;..
            #     '';;;;;;''  ;;  '';;..        '';;;;;;    ;;  '';;..
            #         '';;..  ;;  ..;;''            '';;..  ;;  ..;;''
            #             '';;;;;;''                    '';;;;;;''
            $canvas[y][x1 + 4, 2] = " , "[(x1 % 16 / 8) ^ (y % 4 / 2), 2]
            $canvas[y + 1][x1 + 4, 2] = "  "
         end
      end
   end
end


# {{{ init_canvas
   template =
   [
      # Template
      "; .;;;. ",
      ";;' ; ';",
      ";;. ; .;",
      "; ';;;' ",
      # Suffix
      "';. ; .;",
      "  ';;;' ",
      "    '   "
   ].map{|i| i.split(//).map{|j| j * 2}.join}
   (height * 2).times{|y| $canvas += [template[y % 4] * width]}

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

   # Add some padding to bottom row.
   3.times{|y| $canvas += [template[y + 4] * width]}

   # Pad right side edges.
   $canvas.size.times{|y| $canvas[y] += " .' "[y % 4] * 2}

   # Initialize disjoint regions.
   height.times{|i|
      (width * 2).times{|j|
         k = [i * 2, j * 8]
         $parent[k] = k
      }
   }
# }}}

# {{{ reserve_enough_boxes
   max_reservable_boxes = (width * 2) * height + 1
   max_reservable_boxes.times{
      if $reserved.size < max_reservable_boxes * 0.4
         # {{{ reserve_boxes
         # Set initial position.
         y0 = rand(height - 5) * 2
         x0 = rand(width - 2) * 16 + (y0 % 4 < 2 ? 16 : 8)

         # See if we can expand further right.
         size = 0
         dy = rand(2) > 0 ? 2 : -2
         while (size < 1 || rand(5) > 0) &&
               (p = x0 + 8 * size) < width * 16 - 24 &&
               (d = y0 + dy * size) < height * 2 - 7 &&
               d > 1 &&
               # {{{ is_available
                  (0..2).all?{|i| !$reserved[[d + i * 2, p]] &&
                                  !$reserved[[d + i * 2, p + 8]]}
               # }}}
            size += 1
         end
         if size > 0
            # Reserve cells.
            size.times{|i|
               3.times{|j|
                  [0, 8].each{|k|
                     $reserved[[y0 + i * dy + j * 2, x0 + i * 8 + k]] = 1
                  }
               }
            }

            # Remove walls.
            dx = rand(2) > 0 ? 8 : -8
            d = dx * dy < 0
            py1 = px1 = py2 = px2 = nil
            size.times{|i|
               # Merge A+B
               merge_cells(cy1 = y0 + i * dy + (dx > 0 ? 0 : 4),
                           cx1 = x0 + i * 8,
                           ny1 = cy1,
                           nx1 = cx1 + 8)
               # Merge D+E
               merge_cells(cy2 = cy1 + (d ? -2 * dy : dy),
                           cx2 = cx1 + (d ? 8 : 0),
                           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
            merge_cells(cy = d ? y0 + 2 : py2,
                        cx = d ? x0 : px2 + 8,
                        cy - dy,
                        cx)
         end
         # }}}
      end
   }
# }}}

# {{{ remove_vertical_walls + get_diagonal_walls
   walls = []
   height.times{|i|
      width.times{|j|
         merge_cells(y = i * 2,
                     x = j * 16 - i % 2 * 8,
                     y,
                     x + (!$reserved[[y, x]] &&
                          !$reserved[[y, x + 8]] ? 8 : 0))
      }
      (1..width * 2 - 2).each{|j|
         walls += i > 0 ? [[y = i * 2, x = j * 8, y - 2, x]] : []
      }
   }
   walls = walls.shuffle
# }}}

# {{{ join_cells + make_maze_solvable
   2.times{|i|
      walls.each{|y1, x1, y2, x2|
         if (i < 1 ||
             canonical_parent(0, 0) !=
                 canonical_parent(height * 2 - 2, width * 16 - 8)) &&
            !$reserved[[y1, x1]] &&
            !$reserved[[y2, x2]]
            merge_cells(y1, x1, y2, x2)
         end
      }
      $reserved = {}
   }
# }}}

# {{{ mark_start_and_end
   merge_cells(-2, 0, 0, 0)
   merge_cells(y = height * 2,
               x = width * 16 - 8,
               y - 2,
               x)
# }}}

$canvas.each{|line| puts line}