Fwd: Please Forward: Ruby Quiz Submission

Begin forwarded message:

> From: James Koppel <[e-mail]>
> Date: May 26, 2007 2:20:54 PM CDT
> To: [e-mail], [e-mail]
> 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.