Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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)
Add Comment
Please, Sign In to add comment