Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Brute force solver for Riddle Express problem described at http://fivethirtyeight.com/features/this-challenge-will-boggle-your-mind/
"""
Python (2.x) brute force solver for fivethirtyeight.com 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 https://github.com/dwyl/english-words.
Usage:
python riddler161021.py <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:
try:
d[len(word)].append(word)
except KeyError:
## too long or too short. Ignore it.
pass
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:
found.append(word)
break
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:
break
else:
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
walkUp().
"""
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)
walkBack(dfound)
print "Done"
if __name__ == "__main__":
import sys
WORDFILE = sys.argv[1]
run(WORDFILE)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.