"Word-Target" Puzzle Solver in Java

Question

Have recently been writing a few puzzle solvers in Java, this is my latest attempt. It solves the "Word-Target" puzzle found in some newspapers. You may have seen it before:

Words must be found by using any of the letters in the grid in any order, however each word must contain the centre letter, and must be at least 4 characters long.

The program takes in two text files, one dictionary text file (must be in alphabetical order already) and one puzzle text file:

puzzle.txt:

R O Y
S V N
E U L

I use the dictionary located here: dict2.txt

Program output:

~~~$ java WordTarget dict2.txt puzzle.txt 
WORD GRID:
r o y
s V n
e u l

Found 38 results with 4 letters or more
Found 9 results with 4 letters: 
 - envy
 - levy
 - love
 - oven
 - over
 - revs
 - rove
 - very
 - vole
Found 12 results with 5 letters: 
 - envoy
 - lover
 - loves
 - nervy
 - novel
 - ovens
 - overs
 - ovule
 - roves
 - servo
 - solve
 - voles
Found 12 results with 6 letters: 
 - envoys
 - louver
 - lovers
 - novels
 - overly
 - ovules
 - sloven
 - solver
 - survey
 - velour
 - venous
 - voyeur
Found 4 results with 7 letters: 
 - louvers
 - nervous
 - velours
 - voyeurs
Found 0 results with 8 letters: 
Found 1 results with 9 letters: 
 - nervously
Time taken: 524 milliseconds
Memory used: 11 MB

WordTarget.java:

/**
 * Class Name:        WordTarget
 *
 * @author:           Thomas McKeesick
 * Creation Date:     Monday, February 16 2015, 02:25 
 * Last Modified:     Tuesday, March 03 2015, 11:25
 * 
 * Class Description: A Java class that solves the 9 letter "Word-Target"
 *                    puzzle.
 *
 * @version 0.2.0
 */

import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;

import java.io.FileReader;
import java.io.BufferedReader;

import java.io.IOException;

public class WordTarget {

    private static int MIN_LENGTH = 4;
    private static List<String> dict;

    public static void main(String[] args) {

        if( args.length < 2 ) {
            System.err.println("Usage: java Wordsquare <dictionary> <puzzle>");
            System.exit(1);
        } else if( args.length == 3 ) {
            MIN_LENGTH = Integer.parseInt(args[2]);
        }

        long startTime = System.currentTimeMillis();

        dict = loadDict(args[0]);
        char[] grid = loadPuzzle(args[1]);
        List<String> results = findStrings(grid);

        System.out.println("WORD GRID:");
        System.out.println(grid[0] + " " + grid[1] + " " + grid[2] + "\n" +
                           grid[3] + " " + grid[4] + " " + grid[5] + "\n" +
                           grid[6] + " " + grid[7] + " " + grid[8] + "\n");

        //Removes duplicates from array, then adds back into original array
        HashSet<String> set = new HashSet<String>();
        set.addAll(results);
        results.clear();
        results.addAll(set);

        Collections.sort(results);

        System.out.println("Found " + results.size() + " results with " +
                           MIN_LENGTH + " letters or more");

        for(int i = MIN_LENGTH; i <= grid.length; i++) {
            ArrayList<String> tmp = new ArrayList<String>();
            for(String s: results) {
                if(s.length() == i ) {
                    tmp.add(s);
                }
            }
            System.out.println("Found " + tmp.size() + " results with " + i +
                               " letters: ");
            for(String s: tmp) {
                System.out.println(" - " + s);
            }
        }

        Runtime r = Runtime.getRuntime();
        r.gc();

        long endTime = System.currentTimeMillis();
        System.out.println("Time taken: " + (endTime - startTime) + 
                           " milliseconds");
        System.out.println("Memory used: " + 
                    ((r.totalMemory() - r.freeMemory())/1024/1024) + " MB");
        System.exit(0);
    }

    /**
     * Private method to load a puzzle text file into a char array
     * @param filename The name of the file to load
     * @return The char array containing the text file, with the "centre" letter
     *         in upper case to avoid finding duplicate letters when searching
     *         in the permute method.
     */
    private static char[] loadPuzzle(String filename) {
        char[] grid = new char[9];
        try {
            BufferedReader in = new BufferedReader(new FileReader(filename));

            String line;
            int n = 0;
            while( (line = in.readLine()) != null ) {
                String[] row = line.split("\\s");
                for(int i = 0; i < 3; i++) {
                    if( n != MIN_LENGTH ) {
                        grid[n] = Character.toLowerCase(
                                                row[i].charAt(0));
                    } else {
                        grid[n] = Character.toUpperCase(
                                                row[i].charAt(0));
                    }
                    n++;
                }
            }
        } catch( IOException e ) {
            System.err.println("A file error occurred: " + filename +
                               "Error message: " + e.getMessage() + 
                               e.getStackTrace());
            System.exit(1);
        }
        return grid;
    }

    /**
     * A method that loads a dictionary text file into a tree structure
     * @param filename The dictionary file to load
     * @return The ArrayList containing the dictionary
     */
    private static List<String> loadDict(String filename) {
        dict = new ArrayList<String>();
        try {
            BufferedReader in = new BufferedReader(
                    new FileReader(filename));
            String word;
            while( (word = in.readLine()) != null ) {
                dict.add(word);
            }
        } catch( IOException e ) {
            System.err.println("A file error occurred: " + filename );
            System.exit(1);
        }
        return dict;
    }

    /**
     * Private method to call the permute function, provides a List to
     * populate and the "centre" character.
     * @param grid The puzzle grid to solve
     * @return The List containing the words found in the puzzle
     */
    private static List<String> findStrings(char[] grid){
        List<String> tmp = new ArrayList<String>();
        String str = new String(grid);
        char centre = grid[4];
        tmp = permute(tmp, str, MIN_LENGTH, 
                String.valueOf(centre));
        return tmp;        
    }

    /**
     * Outer function to call the recursive permute function
     * @param words The ArrayList to populate
     * @param str   The string containing the letters to permute, the "centre"
     *              letter is capitalised.
     * @param minLength The minimum amount of letters that a word must contain
     * @param centre The "centre" letter that each word must contain
     * @return The ArrayList of all dictionary words found in str
     */
    private static List<String> permute(List<String> words, String str, 
                                        int minLength, CharSequence centre) {
        permute("", str, words, minLength, centre);
        return words;
    }

    /**
     * The recursive permute function. Generates every permutation of every
     * length from 0-the length of the string. Checks whether each string is
     * larger than the minimum length supplied, contains the "centre" letter,
     * and is contained in the dictionary. If so, adds it to the ArrayList
     * of strings to be returned.
     */
    private static void permute(String prefix, String str, List<String> words, 
                                int minLength, CharSequence centre) {
        int length = str.length();
        if(prefix.length() >= minLength && prefix.contains(centre) && 
                Collections.binarySearch(dict, prefix.toLowerCase()) >= 0) {
            words.add(prefix.toLowerCase());
        }
        if( length != 0 ) {
            for(int i = 0; i < length; i++) {
                permute(prefix + str.charAt(i), 
                    str.substring(0, i) + str.substring(i+1, length),
                    words, minLength, centre);
            }
        }
    }
}

I was just looking for any general advice on style or efficiency. I like the elegance of the recursive solution currently but it still checks 986 410 strings. Was thinking of creating a "reverse dictionary" of strings that are 3/4 characters long that are impossible starting sequences for words, such as "abx". This could save quite a lot of recursion.

Answer 1

Use the diamond operator <>

You can simplify expressions like these:

HashSet<String> set = new HashSet<String>();
ArrayList<String> tmp = new ArrayList<String>();

Using the diamond operator <>:

HashSet<String> set = new HashSet<>();
ArrayList<String> tmp = new ArrayList<>();

Use interface types instead of implementations

At several places, for example in the examples in the previous section you declared variables using concrete implementation types. It's recommended to declare variables using interface types instead:

Set<String> set = new HashSet<>();
List<String> tmp = new ArrayList<>();

Printing arrays

This probably won't work the way you want it:

System.err.println("A file error occurred: " + filename +
        "Error message: " + e.getMessage() +
        e.getStackTrace());

e.getStackTrace() returns a StackTraceElement[], and arrays in Java don't have a useful toString implementation. You can fix that by wrapping in Arrays.toString(...):

System.err.println("A file error occurred: " + filename +
        "Error message: " + e.getMessage() +
        Arrays.toString(e.getStackTrace()));

Avoid System.exit (maybe except in main)

Whenever possible, avoid using System.exit. It's best to organize programs in a way that the methods naturally return when they have accomplished their jobs, and the main method simple reaches its end.

Note that the System.exit(0); at the end of the main method is unnecessary.

In loadDict, if something goes wrong while loading the dictionary it exits. This method should not have the responsibility of controlling the program flow. It would be better to let it throw an exception, and let the caller decide how to handle the problem.

In the main method it's acceptable to call System.exit(1), as the main method is in charge of the program's flow. You can also just not catch the exception thrown by loadDict, let the application crash with a stack trace. It might not be very friendly, but it won't be very different from what you're doing now, printing the stack trace.

Using a Scanner

Reading from a file line by line is a lot simpler using a Scanner:

Scanner scanner = new Scanner(new File(filename));
while (scanner.hasNextLine()) {
    dict.add(scanner.nextLine());
}

Answer 2

One thing should do is specify constant, unchanging variables as final:

private static final int MIN_LENGTH = 4;

Now, you will not be allowed to modify the variable.

You spread your statements over multiple lines too often; many of these would look better on one line, including these:

BufferedReader in = new BufferedReader(new FileReader(filename));

tmp = permute(tmp, str, MIN_LENGTH, String.valueOf(centre));

Also, you have a large main() method. You should delegate most of the work to other methods and just use main() to start the program.

It is excellent that you always use braces, even around one-line if statements and loops; this will help you prevent errors.