states.py

import networkx as nx

def main():

    G = nx.Graph()

    # states = ['new mexico', 'oklahoma', 'texas']
    # states = ['new mexico', 'oklahoma', 'texas', 'arkansas', 'louisiana', 'mississippi']

    # G.add_nodes_from(states)
    # 
    # G.add_edge('new mexico', 'texas')
    # G.add_edge('new mexico', 'oklahoma')
    # G.add_edge('texas', 'oklahoma')
    # G.add_edge('texas', 'louisiana')
    # G.add_edge('texas', 'arkansas')
    # G.add_edge('louisiana', 'arkansas')
    # G.add_edge('oklahoma', 'arkansas')
    # G.add_edge('mississippi', 'arkansas')
    # G.add_edge('mississippi', 'louisiana')

    # graph
    G = nx.read_adjlist(file("us_states.txt", "r"), nodetype=str)
    states = G.nodes()
    
    prefix_length = 7
    prefixes = set()
    
    path_length = 9
    
    # words
    words = set()
    max_word_length = 0
    for line in file("words.txt"):
        word = line.strip()
        prefixes.add(word[0:prefix_length])
        if len(word) > max_word_length:
            max_word_length = len(word)
        words.add(word)
            
    all_paths = set()

    def add_next_steps(path):
        """Return list of paths that are one step longer than path
        For example: When given [MS,AR], return [[MS,AR,OK],[MS,AR,LA],[MS,AR,TX]].
        """
        new_paths = []
        if len(path) >= path_length:
            return new_paths
        for neighbor in G.neighbors(path[len(path)-1]):
            if neighbor not in path:
                new_path = list(path)
                new_path.append(neighbor)
                new_paths.append(new_path)
        return new_paths
            
    while True:
        a = len(all_paths)
        for start_state in states:
            all_paths.add(tuple([start_state]))
            paths_to_add = []
            for p in all_paths:
                for new_path in add_next_steps(p):
                    paths_to_add.append(new_path)
            for p in paths_to_add:
                all_paths.add(tuple(p))
        if len(all_paths) == a:
            print "%s total paths found" % a
            # no new paths added, we're done
            break

    paths = set()
    for p in set(all_paths):
        if len(p) == path_length:
            paths.add(p)
    
    print "%s paths of length %s" % (len(paths), path_length)

    solutions = set()

    class Fragment(object):
        def __init__(self, frag, states):
            self.frag = frag
            self.states = states
        
        def __hash__(self):
            return hash(self.frag)
 
        def __eq__(self, other):
            return self.frag == other.frag
             
    for path in paths:
        # print path
        frags = {}
        for level, state_abbr in enumerate(path):
            frags[level] = set()
            state = get_state(state_abbr)
            state_letters = state.replace(" ", "").lower()
            
            if level == 0:
                # first state
                for x in xrange(len(state_letters)):
                    new_frag = state_letters[0:x+1]
                    # if len(new_frag) >= prefix_length and new_frag[0:prefix_length] not in prefixes:
                    #     break
                    frags[level].add(Fragment(new_frag, [state]))
            else:
                frags_to_add = set()
                for f in frags[level-1]:
                    states = list(f.states)
                    states.append(state)
                    for x in xrange(len(state_letters)):
                        new_frag = f.frag+state_letters[0:x+1]
                        if len(new_frag) >= max_word_length:
                            break
                        if len(new_frag) >= prefix_length and new_frag[0:prefix_length] not in prefixes:
                            break
                        frags_to_add.add(Fragment(new_frag, states))
                for f in frags_to_add:
                    # if len(f.frag) <= max_word_length:
                    frags[level].add(f)
        
        for k,v in frags.iteritems():
            for f in v:
                if len(f.frag) >= 8 and f.frag not in solutions and f.frag in words:
                    print "%s %s" % (f.frag, f.states)
                    print path
                    print ""
                    solutions.add(f.frag)
                            
    # answers = []
    # for fragment in fragments:
    #     # print fragment.frag
    #     if fragment.frag in words and len(fragment.frag) >= 6:
    #         answers.append(fragment)
    # 
    # answers.sort(key=lambda a: len(a.frag), reverse=True)
    # 
    # for a in answers:
    #     print "%s %s" % (a.frag, a.states)
    
    # for a in sorted(answers, key=len, reverse=True):
    #     print a

    # for x in G.neighbors(start):
    #     path = [start]
    #     path.append(x)
    #     paths.append(path)

abbreviations = {}
abbreviations['AL'] = "Alabama"
abbreviations['AK'] = "Alaska"
abbreviations['AZ'] = "Arizona"
abbreviations['AR'] = "Arkansas"
abbreviations['CA'] = "California"
abbreviations['CO'] = "Colorado"
abbreviations['CT'] = "Connecticut"
abbreviations['DE'] = "Delaware"
abbreviations['FL'] = "Florida"
abbreviations['GA'] = "Georgia"
abbreviations['HI'] = "Hawaii"
abbreviations['ID'] = "Idaho"
abbreviations['IL'] = "Illinois"
abbreviations['IN'] = "Indiana"
abbreviations['IA'] = "Iowa"
abbreviations['KS'] = "Kansas"
abbreviations['KY'] = "Kentucky"
abbreviations['LA'] = "Louisiana"
abbreviations['ME'] = "Maine"
abbreviations['MD'] = "Maryland"
abbreviations['MA'] = "Massachusetts"
abbreviations['MI'] = "Michigan"
abbreviations['MN'] = "Minnesota"
abbreviations['MS'] = "Mississippi"
abbreviations['MO'] = "Missouri"
abbreviations['MT'] = "Montana"
abbreviations['NE'] = "Nebraska"
abbreviations['NV'] = "Nevada"
abbreviations['NH'] = "New Hampshire"
abbreviations['NJ'] = "New Jersey"
abbreviations['NM'] = "New Mexico"
abbreviations['NY'] = "New York"
abbreviations['NC'] = "North Carolina"
abbreviations['ND'] = "North Dakota"
abbreviations['OH'] = "Ohio"
abbreviations['OK'] = "Oklahoma"
abbreviations['OR'] = "Oregon"
abbreviations['PA'] = "Pennsylvania"
abbreviations['RI'] = "Rhode Island"
abbreviations['SC'] = "South Carolina"
abbreviations['SD'] = "South Dakota"
abbreviations['TN'] = "Tennessee"
abbreviations['TX'] = "Texas"
abbreviations['UT'] = "Utah"
abbreviations['VT'] = "Vermont"
abbreviations['VA'] = "Virginia"
abbreviations['WA'] = "Washington"
abbreviations['WV'] = "West Virginia"
abbreviations['WI'] = "Wisconsin"
abbreviations['WY'] = "Wyoming"
 
def get_state(abbr):
    return abbreviations[abbr]
        
if __name__ == '__main__':
    main()

us_states.txt

# Author Gregg Lind
# License: Public Domain. I would love to hear about any projects you use if it for though!
# AK
AL MS TN GA FL
AR MO TN MS LA TX OK
AZ CA NV UT CO NM
CA OR NV AZ
CO WY NE KS OK NM AZ UT
CT NY MA RI
DE MD PA NJ
FL AL GA
GA FL AL TN NC SC
# HI
IA MN WI IL MO NE SD
ID MT WY UT NV OR WA
IL IN KY MO IA WI
IN MI OH KY IL
KS NE MO OK CO
KY IN OH WV VA TN MO IL
LA TX AR MS
MA RI CT NY NH VT
ME NH
MI WI IN OH
MN WI IA SD ND
MO IA IL KY TN AR OK KS NE
MS LA AR TN AL
MT ND SD WY ID
NC VA TN GA SC
ND MN SD MT
NE SD IA MO KS CO WY
NH VT ME MA
NJ DE PA NY
NM AZ UT CO OK TX
NV ID UT AZ CA OR
NY NJ PA VT MA CT
OH PA WV KY IN MI
OK KS MO AR TX NM CO
OR CA NV ID WA
PA NY NJ DE MD WV OH
RI CT MA
SC GA NC
SD ND MN IA NE WY MT
TN KY VA NC GA AL MS AR MO
TX NM OK AR LA
UT ID WY CO NM AZ NV
VT NY NH MA
WA ID OR
WI MI MN IA IL
WV OH PA MD VA KY
WY MT SD NE CO UT ID