From: Jesse Merriman <jesse.d.merriman@...>
Date: 2007-05-27T22:49:15+09:00
Subject: [SOLUTION][QUIZ] Fractals (#125)

--Boundary-00=_0wYWGFyZ4Djt9UP
Content-Type: Multipart/Mixed;
  boundary="Boundary-00=_0wYWGFyZ4Djt9UP"

--Boundary-00=_0wYWGFyZ4Djt9UP
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

My solution uses a simple recursive method to build a turtle-graphics string
for the fractal. I use three commands:

 F: move forward one unit
 L: turn left, but do not move
 R: turn right, but do not move

So level 1 can be represented by "FLFRFRFLF". I thought of doing it more
compactly and letting L & R imply a move, so that level 1 would be
"FLRRL", but that made some of my code more complex, so I stuck with the
verbose way.

My code (in fractals.rb) can accept different level-0 and level-1 turtle
strings, so it can be used to build other fractals besides the one in the
quiz. The basic algorithm I use is:

  For every char in level-1:
    If the char is the level-0 char, insert level-n-1, else insert the char

This is a bit different than:

  For every level-n-1 in self, insert self

But it seems to be equivalent. So the turtle-string-building code is pretty
short. Most of my code is for converting that string into different output
formats. These include the turtle string itself, text like that in the
original quiz email (turtle_text.rb), displayed on the screen using RMagick
(non-Windows only, if I remember the docs correctly), and any graphic format
that RMagick can write (turtle_draw.rb and turtle_image.rb).

Here's some examples:

$ ./fractals.rb 2
        _
      _| |_
    _|     |_
  _|_       _|_
_| |_|     |_| |_

$ ./fractals.rb 3 -format display # fractal display with ImageMagick

$ ./fractals.rb 3 -format png
Wrote level-3 fractal to fractal_F_FLFRFRFLF_3.png

$ ./fractals.rb 3 -l1 FLFFRF # alternate level-1 rule
   _
  |
 _|
|_ _
    |
    |_ _
       _|      _               _
      |       | |_ _          | |_ _
     _|    _ _|     |      _ _|    _|
    |_ _  |         |_ _  |       |
        |_|             |_|      _|
                                |_ _
                                    |
                                    |_ _
                                       _|
                                      |
                                     _|

(See the comment at the top of fractals.rb for the full usage.)

The RMagick stuff went pretty well, but the one thing that annoyed me was that
setting Draw's affine transformation matrix does not affect previous drawing
calls like line(). So I have to trace over the entire fractal once beforehand
just to get the size of it to set up the affine.

Also, for my TurtleText.textize method, I wanted to be able to use
Turtle.each_coord, and convert graphics coords to text coords. I couldn't find
a nice way to do that, though. For example, here are the widths and heights of
some fractals using graphics and text:

Turtle  Wg Wt  Hg Ht
F        1  1   0  1
LF       0  1   1  1

So Wt (text width) can't be calculated using only Wg, and neither for Ht and
Hg. This led to some kind-of duplication of code spirit, rather than letter,
in textize() and each_coord(). I think that, for the fractal in the quiz,
the widths and heights for level L are:

Wt: 2*3**L - 1
Ht: (3**L / 2).ceil
Wg: 3**L
Hg: (3**L / 2).floor

Though since I wanted to be general for other fractals, I couldn't use these.

It was fun to play around with different base strings, and see the resulting
image. Here's a few interesting ones I found (you can infer the rules from the
filenames):

http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_FFL_10.png
http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_FLFRF_6.png
http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_RFRFF_8.png
http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_FLFLFR_10.png
http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_LFFFRFLFLF_4.png
http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_RFRFLFF_6.png
http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_FLFRFRFLF_4.png
http://www.jessemerriman.com/images/ruby_quiz/125_fractals/fractal_F_LFFF_6.png

-- 
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/

--Boundary-00=_0wYWGFyZ4Djt9UP
Content-Type: application/x-ruby;
  name="fractals.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="fractals.rb"

#!/usr/bin/env ruby
# Ruby Quiz 125: Fractals
# fractals.rb
#
# Usage: ./fractals.rb LEVEL [-l0 LEVEL_0] [-l1 LEVEL_1] \
#                      [-format turtle | text | display | IMG_FORMAT]
#
# LEVEL: an integer >= 0.
# LEVEL_0 and LEVEL_1: turtle-graphics strings describing the first two levels
#                      of the fractal (defaults: F & FLFRFRFLF).
#
# Formats (default: text):
#   turtle:     Print out a turtle-graphics string of Fs, Ls, and Rs.
#   text:       Print out a textual representation of the fractal.
#   display:    Use RMagick to display the image.
#   IMG_FORMAT: An image format like png, jpg, or gif that RMagick understands.

DefaultLevel0 = 'F'
DefaultLevel1 = 'FLFRFRFLF'
DefaultFormat = 'text'

class Fractal
  # Create a new fractal from the givel level_0 and level_1 turtle strings.
  def initialize level_0, level_1
    @level_0 = level_0
    @level_0_byte = level_0[0] # Just to keep from re-calculating it over & over
    @level_1 = level_1
    self
  end

  # Return the turtle string for drawing the fractal to the given level.
  def turtle level
    if level.zero?   then @level_0
    elsif level == 1 then @level_1
    else
      s = ''
      @level_1.each_byte do |b|
        b == @level_0_byte ? s += turtle(level-1) : s += b.chr
      end
      s
    end
  end
end

if __FILE__ == $0
  # Read arguments.
  level = ARGV.first.to_i

  i = ARGV.index '-l0'
  lev0 = (i.nil? ? DefaultLevel0 : ARGV[i+1].upcase)
  i = ARGV.index '-l1'
  lev1 = (i.nil? ? DefaultLevel1 : ARGV[i+1].upcase)

  i = ARGV.index '-format'
  format = (i.nil? ? DefaultFormat : ARGV[i+1])

  # Build the turtle-graphics string of the fractal.
  turtle = Fractal.new(lev0, lev1).turtle level

  # Output.
  if format == 'turtle'
    puts turtle
  elsif format == 'text'
    require 'turtle_text'
    puts TurtleText.textize(turtle)
  else
    require 'turtle_image'
    image = TurtleImage.new turtle
    if format == 'display'
      image.display
    else
      begin
        filename = "fractal_#{lev0}_#{lev1}_#{level}.#{format}"
        image.write filename
        puts "Wrote level-#{level} fractal to #{filename}"
      rescue Exception => ex
        $stderr.puts "There was an error writing the image to #{filename}"
        $stderr.puts "Are you sure the format '#{format}' is valid?"
        $stderr.puts "(#{ex})"
      end
    end
  end
end

--Boundary-00=_0wYWGFyZ4Djt9UP
Content-Type: application/x-ruby;
  name="turtle_text.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="turtle_text.rb"

# Ruby Quiz 125: Fractals
# turtle_text.rb

require 'turtle'

# Contains the textize method for creating a text representation of a turtle
# graphic.
module TurtleText
  BG         = ' '
  Vertical   = '|'
  Horizontal = '_'

  # Returns a string representation for the given turtle graphics string.
  # Too bad Turtle.each_coord doesn't seem to be usable here, what with the
  # special x & y adjustments and such.
  def TurtleText.textize turtle
    x, y, grid = 0, 0, []
    last_abs_dir = nil

    # These two derement procs will automatically shift things up or right if
    # the values try to go below zero.
    decrement_x = lambda do
      if x > 0 then x -= 1
      else grid.each { |row| row.insert(0, nil) } end
    end
    decrement_y = lambda do
      if y > 0 then y -= 1
      else grid.insert 0, [] end
    end

    Turtle.each_absolute_direction(turtle) do |abs_dir|
      grid[y] = [] if grid[y].nil? # Hmm.. any way to give an array a default?

      if abs_dir == Turtle::Up
        grid[y][x] = Vertical
        y += 1
      elsif abs_dir == Turtle::Right
        x += 1 if not last_abs_dir.nil?
        grid[y][x] = Horizontal
        x += 1
      elsif abs_dir == Turtle::Down
        decrement_y[]
        grid[y][x] = Vertical
      else # abs_dir == Turtle::Left
        decrement_x[] if not last_abs_dir.nil?
        grid[y][x] = Horizontal
        decrement_x[]
      end

      last_abs_dir = abs_dir
    end

    # Convert grid to a string, reversing first since its upside-down.
    grid.reverse.inject('') do |str, row|
      str + row.map { |v| v.nil? ? BG : v }.join + "\n" 
    end.chomp
  end
end

--Boundary-00=_0wYWGFyZ4Djt9UP
Content-Type: application/x-ruby;
  name="turtle_draw.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="turtle_draw.rb"

# Ruby Quiz 125: Fractals
# turtle_draw.rb

require 'turtle'
require 'RMagick'

class TurtleDraw < Magick::Draw
  StrokeLength = 10 # pixels

  attr_reader :min_x, :min_y, :max_x, :max_y

  # Create a new TurtleDraw from the given string. x_ and y_translation are
  # extra (Cartesian) translations for the affine transform.
  def initialize turtle, x_translation = 0, y_translation = 0
    super()
    setup_attributes
    setup_affine turtle, x_translation, y_translation
    draw_turtle turtle
    self
  end

  # Setup all graphic attributes.
  def setup_attributes
    fill_opacity    0
    stroke          'gold3'
    stroke_width    2
    stroke_linecap  'round'
    stroke_linejoin 'round'
  end

  # The affine transform needs to do two things:
  #   - flip the coordinate system so y increases upwords (Cartesian)
  #   - shift to keep everything in the positive quadrant
  def setup_affine turtle, x_translation = 0, y_translation = 0
    min, max = Turtle.corners turtle
    @min_x, @min_y = min.map! { |v| StrokeLength * v }
    @max_x, @max_y = max.map! { |v| StrokeLength * v }
    affine 1, 0, 0, -1, -@min_x + x_translation , @max_y + y_translation
  end

  # Draw the given turtle string, setting the corner coords along the way.
  def draw_turtle turtle
    last_x = last_y = 0
    Turtle.each_coord(turtle, false) do |x, y|
      x, y = x * StrokeLength, y * StrokeLength
      line last_x, last_y, x, y
      last_x, last_y = x, y
    end
  end
end

--Boundary-00=_0wYWGFyZ4Djt9UP
Content-Type: application/x-ruby;
  name="turtle_image.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="turtle_image.rb"

# Ruby Quiz 125: Fractals
# turtle_image.rb

require 'turtle_draw'
require 'RMagick'

# This class isn't really necessary, what with TurtleDraw doing the hard work.
# It just sets up some attributes and uses a TurtleDraw to draw on itself.
class TurtleImage < Magick::Image
  BGColor = 'black'
  Border  = 10 # pixels

  # Create a new TurtleImage from the given string.
  def initialize turtle
    draw = TurtleDraw.new turtle, Border, Border
    width  = draw.max_x - draw.min_x + 2*Border
    height = draw.max_y - draw.min_y + 2*Border
    super(width, height) { self.background_color = BGColor }
    draw.draw self
    self
  end
end

--Boundary-00=_0wYWGFyZ4Djt9UP
Content-Type: application/x-ruby;
  name="turtle.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="turtle.rb"

# Ruby Quiz 125: Fractals
# turtle.rb

# Miscellaneous turtle-graphics stuff.
module Turtle
  Up, Left, Right, Down = (0..3).to_a # absolute directions

  # Yield once for each absolute direction moved in when following the given
  # turtle string. abs_dir is the initial absolute direction.
  def Turtle.each_absolute_direction turtle, abs_dir = Right
    turtle.each_byte do |b|
      rel_dir = b.chr
      # Perhaps some trig would be better than all these ifs?
      if abs_dir == Up
        if    rel_dir == 'L' then abs_dir = Left
        elsif rel_dir == 'R' then abs_dir = Right end
      elsif abs_dir == Right
        if    rel_dir == 'L' then abs_dir = Up
        elsif rel_dir == 'R' then abs_dir = Down end
      elsif abs_dir == Down
        if    rel_dir == 'L' then abs_dir = Right
        elsif rel_dir == 'R' then abs_dir = Left end
      else # abs_dir == Left
        if    rel_dir == 'L' then abs_dir = Down
        elsif rel_dir == 'R' then abs_dir = Up end
      end

      yield(abs_dir) if rel_dir == 'F'
    end
  end

  # Return an array of two arrays, each containing the coords of the lower-left
  # corner and the upper-right corner of the given turtle string.The initial
  # coordinate is [0, 0]. Each segment has a length of 1.
  def Turtle.corners turtle
    min_x = max_x = min_y = max_y = 0
    last_x = last_y = 0
    each_coord(turtle, false) do |x, y|
      min_x = x if x < min_x; max_x = x if x > max_x
      min_y = y if y < min_y; max_y = y if y > max_y
      last_x, last_y = x, y
    end
    [[min_x, min_y], [max_x, max_y]]
  end

  # Yield once for each x,y coordinate for the given string. The coord is an
  # array of two numbers. The initial coordinate is [0, 0]. Each segment has a
  # length of 1.
  def Turtle.each_coord turtle, yield_first = true
    abs_dir = Right
    x = y = 0
    yield([x, y]) if yield_first

    each_absolute_direction(turtle) do |abs_dir|
      if    abs_dir == Up    then y += 1
      elsif abs_dir == Right then x += 1
      elsif abs_dir == Down  then y -= 1
      else                        x -= 1 end # abs_dir == Left
      yield [x, y]
    end
  end
end

--Boundary-00=_0wYWGFyZ4Djt9UP--
--Boundary-00=_0wYWGFyZ4Djt9UP--