1 /**
  2  * Author:  Elvis Montero
  3  * URL:     www.elvismontero.com
  4  * License: This code is licensed under the Creative Commons Attribution
  5  *          Share-Alike License v3.0 or any other later version.
  6  */
  7 
  8 package progpraxis;
  9 
 10 import java.io.BufferedReader;
 11 import java.io.FileReader;
 12 import java.io.IOException;
 13 import java.util.Set;
 14 import java.util.TreeSet;
 15 import java.math.BigInteger;
 16 import java.util.ArrayList;
 17 import java.util.List;
 18 
 19 public class WordCubeSolver {
 20 
 21     private enum FILE {
 22 
 23         CONNECTIVES("connectives"), PROPERNAMES("propernames"), WORDS("web2"), WORDS2("web2a");
 24 
 25         FILE(String value) {
 26             fileName = value;
 27         }
 28         private String fileName;
 29 
 30         @Override
 31         public String toString() {
 32             return this.fileName;
 33         }
 34     }
 35 
 36     public static void main(String[] args) {
 37         long startTime = System.nanoTime();
 38         if (args == null || args.length < 2 || args[0].length() != 9) {
 39             throw new IllegalArgumentException("Usage: java WordCubeSolver CUBE_AS_9_CHAR_STRING PATH_TO_DICT_ROOT");
 40         }
 41         
 42         // Load dictionary to memory
 43         Set<String> dictionary = loadDictionary(args[1]);
 44 
 45         // Generate all unique, sorted permutations for each case
 46         Set<String> fourLetterWords  = generateWords(toStringArray(args[0]), 4, args[0].charAt(4) + "");
 47         Set<String> fiveLetterWords  = generateWords(toStringArray(args[0]), 5, args[0].charAt(4) + "");
 48         Set<String> sixLetterWords   = generateWords(toStringArray(args[0]), 6, args[0].charAt(4) + "");
 49         Set<String> sevenLetterWords = generateWords(toStringArray(args[0]), 7, args[0].charAt(4) + "");
 50         Set<String> eightLetterWords = generateWords(toStringArray(args[0]), 8, args[0].charAt(4) + "");
 51         Set<String> nineLetterWords  = generateWords(toStringArray(args[0]), 9, args[0].charAt(4) + "");
 52 
 53         System.out.println("Words found in the dictionary for the given Word Cube: ");
 54         // Check if any of the generated words is part of the dictionary
 55         check(fourLetterWords, dictionary);
 56         check(fiveLetterWords, dictionary);
 57         check(sixLetterWords, dictionary);
 58         check(sevenLetterWords, dictionary);
 59         check(eightLetterWords, dictionary);
 60         check(nineLetterWords, dictionary);
 61         
 62         long endTime = System.nanoTime();
 63         System.out.println("Done! Elapsed time: " + (endTime - startTime) / (double) (1000000000) + " secs");
 64     }
 65 
 66     private static Set<String> loadDictionary(String pathToDict) {
 67         pathToDict = (pathToDict.endsWith("/")) ? pathToDict : pathToDict + "/";
 68         Set<String> dict = new TreeSet<String>();
 69         for (FILE fileName : FILE.values()) {
 70             try {
 71                 BufferedReader input = new BufferedReader(new FileReader(pathToDict + fileName.toString()));
 72                 String line = null;
 73                 while ((line = input.readLine()) != null) {
 74                     dict.add(line.trim());
 75                 }
 76                 input.close();
 77             } catch (IOException exception) {
 78                 System.out.println("The dictionary couldn't be read!");
 79                 System.exit(1);
 80             }
 81         }
 82 
 83         return dict;
 84     }
 85 
 86     private static void check(Set<String> words, Set<String> dict) {
 87         for (String word : words) {
 88             if (dict.contains(word)) {
 89                 System.out.println(word);
 90             }
 91         }
 92     }
 93 
 94     private static Set<String> generateWords(String[] elements, int k, String mandatory) {
 95         List<String> combinations = new ArrayList<String>();
 96         int[] indices;
 97         CombinationGenerator x = new CombinationGenerator(elements.length, k);
 98         StringBuffer combination;
 99         while (x.hasMore()) {
100             combination = new StringBuffer();
101             indices = x.getNext();
102             for (int i = 0; i < indices.length; i++) {
103                 combination.append(elements[indices[i]]);
104             }
105             if (combination.indexOf(mandatory) == -1) {
106                 continue;
107             }
108             combinations.add(combination.toString());
109         }
110 
111         Set<String> permutations = new TreeSet<String>();
112 
113         // Unique, sorted permutations for each combination
114         for (String comb : combinations) {
115             int[] pos;
116             String[] combElements = toStringArray(comb);
117             PermutationGenerator permEngine = new PermutationGenerator(combElements.length);
118             StringBuffer permutation;
119             while (permEngine.hasMore()) {
120                 permutation = new StringBuffer();
121                 pos = permEngine.getNext();
122                 for (int i = 0; i < pos.length; i++) {
123                     permutation.append(combElements[pos[i]]);
124                 }
125                 permutations.add(permutation.toString());
126             }
127         }
128 
129         return permutations;
130     }
131 
132     private static String[] toStringArray(String input) {
133         String[] result = new String[input.length()];
134         for (int i = 0; i < result.length; i++) {
135             result[i] = input.charAt(i) + "";
136         }
137         return result;
138     }
139 }
140 
141 // Permutation Generator by Michael Gilleland.
142 // Read more at http://www.merriampark.com/perm.htm
143 class PermutationGenerator {
144 
145     private int[] a;
146     private BigInteger numLeft;
147     private BigInteger total;
148 
149     public PermutationGenerator(int n) {
150         if (n < 1) {
151             throw new IllegalArgumentException("Min 1");
152         }
153         a = new int[n];
154         total = getFactorial(n);
155         reset();
156     }
157 
158     public final void reset() {
159         for (int i = 0; i < a.length; i++) {
160             a[i] = i;
161         }
162         numLeft = new BigInteger(total.toString());
163     }
164 
165     public BigInteger getNumLeft() {
166         return numLeft;
167     }
168 
169     public BigInteger getTotal() {
170         return total;
171     }
172 
173     public boolean hasMore() {
174         return numLeft.compareTo(BigInteger.ZERO) == 1;
175     }
176 
177     private static BigInteger getFactorial(int n) {
178         BigInteger fact = BigInteger.ONE;
179         for (int i = n; i > 1; i--) {
180             fact = fact.multiply(new BigInteger(Integer.toString(i)));
181         }
182         return fact;
183     }
184 
185     public int[] getNext() {
186 
187         if (numLeft.equals(total)) {
188             numLeft = numLeft.subtract(BigInteger.ONE);
189             return a;
190         }
191 
192         int temp;
193         int j = a.length - 2;
194         while (a[j] > a[j + 1]) {
195             j--;
196         }
197 
198         int k = a.length - 1;
199         while (a[j] > a[k]) {
200             k--;
201         }
202 
203         temp = a[k];
204         a[k] = a[j];
205         a[j] = temp;
206 
207         int r = a.length - 1;
208         int s = j + 1;
209 
210         while (r > s) {
211             temp = a[s];
212             a[s] = a[r];
213             a[r] = temp;
214             r--;
215             s++;
216         }
217 
218         numLeft = numLeft.subtract(BigInteger.ONE);
219         return a;
220     }
221 }
222 
223 // Combinations Generator by Michael Gilleland.
224 // Read more at http://www.merriampark.com/comb.htm
225 class CombinationGenerator {
226 
227     private int[] a;
228     private int n;
229     private int r;
230     private BigInteger numLeft;
231     private BigInteger total;
232 
233     public CombinationGenerator(int n, int r) {
234         if (r > n) {
235             throw new IllegalArgumentException();
236         }
237         if (n < 1) {
238             throw new IllegalArgumentException();
239         }
240         this.n = n;
241         this.r = r;
242         a = new int[r];
243         BigInteger nFact = getFactorial(n);
244         BigInteger rFact = getFactorial(r);
245         BigInteger nminusrFact = getFactorial(n - r);
246         total = nFact.divide(rFact.multiply(nminusrFact));
247         reset();
248     }
249 
250     public final void reset() {
251         for (int i = 0; i < a.length; i++) {
252             a[i] = i;
253         }
254         numLeft = new BigInteger(total.toString());
255     }
256 
257     public BigInteger getNumLeft() {
258         return numLeft;
259     }
260 
261     public boolean hasMore() {
262         return numLeft.compareTo(BigInteger.ZERO) == 1;
263     }
264 
265     public BigInteger getTotal() {
266         return total;
267     }
268 
269     private static BigInteger getFactorial(int n) {
270         BigInteger fact = BigInteger.ONE;
271         for (int i = n; i > 1; i--) {
272             fact = fact.multiply(new BigInteger(Integer.toString(i)));
273         }
274         return fact;
275     }
276 
277     public int[] getNext() {
278 
279         if (numLeft.equals(total)) {
280             numLeft = numLeft.subtract(BigInteger.ONE);
281             return a;
282         }
283 
284         int i = r - 1;
285         while (a[i] == n - r + i) {
286             i--;
287         }
288         a[i] = a[i] + 1;
289         for (int j = i + 1; j < r; j++) {
290             a[j] = a[i] + j - i;
291         }
292 
293         numLeft = numLeft.subtract(BigInteger.ONE);
294         return a;
295 
296     }
297 }