Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Brute force solver for Riddle Express problem described at
Python (2.x) brute force solver for Riddler Express problem 10/21/2016.
May be applied to any ascii text file containing a list of words to be considered.
Tested with word2.txt file from
python <textfile>
Author: Michael F. Ellis
Copyright 2016 Ellis & Grant, Inc.
License: Public Domain with attribution requested.
def wordfile2list(name):
Return a list of words read from file. Assumes one word per line.
return [word.strip() for word in open(name, 'r')]
def initWordLists(lengths):
Return a dictionary of word lists keyed by length.
Arg: lengths is a range of permissible word lengths.
d = dict()
for n in lengths:
d[n] = []
for word in wordfile2list("words2.txt"):
if word.lower() == word:
except KeyError:
## too long or too short. Ignore it.
return d
def superwords(n, dwords, dfound):
Find all words of length n+1 that contain at least one word of length n.
found = []
sub_list = dfound[n]
candidates = dwords[n+1]
for word in candidates:
for subword in sub_list:
if subword in word:
return found
def walkUp(dwords):
Build a dictionary derived from dwords containing only words that can built
one letter at a time starting with a word of length 2.
d = {2: dwords[2]}
for n in sorted(dwords.keys()):
found = superwords(n, dwords, d)
nfound = len(found)
print "Found {} superwords of length {}.".format(nfound, n+1)
if nfound == 0:
d[n+1] = found
return d
def subword(word, dfound):
Find at least one word of length n-1 contained in words of length n.
dfound is a dictionary of superwords created by walkUp()
n = len(word)
sub_list = dfound[n-1]
for subword in sub_list:
if subword in word:
return subword
def walkBack(dfound):
Trace a construction path for each of the longest words found by
longest_words = dfound[max(dfound.keys())]
print longest_words
for word in longest_words:
print word
seq = [word]
n = len(word)
while n > 2:
seq.append(subword(seq[-1], dfound))
n -= 1
print ' '.join(reversed(seq))
def run(wordfile):
""" The top level routine """
dwords = initWordLists(range(2,16))
dfound = walkUp(dwords)
print "Done"
if __name__ == "__main__":
import sys
WORDFILE = sys.argv[1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment