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.