Guest User

state_path.py

a guest
Nov 29th, 2017
152
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #/usr/bin/python
  2. import networkx as nx
  3. from nltk.corpus import wordnet as wn
  4. import re
  5. import itertools
  6.  
  7. #%%
  8. # Get words and phrases from Wordnet between 8 and 10 characters long
  9. words = set()
  10. for l in wn.all_lemma_names():
  11.     if re.match(r'^[A-Za-z\.\-\_]+$',l):
  12.         alpha_l = re.sub('[^A-Z]+','',l.upper())
  13.         if len(alpha_l) in (8,9,10):
  14.             words.add(alpha_l)
  15.        
  16. #%%
  17. # Create a graph of state borders
  18. G = nx.Graph()
  19. states = set()
  20. state_borders = [['AL', 'FL'], ['AL', 'GA'], ['AL', 'MS'], ['AL', 'TN'], ['AR', 'LA'], ['AR', 'MO'], ['AR', 'MS'], ['AR', 'OK'], ['AR', 'TN'], ['AR', 'TX'], ['AZ', 'CA'], ['AZ', 'NM'], ['AZ', 'NV'], ['AZ', 'UT'], ['CA', 'NV'], ['CA', 'OR'], ['CO', 'KS'], ['CO', 'NE'], ['CO', 'NM'], ['CO', 'OK'], ['CO', 'UT'], ['CO', 'WY'], ['CT', 'MA'], ['CT', 'NY'], ['CT', 'RI'], ['DE', 'MD'], ['DE', 'NJ'], ['DE', 'PA'], ['FL', 'GA'], ['GA', 'NC'], ['GA', 'SC'], ['GA', 'TN'], ['IA', 'IL'], ['IA', 'MN'], ['IA', 'MO'], ['IA', 'NE'], ['IA', 'SD'], ['IA', 'WI'], ['ID', 'MT'], ['ID', 'NV'], ['ID', 'OR'], ['ID', 'UT'], ['ID', 'WA'], ['ID', 'WY'], ['IL', 'IN'], ['IL', 'KY'], ['IL', 'MO'], ['IL', 'WI'], ['IN', 'KY'], ['IN', 'MI'], ['IN', 'OH'], ['KS', 'MO'], ['KS', 'NE'], ['KS', 'OK'], ['KY', 'MO'], ['KY', 'OH'], ['KY', 'TN'], ['KY', 'VA'], ['KY', 'WV'], ['LA', 'MS'], ['LA', 'TX'], ['MA', 'NH'], ['MA', 'NY'], ['MA', 'RI'], ['MA', 'VT'], ['MD', 'PA'], ['MD', 'VA'], ['MD', 'WV'], ['ME', 'NH'], ['MI', 'OH'], ['MI', 'WI'], ['MN', 'ND'], ['MN', 'SD'], ['MN', 'WI'], ['MO', 'NE'], ['MO', 'OK'], ['MO', 'TN'], ['MS', 'TN'], ['MT', 'ND'], ['MT', 'SD'], ['MT', 'WY'], ['NC', 'SC'], ['NC', 'TN'], ['NC', 'VA'], ['ND', 'SD'], ['NE', 'SD'], ['NE', 'WY'], ['NH', 'VT'], ['NJ', 'NY'], ['NJ', 'PA'], ['NM', 'OK'], ['NM', 'TX'], ['NV', 'OR'], ['NV', 'UT'], ['NY', 'PA'], ['NY', 'VT'], ['OH', 'PA'], ['OH', 'WV'], ['OK', 'TX'], ['OR', 'WA'], ['PA', 'WV'], ['SD', 'WY'], ['TN', 'VA'], ['UT', 'WY'], ['VA', 'WV']]
  21. for st1,st2 in state_borders:
  22.     states.add(st1); states.add(st2)
  23.     G.add_node(st1); G.add_node(st2)
  24.     G.add_edge(st1,st2)
  25.    
  26. #%%
  27. # Loop through simple paths and look for words
  28. for st1, st2 in itertools.permutations(states,2):
  29.     for path in nx.all_simple_paths(G,st1,st2,cutoff=10):
  30.         word = ''.join(x[0] for x in path)
  31.         if word in words:
  32.             print word, path
  33.  
  34. # Results:
  35. """
  36. MINKCOAT ['MO', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TX']
  37. MINKCOAT ['MO', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TN']
  38. MINKCOAT ['MN', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TX']
  39. MINKCOAT ['MN', 'IA', 'NE', 'KS', 'CO', 'OK', 'AR', 'TN']
  40. """
RAW Paste Data