-
Notifications
You must be signed in to change notification settings - Fork 0
/
webster.py
83 lines (69 loc) · 2.53 KB
/
webster.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import json
# DICT_FILENAME = "mit10k.json"
DICT_FILENAME= "dictionaries/letterboxed.json"
TEST_DICTIONARY = ['apple', 'ball', 'cat', 'aaab', 'bab', 'foo', 'apples']
class WebsterDict:
#
def __init__(self):
self.head = Node()
def load(self, path_to_file=DICT_FILENAME):
with open(path_to_file) as f:
base_dictionary = json.load(f)
for word in base_dictionary.keys():
# for word in TEST_DICTIONARY:
word = [x for x in word]
self.head.append(word)
def is_word(self, word, pointer=None):
if pointer is None:
pointer = self.head
if type(word) is str:
word = [x for x in word.lower()]
if len(word) == 0:
return pointer.is_word
if word[0] in pointer.children:
return self.is_word(word[1:], pointer.children[word[0]])
return False
def dump(self, pointer=None, result=[], my_word=''):
if pointer is None:
pointer = self.head
if pointer.is_word:
result.append(my_word)
for child in pointer.children.keys():
self.dump(pointer.children[child], result, my_word + child)
result.sort()
return result
def prune(self, list_of_values_to_remove, pointer=None):
# initial function call
if pointer is None:
self.prune(list_of_values_to_remove, self.head)
return
# node pruning
children = [k for k in pointer.children.keys()]
for child_value in children:
if child_value not in list_of_values_to_remove:
pointer.children.pop(child_value)
else:
self.prune(list_of_values_to_remove, pointer.children[child_value])
class Node:
def __init__(self):
self.value = None
self.children = {}
self.is_word = False
def __repr__(self):
return "<'{}' (node) / {}>".format(self.value, len(self.children))
def append(self, list_of_values):
if len(list_of_values) == 0:
# list empty- return
self.is_word = True
return
if list_of_values[0] in self.children:
target = self.children[list_of_values[0]]
else:
target = Node()
target.value = list_of_values[0]
target.append(list_of_values[1:])
self.children[target.value] = target
def find_child(self, value):
return self.children[value]
def has_child(self, value):
return value in self.children