From: atgeirr <atgeirr@...>
Date: 2005-05-26T23:35:20+09:00
Subject: Re: Tiling Turmoil (#33)

I am a bit late with my solution, but it's my first Ruby Quiz, and my
largest ruby program so far, so I'll send it in anyway... I didn't know
the problem, but found the same solution everybody else did. I have not
used recursion in the solution, in order to not compute the low-level
solutions over and over again. Instead I compute the 'overlays'
(partial solutions) from the smallest to the largest, then I rotate
them properly, and finally put them all on the board.

I have some requests, if anyone would be so kind as to take a look:

1) Style in general. What have I done that is 'unrubyish'? Are there
more elegant ways of doing things?

2) If a want a 'mathematical' vector, that treats + as addition and not
as concatenation, what can I do? I added the method 'add!' to class
Array for this, but it would be nice to know if there is a standard
facility for this.

3) I gave my Board class a copy method. Is there a better way to copy
an array than concatenating the source to an empty ([]) target? I found
no 'copy' method in the docs.

The code:
===============================================


class Array
  def add!(other)
    if other.length != length
      somethingswrong
    end
    each_index { |i| self[i] += other[i] }
    self
  end
end


# Represents the board. Handles rotation and board manipulation.
class Board

  attr_reader :n, :squares
  attr_writer :n, :squares

  # The board size will be 2**r by 2**r.
  def initialize(r = 0, val = 0)
    @n = 2**r
    @squares = Array.new(@n**2, val)
  end

  # Make a deep copy
  def copy
    retval = Board.new
    retval.n = @n
    retval.squares = []
    retval.squares.concat(@squares)
    retval
  end

  # Prettyprinting the board
  def to_s
    output = "Board is #{@n} by #{@n}.\n"
    @n.times do |i|
      @squares[@n*i...@n*(i+1)].each do |s|
        output += sprintf("%5d ", s)
      end
      output += "\n"
    end
    output += "\n"
  end

  # Rotate the board by 90 degrees, CCW.
  def rotate!
    rotated = Array.new(@n**2, 0)
    @n.times do |i|
      @n.times do |j|
        rotated[@n*i + j] = @squares[@n*j + (@n-i-1)]
      end
    end
    @squares = rotated
    self
  end

  def increment!(val = 1)
    @squares.each_index { |i| @squares[i] += val if @squares[i] > 0 }
    self
  end

  # Set a square to a particular value
  def set!(row, col, val)
    @squares[@n*row + col] = val
    self
  end

  # Overlay a sub-board over this one, at a specific location.
  # The (row, col) coordinates should be the upper left corner
  # of the area to overlay. Overlaying means we simply add the
  # values of the inserted board to the current board values.
  # We do not check that the insertion is valid wrt size of
  # sub-board, position, etc.! So be careful...
  def insert!(row, col, subboard)
    sn = subboard.n
    row.upto(row + sn - 1) do |r|
      rowtoadd = subboard.squares[(r-row)*sn...(r-row+1)*sn]
      target = @squares[(r*@n + col)...(r*@n + col + sn)]
#       puts "----" + target.to_s
#       puts "++++" + rowtoadd.to_s
      target.add!(rowtoadd)
      @squares[(r*@n + col)...(r*@n + col + sn)] = target
    end
    self
  end

end



class TilingPuzzle

  def initialize(r)
    @board = Board.new(r)
    @r = r
  end

  def to_s
    @board.to_s
  end

  def solve!(row, col)
    # Make some overlays of increasing size
    overlays = []
    # Initialize the first overlays
    overlays[0] = Board.new(0, 0)
    overlays[1] = Board.new(1, 1)
    overlays[1].set!(0, 0, 0)
    # Now build every successive overlay
    2.upto(@r) do |i|
      # Every overlay consists of four copies of the previous one,
      # incremented by the number of L-tiles in it every time.
      overlays[i] = Board.new(i)
      o = overlays[i-1].copy
      inc = 4**(i-2)
      pl = 2**(i-1)
      o.increment!(inc)
      overlays[i].insert!(pl/2, pl/2, o)
      o.increment!(inc)
      overlays[i].insert!(pl, pl, o)
      o.rotate!.increment!(inc)
      overlays[i].insert!(0, pl, o)
      o.rotate!.rotate!.increment!(inc)
      overlays[i].insert!(pl, 0, o)
    end

    # Now we can simply tile every overlay around the empty spot,
    # as long as we rotate them properly. Let's first compute the
number
    # of rotations necessary
    rots = [0]
    @r.downto(1) do |i|
      # Can I make this more elegant?
      if (row >= 2**(i-1)) && (col < 2**(i-1))
        rots[i] = 1;
      elsif (row >= 2**(i-1)) && (col >= 2**(i-1))
        rots[i] = 2;
      elsif (row < 2**(i-1)) && (col >= 2**(i-1))
        rots[i] = 3
      else
        rots[i] = 0
      end
#      puts "row = #{row}, col = #{col}"
      row = row % (2**(i-1))
      col = col % (2**(i-1))
    end

    # Now, let's put everything in place!
    offsetrow, offsetcol = 0, 0
    @r.downto(1) do |i|
      (rots[i]).times { overlays[i].rotate! }
      @board.insert!(offsetrow, offsetcol, overlays[i])
      offsetrow += 2**(i-1) if [1, 2].include?(rots[i])
      offsetcol += 2**(i-1) if [2, 3].include?(rots[i])
    end
    self
  end

end


size = 4
row = rand(2**size)
col = rand(2**size)
puts TilingPuzzle.new(size).solve!(row, col)

====================================================

Atgeirr Fl� Rasmussen