find_all_words.py

import functools
import sys
from collections import namedtuple

Memo = namedtuple('Memo', ['word', 'neighbors', 'visited'])

#sys.setrecursionlimit(10 * 1000 * 1)
#@functools.lru_cache()
def find_words(input, dictionary_set):
  """
  Find all "simple paths" in an undirected graph
  """

  for row in range(len(input)):
    for col in range(len(input[0])):
      stack = [Memo('', [(row, col)], set())]
      while stack:
        uber_word, uber_neighbors, uber_visited = stack.pop()
        while uber_neighbors:
          (x, y) = uber_neighbors.pop()
          sub_visited = uber_visited.copy()
          word = uber_word

          if (x, y) not in sub_visited:
            sub_visited.add((x, y))
          
            word += input[x][y]
            check_word(word, dictionary_set)

            sub_neighbors = find_neighbors(x, y, len(input), len(input[0]), sub_visited)
            stack.append(Memo(word, sub_neighbors, sub_visited))

            if len(word) > 9:
              raise Exception('word can never be longer than 9 characters')

            if not(sub_neighbors):
                print('no_neighbors', word)

def check_word(word, dictionary_set):
  print('checking', word)
  if word in dictionary_set:
    print(word) 
        
def find_neighbors(r, c, x_limit, y_limit, visited):
  result = set([
    (r-1, c-1), #W
    (r-1, c), #I
    (r+1, c), #A
    (r, c-1), #S
    (r, c+1), #K
    (r+1, c-1), #E
    (r+1, c+1), #X
    (r-1, c+1)  #N
  ]) - visited

  return [elem for elem in result if 0 <= elem[0] < x_limit and 0 <= elem[1] < y_limit]
   
 

'''
wse
ita
nkx

wt...
ws...
''' 
input = [['w', 's', 'e'], ['i', 't', 'a'], ['n', 'k', 'x']]
dictionary_set = set(['sea', 'tin', 'win', 'wink', 'set', 'seat', 'kite', 'tax'])
find_words(input, dictionary_set)

• Words formed when there are no neighbors or the number of complete simple paths found:
  • 4224
• Words that were checked:
  • 10305

python find_all_words.py  | grep no_neighbors | wc -l
    4224
python find_all_words.py  | grep checking | wc -l
   10305