#!/usr/bin/ruby
# The goal is to generate a sense sense of trick art by mixing
# isometric projections, like these:
#
#        ..;;'';;..              ..;;;;;;..
#    ..;;''      '';;..      ..;;''  ;;  '';;..
#    ;;;;..      ..;;;;      ;;      ;;      ;;
#    ;;  '';;..;;''  ;;      ;;      ;;      ;;
#    ;;      ;;      ;;      ;;  ..;;'';;..  ;;
#    ;;      ;;      ;;      ;;;;''      '';;;;
#    '';;..  ;;  ..;;''      '';;..      ..;;''
#        '';;;;;;''              '';;..;;''
#
# This is done by creating a grid of triangles, and then removing the
# appropriate walls.  Throughout this code, the triangles are
# identified by the center of their top edges (A and B below).  This
# is entirely arbitrary but just seemed like a good idea at the time.
# Later versions of the code used a simpler coordinate system because
# it's not such a good idea after all.
#
#    01234567890123456789012345678901234567890123456789
#  0     ..;;;;;;..      ..;;;;;;..      ..;;;;;;..     | Prefix
#  1 ..;;A'  ;;  B';;..;;''  ;;  '';;..;;''  ;;  '';;.. |
#  2 '';;..  ;;  ..;;;;;;..  ;;  ..;;;;;;..  ;;  ..;;''
#  3     '';;;;;;''  ;;  '';;;;;;''  ;;  '';;;;;;''
#  4     ..;;;;;;..  ;;  ..;;'';;..  ;;  ..;;;;;;..
#  5 ..;;''  ;;  '';;;;;;''      '';;;;;;''  ;;  '';;..
#  6 '';;..  ;;  ..;;''          ..;;;;;;..  ;;  ..;;''
#  7     '';;;;;;''          ..;;''  ;;  '';;;;;;''
#  8     ..;;;;;;..      ..;;''      ;;  ..;;;;;;..
#  9 ..;;''  ;;  '';;..;;''          ;;;;''  ;;  '';;..
# 10 '';;..  ;;      ;;          ..;;;;;;..  ;;  ..;;''
# 11     '';;;;      ;;      ..;;''  ;;  '';;;;;;''
# 12     ..;;;;;;..  ;;  ..;;;;;;..  ;;  ..;;;;;;..
# 13 ..;;''  ;;  '';;;;;;''  ;;  '';;;;;;''  ;;  '';;..
# 14 '';;..  ;;  ..;;;;      ;;      '';;..  ;;  ..;;''
# 15     '';;;;;;''  ;;      ;;          '';;;;;;''
# 16     ..;;;;;;..  ;;  ..;;'';;..          ;;;;..
# 17 ..;;''  ;;  '';;;;;;''      '';;..      ;;  '';;..
# 18 '';;..  ;;  ..;;;;;;..          '';;..  ;;  ..;;''
# 19     '';;;;;;''  ;;  '';;..          '';;;;;;''
# 20     ..;;;;;;..  ;;  ..;;;;;;..      ..;;;;;;..
# 21 ..;;''  ;;  '';;;;;;''  ;;  '';;..;;''  ;;  '';;..
# 22 '';;..  ;;  ..;;;;;;..  ;;  ..;;;;;;..  ;;  ..;;''
# 23     '';;;;;;''  ;;  '';;;;;;''  ;;  '';;;;;;''
# 24     ..;;;;;;..  ;;  ..;;;;;;..  ;;  ..;;;;;;..
# 25 ..;;''  ;;  '';;;;;;''  ;;  '';;;;;;''  ;;  '';;..
# 26 '';;..  ;;  ..;;'';;..  ;;  ..;;'';;..  ;;  ..;;'' | Suffix
# 27     '';;;;;;''      '';;;;;;''      '';;;;;;''     |
# 28         ''              ''              ''         |
#                                                    ^^
#                                                    Padding
#
# Just generating isometric ASCII art isn't particularly fun, so this
# program is also a maze generator.  This works by removing edges in
# the triangles to create paths.  For example, the center room below
# is accessible from all its neighbors.
#
#        ..;;'';;..      ..;;'';;..
#    ..;;''      '';;..;;''      '';;..
#    '';;..       ,;;'';;,       ..;;''
#        '';;..;;          ;;..;;''
#        ..;;'';;,        ,;;'';;..
#    ..;;''        ;;..;;        '';;..
#    '';;..      ..;;'';;..      ..;;''
#        '';;..;;''      '';;..;;''
#            ''              ''
# Most other maze generators build up a set of connected rooms from
# logical coordinates and output the maze from there, typically by
# performing random walks from room to room.  This program starts from
# a rendered canvas and builds a maze using screen coordinates, by
# joining random rooms.  It does this in order to preserve the
# embedded isometric images.
#
#  1. Start with rendered canvas, with some edges reserved for the
#     embedded images.  In particular, only embedded images contain
#     vertical edges, all other edges are diagonal.
#
#  2. Cut holes in all diagonal edges except reserved ones, but only
#     cut a hole if it joins two regions that are not already
#     connected through other paths (i.e. no cycles in maze).
#
#  3. Cut holes in reserved diagonal edges until starting room and
#     exit room are part of the same region.
#
# Because we never cut holes in vertical walls, there is a possibility
# that some mazes are unsolvable.  We avoid unsolvable mazes by making
# sure that the top and bottom rows are free of vertical walls, so we
# should always have a path.  Still, there is a small possibility that
# some mazes are unsolvable.  Very small possibility.  There is a much
# higher possibility that some rooms are unreachable, this is by
# design and is working as intended.
#
# Maze generators are common in IOCCC but has yet to win in TRICK.
# Also, despite the contest being named TRICK, no trick art has won
# yet.  This entry should fulfill both gaps quite well.


# Maze dimensions.  These minimum sizes are chosen so that we don't
# get strange artefacts with the middle boxes.
$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.  Two triangles are part of the same region if they
# share the same parent pointer.  See also:
# https://en.wikipedia.org/wiki/Disjoint-set_data_structure
$parent = {}

# Output buffer.
$canvas = []

# Triangles that are used in middle boxes.  We don't want to use edges
# to these triangles as maze paths unless we have no other choice.
$reserved = {}

# Build dictionary key from a coordinate.
def key(y, x)
   # This is a string key, as opposed to simply [y,x].  The former appears
   # to be more efficient in terms of running time.  The latter is more
   # space efficient in terms of code size, so later versions of this code
   # uses lists and don't bother with this function.
   return "#{y},#{x}"
end

# Get the canonical parent for a particular cell.
#
# We can save a few bytes here by rewriting this function using
# recursion, but because ruby does not enable tail call optimization
# by default, we will get SystemStackError easily, so it's not worth it.
def canonical_parent(k)
   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(key(y1, x1))
   k2 = canonical_parent(key(y2, x2))
   $parent[k1] = $parent[k2] = [k1, k2].min

   if y1 == y2
      # Merging horizontal cells.
      #     ..;;;;;;..              ..;;'';;..
      # ..;;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
      # Merging vertical cells.
      y = [y1, y2].max
      if $reserved[k1] && $reserved[k2]
         # Knock down the entire wall if we are building graphics for
         # the middle boxes.
         #     ..;;;;;;..                    ..;;;;;;..
         # ..;;''  ;;  A';;..            ..;;''  ;;  '';;..
         # '';;..  ;;  ..;;;;;;..    ->  '';;..  ;;      ;;;;..
         #     '';;;;;;B'  ;;  '';;..        '';;;;      ;;  '';;..
         #         '';;..  ;;  ..;;''            '';;..  ;;  ..;;''
         #             '';;;;;;''                    '';;;;;;''
         $canvas[y - 1][x1 - 2, 6] = "      "
         $canvas[y    ][x1 - 2, 6] = "      "
      else
         # Open a small gap when we just want a path through the
         # walls, to preserve most of the isometric look.
         #     ..;;;;;;..                    ..;;;;;;..
         # ..;;''  ;;  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 = key(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[key(y + i * 2, x)] &&
                          !$reserved[key(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[key(y0 + i * dy + j * 2, x0 + i * 8)] = 1
         $reserved[key(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[key(y, x)] && !$reserved[key(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|
      # Knock down walls only if they allows current reachable
      # region to be expanded.
      k1 = key(y1, x1)
      k2 = key(y2, x2)
      if !$reserved[k1] && !$reserved[k2] &&
         canonical_parent(k1) != canonical_parent(k2)
         merge_cells(y1, x1, y2, x2)
      end
   }
end

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

   top_left = key(1, 4)
   bottom_right = key($height - 1, $width - 4)
   walls.each{|y1, x1, y2, x2|
      if canonical_parent(top_left) == canonical_parent(bottom_right)
         return
      end
      k1 = key(y1, x1)
      k2 = key(y2, x2)
      if canonical_parent(k1) != canonical_parent(k2)
         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}