[QUIZ] Tiling Turmoil (#33)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
by Greg Brown
This weeks quiz is based off of a mathematical proof we were taught in my
discrete mathematics class a few weeks ago. Though I can already hear some of
you running for the hills at the mention of the four letter word that is math, I
can assure you that this is more of a thinking problem than it is number
crunching. The basic idea is pretty simple.
You're going to tile L-trominos on a 2**n by 2**n board that is missing a single
square. What's an L-tromino? It's simply a 2 by 2 square with a corner missing
that looks like an L.
For further clarification, this is what they look like:
#
# #
Well, I guess it's time to stop being vague and give you the problem definition.
For any 2**n by 2**n board with a single square missing in a random location,
you must write a program that will tile L-trominos in such a way that the grid
is completely filled in.
Your program should take the value for n as the input, and somehow display the
board with the trominos properly laid out as the output. It should place the
missing square at random each time the board is generated. (Otherwise this would
be too easy!)
For example, the empty board of n = 2 would be something like this:
_ _ _ _
_ _ X _
_ _ _ _
_ _ _ _
The solution for that might look like:
1 1 2 2
1 5 X 2
3 5 5 4
3 3 4 4
As you can see, all squares are completely filled with the exception of the
empty square which was randomly placed.
It may look simple on a 4 by 4 board, but once you get up to a 128 by 128 or
even 4096 by 4096, it becomes more and more obvious that guess and check is just
not going to work.
The level of difficulty of this problem depends entirely on how much you already
know about it. If you want an easy ride, look for the proof and just implement
it.
If you want more of a challenge, avoid Googling the topic and try to find clever
ways to actually show how your program solves the problem.
Hope you have fun with this quiz, and if you write a really good one, you can
help me tile my bathroom floor next week as a prize. :)
Jason Bailey
ie 4 by 4096 ??
> -------- Original Message --------
> Subject: [QUIZ] Tiling Turmoil (#33)
> From: Ruby Quiz <ja...@grayproductions.net>
> Date: Fri, May 20, 2005 8:37 am
> To: ruby...@ruby-lang.org (ruby-talk ML)
>
---snip---
Mike
>
> ie 4 by 4096 ??
>
"You're going to tile L-trominos on a 2**n by 2**n board that is missing a
single square. What's an L-tromino? It's simply a 2 by 2 square with a
corner missing that looks like an L."
Since "n" will be the same, the sides will always have the same length - so
you only have to worry about squares.
-M
Brian Schröder
> Is there an assumption that this is a square or can it be a rectangle?
>
> ie 4 by 4096 ??
>
best regards,
Brian
James Edward Gray II
> Is there an assumption that this is a square or can it be a rectangle?
>
> ie 4 by 4096 ??
From the quiz:
On May 20, 2005, at 7:37 AM, Ruby Quiz wrote:
> You're going to tile L-trominos on a 2**n by 2**n board that is
> missing a single
Or in other words, it's always square. :)
James Edward Gray II
Adriano Ferreira
> Is there an assumption that this is a square or can it be a rectangle?
>
> ie 4 by 4096 ??
The man said "on a 2**n by 2**n board". This assumption guarantees the
board has at least a number of squares (2**(2n)-1) which is multiple
of 3 (proof left to the interested reader). Probably it also
guarantees that the L-trominos (with 3 squares) can be fitted into the
board. The situation is different with rectangles: for example, a 4 by
8 board has 31 squares which are not divisible by 3. So you can't fill
it with L-trominos without leaving a blank square.
Regards.
Adriano.
Jason Bailey
;)
> -------- Original Message --------
> Subject: Re: [QUIZ] Tiling Turmoil (#33)
> From: James Edward Gray II <ja...@grayproductions.net>
> Date: Fri, May 20, 2005 9:11 am
> To: ruby...@ruby-lang.org (ruby-talk ML)
>
> On May 20, 2005, at 7:55 AM, Jason Bailey wrote:
>
> > Is there an assumption that this is a square or can it be a rectangle?
> >
> > ie 4 by 4096 ??
>
Michael Ulm
OTOH, the "canonical" solution of this problem should (with minor
modification) work for a 2**n by 2**m board whenever n + m is even
(i.e. whenever the number of empty squares is divisible by 3).
Michael
--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: micha...@isis-papyrus.com
Visit our Website: www.isis-papyrus.com
Kero
> you must write a program that will tile L-trominos in such a way that the grid
> is completely filled in.
>
> Your program should take the value for n as the input, and somehow display the
> board with the trominos properly laid out as the output. It should place the
> missing square at random each time the board is generated. (Otherwise this would
> be too easy!)
> The level of difficulty of this problem depends entirely on how much you already
> know about it. If you want an easy ride, look for the proof and just implement
> it.
Yeah. I knew the problem, I didn't need google.
So I decided to
- generate* all (sub)tiles and
- have only that part of the board in memory that needs to be printed
(quadtree into details for current line, by using the Ruby stack;
If anyone knows how to keep less administration, let me know :)
> Hope you have fun with this quiz, and if you write a really good one, you can
> help me tile my bathroom floor next week as a prize. :)
Not a chance :)
Besides I fear my code is more cryptic than it could be.
Bye,
Kero.
+--- Kero ------------------------- kero@chello@nl ---+
| all the meaningless and empty words I spoke |
| Promises -- The Cranberries |
+--- M38c --- http://members.chello.nl/k.vangelder ---+
# 1) There is no regular coverage of trominos over a 2**n square board (3 does
# not divide 2**n)
# 2) however, tromino's can cover 3/4 of such a board. the factor three has
# been introduced. Which three quarters? Let me show you:
#
# +---+ Which in itself is a tromino-shaped area, but twice as big.
# | | You can't miss the factor 2 which also appears in 2**n, so
# | +-+ this basically gives the algorithm for the solution away.
# | | |
# +-+ +-+-+ 3) We shall display the board. I'm going to try to use the
# | | | | recursion efficiently and not keep the entire board in
# | +---+ | memory.
# | | |
# +---+---+ 4) Line-by-line we see one or two squares of a tromino that we
# must know. Three squares, four orientations, twelve ids.
# F T L J, clockwise numbered :F1 :F2 :F3 etc
# We would have, from the above shape
# :L => [
# [ :F2, :F3, 0, 0 ],
# [ :F1, :L3, 0, 0 ],
# [ :L3, :L2, :L1, :J1 ],
# [ :L2, :L1, :J3, :J2 ]
# ],
# but that's not recursive, so we get (clockwise):
# :L1 => [:L1, :J1, :J2, :J3],
# :L2 => [:L3, :L2, :L1, :L2],
# :L3 => [:F2, :F3, :L3, :F1],
# We're lazy (and we hate typos) so we'll generate this
class Array
# shift element and append it again, name from CPU registers
def rotate!()
push(shift)
end
# substitute first occurrence of +orig+
def sub(orig, replace)
result = dup
result[index(orig)] = replace
result
end
end
Trominos = [ :J0, :T0, :F0, :L0 ] # rotating J counterclockwise gives T, F, L
Sub = {}
# Set tromino in 2x2 square, clockwise, using :X0 as 'empty'
# With only these set, the script already works for n==1 :)
a = (0..3).to_a # clockwise numbering of :J, 0 being 'empty' (excluded square)
Trominos.each { |sym|
str = (0..3).collect { |i| ":#{sym}#{a[i]}".sub(/0/, "") }.join(", ")
Sub[sym] = eval("[#{str}]")
a.rotate! # rotate counterclockwise
}
# For all 12 possibilities, set subsquare, clockwise
(0..3).each { |i|
counter = Trominos[(i+1) % 4]
sym = Trominos[i]
clockwise = Trominos[(i+3) % 4]
first = eval(":#{sym}".sub(/0/, "1"))
Sub[first] = Sub[counter].sub(counter, first)
second = eval(":#{sym}".sub(/0/, "2"))
Sub[second] = Sub[sym].sub(sym, second)
third = eval(":#{sym}".sub(/0/, "3"))
Sub[third] = Sub[clockwise].sub(clockwise, third)
}
def base(n, x, y)
case [x>>(n-1), y>>(n-1)]
when [0, 0]; Sub[:J0]
when [1, 0]; Sub[:L0]
when [1, 1]; Sub[:F0]
when [0, 1]; Sub[:T0]
end
end
def solve(n, x, y, *fields)
if n == 1
puts fields.join(" ").sub(/.0/, " ")
else
n = n - 1
nn = 2 ** n
x, y = x % nn, y % nn
subs = fields.collect { |f|
# subsquares can be looked up, for :X0 we need proper tromino
Trominos.include?(f) ? base(n, x, y) : Sub[f]
}
solve(n, x, y, *subs.collect { |s0, s1, s2, s3| [s0, s1] }.flatten)
solve(n, x, y, *subs.collect { |s0, s1, s2, s3| [s3, s2] }.flatten)
end
end
if ARGV[0].to_i == 0
STDERR.puts "Usage: #{$0} n # where the field is 2**n square"
else
n = ARGV[0].to_i
size = 2 ** n
x, y = rand(size), rand(size)
puts "Hole at (#{x}, #{y}) # note that (0, 0) is top left"
b = base(n, x, y)
solve(n, x, y, *b.values_at(0, 1))
solve(n, x, y, *b.values_at(3, 2))
end
Dominik Bathon
here is my solution. I didn't know this problem and I didn't google ;-)
It works recursive:
For n=1 it is easy: just place one tromino, so that the empty square is
empty.
For bigger n, divide the problem into four n-1 sub problems. For example:
________
________
_____x__
________
________
________
________
________
This can be solved by solving the following problems:
____
____
____
___o
____
____
_x__
____
___o
____
____
____
o___
____
____
____
Putting their solutions together we get:
11112222
11112222
11112x22
111o2222
333oo444
33334444
33334444
33334444
So the last missing tromino can easily be placed.
The program accepts one optional argument (n), it defaults to 3.
It outputs solutions for all possible empty squares.
Dominik
#######################################################
# A simple 2D array, the width and height are immutable once it is created.
# #to_s accepts an optional block that can format the elements.
class Array2D
attr_reader :w, :h
def initialize(w, h, defel=nil)
@w, @h=w, h
@array=Array.new(w*h, defel)
end
def [](x, y)
@array[(y%h)*w+(x%w)]
end
def []=(x, y, v)
@array[(y%h)*w+(x%w)]=v
end
def to_s
(0...h).collect { |y|
(0...w).collect { |x|
v=self[x, y]
block_given? ? yield(v) : v
}.join " "
}.join "\n"
end
end
class TrominoTiler
def initialize(n)
n=[1, n].max
# initialize the working array
@a=Array2D.new(1 << n, 1 << n)
end
def tile_with_empty(x, y)
@tilenum=0 # counter
tile_recursive(0, @a.w, 0, @a.h, x, y)
@a
end
private
# tiles the area of @a determined by xb,xe and yb,ye (b is begin,
e is
# end, so xb,xe is like the range xb...xe) with trominos, leaving
# empty_x,empty_y empty
def tile_recursive(xb, xe, yb, ye, empty_x, empty_y)
half=(xe-xb)/2
if half==1
# easy, just one tromino
@tilenum+=1
# set all 4 squares, empty is fixed below
@a[xb , yb ]=@tilenum
@a[xb+1, yb ]=@tilenum
@a[xb , yb+1]=@tilenum
@a[xb+1, yb+1]=@tilenum
else
# tile recursive
mytile=(@tilenum+=1)
# where to split the ranges
xh, yh=xb+half, yb+half
[ # the 4 sub parts:
[xb, xh, yb, yh, xh-1, yh-1],
[xh, xe, yb, yh, xh , yh-1],
[xb, xh, yh, ye, xh-1, yh ],
[xh, xe, yh, ye, xh , yh ]
].each { |args|
# if empty_x,empty_y is in this part, we
have
# to adjust the last two arguments
if (args[0]...args[1]).member?(empty_x) &&
(args[2]...args[3]).member?(empty_y)
args[4]=empty_x
args[5]=empty_y
end
tile_recursive(*args)
@a[args[4], args[5]]=mytile
}
end
# fix empty square
@a[empty_x, empty_y]=nil
end
end
if $0 == __FILE__
n=(ARGV[0] || 3).to_i
d=1 << n
maxw=((d*d-1)/3).to_s.size
tiler=TrominoTiler.new(n)
# show solutions for all possible empty squares
d.times { |y|
d.times { |x|
puts tiler.tile_with_empty(x, y).to_s { |v|
v.to_s.rjust(maxw)
}, ""
}
}
end
Matthew Westcott
completed without googling.
The distinguishing feature here compared to the other solutions posted
so far, is that I'm doing the recursion by creating a tree of Square
objects beforehand, in an effort to make it more OOPish.
#!/usr/bin/ruby
# Proof by induction
# Base case: a 2x2 board with one missing square.
# Trivially, the remaining 3 squares form an L-tromino.
# Step:
# Assume that any (2**(n-1) x 2**(n-1)) board with a square missing
can be solved.
# A (2**n x 2**n) board can be divided into four (2**(n-1) x 2**(n-1))
quadrants.
# One of these quadrants contains the missing square.
# An L-tromino can be placed in the centre of the board, rotated such
that it occupies
# one square of each of the other three quadrants.
# The result of this is four quadrants, each of which has one square
missing.
# By our original assumption, each of these can be solved.
# Note that at each stage of subdivision, each quadrant contains
precisely one
# square that is either 1) the missing square, or 2) occupied by an
L-tromino
# that overlaps onto other quadrants.
class Square
# Represents a square portion of the board.
attr_reader :central_corner_x, :central_corner_y
def initialize(size, left = 0, top = 0, central_corner_x = nil,
central_corner_y = nil)
@size = size # Size of this square
@left = left # X coordinate of leftmost point
@top = top # Y coordinate of topmost point
@central_corner_x = central_corner_x
@central_corner_y = central_corner_y
# Coordinates of the corner closest to the middle
# of the parent square (or nil if the square has no parent)
if size > 1
# divide into quadrants
quad_size = @size / 2
@quadrants = [
Square.new(quad_size, @left, @top, @left + quad_size - 1, @top +
quad_size - 1),
Square.new(quad_size, @left + quad_size, @top, @left + quad_size,
@top + quad_size - 1),
Square.new(quad_size, @left, @top + quad_size, @left + quad_size -
1, @top + quad_size),
Square.new(quad_size, @left + quad_size, @top + quad_size, @left +
quad_size, @top + quad_size)
]
end
end
def contains?(x, y)
# Determine whether this square contains the given point
(@left...(@left+@size)) === x && (@top...(@top+@size)) === y
end
def solve(board, missing_x, missing_y, count = 1)
# board = a board which is to have the portion indicated by this
Square object filled with L-trominos
# missing_x, missing_y - the coordinates of a square not to be filled
# count = the current L-tromino number
# Returns the next available unused L-tromino number
if @size == 1
board[@top][@left] = count unless contains?(missing_x, missing_y)
count
else
next_count = count + 1
@quadrants.each { |quadrant|
if quadrant.contains?(missing_x, missing_y)
# a square in this quadrant is already missing - can solve the
quadrant straight off
next_count = quadrant.solve(board, missing_x, missing_y, next_count)
else
# artificially 'create' a missing square before solving the quadrant
board[quadrant.central_corner_y][quadrant.central_corner_x] = count
next_count = quadrant.solve(board, quadrant.central_corner_x,
quadrant.central_corner_y, next_count)
end
}
next_count
end
end
end
puts "Board magnitude? (1 = 2x2, 2 = 4x4, 3 = 8x8, 4 = 16x16...)"
n = gets.to_i
size = 2**n
digits = (n*2) / 5 + 1 # how many base-32 digits we need to give each
L-tromino its own ID
board = (0...size).collect{ (0...size).collect { 0 } }
Square.new(size).solve(board, rand(size), rand(size))
board.each do |row|
puts row.map{ |i| i.to_s(32).rjust(digits) }.join(' ')
end
Jannis Harder
fill an
16x1 square with pencil and paper.
It use the fact that 4 Ls can create a new L with the size doubled:
1 1
1 4
2 4 4 3
2 2 3 3
I use this to create Ls in any n**2 size.
Example of the algorithm:
Board:
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . X . . . .
. . . . . . .
. . . . . . .
The first step is to apply a 2x2 grid to the board:
.|. .|. .|. .
.|. .|. .|. .
".|.".|.".|.".
.|. .|. .|. .
".|.".|.".|.".
.|. X|. .|. .
".|.".|.".|.".
.|. .|. .|. .
Now if fill the square with the X:
.|. .|. .|. .
.|. .|. .|. .
".|.".|.".|.".
.|. .|. .|. .
".|1"1|.".|.".
.|1 X|. .|. .
".|.".|.".|.".
.|. .|. .|. .
I repeat the steps with an 4x4 and 8x8 grid:
4x4:
. . .|. . . .
. . .|. . . .
. . .|. . . .
. . .|. . . .
2"2 1"1|.". .".
2 5 1 X|. . . .
3 5 5 4|. . . .
3 3 4 4|. . . .
8x8:
7 7 8 8 a a b b
7 9 9 8 a d d b
6 9 i i j j d c
6 6 i l l j c c
2 2 1 1 l k e e
2 5 1 X k k h e
3 5 5 4 g h h f
3 3 4 4 g g f f
My solution does the same thing but instead of applying a grid to the
board it
uses some bit shifting and multiplication. The Ls are created using a
recursive
method.
It generates HTML output (tested with Safari and Firefox)
--
Jannis Harder
Jim Freeze
> Here's my solution, and without googling!.
>
> I'm new in Ruby, and I have a little doubt in my solution. The to_s
> method is too slow in the way I implemented it, Is there any better
> approach?.
>
Yes. There are a couple of things you can do.
> def to_s
> cad = ''
> @tiles.each_index { |i|
># cad += @tiles[i] + ' '
cad << @tiles[i] << ' '
># cad += "\n" if i%@w==@w-1
cad << "\n" if i%@w==@w-1
> }
> return cad
> end
The other thing you can do (with some extra modification) is start with:
cad = []
and when you are done, do
cad.join("\n")
--
Jim Freeze
Ruby: I can explain it to ya but I can't understand it fer ya.
James Edward Gray II
> Here's my solution, and without googling!.
Nice job.
> I'm new in Ruby,
Welcome!
> and I have a little doubt in my solution. The to_s method is too
> slow in the way I implemented it, Is there any better approach?.
[snip]
> def to_s
> cad = ''
> @tiles.each_index { |i|
> cad += @tiles[i] + ' '
> cad += "\n" if i%@w==@w-1
> }
> return cad
> end
I haven't tested or timed it, but one way might be:
def to_s
@tiles.join(" ").sub!(/((?:[0-9X]+\s+){#{@w}})/, "\\1\n") + "\n"
end
Hope that helps.
James Edward Gray II
Bill Atkins
board. Most of the work is done in the recursive #do_tile function.
The algorithm works by breaking down a board into four quadrants and
determining which of these quadrants has a non-empty square. It then
places a tile so that the tile will bracket the edge of the quadrant
with the non-empty square. It then recursively tiles these quadrants.
Each of these quadrants will have an empty space because the tile
placed in the last step has one square in each of the three quadrants
that didn't already have a non-empty square.
I didn't google, but I did have this problem in my Discrete Structures
class earlier in the year. :P
class Square
def initialize n
raise "n must be > 0" unless n > 0
# create a 2**n x 2**n board filled with dashes
@size = 2 ** n
@board = Array.new @size do
Array.new @size do
"-"
end
end
# a randomly-placed X indicates the hole
@board[ rand(@size) ][ rand(@size) ] = "X"
@cur_tile = 1
end
def to_s
@board.collect { |row| row.collect { |item|
"%#{Math.log(@size).to_i}s" % [item] }.join " " }.join "\n"
end
def tile!
# (0, 0, @size) means the @size x @size square extending to the right and
# downward from (0, 0)
do_tile 0, 0, @size
end
def do_tile row, col, size
# base case
if size < 2
return
end
sub_size = size / 2
# define each quadrant
top_left = [row, col, sub_size]
top_right = [row, col + sub_size, sub_size]
bottom_left = [row + sub_size, col, sub_size]
bottom_right = [row + sub_size, col + sub_size, sub_size]
# one of the quadrants will have a non-empty tile; bracket that quadrant
# with a tile
if has_filled_tile? *top_left
@board[row + sub_size - 1] [col + sub_size] = @cur_tile
@board[row + sub_size] [col + sub_size] = @cur_tile
@board[row + sub_size] [col + sub_size - 1] = @cur_tile
elsif has_filled_tile? *top_right
@board[row + sub_size - 1] [col + sub_size - 1] = @cur_tile
@board[row + sub_size] [col + sub_size - 1] = @cur_tile
@board[row + sub_size] [col + sub_size] = @cur_tile
elsif has_filled_tile? *bottom_left
@board[row + sub_size - 1] [col + sub_size - 1] = @cur_tile
@board[row + sub_size - 1] [col + sub_size] = @cur_tile
@board[row + sub_size] [col + sub_size] = @cur_tile
elsif has_filled_tile? *bottom_right
@board[row + sub_size - 1] [col + sub_size - 1] = @cur_tile
@board[row + sub_size] [col + sub_size - 1] = @cur_tile
@board[row + sub_size - 1] [col + sub_size] = @cur_tile
else
raise "broken"
end
@cur_tile += 1
# recursively tile the quadrants
do_tile *top_left
do_tile *top_right
do_tile *bottom_left
do_tile *bottom_right
end
private :do_tile
def has_filled_tile? row, col, size
size.times do |r|
size.times do |c|
if @board[row + r] [col + c] != "-"
return true
end
end
end
false
end
end
s = Square.new 2
s.tile!
puts s.to_s
--
Bill Atkins
Ruby Quiz
in solving this problem. Most of the submissions used this technique and most
of them even figured it out without Google's help. Proof positive that coding
in Ruby increases the IQ.
Let's cover that proof. The easiest instance of the provided challenge is when
n = 1. No matter which square is missing from that, exactly one L-tromino fits
in the remaining squares. Here are all four possibilities:
X 1 1 X 1 1 1 1
1 1 1 1 X 1 1 X
Obviously, larger values on n require a little more thinking. Only a little
though, if we're clever. When n = 2, we can divide the board into quadrants to
get four 2 x 2 boards:
_ _ | X _
_ _ | _ _
---------
_ _ | _ _
_ _ | _ _
We can easily see that one of those is just the trivial case from above. The
key insight is that the other three quadrants could be made into the same
trivial case, with one well-placed L-tromino in the center:
_ _ | X _
_ 1 | _ _
---------
_ 1 | 1 _
_ _ | _ _
Now we have four simple problems to solve, no thought required:
2 2 | X 3
2 1 | 3 3
---------
6 1 | 1 5
6 6 | 5 5
What about n = 3 and beyond? Well, dividing n = 3 into quadrants, with another
well-placed center L-tromino, gives us four n = 2 problems. We can solved each
of those, as we did above. Then n = 4 can be divided into four n = 3 problems.
By now, you should see the pattern.
No matter how big the board gets, we can drop an L-tromino in the middle and
divide it into quadrants. We can keep reducing those sections into quadrants of
their own, until we get all the way back to a bunch of trivial n = 1 problems.
Here's a link to a nice graphical display of that proof, for those who still
need to see it in action:
http://www.cut-the-knot.org/Curriculum/Geometry/Tromino.shtml
Jannis Harder's solution produced pretty HTML output similar to what you see at
the above link, but uses a different strategy to obtain the answers. You might
want to run it a few times, to examine that technique.
The solutions emulating the proof, were all fairly similar in function.
Differing mainly is code style. Let's break down one such solution by Dominik
Bathon. Here's the helper class from Dominik's code:
#######################################################
# A simple 2D array, the width and height are immutable once it is created.
# #to_s accepts an optional block that can format the elements.
class Array2D
attr_reader :w, :h
def initialize(w, h, defel=nil)
@w, @h=w, h
@array=Array.new(w*h, defel)
end
def [](x, y)
@array[(y % h) * w + (x % w)]
end
def []=(x, y, v)
@array[(y % h) * w + (x % w)]=v
end
def to_s
(0...h).collect { |y|
(0...w).collect { |x|
v=self[x, y]
block_given? ? yield(v) : v
}.join " "
}.join "\n"
end
end
# ...
The comment tells you what we're looking at here, a two-dimensional Array. The
internal storage format (setup in initialize()) is really just a normal Array,
with some clever indexing that you can see in the []() and []=() methods.
The to_s() method is pretty interesting. You can see that is just generates
each x and y combination and feeds those to []() to get each square. A couple
of join()s at the end of the method create first rows and then a final String
from that, separating the squares with spaces and the rows with newlines.
There's a nice use of blocks here though. Each square is passed to a block (if
given), so that it may format the square for display.
Now we're ready to examine the solution class:
# ...
class TrominoTiler
def initialize(n)
n=[1, n].max
# initialize the working array
@a=Array2D.new(1 << n, 1 << n)
end
def tile_with_empty(x, y)
@tilenum=0 # counter
tile_recursive(0, @a.w, 0, @a.h, x, y)
@a
end
# ...
These two methods make up the public face of the solver. First, initialize()
creates an instance of the Array2D we just examined. Don't let the bit shifting
throw you, 1 << n is just another way to say the 2**n from the quiz.
The other method, tile_with_empty(), takes an x and y position for the empty
square and kicks-off the process to find a solution. We can see that it sets
some kind of counter, calls tile_recursive() with the dimensions of the board
and the empty square coordinates, then returns the modified Array2D. Clearly we
need to see tile_recursive() to make sense of this:
# ...
private
# tiles the area of @a determined by xb,xe and yb,ye (b is begin,
# e is end, so xb,xe is like the range xb...xe) with trominos,
# leaving empty_x,empty_y empty
def tile_recursive(xb, xe, yb, ye, empty_x, empty_y)
half=(xe-xb)/2
if half==1
# easy, just one tromino
@tilenum+=1
# set all 4 squares, empty is fixed below
@a[xb , yb ]=@tilenum
@a[xb+1, yb ]=@tilenum
@a[xb , yb+1]=@tilenum
@a[xb+1, yb+1]=@tilenum
else
# tile recursive
mytile=(@tilenum+=1)
# where to split the ranges
xh, yh=xb+half, yb+half
[ # the 4 sub parts:
[xb, xh, yb, yh, xh-1, yh-1],
[xh, xe, yb, yh, xh , yh-1],
[xb, xh, yh, ye, xh-1, yh ],
[xh, xe, yh, ye, xh , yh ]
].each { |args|
# if empty_x,empty_y is in this part, we
# have to adjust the last two arguments
if (args[0]...args[1]).member?(empty_x) &&
(args[2]...args[3]).member?(empty_y)
args[4]=empty_x
args[5]=empty_y
end
tile_recursive(*args)
@a[args[4], args[5]]=mytile
}
end
# fix empty square
@a[empty_x, empty_y]=nil
end
end
# ...
This is the heart of Dominik's solution. The method is a code representation of
the proof I outlined earlier. It starts by locating the center of the board.
It can branch two different ways from there. The first is when the center is 1,
showing that we're dealing with the trivial n = 1 case from the proof. When
that's the case, the code fills the board with the counter we saw initialized in
the previous method. That will actually fill four squares instead of the needed
three, but if you glance at the last line of the program you'll see that the
empty square is cleared before we return.
The other case the method deals with (the else clause), is for all bigger values
of n. Here, the method memorizes its counter, because it will be increased by
the coming recursion. Then, using the earlier found half-way point, the board
is divided into four equal quadrants. When created, the corner at the center of
the board is used as the new empty square, which represents our "well placed
center L-tromino" from the quiz. The code then corrects that auto-generated
empty square for the quadrant that already had one. Finally, the method
recurses by passing the dimensions of the new quadrant and the empty square for
that quadrant. After the quadrant is filled by that call, the corners are set
to the counter value memorized earlier.
That method will fill the entire board with numbered L-trominos by the time it
returns. The application code needed to finish off the solution is minimal:
# ...
if $0 == __FILE__
n=(ARGV[0] || 3).to_i
d=1 << n
maxw=((d*d-1)/3).to_s.size
tiler=TrominoTiler.new(n)
# show solutions for all possible empty squares
d.times { |y|
d.times { |x|
puts tiler.tile_with_empty(x, y).to_s { |v|
v.to_s.rjust(maxw)
}, ""
}
}
end
Dominik reads the specified size or defaults, then uses two lines of clever math
to determine what the largest numbered L-tromino is going to be in the result.
The code memorizes the size of that number, for use in the output block.
Then we get to the solver. An instance of TrominoTiler is created and
tile_with_empty() is called not for one random square by for all possible empty
squares. Those results are shown using Array2D's to_s() method. The passed
block pads small numbers to the maximum width memorized earlier. That gives us
a complete solution.
Many thanks to all you clever tilers out there. Golomb would be proud.
Ruby Quiz for next week: Send in some fresh suggestions. We're out of topics
and need some new material. Ruby Quiz will take a one week break to give you
all time to find some and me time to participate in one of the codefests. Enjoy
the break, but don't forget to send in those ideas!
atgeirr
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
Greg Brown
>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.
I have some ideas about the first 2 but I'll leave it to the experts to
give you the 'good' answers. But for 3, some_copy = some_array.dup
should do the trick.
Ara.T.Howard
i think it's often better to implement your own copy method since dup only
copies the arrray - not it's contents.
harp:~ > irb
irb(main):001:0> a = [ hash = {:k => :v} ]
=> [{:k=>:v}]
irb(main):002:0> a_dup = a.dup
=> [{:k=>:v}]
irb(main):003:0> a[0]['key'] = 'value'
=> "value"
irb(main):004:0> a_dup
=> [{:k=>:v, "key"=>"value"}]
clone doesn't really help either
irb(main):005:0> a = [ hash = {:k => :v} ]
=> [{:k=>:v}]
irb(main):006:0> a_clone = a.clone
=> [{:k=>:v}]
irb(main):007:0> a[0]['key'] = 'value'
=> "value"
irb(main):008:0> a_clone
=> [{:k=>:v, "key"=>"value"}]
my utility classes never get written w/o
def copy obj
Marshal::load(Marshal::dump(obj))
end
although i know this is frowned upon...
FYI.
-a
--
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| My religion is very simple. My religion is kindness.
| --Tenzin Gyatso
===============================================================================
atgeirr
Array contains only numbers. Is that correct? Anyway, I did not know
about dup, so thanks! I do not really understand the difference between
dup and clone, though.
Atgeirr
Dominik Bathon
#clone works like #dup, but it keeps more properties of the original
object:
#clone keeps a frozen object frozen, while #dup doesn't:
irb(main):007:0> a="hallo"
=> "hallo"
irb(main):008:0> a.freeze
=> "hallo"
irb(main):009:0> a.frozen?
=> true
irb(main):010:0> a.dup.frozen?
=> false
irb(main):011:0> a.clone.frozen?
=> true
and a cloned singleton class can not be instantieted, while a dupped
singleton class can:
irb(main):012:0> (class << a; self; end).new
TypeError: can't create instance of virtual class
from (irb):12:in `new'
from (irb):12
from :0
irb(main):013:0> (class << a; self; end).clone.new
TypeError: can't create instance of virtual class
from (irb):13:in `new'
from (irb):13
from :0
irb(main):014:0> (class << a; self; end).dup.new
=> ""
For the full details, here is the source of both functions from
ruby-1.8.2/object.c:
VALUE
rb_obj_clone(obj)
VALUE obj;
{
VALUE clone;
if (rb_special_const_p(obj)) {
rb_raise(rb_eTypeError, "can't clone %s", rb_obj_classname(obj));
}
clone = rb_obj_alloc(rb_obj_class(obj));
RBASIC(clone)->klass = rb_singleton_class_clone(obj);
RBASIC(clone)->flags = (RBASIC(obj)->flags | FL_TEST(clone, FL_TAINT))
& ~(FL_FREEZE|FL_FINALIZE);
init_copy(clone, obj);
RBASIC(clone)->flags |= RBASIC(obj)->flags & FL_FREEZE;
return clone;
}
VALUE
rb_obj_dup(obj)
VALUE obj;
{
VALUE dup;
if (rb_special_const_p(obj)) {
rb_raise(rb_eTypeError, "can't dup %s", rb_obj_classname(obj));
}
dup = rb_obj_alloc(rb_obj_class(obj));
init_copy(dup, obj);
return dup;
}
Dominik
James Edward Gray II
> As far as I can understand, dup would actually work here, since the
> Array contains only numbers. Is that correct?
Yes, in instances where you're just dealing with simple numbers, dup
() should meet your needs.
James Edward Gray II