Strange Tales

(Submitted by Jeff Dever to the original posting)

Interesting. This is really my first experience being exposed to a coding dojo, but I must say I do like the martial art metaphor for computer science. I appreciate karfai's verbose description of this particular kata walkthrough and am inspired to participate, even though I am disjoint in time and space.

As I exercise my way through following along with the description, I find the decision to atomize the initial roman numeral string to be a comfortable move, but one that doesn't follow smoothly. The atomize function does the divide and conquer of the complexity where the preceding numeral must be subtracted from the following numeral. But it is ugly because it requires:

• a definition of atoms that are not actually atomic, like IV, IX, XL ...
• iteration over the list twice, once to atomize the numerals and again to c ompute
• repeated use of the temporary storage array parts for each st ring to convert

It seems like we can make this simpler and do it in a single pass without extra sto rage. I see the resistance of not wanting to look ahead when computing a running sum t o see if you should be subtracting the current numeral based on what the next numeral is. eg the first I counts as -1 in IV but counts as 1 in II.

This is where my thought process diverged from the other martial artists in the doj o, in that the next thing that came to mind is, "what if I traverse the list backwards ?". This is something I commonly do when thinking about a problem, is to run it throu gh in different orderings. Forwards, backwards, sorted, semi-sorted, whatever might m ake a difference to the quality of the algorithm. I've never really thought about it in these terms before, its just something that I do.

If you iterate over the roman numerals from the end to the start, you always know if you should add or subtract a digit based on the previous numeral since the base case is to always add the last numeral. This is more elegant than iterating forwards since you don't have to make a decision on the first numeral processed. (Note that there are some other rules of roman numerals that are not covered here but my goal was to satisfy the tests without having to look anything up whatsoever.)

I scribbled down the workings of this idea on paper to figure out what the condition should be (<, >, <= ...) and realized that I still had to store a prev value for use in my condition. With that, I jumped right to code. First I copied all the original code into a file and figured out how to work the test harness (never used Python unittest before) and got the original code working. I then replaced the original romanto_int(), atomize() and canprecede() routines with the following single function:

def roman_to_int_jeff(numeral):
        numerals = {
                "I": 1,
                "V": 5,
                "X": 10,
                "L": 50,
                "C": 100,
                "D": 500,
                "M": 1000,
                }

    #traverse the list backwards
    #if the current is less than the preceeding, decrement

    return 0

I then ran it and watched the test cases fail, which they did. Good, I'm back on track with test driven design. You'll notice that I put some comments in there that don't have any code to support them yet. That is my custom when programming the kernel of some behaviour, to comment the behaviour before I implement the functionality. I don't know how many people do this, but there is at least one other person, the one I stole the idea from. When I was at the University of Victoria for my one semester there, I had to explain to someone who was a year ahead of me how to perform a task and he wrote what I said down as comments. I've been doing that ever since.

So the next step was to write the code to satisfy the comments, which was really easy to do since there is so little to it. That left me with the following result:

def roman_to_int_jeff(numeral):
        numerals = {
                "I": 1,
                "V": 5,
                "X": 10,
                "L": 50,
                "C": 100,
                "D": 500,
                "M": 1000,
                }

    #traverse the list backwards
    #if the current is less than the preceding, decrement
    rv = 0
    prev = -1
    i = len(numeral) - 1
    while i >= 0:
            curr = numerals[numeral[i]]
            if curr < prev:
                    rv -= curr
            else:
                    rv += curr
            prev = curr
            i -= 1

    return rv

This Thursday past, AC and I decided to try a simple kata that I’d seen posted on another website. The problem is pretty simple: translate strings of roman numerals into integers. I suggested doing the kata in Python. We’re just starting a Python project at work, so I thought this would be an easy way to get a quick introduction to the language. As is typical in the dojo, we decided to work test-first.

The code shown for these behaviours (tests) is the result of a later refactoring of our test code. I’ve left it this way rather than reverting to the original tests because I think that it’s easier to read and I won’t need to repeat parts of the code as we progress.

AC started the ball rolling by writing the first behaviour that we needed to satisfy: all of the primitive roman numerals (I, V, X, L, C, D, M):

import unittest

def roman_to_int(numeral)
  return 0

class RomanNumeralTest(unittest.TestCase):
  def verify(self, expectations):
    for k in expectations:
        actual = roman_to_int(k)
        self.failUnlessEqual(expectations[k], actual, "for %s: expected %s, got %s" % (k, expectations[k], actual) )

  def testSingularNumeral(self):
    expectations = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
    self.verify(expectations)

Once we got this test running under a test harness, I took the keyboard to produce code to satisfy this behaviour. Since we started with set of values, I decided that the simplest way to solve the problem would be to use a dictionary which mapped a numeral string to an integer.

def roman_to_int(numeral):
  numerals = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
  return numerals[numeral]

I wrote the next expected behaviour: combinations of primitive elements.

def testRepetition(self):
    expectations = { "II": 2, "III": 3, "XX": 20, "XXX": 30, "CC": 200, "CCC": 300, "MM": 2000, "MMM" : 3000 }
    self.verify(expectations)

Since Python allows you to use a string as if it were an array, AC was able to very quickly implement a solution using Python’s ‘for’ construct.

def roman_to_int(numeral):
  numerals = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
  rv = 0
  for n in numeral:
      rv += numerals[n]

  return rv

This change got us very close to completing the kata. Or, so we thought until AC implemented the next behaviour test: the set of numerals where the preceding numeral specifies the number less than the following numeral.

def testPreceeding(self):
    expectations = { 'IV' : 4,  'IX' : 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM' : 900}
    self.verify(expectations)

The failure output from our test (“AssertionError: for IX: expected 9, got 11”) clearly indicated that our current solution had been a bit naive. We’d assumed that we would always be able to traverse the numeral from left to right using addition to build up the result. As you can tell from the test failure, this meant we were unable to distinguish ‘IX’ from ‘XI’.

We spent a few minutes discussing the different ways that we should approach this problem. AC suggested that we might be able to detect when we’re in a situation like ‘IX’ and use subtraction over addition. This seemed like a plausible solution, but I was enjoying the simplicity of the current solution (a single loop). My concern was that introducing some conditional logic to determine which arithmetic operation to use in the loop would complicate the procedure, making the code more difficult to read.

Since I was having trouble explaining a different solution, I decided to just show it in code. It starts with a simple refactoring: extracting a new method to break a numeral into it’s parts.

def atomize(numeral):
    parts = numeral
    return parts

def roman_to_int(numeral):
    numerals = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
    rv = 0
    for n in atomize(numeral):
        rv += numerals[n]

    return rv

We verified that out previous working tests still functioned after this refactoring, then continued. The next step was to introduce a predicate into atomize() which determined whether a particular numeral could precede another.

def can_precede(l, r):
    return 0

def atomize(numeral):
    parts = []
    i = 0
    inc = 1
   while i < len(numeral):
    if (i + 1) < len(numeral) and can_precede(numeral[i], numeral[i + 1]):
        parts.append(numeral[i] + numeral[i + 1])
        inc = 2
    else:
        parts.append(numeral[i])

    i += inc

    return parts

With this code in place, it was easy to complete the failing test by introducing a precedence table into can_precede() and by adding the require atoms to the original numeral lookup table.

def can_precede(l, r):
  precedence = {
    'I': ['V', 'X'],
    'X': ['L', 'C'],
    'C': ['D', 'M']
  }
  valid = []
  if (l in precedence):
    valid = precedence[l]
  return (r in valid)

def atomize(numeral):
  parts = []
  i = 0
  inc = 1
  while i < len(numeral):
    if (i + 1) < len(numeral) and can_precede(numeral[i], numeral[i + 1]):
        parts.append(numeral[i] + numeral[i + 1])
        inc = 2
    else:
        parts.append(numeral[i])

    i += inc

  return parts

def roman_to_int(numeral):
  numerals = {
    "I": 1,   'IV': 4,
    "V": 5,   "IX": 9,
    "X": 10,  "XL": 40,
    "L": 50,  'XC': 90,
    "C": 100, 'CD': 400,
    "D": 500, 'CM': 900,
    "M": 1000
  }

  rv = 0
  for n in atomize(numeral):
    rv += numerals[n]

  return rv

At this point, we were pretty confident that we’d completed the kata. AC wrote a number of other behaviour tests to verify that this was correct.

def testFollowing(self):
    expectations = {
        "VI" : 6,  "XI" : 11, "LX": 60, "CX": 110, "DC": 600, "MC" : 1100,
        "VII" : 7,  "XII" : 12, "LXX": 70, "CXX": 120, "DCC": 700, "MCC" : 1200,
        "VIII" : 8,  "XIII" : 13, "LXXX": 80, "CXXX": 130, "DCCC": 800, "MCCC" : 1300,
    }
    self.verify(expectations)

def testSimpleCombinations(self):
    expectations = {
        "XIV" : 14,  "XVI" : 16, "XVII": 17, "CXL": 140, "CLX": 160, "MCD" : 1400, "MDC" : 1600
    }
    self.verify(expectations)

def testYears(self):
    expectations = {
        "MDCCCXCIX" : 1899,  "MDCCCLXVII" : 1867, "MCMLXVII": 1967, "MMVIII": 2008, "MDCCCXII": 1812, "MDCCLXXVI" : 1776, "MCDXCII" : 1492
    }
    self.verify(expectations)

The final test demonstrated a subtle bug in our implementation of atomize(). We incorrectly initialize inc outside of the loop rather than at each iteration through the loop. This was quickly corrected and, after running our tests, we determined that we’d completed the behavioural requirements of the kata: our code implemented a Roman numeral parser.

As far as I was concerned, we weren’t yet finished the kata. The current implementation of atomize() didn’t really please me aesthetically. So, we continued into the next part of any programming session: refactoring for clarity, readability and aesthetics. Throughout this process, we used our existing tests to verify that we continued to meet all of the behavioural requirements.

Our first refactoring eliminated a branch from the conditional expression during the loop. This simplification makes the loop easier to understand.

def atomize(numeral):
  parts = []
  i = 0
  while i < len(numeral):
    part = numeral[i]
    inc = 1
    if (i + 1) < len(numeral) and can_precede(numeral[i], numeral[i + 1]):
        part += numeral[i + 1]
        inc = 2

    parts.append(part)
    i += inc

  return parts

Our second refactoring eliminated inc, an unnecessary variable and the i + 1 expressions were stored in a variable. Once again, reducing the amount of code in a procedure makes it easier to read.

def atomize(numeral):
  parts = []
  i = 0
  while i < len(numeral):
    part = numeral[i]
    next_i = (i + 1)
    if next_i < len(numeral) and can_precede(numeral[i], numeral[next_i]):
        part += numeral[next_i]

    parts.append(part)
    i += len(part)

 return parts

We spent a little more time looking at the code to see if there was any other refactoring remaining, but determined that this was the best we could do.

After a bit of discussion, we decided that this had been a pretty fun kata to perform. The problem was simple enough to finish in 60-70 minutes, but there was enough complexity that we’d taken a moment to step back from the keyboard an discuss how we might approach the problem. I’ll keep this kata in the repertoire of the dojo for future sessions; I think it would be an excellent one to pull out on evenings when new people attend the gathering.

For a while now, I’ve been considering what would constitute warm up exercises at the coding dojo. Typically, in a martial arts group, these exercises serve to prepare participants for the athletic exertion of the session. Often, these exercises bear some relation to the martial art and therefore serve a dual purpose: a warm-up with some bearing on the art itself. A clever teacher might even relate the warm-up exercises to the evening’s study.

A couple of sessions ago, I remarked to AC about a question I’d asked during a recent job interview session. The question was related to traversing a linked list (a typical, simple programming question). The actual question had been to reverse the linked list, but AC (still in the process of de-cycling) misheard and thought I’d said “print” the list in reverse order. He quickly suggested that this should be an easy endeavour. With this challenge, I decided to take the opportunity to present a potential solution that went well beyond the initial question in order to explore a common container data structure use pattern.

Deciding to use C, we started the exercise with a definition and declaration of a linked list:

typedef struct _s_node Node;

struct _s_node {
    char* name;
    Node* next;
};

int main(int argc, char* argv[])
{
    Node n4 = { "node4", NULL };
    Node n3 = { "node3", &n4 };
    Node n2 = { "node2", &n3 };
    Node n1 = { "node1", &n2 };
    Node n0 = { "node0", &n1 };

    return 0;
}

From this point, I decided that I should demonstrate a simple iteration over the linked list. Using a loop, we print the name field in the Node structure:

#include <stdio.h>

typedef struct _s_node Node;

struct _s_node {
        char* name;
    Node* next;
};

int main(int argc, char* argv[])
{
    Node n4 = { "node4", NULL };
    Node n3 = { "node3", &n4 };
    Node n2 = { "node2", &n3 };
    Node n1 = { "node1", &n2 };
    Node n0 = { "node0", &n1 };

    Node* it = &n0;
    do {
        printf("%s\n", it->name);
    } while ( NULL != (it = it->next) );

    return 0;
}

Now, that we had an understanding of how our simple linked list could be used and interpreted, we returned to the challenge at hand: operating on the list in reverse order. In order to make the problem interesting to AC (who’d grown a little bored during the 5-10 minutes it took us to get this far), I suggested that we could accomplish that requirement without using a looping structure. That challenge was enough to whet his interest again. After a few more minutes of typing, I completed a recursive solution to the challenge:

#include <stdio.h>

typedef struct _s_node Node;

struct _s_node {
    char* name;
    Node* next;
};

void print_reverse(Node* n)
{
    if ( n ) {
        print_reverse(n->next);
        printf("Node: %s\n", n->name);
    }    
}

int main(int argc, char* argv[])
{
    Node n4 = { "node4", NULL };
    Node n3 = { "node3", &n4 };
    Node n2 = { "node2", &n3 };
    Node n1 = { "node1", &n2 };
    Node n0 = { "node0", &n1 };

    Node* it = &n0;
    do {
        printf("%s\n", it->name);
    } while ( NULL != (it = it->next) );

    print_reverse(&n0);

    return 0;
}

Having solved the problem, I could’ve ended the exercise at this point. In approximately 10 minutes, I’d presented a simple data structure and a fun little way of using it. Since none of the other dojo regulars had arrived yet (and I was having fun), I decided to continue the exercise into a generalized solution that demonstrated a typical pattern that I’ve observed when working with container data structures.

Since the initial operation on the list (print all the names) and the second were so similar, refactoring the solution seemed to be the next task on the list. For symmetry, the do/while loop of the first operation was turned into a recursive approach.

#include <stdio.h>

typedef struct _s_node Node;

struct _s_node {
    char* name;
    Node* next;
};

void print_forward(Node* n)
{
    if ( n ) {
        printf("Node: %s\n", n->name);
        print_forward(n->next);
    }    
}

void print_reverse(Node* n)
{
    if ( n ) {
        print_reverse(n->next);
        printf("Node: %s\n", n->name);
    }    
}

int main(int argc, char* argv[])
{
    Node n4 = { "node4", NULL };
    Node n3 = { "node3", &n4 };
    Node n2 = { "node2", &n3 };
    Node n1 = { "node1", &n2 };
    Node n0 = { "node0", &n1 };

    print_forward(&n0);
    print_reverse(&n0);

    return 0;
}

The obvious similarity of the two print_ procedures was immediately apparent after this refactoring. In fact, that’s the nice thing about refactoring iteratively: you get to slowly see the patterns emerge in your code. After a few minutes of discussion, we decided to implement a generalized solution. We extracted the operative functionality from the traversal of the container using function pointers:

#include <stdio.h>

typedef struct _s_node Node;

struct _s_node {
    char* name;
    Node* next;
};

void print_name(Node* n)
{
    printf("Node: %s\n", n->name);
}

typedef void (*map_f)(Node*);

void apply(Node* n, map_f pre, map_f post)
{
    if ( n ) {
        if ( pre ) {
            (*pre)(n);
        }

        apply(n->next, pre, post);

        if ( post ) {
            (*post)(n);
        }
    }
}

int main(int argc, char* argv[])
{
    Node n4 = { "node4", NULL };
    Node n3 = { "node3", &n4 };
    Node n2 = { "node2", &n3 };
    Node n1 = { "node1", &n2 };
    Node n0 = { "node0", &n1 };

    apply(&n0, print_name, NULL);
    apply(&n0, NULL, print_name);

    return 0;
}

I’ve taken to calling this pattern the traverser (which came from a long-running conversation between myself and MC). As mentioned above, it’s a separation of an algorithm that iterates over a container and the operations during that iteration.

Later on, I refined this solution to implement the actual question that I’d asked earlier in the day: reversal of the elements of a linked list. Here’s the solution that I came to (omitting the common parts of previous code listings):

void reverse(Node* n)
{
    if ( n->next ) {
        n->next->next = n;
        n->next = NULL;
    }
}

int main(int argc, char* argv[])
{
    Node n4 = { "node4", NULL };
    Node n3 = { "node3", &n4 };
    Node n2 = { "node2", &n3 };
    Node n1 = { "node1", &n2 };
    Node n0 = { "node0", &n1 };

    apply(&n0, NULL, reverse);
    apply(&n4, print_name, NULL);

    return 0;
}

This entire exercise took less than half an hour to accomplish. That’s a short enough time that I don’t think attention will wander. The only remaining issue with this concept is the simplicity of the exercises. A decent programmer will tend to solve the problem and remember the solution for the next time. My concern is that they will grow bored with the process once we run out of little problems to tackle.

In a certain way, the projects portion of the dojo services this concern. A project tends to be longer running and more like the typical sort of thing a programmer will face in their day job. To a certain extent, this tends to grab the attention of programmers at the dojo for longer periods of time. Of course, even projects tend to wax and wane. Once the interesting aspects of the project have been solved, attention also wanders.

In order to get something useful out of the concept I’ve introduced in this posting, I’ll have to make certain that all of the exercises orbit around core tenants of programming (Patterns, for example). The more I consider it, I suspect this signifies the beginning of a style at the dojo. Deriving a style, I think, is a fundamental part of the progress of an art.

At least we’re on the right track.