Solving word wheels

(0 comments)

The Guardian is one of several newspapers which publish a daily "word wheel" puzzle: eight letters are arranged in a circle around a central letter and the goal is to make as many words as possible including the central letter and using each letter once. The words should be more than 4 letters in length.

enter image description here

The anagram solver presented in the previous post is easily adapted to solve word wheels:

import sys
from collections import Counter

DICTIONARY_FILENAME = 'sowpods.txt'
MIN_WORD_LENGTH = 4

def read_words(filename):
    """Read in words from filename, making them all lower case."""

    return [line.strip().lower() for line in open(filename)]

def make_trie(words):
    """Build a trie from the iterable object words."""

    root = {}
    for word in words:
        this_dict = root
        for letter in word:
            this_dict = this_dict.setdefault(letter, {})
        this_dict[None] = None
    return root

def wordwheel(letters, central_letter):
    """Return (yield) all anagrams of letters found in the dictionary."""

    def _anagram(letter_counts, path, root, central_letter):
        """Find anagrams of the letters and counts in the dict letter_counts.

        _anagram is called recursively to search the trie for anagrams: each
        letter from the letter_counts keys which is found in the trie is added
        to the path list and its count decreased before _anagram is called
        from the current position in the trie.
        _anagram is a generator: it yields words of the same length of the
        original word (word_length) as it encounters them.

        """
        if None in root.keys() and len(path) >= MIN_WORD_LENGTH:
            word = ''.join(path)
            if central_letter in word:
                yield word
        for letter, this_dict in root.items():
            count = letter_counts.get(letter, 0)
            if count == 0:
                continue
            letter_counts[letter] = count - 1
            path.append(letter)
            for word in _anagram(letter_counts,path,this_dict,central_letter):
                if central_letter in word:
                    yield word
            path.pop()
            letter_counts[letter] = count

    # Build a dictionary of letter: count pairs from the input letters sequence
    letter_counts = Counter(letters)
    for word in _anagram(letter_counts, [], trie, central_letter):
        yield word

if __name__ == '__main__':
    # Get the letters from the command line and return all anagrams.
    try:
        letters = sys.argv[1]
    except IndexError:
        print('usage: {} <letters>'.format(sys.argv[0]))
        print('The central letter should be given first.')
        sys.exit(1)

    trie = make_trie(read_words(DICTIONARY_FILENAME))

    words = list(wordwheel(letters, letters[0]))
    words.sort(key=lambda word: len(word))
    print('\n'.join([word.upper() if len(word)==len(letters) else word
                        for word in words]))
    print(len(words), 'words found.')

For example,

$ python wordwheel.py iedwnhovr
onie
deni
dine
dino
...
hordein
overwind
WINDHOVER
Current rating: 4.2

Comments

Comments are pre-moderated. Please be patient and your comment will appear soon.

There are currently no comments

New Comment

required

required (not published)

optional

required