Documentation
¶
Index ¶
Constants ¶
const PrefixLength = 3
PrefixLength is a package constant for consistent splitting on the word prefix optimization
Variables ¶
This section is empty.
Functions ¶
Types ¶
type WordPrefix ¶
type WordPrefix struct {
Prefix string // Character(s) in this set (redundant in use as the previous map will have this same prefix)
IsWord bool // Bool if the prefix to this letter is also a word
Words WordPrefixGroup // Map of the next list of words
}
A WordPrefix is a node in the lexicon tree. This node can represent the last letter of a word, and can link to many more nodes in the tree. Due to the nature of
func NewWordPrefix ¶
func NewWordPrefix(prefix string, isWord bool) WordPrefix
NewWordPrefix is a factory function for creating new word prefix nodes
type WordPrefixGroup ¶
type WordPrefixGroup map[string]WordPrefix
A WordPrefixGroup is a group of word prefix nodes
func NewLexicon ¶
func NewLexicon(filename string) (WordPrefixGroup, error)
NewLexicon reads in a lexicon from a file and holds it in memory while the current solver is running. It makes a tree map of the words so that when searching, it is easily possible to tell the moment input deviates from possible words. It Starts with a key of the first 3 letters since that is the minimum lengthfor valid boggle words.
On Efficiency: The worst cases of both memory and CPU depend on the length of the longest word added to the map. For the purposes of Boggle, the worst case word can only be 25 characters long. And Since the first 3 letters are in the root nodes, The maximum is 2 less than the length of the word.
Memory Efficiency: Theoreritical O(26^(N - 2)) where N is the length of the longest word in the dictionary. Actual O(26^(25 - 2))
CPU Efficiency: Theoreritical: O((N-2)) where N is the length of the longest word in the dictionary. Actual O(25 - 2)
DIAGRAM Input: test, tests, testy, testing
false false true [ i ] -- [ n ] -- [ g ] /
false true / true [ tes ] -- [ t ] -- [ s ]
\ \ true [ y ]
Source Files