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.
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());
}
}
}
