5
\$\begingroup\$

This is a challenge up on Programming Praxis, however there are no Java solutions, and there are few Java implementations elsewhere on the internet.

Most of these implementations simply search the grid for the words that the user is supposed to find. This program finds ALL of the dictionary words that are in the word search puzzle, not just the ones that are supposed to be found. As a result the code is a bit lengthy; this is also due to the commenting.

EDIT: The dictionary file must be in alphabetical order, as Collections.binarySearch is used. The program used my Red-Black implementation yesterday but have removed this in favour of ArrayList so it now only requires the one file.

The source files and dictionary/puzzle files can be found here.

GitHub

Usage & Output:

Input file (lovatts 18x18):

11 11
B E I E L P I T L U M
R S P E C I A L M C D
R R U N C O M M O N A
S E A N A M E N D T S
E V T L D O T S I C S
G I F L U R A D F N O
N D F E A G Y D Y I R
A D E S U F N O C T T
R A T M O S A I C S E
T T E T A R A P S I D
S H E E T A I V E D R

The first two numbers represent the number of rows and the number of columns respectively. The rest of the file is the puzzle grid, with the characters separated by spaces. I could do it with no spaces but it makes the original file much more human-readable this way.

Command and output:

java WordSearch dictionary.txt lovatts18.txt 7

    A B C D E F G H I J K 
   ----------------------
01 |B E I E L P I T L U M 
02 |R S P E C I A L M C D 
03 |R R U N C O M M O N A 
04 |S E A N A M E N D T S 
05 |E V T L D O T S I C S 
06 |G I F L U R A D F N O 
07 |N D F E A G Y D Y I R 
08 |A D E S U F N O C T T 
09 |R A T M O S A I C S E 
10 |T T E T A R A P S I D 
11 |S H E E T A I V E D R

Searching for words with 7 or more letters:

Found 14 words:

[K, 3 ] -> [K, 10] : ASSORTED
[I, 8 ] -> [C, 8 ] : CONFUSE
[I, 8 ] -> [B, 8 ] : CONFUSED
[J, 2 ] -> [C, 9 ] : CONTRAST
[J, 11] -> [D, 11] : DEVIATE
[K, 10] -> [C, 10] : DISPARATE
[J, 11] -> [J, 4 ] : DISTINCT
[B, 7 ] -> [B, 1 ] : DIVERSE
[D, 9 ] -> [J, 9 ] : MOSAICS
[K, 1 ] -> [D, 1 ] : MULTIPLE
[I, 10] -> [B, 3 ] : SINGULAR
[B, 2 ] -> [H, 2 ] : SPECIAL
[A, 11] -> [A, 5 ] : STRANGE
[C, 3 ] -> [J, 3 ] : UNCOMMON
Time taken: 216 milliseconds
Memory used: 9922 kB

The source code is as follows (all files are available at the link above). I did originally write it without the inner class, but it performs much quicker this way and the memory usage is unchanged.

WordSearch.java

/**
 * Class Name:        WordSearch
 *
 * @author            Thomas McKeesick
 * Creation Date:     Wednesday, January 21 2015, 01:57
 * Last Modified:     Thursday, February 19 2015, 10:02
 *
 * @version 0.2.3     See CHANGELOG
 * Class Description: A java program that will solve a
 *         word search puzzle given in the form of a grid.
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.io.FileReader;
import java.io.BufferedReader;

import java.io.IOException;

public class WordSearch {
    public static class WordInfo {

        private String word;
        private int rowFrom;
        private int rowTo;
        private int colFrom;
        private int colTo;

        WordInfo(String word, int rowFrom, int colFrom, int rowTo, int colTo) {
            this.word = word;
            this.rowFrom = rowFrom;
            this.rowTo = rowTo;
            this.colFrom = colFrom;
            this.colTo = colTo;
        }

        public String getWord() { return word; }
        public int getRowFrom() { return rowFrom; }
        public int getRowTo() { return rowTo; }
        public int getColFrom() { return colFrom; }
        public int getColTo() { return colTo; }

        public String toString() {
            String info = "[" + (char) (colFrom + 'A') + ", " +
                    String.format("%-2s", (rowFrom+1)) + "] -> [" + 
                    (char)(colTo+'A') + ", " + 
                    String.format("%-2s", (rowTo+1)) + "] : " + 
                    word.toUpperCase();
            return info;
        }
        public int compareTo(WordInfo word2) {
            return word.compareTo(word2.word);
        }
    }

    private static int numLetters = 3;

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();

        if( args.length < 2 ) {
            System.err.println("Must input a dictionary AND puzzle" +
                    "file to read");
            System.err.println("Usage: java WordSearch <dictionary> <puzzle>" +
                               "<minimum_number_of_letters>");
            System.exit(1);
        }

        if( args.length == 3 ) {
            numLetters = Integer.parseInt(args[2]);
        }

        ArrayList<String> dict = loadDict(args[0]);
        char[][] grid = loadPuzzle(args[1]);
        ArrayList<WordInfo> solutions = findWords(grid, dict, numLetters);

        printGrid(grid);
        printSolutions(solutions, numLetters);

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

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

    /**
     * A method that loads a dictionary text file into a tree structure
     * @param filename The dictionary file to load
     * @return The Red-Black tree containing the dictionary
     */
    private static ArrayList<String> loadDict(String filename) {
        ArrayList<String> 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;
    }

    /**
     * Loads a word puzzle from a text file into a 2D char array
     * @param filename The puzzle file to load
     * @return The word-search puzzle in a char array
     */
    public static char[][] loadPuzzle(String filename) {
        char[][] grid = new char[0][0];
        try {
            BufferedReader in = new BufferedReader(
                    new FileReader(filename));

            String line = in.readLine();

            int rows = Integer.parseInt(line.split(" ")[0]);
            int cols = Integer.parseInt(line.split(" ")[1]); 
            grid = new char[rows][cols];

            int rowNum = 0;
            int colNum = 0;

            while( (line = in.readLine()) != null ) {
                colNum = 0;
                String[] letters = line.split(" ");
                for( String s : letters ) {
                    grid[rowNum][colNum] = 
                            Character.toLowerCase( s.charAt(0) );
                    colNum++;
                }
                rowNum++;
            }
        } catch( IOException e ) {
            System.err.println("A file error occurred: " + filename );
            System.exit(1);
        }
        return grid;
    }

    /**
     * Private method that returns all possible solution strings from the word
     * puzzle
     * @param grid The word puzzle to search
     * @return The ArrayList of strings found by the method
     */
    private static ArrayList<WordInfo> findWords(char[][] grid, 
                                                 ArrayList<String> dict,
                                                 int numLetters) {
        int cols = grid[0].length;
        int rows = grid.length;
        ArrayList<WordInfo> results = new ArrayList<WordInfo>();

        for( int i = 0; i < rows; i++ ) {
            for( int j = 0; j < cols; j++ ) {
                if(i - (numLetters-1) >= 0) {
                    results.addAll(moveN(grid, dict, i, j));
                }
                if(j - (numLetters-1) >= 0) {
                    results.addAll(moveW(grid, dict, i, j));
                }
                if( j - (numLetters-1) >= 0 && i - (numLetters-1) > 0) {
                    results.addAll(moveNW(grid, dict, i, j));
                }
                if( i - (numLetters-1) >= 0 && j + (numLetters-1) < cols) {
                    results.addAll(moveNE(grid, dict, i, j, rows, cols));
                }
            }
        }
        return results;
    }

    /*-----------------------------------------------------------------------\.
     *        MOVE METHODS                                                    |
     *********^^^^^^^^^^^^***************************************************/

    /**
     * Private method that returns all North and reverse-North (South) strings
     * found for the supplied position in the word puzzle
     * @param grid The word puzzle to use
     * @param row The row number of the letter
     * @param col The column number of the letter
     * @return The ArrayList of the north and south strings above the point
     * supplied
     */
    private static ArrayList<WordInfo> moveN(char[][] grid, 
                                             ArrayList<String> dict, 
                                             int row, int col) {

        ArrayList<WordInfo> results = new ArrayList<WordInfo>();
        StringBuilder word = new StringBuilder();
        for( int i = row; i >= 0; i-- ) {
            word.append(grid[i][col]);
            if(word.length() >= numLetters) {
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), 
                                row, col, i, col));
                }
                word.reverse();
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), 
                                i, col, row, col));
                }
                word.reverse();
            }
        }
        return results;
    }

    /**
     * Private method that returns all West and reverse-West (East) strings
     * found for the supplied position in the word puzzle
     */
    private static ArrayList<WordInfo> moveW(char[][] grid, 
                                             ArrayList<String> dict, 
                                             int row, int col ) {

        ArrayList<WordInfo> results = new ArrayList<WordInfo>();
        StringBuilder word = new StringBuilder();

        for( int j = col; j >= 0; j-- ) {
            word.append(grid[row][j]);
            if(word.length() >= numLetters) {
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), 
                                row, col, row, j));
                }
                word.reverse();
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), 
                                row, j, row, col));
                }
                word.reverse();
            }
        }
        return results;
    }

    /**
     * Private method that returns all North-West and reverse-North-West 
     * (South-East) strings found for the supplied position in the word puzzle
     */
    private static ArrayList<WordInfo> moveNW(char[][] grid, 
                                              ArrayList<String> dict,
                                              int row, int col) {

        ArrayList<WordInfo> results = new ArrayList<WordInfo>();
        StringBuilder word = new StringBuilder();

        for( int i = row, j = col; i >= 0 && j >= 0; i--, j-- ) {
            word.append(grid[i][j]);
            if(word.length() >= numLetters) {
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), row, col, i, j));
                }
                word.reverse();
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), i, j, row, col));
                }
                word.reverse();
            }
        }
        return results;
    }

    /**
     * Private method that returns all North-East and reverse-North-East 
     * (South-West) strings found for the supplied position in the word puzzle
     */
    private static ArrayList<WordInfo> moveNE(char[][] grid, 
                                              ArrayList<String> dict, 
                                              int row, int col, 
                                              int numRows, int numCols) {

        ArrayList<WordInfo> results = new ArrayList<WordInfo>();
        StringBuilder word = new StringBuilder();
        for( int i = row, j = col; i >= 0 && j < numCols; i--, j++) {
            word.append(grid[i][j]);
            if(word.length() >= numLetters) {
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), row, col, i, j));
                }
                word.reverse();
                if(Collections.binarySearch(dict, word.toString()) >= 0) {
                    results.add(new WordInfo(word.toString(), i, j, row, col));
                }
                word.reverse();
            }
        }
        return results;
    }

    /*-----------------------------------------------------------------------\.
     *        FORMAT AND PRINT METHODS                                        |
     *********^^^^^^^^^^^^^^^^^^^^^^^^***************************************/

    /**
     * Prints the word search grid in human-readable form with coordinates.
     * All characters in the grid are upper case, rows numbers are alphabetic
     * and colums are integers 
     * @param grid The word search grid to print
     */
    public static void printGrid(char[][] grid) {     
        System.out.print("    ");
        for( int i = 0; i < grid.length; i++ ) {
            System.out.print((char) ('A' + i) + " ");
        }
        System.out.println();
        System.out.print("   ");
        for( int i = 0; i < grid.length; i ++ ) {
            System.out.print("--");
        }
        System.out.println();

        int rowNum = 1;
        for( char[] row : grid ) {
            System.out.printf("%02d |", rowNum);
            for( char c : row ) {
                System.out.print(Character.toUpperCase(c) + " ");
            }
            System.out.println();
            rowNum++;
        }
        System.out.println();
    }

    /**
     * Sorts the solutions into alphabetical order, then prints them to the
     * user
     * @param words The ArrayList of solutions to print 
     */
    public static void printSolutions(ArrayList<WordInfo> words, 
                                      int numLetters) {

        Collections.sort(words, new Comparator<WordInfo>() {
            @Override
            public int compare(WordInfo word1, WordInfo word2) {
                return word1.compareTo(word2);
            }
        });

        System.out.println("Found " + words.size() + " words with " +
                            numLetters + " letters or more");
        for(WordInfo w: words) {
            System.out.println(w.toString());
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$
    /**
     * A method that loads a dictionary text file into a tree structure
     * @param filename The dictionary file to load
     * @return The Red-Black tree containing the dictionary
     */
    private static ArrayList<String> loadDict(String filename) {
        ArrayList<String> 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;
    }

Your Javadoc is out of date. It still thinks that you are returning a tree.

As a general rule, you should return a List (the interface) rather than an ArrayList (the implementation). This will make it much easier to change the implementation in the future.

You are missing an

            in.close();

in your try block.

I actually think that you are better off allowing the exception to create a stack trace and crash the program. While testing this, I was drawing the exception because the file was in the wrong place. Since you don't log the real error anywhere, I had to remove the try/catch block in order to get the error message. If you mark the method as throwing an IOException, it actually makes it easier to debug.

    private static List<String> loadDict(String filename) throws IOException {

Of course, if you do that, you need to mark main as throwing an exception as well.

I tried storing the dictionary in a trie, but it was slower and took more memory than your solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ Even better than in.close() would be try-with-resources. \$\endgroup\$ – 200_success Mar 1 '15 at 11:03
  • \$\begingroup\$ @200_success That sounds like the beginnings of an answer. \$\endgroup\$ – Brythan Mar 1 '15 at 17:01
  • \$\begingroup\$ Cheers for your answer Brythan. I had the loadPuzzle method throw a message with e.getMessage(), and I've done the same now in the loadDict method. Have also changed the ArrayList returns to Lists :) \$\endgroup\$ – tmck-code Mar 2 '15 at 1:07
  • \$\begingroup\$ And you get a tick sir! Thank you very much for your answer, didn't think I was going to get one in the end. CodeReview rules :) \$\endgroup\$ – tmck-code Mar 2 '15 at 21:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.