From: David Tran <email55555@...>
Date: 2005-05-26T06:20:30+09:00
Subject: Re: [SOLUTION] Ruby Quiz #33 Tiling Turmoil

=begin

  * Program : Solution for Ruby Quiz #33 Tiling Turmoil
  * Author  : David Tran
  * Date    : 2005-05-25
  * Version : Fast, less iteration version

  Here is my other solution.
  
  Below note is only apply for n >= 3 ( start from 8x8 )
  for n =1 (2x2) and n=2 (4x4) the solution is unique.
  
  It still has a special case need to solve. 
  (Do not want google to find solution for the special case)

  The small rectangle form by tromino is 2x3 (or 3x2) note as R(2,3).
  Below, it discuss only for 2x3 case. (for 3x2, just rotate it)
  
  This means all area of 2nx3m can tile by the small rectangle of 2 tromino.

  So, for 2^n x 2^n cases:
  1. If the missing cell is in the central square of 2^(n-1) x 2^(n-1)
     (see graph below, form by 6 + 7 + 10 + 11)
     then the around central square could tile by R(2,3).

     +----+----+----+----+  The big square is 2^n x 2^n
     | 1  |  2 |  3 | 4  |  Each small square is 2^(n-2) x 2^(n-2)
     |    |    |    |    |
     +----+----+----+----+
     | 5  |  6 | 7  | 8  |
     |    |   x|    |    |
     +----+----+----+----+
     | 9  | 10 | 11 | 12 |
     |    |    |    |    |
     +----+----+----+----+
     | 13 | 14 | 15 | 16 |
     |    |    |    |    |
     +----+----+----+----+
      
     The around central can form by 4 rectangles and can be tile by R(2,3).
     * first-rectangle: 1 + 2 + 3
       start point (0, 0), width = 3 x 2^(n-2), height = 2^(n-2)
       As you can see width is divisible by 3 and height is divisible by 2.
     * second-rectangle: 4 + 8 + 12
     * third-rectangle: 14 + 15 + 16
     * fourth-rectangle: 5 + 9 + 13

     And this reduce the problem downto the central 2^(n-1)x2^(n-1) to solve.
     
  2. If the missing cell is in one of the corner 2^(n-2)x2^(n-2) then
     the problem is downto solve that corner; out of the corner could tile
     by R(2,3). For example: if the missing cell is on top-left corner.
     Out of that corner is:
     * first-rectangle : form by 2 + 3 + 4
       width = 3 x 2^(n-2), hieght = 2^(n-2), can be tile by R(3,2)
     * second-rectangle : form by 5+6+7+8+ ... + 16
       width = 2^n, height = 3 x 2^(n-2), can be tile by R(2,3)
     
     +----+----+----+----+
     | 1  |  2 |  3 | 4  |
     |  x |    |    |    |
     +----+----+----+----+
     | 5  |  6 |  7 | 8  |
     |    |    |    |    |
     +----+----+----+----+
     | 9  | 10 | 11 | 12 |
     |    |    |    |    |
     +----+----+----+----+
     | 13 | 14 | 15 | 16 |
     |    |    |    |    |
     +----+----+----+----+
     
  3. We already see the missing cell on center (6+7+10+11) case.
     Also the missing cell on corner (1, 4, 13 or 16) case.
     Now, let's see if missing cell on the center border square 
     of 2^(n-2)x2^(n-2) ( For example form by half #2 and half #3 )

     +----+----+----+----+
     | 1  | 2! | ! 3| 4  |
     |    |  !x| !  |    |
     +----+----+----+----+
     |__5_|  6 |  7 | 8  |
     |    |    |    |    |
     +----+----+----+----+
     |__ _| 10 | 11 | 12 |
     |  9 |    |    |    |
     +----+----+----+----+
     | 13 | 14 | 15 | 16 |
     |    |    |    |    |
     +----+----+----+----+

     The problem reduce to solve that 2^(n-2)x2^(n-2) square only.
     Outside of that square, it could tile by R(2,3).
     * first-rectangle : 5 + 6 + 7 + ... + 16 could tile by R(2,3)
       this rectangle already discussed on 2. (see above corner case)
     * second-rectangle : 1 + half of 2
       width = 2^(n-2) + (2^(n-2) / 2) = 3 x 2^(n-3) 
       height = 2^(n-2)
       (width is divisible by 3, height is divisible by 2)
     * third-rectangle : half 3 + 4 
       could tile by R(2,3) too, same logic as second rectangle.
       
  4. The rest of missing cell possible is "special" case,
     For example the missing cell on half left of 2, or half right of 3,
     or half top of 5, or half bottom of 9 ... etc
     By using paper and pencil, I could solve it easily (for 8x8, 16x16), 
     it is try to place a tromino with one case in central square (6+7+10+11),
     and the problem downto solve the central square; and the around the 
     center square is tile by R(2,3).
     Unfortunately, I have not yet come out with a generic logic for it.
     For those special case, I will just back to normal solve-by_inductive
     logic for first iteration.


   Note the code is a little mess, maybe define a rotateFloor method
   to help clean up...

=end

class Floor 
    
  attr_accessor :width, :height
  
  def initialize(width, height=width, data=nil)
    @width = width
    @height = height
    @data = data ? data : Array.new(width) { Array.new(height) }
  end

  def [](x, y)
    @data[x][y]
  end

  def []=(x, y, value)
    @data[x][y] = value
  end

  # Maximum tiles needs to cover floor without excess floor
  def number_tiles
    width * height / 3
  end
  
  def include?(x, y)
    0 <= x && x < width && 0 <= y && y < height
  end
  
  def tile(missing_x, missing_y, start_tile_number = 1)    
    n = @width
    nb = start_tile_number
    if n <= 4
      tile_by_inductive(missing_x, missing_y, start_tile_number)
      return
    end

    squares = {
      ##### central square case #####
      [n/4, n/4, n/2] => [[0, 0, 3*n/4, n/4], [3*n/4, 0, n/4, 3*n/4],
                          [0, n/4, n/4, 3*n/4],[n/4, 3*n/4, 3*n/4, n/4] ],
                          
      ##### corner square case  #####
      [0, 0, n/4]         => [ [n/4, 0, 3*n/4, n/4], [0, n/4, n, 3*n/4] ],
      [3*n/4, 0, n/4]     => [ [0, 0, 3*n/4, n/4], [0, n/4, n, 3*n/4] ],
      [0, 3*n/4, n/4]     => [ [0, 0, n, 3*n/4], [n/4, 3*n/4, 3*n/4, n/4] ],
      [3*n/4, 3*n/4, n/4] => [ [0, 0, n, 3*n/4], [0, 3*n/4, 3*n/4, n/4] ],
      
      ##### middle border square case  #####
      [3*n/8, 0, n/4] => [[0,0,3*n/8,n/4], [5*n/8,0, 3*n/8,n/4], [0,
n/4, n, 3*n/4]],
      [0, 3*n/8, n/4] => [[0,0,n/4,3*n/8], [0,5*n/8, n/4, 3*n/8],
[n/4, 0, 3*n/4,n]],
      [3*n/8, 3*n/4, n/4]
=>[[0,3*n/4,3*n/8,n/4],[5*n/8,3*n/4,3*n/8,n/4],[0,0,n,3*n/4]],
      [3*n/4, 3*n/8, n/4] =>[[3*n/4,0,
n/4,3*n/8],[3*n/4,5*n/8,n/4,3*n/8],[0,0,3*n/4,n]]
    }

    squares.each do |(from_x, from_y, size), rectangles|
      x = missing_x - from_x
      y = missing_y - from_y
      floor = subFloor(from_x, from_y, size)
      if floor.include?(x, y)
        rectangles.each do |(from_x, from_y, width, height)|
          rectangle_floor = subFloor(from_x, from_y, width, height)
          rectangle_floor.tile_without_missing(nb)
          nb += rectangle_floor.number_tiles
        end
        floor.tile(x, y, nb)
        return
      end      
    end

    ##### at this point, the missing cell is on the "special cases" #####
    tile_by_inductive(missing_x, missing_y, start_tile_number)
  end
  
  protected
  
  def tile_by_inductive(missing_x, missing_y, start_tile_number)
    half_width = width / 2
    half_height = height / 2
    shifts = [ [0, 0], [half_width,0], 
               [0, half_height], [half_width, half_height] ]
               
    missings = [ [half_width - 1, half_height - 1], [0, half_height - 1],
                 [half_width - 1, 0], [0, 0] ]

    floors = shifts.inject([]) do |floors, (from_x, from_y)|
      floors << subFloor(from_x, from_y, half_width, half_height)
    end
    
    nb = start_tile_number + 1
    shifts.each_with_index do |(from_x, from_y), i|
      x = missing_x - from_x
      y = missing_y - from_y
      if !floors[i].include?(x, y)
        x = missings[i][0]
        y = missings[i][1]
        floors[i][x,y] = start_tile_number
      end
      if width > 2 && height > 2
        floors[i].tile(x, y, nb) # call normal tile (not tile_by_inductive) !
        nb += floors[i].number_tiles
      end
    end
  end

  def tile_without_missing(start_tile_number)
    nb = start_tile_number - 1
    if (width % 2 == 0 && height % 3 == 0)
      (0...width).step(2) do |x|
        (0...height).step(3) do |y|
          self[x,y] = self[x+1,y] = self[x+1,y+1] = (nb += 1)
          self[x,y+1] = self[x,y+2] = self[x+1,y+2] = (nb += 1)
        end
      end
    elsif (width % 3 == 0 && height % 2 == 0)
      (0...width).step(3) do |x|
        (0...height).step(2) do |y|
          self[x,y] = self[x,y+1] = self[x+1,y] = (nb += 1)
          self[x+1,y+1] = self[x+2,y] = self[x+2,y+1] = (nb += 1)
        end
      end        
    else
      fail "Without missing cell, this can only tile a " +
           "floor area of 2nx3m or 3nx2m rectangle."
    end    
  end
  
  private 

  def subFloor(from_x, from_y, width, height=width)
    floor = Floor.new(width, height, @data)
    class << floor
      attr_accessor :from_x, :from_y
      alias :old_get :[]
      alias :old_set :[]=
      
      def [](x, y)
        old_get(@from_x + x, from_y + y)
      end
      
      def []=(x, y, value)
        old_set(@from_x + x, from_y + y, value)
      end
    end
    floor.from_x = from_x + (respond_to?(:from_x) ? self.from_x : 0)
    floor.from_y = from_y + (respond_to?(:from_y) ? self.from_y : 0)
    floor
  end
  
end

(puts "Usage: #$0 n"; exit) if ARGV.size <= 0 || ARGV[0].to_i <= 0
n = 2 ** ARGV[0].to_i
floor = Floor.new(n)
missing_x = rand(n)
missing_y = rand(n)
floor[missing_x, missing_y] = 'X'
floor.tile(missing_x, missing_y)
format = "%#{(n*n/3).to_s.size+1}s"
(0...n).each {|y| (0...n).each {|x| print(format % floor[x,y]) }; puts }


=begin
# Simple unit test
n = 16
(0...n).each do |x|
  (0...n).each do |y|
    floor = Floor.new(n, n)
    floor[x,y] = 0
    floor.tile(x, y)
    a = Array.new(n*n/3+1, 0)
    (0...n).each { |i| (0...n).each { |j| a[floor[i,j]] += 1 } }
    a[0] += 2
    a.each { |e| fail "FAIL: missing at #{x}, #{y}" if e != 3 }
    puts "Missing at #{x}, #{y} => OK"
  end
end
=end