My code fu is strong these days, three Code
Katas in the last few days.
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.
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) < 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