James Gray
5/27/2007 5:19:00 PM
Begin forwarded message:
> From: James Koppel <darmaniiii@yahoo.com>
> Date: May 26, 2007 2:20:54 PM CDT
> To: submission@rubyquiz.com, submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> Here is my solution to Ruby Quiz #125.
>
> Rather than limit the problem domain to the fractal posted, I
> decided to attempt to make my solution work for all fractals
> generated by replacing each segment with a shape that can be
> represented by contiguous underscores and vertical pipes (i.e.: no
> angled segments) . The engine behind the fractal expansions is the
> FractalNode class, which treats a shape as a quasi-tree, and each
> pipe/underscore as a node with zero or more children, a parent, the
> direction by which it is offset from its parent (those who read my
> code would do well to treat "direction" and "offset" as near-
> synonyms, as for various routines the two are often cross-
> dependent), and an orientation. To create the fractals, a block is
> used. Note that method_missing is utilized so that various methods
> are writers with arguments and readers without. As an example, the
> level 1 of the given fractal is constructed as follows in the code:
>
> #The following figure
> # _
> #_| |_
> standard_fractal = FractalNode.new do
> orientation :up
> child do
> orientation :right
> offset :down_right
> child do
> orientation :up
> offset :down_right
> end
> end
> child do
> orientation :left
> offset :down_left
> child do
> orientation :up
> offset :down_left
> end
> end
> end
>
> The code includes, commented out, many other fractals I tested, as
> well as modifications on the standard order 0 fractal.
>
> Because it used two rows of representation to display each row of
> the fractal (i.e.: in the representation of the example fractal on
> the site, the pipe is in a row between the two underscores despite
> being displayed in the same row), with the exception of simple
> horizontal fractals, although it can represent fractal nodes with
> orthagonal offsets, it cannot correctly display them. However, the
> example fractal only uses diagonal offsets, so it still meets the
> criteria.
>
> The method that replaces every node with the replacement given is
> fractal_expand. To know which part of a fractal should be connected
> to neighboring expansions, and to change the representation so that
> it is so, the fractal_expand uses follow_branch and
> hierarchial_correct!. Unfortunately, the algorithm of follow
> branch, following the child in as near to the given direction as
> possible until it hits a leaf, returns shape endpoints that humans
> (or at least I) would disagree with. One example of this case is
> the following:
>
> _
> _| |_
> _|_ _|_ <-program chooses here as one of the endpoints
> _| |_
> _| |_
> _| |_<-I'd think it should be here
>
> I tried changing follow_branch to pick a branch according to the
> previous algorithm but, rather than recurse, find the farthest node
> in the direction headed {using direction_most), but, depending the
> direction headed, that algorithm yields inconsistent results (which
> broke the example fractal). My program also has other problems
> expanding the above fractal above level 1; however, that is the
> only fractal I tested for which these problems occurred (it has no
> problems with the given fractal, so it still meets the basic
> criteria), and, due to my limited knowledge of fractals, the
> difficulty in debugging the program using such a complicated
> fractal-tree, the fact that I have other things on my todo-list and
> need to move on, and the fact that I battled a minor illness to
> write this, I have little desire to get it to work with more-
> complex shapes.
>
> Anyway, a few more things to point out. Some of the larger fractals
> may wrap over when printed to STDOUT. To print to to a file, merely
> remove the comments from the driver code at the very bottom. I paid
> little attention to speed when writing this, so some of the larger
> expansions may take a few minutes to print out. The rest of this e-
> mail is the actual program:
>
>
> class Hash
> def inverse
> h = Hash.new
> each_pair {|key, value| h[value] = key}
> h
> end
>
> def map_pair
> h = Hash.new
> each_pair {|key, value| h[key] = yield key, value}
> h
> end
>
> def map_value
> map_pair {|key, value| yield value}
> end
>
> alias + merge!
> end
>
> $orientations = {:up => 0,
> :right => 1,
> :down => 2,
> :left => 3}
>
> $offsets = {:up_right =>1,
> :down_right =>3,
> :down_left =>-3,
> :up_left => -1,
> :up =>0,
> :right =>2,
> :down =>4,
> :left =>-2}
>
> $rotations = {:up_right => :down_right,
> :down_right => :down_left,
> :down_left => :up_left,
> :up_left => :up_right,
> :up => :right,
> :right => :down,
> :down => :left,
> :left => :up}
>
> $direction_meanings = {:up_right => [-1,1],
> :down_right => [1, 1],
> :down_left => [1,-1],
> :up_left => [-1,-1],
> :up => [-1, 0],
> :left => [0,-1],
> :right => [0, 1],
> :down => [1,0]}
>
> def direction_rotated(n,dir)
> n.times {dir = $rotations[dir]}
> dir
> end
>
> class FractalNode
>
> #Methods for creating fractals in blocks
>
> attr_writer :orientation, :offset, :parent, :children
>
> def method_missing(mID, *args)
> if args.empty?
> instance_variable_get("@#{mID}".to_sym)
> else
> send("#{mID}=",args.first)
> end
> end
>
> def child(&block)
> @children << FractalNode.new(&block)
> @children.last.parent = self
> end
>
> def initialize(&block)
> @children = []
> @parent = nil
> @offset = nil
> instance_eval &block
> end
>
> #Methods needed to expand fractals
>
> alias old_dup dup
> def dup
> new = old_dup
> children.each{|c| c.parent = new}
> new
> end
>
> def rotate_offset!(n)
> @offset = direction_rotated(n, offset)
> self
> end
>
> def rotate!(n)
> @orientation =
> $orientations.inverse[(n+$orientations[@orientation])%4]
> self
> end
>
> def rotate_offset(n)
> self.dup.rotate_offset!(n)
> end
>
> def rotate(n)
> self.dup.rotate!(n)
> end
>
> def deep_rotate(n)
> newNode = rotate(n).rotate_offset!(n)
> newNode.children = newNode.children.map {|c| c.deep_rotate(n)}
> newNode
> end
>
> def follow_branch(direction)
> return self if children.empty?
> adjustment = 4-$offsets[direction]/2
> children.sort_by{|c|
> ($offsets[direction_rotated(adjustment, direction)] -
> $offsets[direction_rotated(adjustment, c.offset)]).abs
> }.first.follow_branch(direction)
> end
>
> def hierarchial_correct!(parent=nil)
> if parent != @parent
> @children << @parent if @parent
> @children -= [parent]
> end
> @children.each {|child| child.hierarchial_correct!(self)}
> unless parent == @parent
> if parent
> @offset = direction_rotated(2,parent.offset)
> else
> rotate_offset!(2)
> end
> end
> @parent = parent
> end
>
> def fractal_expand(replacement)
> my_replacement = replacement.deep_rotate($orientations
> [orientation])
> top = nil
> if offset
> top = my_replacement.follow_branch(direction_rotated(2,offset))
> else
> top = my_replacement
> end
> top.hierarchial_correct!
> top.offset = offset
> children.each {|child|
> my_replacement.follow_branch(child.offset).children =
> [child.fractal_expand(replacement)]}
> top
> end
>
> #Methods used to print fractals
>
> def relative_coordinates
> coord_hash = {self => [0,0]}
> children.each do |child|
> branch_coords = child.relative_coordinates
> branch_offset = $direction_meanings[child.offset]
> coord_hash += branch_coords.map_value { |val|
> val.zip(branch_offset).map{|c, c_off| c+c_off}}
> end
> coord_hash
> end
>
> def direction_most(direction)
> y_weight, x_weight = $direction_meanings[direction]
>
> relative_coord_mappings = relative_coordinates
> relative_coords = relative_coord_mappings.values.sort_by {|y,x|
> y*y_weight + x*x_weight}
> relative_coord_mappings.inverse[relative_coords.last]
> end
>
> def vertical?
> @orientation == :left or @orientation == :right
> end
>
> def horizontal?
> !vertical?
> end
>
> require 'enumerator'
> def print_fractal(f=$stdout)
> coord_mappings = relative_coordinates
> highest = direction_most(:up)
> min_y = coord_mappings[highest][0]
> min_y -= 1 if highest.horizontal?
> max_y = coord_mappings[direction_most(:down)][0]
> min_x = coord_mappings[direction_most(:left)][1]
> max_x = coord_mappings[direction_most(:right)][1]
> fractal_rep_arr = [].fill(nil, max_y-min_y)
> 0.upto(max_y-min_y) {|r| fractal_rep_arr[r] = [].fill(nil, 0..
> (max_x - min_x))}
> coord_mappings.each_pair { |node,( y, x)| fractal_rep_arr[y-
> min_y][x-min_x] = node}
> fractal_rep_arr << [].fill(nil,0,max_x) unless
> fractal_rep_arr.length % 2 == 0
> fractal_rep_arr.each_slice(2) do |row_v, row_h|
> row_v.zip(row_h).map{|a| a == [nil,nil] ? [nil] :
> a.compact}.flatten.each do |n|
> if n.nil?
> f.print ' '
> next
> end
> f.print '|' if n.vertical?
> f.print '_' if n.horizontal?
> end
> f.puts
> end
> end
> end
>
> def fractal_level(n,replacement)
> fractal = $starting_fractal
> n.times {fractal = fractal.fractal_expand(replacement.deep_rotate
> (4-$orientations[replacement.orientation]))}
> fractal.deep_rotate($orientations[replacement.orientation])
> end
>
> #The following figure
> #_
> $starting_fractal = FractalNode.new do
> orientation :up
> end
>
> #The following figure
> # _
> #_| |
> #$starting_fractal = FractalNode.new do
> # orientation :up
> # child do
> # orientation :right
> # offset :down_right
> # end
> # child do
> # orientation :left
> # offset :down_left
> # child do
> # orientation :down
> # offset :down_right
> # end
> # end
> # end
>
> #The following figure
> # _
> #| |
> #$starting_fractal = FractalNode.new do
> # orientation :up
> # child do
> # orientation :right
> # offset :down_right
> # end
> # child do
> # orientation :left
> # offset :down_left
> # end
> #end
>
> #The following figure
> # _
> #_| |_
> standard_fractal = FractalNode.new do
> orientation :up
> child do
> orientation :right
> offset :down_right
> child do
> orientation :up
> offset :down_right
> end
> end
> child do
> orientation :left
> offset :down_left
> child do
> orientation :up
> offset :down_left
> end
> end
> end
>
> #The following figure
> #_ _
> # |_|
> #_| |_
> #standard_fractal = FractalNode.new do
> # orientation :up
> # child do
> # orientation :right
> # offset :down_right
> # child do
> # orientation :up
> # offset :down_right
> # end
> # end
> # child do
> # orientation :left
> # offset :down_left
> # child do
> # orientation :up
> # offset :down_left
> # end
> # end
> # child do
> # orientation :left
> # offset :up_left
> # child do
> # orientation :down
> # offset :up_left
> # end
> # end
> # child do
> # orientation :right
> # offset :up_right
> # child do
> # orientation :down
> # offset :up_right
> # end
> # end
> #end
>
> #The following figure
> # _
> #| |
> #standard_fractal = FractalNode.new do
> # orientation :up
> # child do
> # orientation :right
> # offset :down_right
> # end
> # child do
> # orientation :left
> # offset :down_left
> # end
>
> #THIS IS THE ONE THAT DOESN'T WHOLLY WORK
> #The following figure
> # _
> # _| |_
> # _|_ _|_
> # _| |_
> # _| |_
> #_| |_
> #standard_fractal = FractalNode.new do
> # orientation :up
> # child do
> # orientation:left
> # offset :down_left
> # child do
> # orientation :up
> # offset :down_left
> # child do
> # orientation:left
> # offset :down_left
> # child do
> # orientation :up
> # offset :down_left
> # end
> # child do
> # orientation :up
> # offset :down_right
> # child do
> # orientation :right
> # offset :down_right
> # child do
> # orientation :down
> # offset :down_left
> # child do
> # orientation :right
> # offset :down_left
> # child do
> # orientation :down
> # offset :down_left
> # child do
> # orientation :right
> # offset :down_left
> # child do
> # orientation :down
> # offset :down_left
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> # child do
> # orientation:right
> # offset :down_right
> # child do
> # orientation :up
> # offset :down_right
> # child do
> # orientation:right
> # offset :down_right
> # child do
> # orientation :up
> # offset :down_right
> # end
> # child do
> # orientation :up
> # offset :down_left
> # child do
> # orientation :left
> # offset :down_left
> # child do
> # orientation :down
> # offset :down_right
> # child do
> # orientation :left
> # offset :down_right
> # child do
> # orientation :down
> # offset :down_right
> # child do
> # orientation :left
> # offset :down_right
> # child do
> # orientation :down
> # offset :down_right
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> # end
> #end
>
> #The following figure:
> #__
> #standard_fractal = FractalNode.new do
> # orientation :up
> # child do
> # orientation :up
> # offset :right
> # end
> #end
>
> #File.open("fractal.txt", "w") {|f|
> fractal_level(ARGV[0].to_i, standard_fractal).print_fractal#(f)}
>
> Get the Yahoo! toolbar and be alerted to new email wherever you're
> surfing.