The program functions as follows: given a wordlist, a collection of letters, and
ID: 3673084 • Letter: T
Question
The program functions as follows: given a wordlist, a collection of letters, and the length of one of the words, find all possible two words "answers" that use exactly the collection of letters given. The default word list is "wordlist.txt" (provided) and the default collection of letters aadekmmnortww. The default word length is 7. The "wordlist.txt" word list is also provided here in this directory. Note: the program either uses all the defaults or all three parameters must be specified. Here are some examples of correct outputs: > twowords awkward moment > ./twowords wordlist.txt testifythesis 6 feisty theists heists testify shiest testify thesis testify >./twowords wordlist.txt organpizza 5 argon pizza groan pizza orang pizza organ pizza pirog zanza
Explanation / Answer
class TrieNode:
def __init__(self, parent, value):
self.parent = parent
self.children = [None] * 26
self.isWord = False
if parent is not None:
parent.children[ord(value) - 97] = selfdef MakeTrie(dictfile):
dict = open(dictfile)
root = TrieNode(None, '')
for word in dict:
curNode = root
for letter in word.lower():
if 97 <= ord(letter) < 123:
nextNode = curNode.children[ord(letter) - 97]
if nextNode is None:
nextNode = TrieNode(curNode, letter)
curNode = nextNode
curNode.isWord = True
return root
def BoggleWords(grid, dict):
rows = len(grid)
cols = len(grid[0])
queue = []
words = []
for y in range(cols):
for x in range(rows):
c = grid[y][x]
node = dict.children[ord(c) - 97]
if node is not None:
queue.append((x, y, c, node))
while queue:
x, y, s, node = queue[0]
del queue[0]
for dx, dy in ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)):
x2, y2 = x + dx, y + dy
if 0 <= x2 < cols and 0 <= y2 < rows:
s2 = s + grid[y2][x2]
node2 = node.children[ord(grid[y2][x2]) - 97]
if node2 is not None:
if node2.isWord:
words.append(s2)
queue.append((x2, y2, s2, node2))
return words
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.