19 July 2013

Algorithmathon

Today’s goal is to flatten a list of lists into one long list. This means in addition to having a prev_node and next_node attribute the element will also have a child attribute which may or may not point to another list. An Illustration of this is below.

We will be using the Double Linked List (DoLL) base code from Day 6. Follow this link for Algorithmathon Rules. The Source Code is also available. Adding the child attribute to the element would be a good first step. We should write a test and the code to satisfy it as shown below.

``````require 'spec_helper'
# code omitted here
it "should have a 'child' method" do
end
# code omitted here``````
``````require 'spec_helper'
attr_accessor :next_node, :prev_node, :child, :data

def initialize(data=nil,next_node=nil,prev_node=nil,child=nil)
self.data=data
self.next_node=next_node
self.prev_node=prev_node
self.child=child
end
end``````

In order to adequately test that the list flattening is working as desired we need a list that isn’t flat. Since we will need this list in multiple tests the best way to handle this is to use helper methods. Building such a list could be error prone and we should build a test to verify our list is constructed correctly.

``````# code omitted here
it "should build a non flat list correctly" do
list = build_master_list()
list.length().should == 12
list.element_at(0).child.length().should == 6
list.element_at(4).child.length().should == 8
list.element_at(11).child.length().should == 16
end
# code omitted here``````

With the failing test written we can now write our helpers to construct our list.

spec_helper.rb
``````\$LOAD_PATH.unshift File.expand_path('lib')

end

def build_list(number_list)
number_list.each { | the_number |
}
the_list
end

def build_master_list()
the_list=build_list((1..12))
the_list.element_at(0).child=build_list(13..18)
the_list.element_at(4).child=build_list(19..26)
the_list.element_at(11).child=build_list(27..42)
the_list
end``````

The uneven list builder constructed we should move onto writing tests which give our expectations of the flatten! method.

``````# code omitted here
it "should have a length of 42 when it receives the 'flatten!' message" do
list = build_master_list()
list.flatten!()
list.length().should == 42
end

it "should return '13' when it receives the message 'element_at(12).data'" do
list = build_master_list()
list.flatten!()
list.element_at(1).data.should == '13'
end

it "should return '18' when it receives the message 'element_at(6).data'" do
list = build_master_list()
list.flatten!()
list.element_at(6).data.should == '18'
end

it "should return '2' when it receives the message 'element_at(7).data'" do
list = build_master_list()
list.flatten!()
list.element_at(7).data.should == '2'
end
# code omitted here``````

The tests are all passing. It’s Miller time! Kicking back with my BBC Bourbon Barrel Stout, I discuss what we have done so far. You of course are welcome to drink the beverage of your choice:) Suddenly, we realize we haven’t accounted for a child who also has a child! This means we will need to go back and update our tests and the helper methods. Methods which are capable of handling a structure similar to the one illustrated below.

``````# code omitted here
it "should build a non flat list correctly" do
list = build_master_list()
list.length().should == 12
list.element_at(0).child.length().should == 6
list.element_at(0).child.last().child.length().should == 8
list.element_at(4).child.length().should == 8
list.element_at(4).child.element_at(2).child.length().should == 8
list.element_at(11).child.length().should == 3
list.element_at(11).child.element_at(0).child.length().should == 6
end
# code omitted here``````
spec_helper.rb (excerpt)
``````# code omitted here
def build_master_list()
the_list=build_list((1..12))
first_child_list=build_list(13..18)
second_child_list=build_list(19..26)
first_child_list.last().child=second_child_list
the_list.element_at(0).child=first_child_list

first_child_list=build_list(27..34)
second_child_list=build_list(35..42)
first_child_list.element_at(2).child=second_child_list
the_list.element_at(4).child=first_child_list

first_child_list=build_list(43..45)
second_child_list=build_list(46..51)
first_child_list.element_at(0).child=second_child_list
the_list.element_at(11).child=first_child_list
the_list
end
# code omitted here``````

We now have a list that has children which in turn also have children. Unfortunately tests that are already written are now failing and new tests need to be written. Being RSpecofiles (™ pending) we hop right into some tests.

``````# code omitted here
it "should have a length of 51 when it receives the 'flatten!' message" do
list = build_master_list()
list.flatten!()
list.length().should == 51
end

it "should return '13' when it receives the message 'element_at(12).data'" do
list = build_master_list()
list.flatten!()
list.element_at(1).data.should == '13'
end

it "should return '18' when it receives the message 'element_at(6).data'" do
list = build_master_list()
list.flatten!()
list.element_at(6).data.should == '18'
end

it "should return '19' when it receives the message 'element_at(7).data'" do
list = build_master_list()
list.flatten!()
list.element_at(7).data.should == '19'
end

it "should return '5' when it receives the message 'element_at(18).data'" do
list = build_master_list()
list.flatten!()
list.element_at(18).data.should == '5'
end

it "should return '27' when it receives the message 'element_at(19).data'" do
list = build_master_list()
list.flatten!()
list.element_at(19).data.should == '27'
end

it "should return '51' when it receives the message 'element_at(48).data'" do
list = build_master_list()
list.flatten!()
list.element_at(48).data.should == '51'
end

it "should return '45' when it receives the message 'element_at(50).data'" do
list = build_master_list()
list.flatten!()
list.element_at(50).data.should == '45'
end
# code omitted here``````

Several tests are failing and we need to update the code in our DoLL by rewriting the flatten_by_recursion method.

``````# code omitted here
def flatten_by_recursion(element)
unless element.nil?
if element.child.nil?
flatten_by_recursion(element.next_node)
else
flatten_by_recursion(element.next_node)
end
end
end