by Enrique Meza C
You may have noticed that if you have a Golden Rectangle and you cut off a square with side lengths equal to the length shorter rectangle side, then what remains is another Golden Rectangle.
This could go on forever. You can just keep cutting off these big squares and getting smaller and smaller Golden rectangles.
The idea with the Fibonacci series is to do the same thing in reverse. So the quiz:
What you do is start with a square (1 by 1), find the longer side, and add a square of that size to the whole thing to form a new rectangle.
So when we start with a 1 by 1 square the longest side is one, so we add another square to it. Now we have a 2 by 1 rectangle
Then the longest side is two, so we connect a 2 by 2 square to our 2 by 1 rectangle to get a 3 by 2 rectangle. This continues, and the sides of the rectangle will always be a successive Fibonacci number. Eventually the rectangle will be very close to a Golden Rectangle.
I will do a few steps to let you see it in action:
###
# # 1 by 1, so we add 1 by 1 to get...
###
######
# ## # Now it is 2 by 1, so we add 2 by 2 to get......
######
######
# ## #
######
######
# # Now it is 2 by 3, so we add a 3 by 3 to get.......
# #
# #
# #
######
###############
# ## ## #
####### #
# ## #
# ## # Now it is 3 by 5, so we would add a 5 by 5 square.
# ## #
# ## #
###############
Quiz Summary
Before we get into discussing this week's solutions, allow me this brief diversion. Here's a single line from Andrew Johnson's program (with some added whitespace):
That is a trivial implementation of the Fibonacci number sequence, with built-in memoization, relying mainly on C code (Ruby's Hash implementation). It's bloody quick too, whipping my own home-grown memoized version by no small margin.
I just thought I would point that out because it's too cool and surely a pattern we could find other uses for...
Solving the Quiz
You can build the output for this quiz several different ways. My first thought was to spiral the squares, forming a structure similar to the log-cabin quilts my wife makes:
###########################
# # #
# # #
# # #
# # #
# # #
# # #
# # #
# # #
# # #
# ###########
# # # # #
# ##### #
# # # #
# # # #
# # # #
###########################
However, some submissions used a zig-zag approach that ended up looking like the following:
###########################
# # # # #
##### # #
# # # #
# # # #
# # # #
########### #
# # #
# # #
# # #
# # #
# # #
# # #
# # #
# # #
# # #
###########################
This second approach is interesting, because it only ever involves extending the image down or to the right. This turns out to be very easy to code up. Here's a solution by MenTaLguY:
CELL_WIDTH = 5
CELL_HEIGHT = 3
def box( size )
width = size * CELL_WIDTH
height = size * CELL_HEIGHT
lines = ["#" * width] + ["##{ " " * ( width - 1 ) }"] * ( height - 1 )
lines.map! { |line| line.dup }
end
lines = box( 1 )
$*[0].to_i.times do
width = lines.first.size * CELL_HEIGHT
height = lines.size * CELL_WIDTH
if width > height
lines.concat box( width / CELL_WIDTH / CELL_HEIGHT )
else
lines.zip box( height / CELL_WIDTH / CELL_HEIGHT ) do |line, box|
line << box
end
end
end
lines.each { |line| puts "#{ line }#" }
puts "#{ lines.first }#"
The box() method isn't too difficult to break down. A width and height are calculated for the new square and an Array of lines is constructed with liberal use of the repeat operator (*).
There are two point of interest here. First, note that lines are drawn with a top and left border, but not a right or bottom border. That's easier to understand when you see it, so here's a peek at what the lines variable holds after the first call to box():
"# ",
"# " ]
As you can see, CELL_WIDTH and CELL_HEIGHT include one border, but not the other.
The other thing to make note of is the last line of box(). At first, I couldn't figure out why all the lines were being duplicated. The reason is the way Ruby applies the repeat operator to Arrays:
>> ary = ["One String"] * 5
=> ["One String", "One String", "One String", "One String", "One String"]
>> ary.map { |str| str.object_id }
=> [1699134, 1699134, 1699134, 1699134, 1699134]
Since all of those Strings are the same object, appending to them later would cause problems, thus the calls to dup().
The next bit of the solution, the times() iterator, does most of the work. Don't let that Perlish variable $* throw you here, it's just another name for ARGV.
In this section you can see the two different methods for expanding the image. When the width of the current image is greater than the height, a simple call to concat() is used to append the new lines to the bottom of the image. If that's not the case, the lines belong on the right hand side and a combination of zip() and <<() is used to join the old and new lines.
Now remember, none of these boxes have right or bottom borders. Each time a new block is added, its top or left border become the bottom or right border for the blocks that were already there. This keeps the borders from doubling up. However, it also means that we will be missing a bottom and right border, when we are ready to print the end result. The last two lines of this solution handle that, ensuring that a right border is added to the end of each line and that the image is followed by a bottom border line.
That's really all it takes to create a working solution.
Custom Output
If you have ever wanted to see an example for some random output library for Ruby, odds are great there was one in these solutions. It was great to see the impressive array of libraries everyone knows.
One of the interesting forms of output was the PostScript language, used by Matthew Moss. Matthew called his solution "a cheap trick" and it is true that it uses some things we tend to frown on, like liberal use of instance_eval(). Still, I learned a lot from his instant DSL and I think it is worth a look.
Here's the class used to produce the final output:
# Postscript class (what a hack!)
class PS
def initialize(&block)
@cmds = []
instance_eval(&block) if block
end
def push(*args, &block)
@cmds << args.join(' ')
@cmds << instance_eval(&block) if block
end
def to_s
@cmds.join("\n")
end
def page(&block)
instance_eval(&block)
push 'showpage'
end
def path(&block)
push 'newpath'
instance_eval(&block)
end
def gsave(&block)
push 'gsave'
instance_eval(&block)
push 'grestore'
end
def method_missing(name, *args)
push *args + [name]
end
end
# ...
I know absolutely zip about PostScript, but there are a few things of interest in here, even for dummies like me. Notice how this class just encompasses an Array of commands (initialize()), gives you tools to add commands (mainly push()), turns all method calls into commands (method_missing()), and stringifies to a line by line set of commands (to_s()). The other important point here is that pretty much everything takes a block, which allows you to nest calls in a DSL fashion as follows:
# Build Postscript image
doc = PS.new do
def box a, b
l, r = [a.x, b.x].min, [a.x, b.x].max
b, t = [a.y, b.y].min, [a.y, b.y].max
moveto l, b
lineto r, b
lineto r, t
lineto l, t
closepath
end
page do
translate cx, cy
i = 0
coords.each_pair do |a, b|
path do
box a, b
gsave do
setgray Shade.mod_fetch(i += 1)
fill
end
stroke
end
end
setrgbcolor 0.8, 0.4, 0
path do
moveto coords.first
angle = 180
coords.each_pair do |a, b|
d = (a + b) * 0.5
d += (a - d).rot90
arcn d, (d - a).len, angle, (angle -= 90)
end
stroke
end
end
end
puts doc
Obviously, this output relies on methods and variables I haven't shown, but we're just focusing on the technique here. Let's zoom in on a small section of that:
setrgbcolor 0.8, 0.4, 0
path do
moveto coords.first
angle = 180
coords.each_pair do |a, b|
d = (a + b) * 0.5
d += (a - d).rot90
arcn d, (d - a).len, angle, (angle -= 90)
end
stroke
end
# ...
After that block gets evaluated and the method parameters get flipped by method_missing(), you will see some output like:
0.8 0.4 0 setrgbcolor
newpath
0.0 0.0 moveto
5.0 0.0 5.0 180 90 arcn
5.0 0.0 5.0 90 0 arcn
0.0 0.0 10.0 0 -90 arcn
0.0 5.0 15.0 -90 -180 arcn
10.0 5.0 25.0 -180 -270 arcn
10.0 -10.0 40.0 -270 -360 arcn
-15.0 -10.0 65.0 -360 -450 arcn
-15.0 30.0 105.0 -450 -540 arcn
50.0 30.0 170.0 -540 -630 arcn
50.0 -75.0 275.0 -630 -720 arcn
-120.0 -75.0 445.0 -720 -810 arcn
stroke
Obviously Matthew didn't gain a huge advantage in being able to swap the arguments or add commands with normal Ruby syntax. The real win comes from being able to programatically build up these commands, as you see above. A path() was reduced to a simple series of steps that produces complex results. While the interface may be a bit cavalier, I think it does show of how even simple DSLs can be time savers.
My usual thanks to a wide range of creative problem solvers! I was blown away by how many different ways people found to spin this problem.
Tomorrow we have a great quiz about attacking problems from a whole new angle from Jay Anderson...
