Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# Michael-F-Ellis/riddler161021.py

Last active Oct 24, 2016
Brute force solver for Riddle Express problem described at http://fivethirtyeight.com/features/this-challenge-will-boggle-your-mind/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """ 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 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)
to join this conversation on GitHub. Already have an account? Sign in to comment