Brute force solver for Riddle Express problem described at http://fivethirtyeight.com/features/this-challenge-will-boggle-your-mind/

riddler161021.py

"""
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)