Forum: Ruby The Golden Fibonacci Ratio (#69)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2006-03-09 17:01
(Received via mailing list)
Before we get into discussing this week's solutions, allow me this brief
diversion.  Here's a single line from Andrew J.'s program (with
some added
whitespace):

	Fib = Hash.new{ |h, n| n < 2 ? h[n] = n : h[n] = h[n - 1] + h[n - 2] }

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:

	#!/usr/bin/ruby

	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 M..  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 A....
This topic is locked and can not be replied to.