22 July 2013

Algorithmathon Day 8: Double Linked List Unflattening

On Day 8 we will be unflattening the Double Linked List (DoLL) that we flattened on Day 7 of the Algorithmathon. As always we will be following the Rules of Algorithmathon. For your viewing pleasure the source code is also available. How do we go about achieving this unflattening? It seems likely, what we need to do is to reverse the flattening process.

We should be able to reuse our test that verified our helper methods to help us write our first test.

double_linked_list_spec.rb (excerpt)

# code omitted here
    it "should have method 'unflatten!'" do
      DoubleLinkedList.method_defined?(:element_at).should be_true
# code omitted here
    it "should have the correct non flat list when the 'unflatten!' method is called." 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

# code omitted here

To try to grasp how we might solve this problem we can list out the rules we used for flattening the list.

What needs to be done to reverse this process? Well we should probably start at the beginning much like the flattening process.

While it sounds correct this plan will prove ultimately futile. When we flattened our list we started at the bottom and worked our way up. If we reverse this process we need to start at the top and work our way down. It would look something more like this.

In this case the code seems easier to understand than the aforementioned steps.

double_linked_list.rb (excerpt)

# code omitted here
  def unflatten!()
# code omitted here
  def unflatten_by_recursion(element)
    unless element.nil?
      if element.child.nil?
        @length = @length - element.child.length()
# code omitted here

Tomorrow we will start our first foray into Trees and Graphs.

tags: Algorithm - Algorithmathon - Double Linked List - RSpec - Ruby

Less Is More