Algorithmathon Day 7: Double Linked List Flattening
Created: 19 July 2013 Modified:
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.
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.
With the failing test written we can now write our helpers to construct our list.
The uneven list builder constructed we should move onto writing tests which give our expectations of the flatten! method.
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.
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.
Several tests are failing and we need to update the code in our DoLL by rewriting the flatten_by_recursion method.
All our tests are passing and this looks like a good place to stop. Tomorrow we will look into adding an unflatten! method.