Nine letter target

My wife's grandfather is an avid newspaper reader, with a sharp and critical mind. He loves solving puzzles. Last time we caught up, I jokingly said that I could write a program to solve the puzzle he was working on.

The puzzle was a nine letter target, common in Australian newspapers. The aim is to find all possible words in a 3 by 3 grid of letters with between 4 and 9 letters, and the word must also contain the central letter. A puzzle generator is available online.



I managed it, just ;-), with a bit of haggling over whether some of the words were acceptable.

import sys
import collections

def freq(letters):
    '''
    Construct a mapping of letter to frequency in a particular word

    { char -> int }
    '''
    d = collections.defaultdict(int)
    for c in letters:
        d[c] += 1
    return d

def validWord(word, special, targetFreq):
    '''
    Check if a word matches the nine letter word rules
    '''
    # must satisfy length criteria
    if len(word) < 4:
        return False

    # must contain central letter
    if special not in word:
        return False
    # must satisfy letter frequencys
    f = freq(word)
    for c in word:
        if c not in targetFreq:
            return False
        if f[c] > targetFreq[c]:
            return False
    return True

def nineLetterTarget( letters, dictionaryFile ):
    matches = []
    letters = letters.lower()
    special = letters[4]
    targetFreq = freq(letters)
    with open( dictionaryFile, 'r' ) as dictfh:
        for line in dictfh:
            # remove end of line marker
            line = line[:-1]
            # lower case the word
            line = line.lower()
            # only keep the word if it matches
            if validWord(line, special, targetFreq):
                matches.append(line)
    matches.sort( key = lambda word : len(word) )
    return matches

if __name__ == "__main__":
    dictFile = '/usr/share/dict/british-english'
    letters  = 'vnogdreec'
    words = nineLetterTarget( letters, dictFile )
    for word in words:
        print word