class Maze
  DIRECTIONS = [ [1, 0], [-1, 0], [0, 1], [0, -1] ]

  def initialize(width, height)
    @width   = width
    @height  = height
    @start_x = rand(width)
    @start_y = 0
    @end_x   = rand(width)
    @end_y   = height - 1

    
    
    
    
    @vertical_walls   = Array.new(width) { Array.new(height, true) }
    @horizontal_walls = Array.new(width) { Array.new(height, true) }
    
    @path             = Array.new(width) { Array.new(height) }

    
    @horizontal_walls[@end_x][@end_y] = false

    
    generate
  end

  
  def print
    
    puts @width.times.inject() {|str, x| str << (x == @start_x? : )}

    
    @height.times do |y|
      line = @width.times.inject() do |str, x|
        str << (@path[x][y]? : ) << (@vertical_walls[x][y]? : )
      end
      puts line

      puts @width.times.inject() {|str, x| str << (@horizontal_walls[x][y]? : )}
    end
  end

  private

  
  def reset_visiting_state
    @visited = Array.new(@width) { Array.new(@height) }
  end

  
  def move_valid?(x, y)
    (0...@width).cover?(x) && (0...@height).cover?(y) &&!@visited[x][y]
  end

  
  def generate
    reset_visiting_state
    generate_visit_cell(@start_x, @start_y)
  end

  
  def generate_visit_cell(x, y)
    
    @visited[x][y] = true

    
    
    coordinates = DIRECTIONS.shuffle.map { |dx, dy| [x + dx, y + dy] }

    for new_x, new_y in coordinates
      next unless move_valid?(new_x, new_y)

      
      
      connect_cells(x, y, new_x, new_y)
      generate_visit_cell(new_x, new_y)
    end
  end

  
  def connect_cells(x1, y1, x2, y2)
    if x1 == x2
      
      @horizontal_walls[x1][ [y1, y2].min ] = false
    else
      
      @vertical_walls[ [x1, x2].min ][y1] = false
    end
  end
end


maze = Maze.new 20, 10
maze.print