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.
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
Comments
Comments are pre-moderated. Please be patient and your comment will appear soon.
There are currently no comments
New Comment