Class: DictionaryMap

Inherits:
Object
  • Object
show all
Defined in:
lib/dict_map.rb

Overview

The DictionaryMap represents a directed graph of words found in a dictionary. There are 26 starting nodes (assuming there is at least one word in the dictionary beginning with each letter of the alphabet). Each of those nodes Point to succeeding nodes that form the beginnings (and eventually the ends) of words.

Instance Method Summary collapse

Constructor Details

#initialize(file_path) ⇒ DictionaryMap

Returns a new instance of DictionaryMap.



70
71
72
73
74
75
 
# File 'lib/dict_map.rb', line 70

def initialize(file_path)
	@start_nodes = Hash.new
    open(file_path, 'r').readlines.each do |line|
        update_map(@start_nodes, line.downcase.chomp)
    end
end

Instance Method Details

#include?(word) ⇒ Boolean

searches the dictionary quickly for word TODO: potentially add an exhaust? option so that if we want to only search for a word once, it gets exhausted if found.

Returns:

  • (Boolean) 


125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/dict_map.rb', line 125

def include? (word)
    if word.nil? || word.empty?
        return false
    end
    cur_node = self.start_nodes[word[0]]
    index = 1
    #as long as we have more characters in the word and this word has successors, keep moving
    while index < word.size && cur_node.successors[word[index]] do
        cur_node = cur_node.successors[word[index]]
        index += 1
    end
    #if the loop ended, we either ran out of characters in the word
    #or there were no more successors.  If we ran out of characters in the word,
    #this node must be the end or we don't yet have a word 
    #if we had more characters and the dictionary didn't have an answer, this can't be word.
    #things like "nodenasdfasd" count as words.
    #in conclusion, we must be kicked out by the index < word.size test to even be
    #considered. 
    return index == word.size && cur_node.ends_word?
end

#reset ⇒ Object

resets the exhausted status of all nodes



117
118
119
120
121
 
# File 'lib/dict_map.rb', line 117

def reset
    @start_nodes.each_value do |node|
        reset_node(node)
    end
end

#reset_node(node) ⇒ Object

clears the exhausted status of the provided node and its successors



109
110
111
112
113
114
 
# File 'lib/dict_map.rb', line 109

def reset_node(node)
    node.exhausted = false
    node.successors.each_value do |new_node|
        reset_node(new_node)
    end
end

#start_nodes ⇒ Object

the beginning point of navigating the map. Designed this class to allow easy coupling to allow for optimizations. A black box with include? would still be fast, but this was built with Boggle in mind, so we want to be able to cut searches short and mark words as used without having to traverse the tree again.

start_nodes is a map of first character->successor nodes



104
105
106
 
# File 'lib/dict_map.rb', line 104

def start_nodes
    @start_nodes
end

#update_map(init_nodes, word) ⇒ Object

adds information about the word to the map



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/dict_map.rb', line 78

def update_map(init_nodes, word)
    current_nodes = init_nodes   
    char = nil
    #follow the chain of characters in this word
    0.upto(word.size - 1) do |index|
        char = word[index]
        #if we find a point where the letters haven't yet been added, update
        if !current_nodes[char]
            current_nodes[char] = WordNode.new(char)
        end
        #if we're at the last character, denote this node as word-ending
        if index == word.size - 1
            current_nodes[char].end_word!
        #advance position in the map
        else
            current_nodes = current_nodes[char].successors
        end
    end
end