· 8 years ago · Aug 12, 2018, 06:20 AM
1/**
2 puzzleSolver.java
3
4 Takes a word dictionary and a puzzle grid and
5 attempts to find all words in the puzzle.
6
7 Evan M. Purkhiser
8 emp36@zips.uakron.edu
9*/
10
11import java.util.ArrayList;
12import java.util.Hashtable;
13import java.util.HashMap;
14
15class puzzleSolver {
16
17 hashDictionary dictionary;
18
19 /**
20 Find all words that exist in the puzzle
21 from the current dictionary
22
23 @param puzzle A 2D array list of the puzzle grid
24
25 @return A array list of a Object array with the
26 start and end position of the word along with the word
27 */
28 public ArrayList<Object[]> solvePuzzle(ArrayList<ArrayList> puzzle)
29 {
30 // Create a array list to store the results in
31 ArrayList<Object[]> results = new ArrayList<Object[]>();
32
33 // Iterate over every letter in the grid and look for every possible letter combination
34 for(int y = 0; y < puzzle.size(); ++y)
35 for(int x = 0; x < puzzle.get(y).size(); ++x)
36 for(int dy = -1; dy <= 1; ++dy)
37 for(int dx = -1; dx <= 1; ++dx)
38 {
39 // Setup the current position and word
40 int ry = y + dy;
41 int rx = x + dx;
42 String word = (String) puzzle.get(y).get(x);
43
44 // Begin moving in a direction looking for words
45 while(ry >= 0 && rx >= 0 && ry < puzzle.size() && rx < puzzle.get(y).size())
46 {
47 // Only add to the word if we are moving
48 if(!(dy == 0 && dx == 0))
49 word += (String) puzzle.get(ry).get(rx);
50
51 // Check if the word exists in the hashtable and add it to results
52 if(this.dictionary.contains(word))
53 results.add(new Object[]{y, x, ry, rx, word});
54
55 // Move
56 ry += dy;
57 rx += dx;
58
59 // Break if we arn't moving
60 if(dy == 0 && dx == 0) break;
61 }
62 }
63
64 // Return the results
65 return results;
66 }
67
68 /**
69 Store the dictionary into a hashtable
70 by creating a new hastDictionary using the
71 specified hashing type.
72
73 @param dictionary An arrayList of the dictionray
74 @param hashType The hashing type to use
75 */
76 public void setDict(ArrayList<String> dictionary, int hashType)
77 {
78 this.dictionary = this.new hashDictionary(dictionary, hashType);
79 }
80
81 /**
82 Wrapper classfor different hash
83 compression methods
84 */
85 private class hashDictionary {
86
87 hashingMethod hashTable;
88
89 /**
90 Constructor, puts all the words into
91 a hashtable of some type.
92
93 @param dictionary The arrayList dictionray
94 @param hashTye the hash type to use
95 */
96 public hashDictionary(ArrayList<String> dictionary, int hashType)
97 {
98 // Determin what type of compression storage we are using
99 switch(hashType)
100 {
101 case 0 : this.hashTable = this.new linearProbing(); break;
102 case 1 : this.hashTable = this.new doubleHashing(); break;
103 default : this.hashTable = this.new javaHashtable(); break;
104 }
105
106 // Store the dictionary into our hashTable
107 for(String word : dictionary)
108 this.hashTable.put(word);
109 }
110
111 /**
112 Determin if a word currently exists
113 in the hashTable
114
115 @param word The word to look for
116
117 @return boolean if the word exists
118 */
119 public boolean contains(String word)
120 {
121 return this.hashTable.contains(word);
122 }
123
124 /**
125 Calculate a the hashcode of a word
126
127 @param word The string to hash
128 @param m a constant, should be a large prime
129
130 @return int The hashcode
131 */
132 private int hashCode(String word, int m)
133 {
134 return word.hashCode();
135 }
136
137 /**
138 A abstract class that the hash storage
139 methods may extend
140 */
141 private abstract class hashingMethod {
142
143 abstract void put(String word);
144 abstract boolean contains(String word);
145
146 }
147
148 /**
149 Wrapper class for linearProbing storage
150 */
151 private class linearProbing extends hashingMethod {
152
153 HashMap<Integer, String> table = new HashMap<Integer, String>();
154
155 public void put(String word)
156 {
157 // Don't do anything if the hash is in the table
158 if(this.contains(word))
159 return;
160
161 // The hash is not in the table, put it in
162 for(int hash = hashDictionary.this.hashCode(word, 1031); true; ++hash)
163 {
164 if(this.table.get(hash) == null)
165 {
166 this.table.put(hash, word);
167 break;
168 }
169 }
170 }
171
172 public boolean contains(String word)
173 {
174 for(int hash = hashDictionary.this.hashCode(word, 1031); this.table.get(hash) != null; ++hash)
175 if(this.table.get(hash).equals(word))
176 return true;
177
178 return false;
179 }
180
181 }
182
183 /**
184 Wrapper class for doubleHashing storage
185 */
186 private class doubleHashing extends hashingMethod {
187
188 public void put(String word)
189 {
190
191 }
192
193 public boolean contains(String word)
194 {
195
196 return false;
197 }
198
199 }
200
201 /**
202 Wrapper class for java hashtable storage
203 */
204 private class javaHashtable extends hashingMethod {
205
206 Hashtable<String, Boolean> table = new Hashtable<String, Boolean>();
207
208 /**
209 Add a word into the hashtable
210
211 @param word A string
212 */
213 public void put(String word)
214 {
215 this.table.put(word, true);
216 }
217
218 /**
219 Checks if the word is in the table
220
221 @param word A string to search for
222
223 @return boolean If the word was found
224 */
225 public boolean contains(String word)
226 {
227 return this.table.containsKey(word);
228 }
229
230 }
231
232 }
233
234}