Scribd
Upload
6 views1 page

Python Trie and Boggle Solver Code

The document contains a Python 2 script that implements a Trie data structure for storing a dictionary of words. It includes functions to create the Trie from a file and to find valid words in a Boggle game grid using the Trie. The BoggleWords function explores the grid to generate words based on the Trie structure.

Uploaded by

Ashish Kotwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views1 page

Python Trie and Boggle Solver Code

The document contains a Python 2 script that implements a Trie data structure for storing a dictionary of words. It includes functions to create the Trie from a file and to find valid words in a Boggle game grid using the Trie. The BoggleWords function explores the grid to generate words based on the Trie structure.

Uploaded by

Ashish Kotwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Python2

#!/usr/bin/python

class TrieNode:
def __init__(self, parent, value):
[Link] = parent
[Link] = [None] * 26
[Link] = False
if parent is not None:
[Link][ord(value) - 97] = self

def MakeTrie(dictfile):
dict = open(dictfile)
root = TrieNode(None, '')
for word in dict:
curNode = root
for letter in [Link]():
if 97 <= ord(letter) < 123:
nextNode = [Link][ord(letter) - 97]
if nextNode is None:
nextNode = TrieNode(curNode, letter)
curNode = nextNode
[Link] = 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 = [Link][ord(c) - 97]
if node is not None:
[Link]((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 = [Link][ord(grid[y2][x2]) - 97]
if node2 is not None:
if [Link]:
[Link](s2)
[Link]((x2, y2, s2, node2))

return words

You might also like