Code Fu — about:me

My code fu is strong these days, three Code Katas in the last few days.

- Counting Code Lines

Did this one (Kata thirteen) again, this time in a real programming language. Python.

Some 50 odd lines of Python code to strip C and C++ style comments from a text-file and count the remaining lines (excluding empty lines). It’s a simple read-lex-parse-write cycle. Nothing fancy, but it works.

- Word Chains

This one (Kata Nineteen) was different, counting lines of source code is pretty straight forward; either you (ab)use cpp(1) or you write a simple lexer-parser pair. Figuring out how to build the word chains required a bit more thought work.

First, I decided I would do a recursive depth-first search from a to b, examining the candidates at each step in the order most likely to lead quickly to b. This is naturally a hodgepot of heuristics, but measuring the distance between two words by the number of letters they differ, and trying the different branches in order of increasing distance from the goal, seemed like a fine plan.

Next I had to think through if it was worth building a datastructure for the words adjacancy lists, or if one should just grep through the wordlist at every step. In the end I decided to go with the simplest possible solution, grepping through the adjacancy list at each step from a to b, looking for possible words to try. Naturally through all of this, one must keep a list of all the words already visited, so one does not goes there looking again.

This adds up to a grand total of 80 lines of Python code, but most of it is pretty simple stuff (e.g. distance between words, grepping through a list, some wrapping it up as a script), the core of it all is this:

def wordchain(here, there, visited=None):
    if distance(here, there) &lt; 2:
        return [here, there]

    if visited is None:
        visited = [here]

    adj = adjacant(here)
    adj.sort(lambda a, b: cmp(distance(a, there),
                              distance(b, there)))
    for word in adj:
        if word in visited:
            continue
        visited.append(word)

        try:
            wc = wordchain(word, there, visited)
            wc.insert(0, here)
            break
        except NoWordChainException:
            pass
    else:
        raise NoWordChainException, (here, there)

    return wc