November 2008 Archives

(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