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