A conversation with current Hacker Schooler Cerek about writing a boggle solver in Haskell motivated me to squeeze in writing up a solution in Python yesterday morning between appointments with Hacker Schoolers.
The strategy I followed was to generate all candidate
words and check them for validity with a dictionary, with the optimization
of not actually traversing the entire tree of possible words.
I wanted to separate building the candidate words and
checking them for validity, but allow the two processes to communicate to
eliminate branches that weren’t
promising: if no English words begin with
abcd don’t bother investigating
the branch of the tree of candidate words that begin with these letters, like
abcdh. Coroutines seemed like a good fit.
I started coding in Python 2 because that’s still my default for throw-away scripts, but ended up with code like this in a few places:
def candidates(board, row, col, visited, candidate=''): if (yield candidate): # whether this branch is a dead end return for c, (y, x) in unvisited_neighbors(board, visited, row, col): visited.add((y, x)) cands = candidates(board, y, x, visited, candidate+c) for cand in cands: break while True: try: cand = cands.send((yield cand)) except StopIteration: break visited.remove((y, x))
Then remembered - of course,
yield from! I should be using Python 3 for
def candidates(board, row, col, visited, candidate=''): if (yield candidate): # whether this branch is a dead end return for c, (y, x) in unvisited_neighbors(board, visited, row, col): visited.add((y, x)) yield from candidates(board, y, x, visited, candidate+c) visited.remove((y, x))
Having independently come up with something pretty close to the functionality
yield from solidifies how that construct works for me.
See the vim
:TOhtml-generated diff for the full code.1
One more reason to be using Python 3 by default! :)