"Word Search" Program

Question

This is kind of like a "word search" problem, the exceptions being that the words may not be in the grid and I am merely required to determine the number of total instances the search terms appear.

Instructions:

Given a two dimensional array of characters, determine the number of instances search terms occur horizontally, vertically, and diagonally, including in reverse directions. Palindromes, or words that are spelled the same both directions, (“TOT”, “RACECAR”, etc.) count as only 1 instance.

An example would be...

Input:

terms: ONE, TWO, FOUR, FIVE, SIX, NINE, IN

E N I N

V E X E

I N N V

F O U R

Output: 8

(ONE: 2, FOUR: 1, FIVE: 1, NINE: 1, IN: 3)

The search terms and grid are hardcoded into the program

Here is my solution:

import java.util.*;

public class PuzzleSolver
{
    public static String[] SEARCH_LIST = {"ONE", "TWO", "FOUR", "FIVE", "SIX", "NINE", "IN"}; //list of words to be searched

    //sample puzzles
    public static char[][] ex1 = new char[][]{
        {'E', 'N', 'I', 'N'}, 
        {'V', 'E', 'X', 'E'}, 
        {'I', 'N', 'N', 'V'},
        {'F', 'O', 'U', 'R'}
        };    

    //holds parameters to use in findDir() for each direction
    //first two parameters govern the horizontal working room
    //second two parameters govern the vertical working room
    //third two parameters govern the next grid element to be analyzed
    public static final int[][] directions = new int[][]{ 
        {1, 0, 1, 0, -1, -1}, //up left
        {1, 0, 0, 0, -1, 0},  //up
        {1, 0, -1, 1, -1, 1},  //up right
        {0, 0, 1, 0, 0, -1},  //left
        {0, 0, -1, 1, 0, 1},  //right
        {-1, 1, 1, 0, 1, -1}, //down left
        {-1, 1, 0, 0, 1, 0},  //down
        {-1, 1, -1, 1, 1, 1}}; //down right

    private static ArrayList<char[]> SEARCH_LIST2;
    private static char puz[][];
    private static int height = 0;
    private static int width = 0;

    public static void main(String args[]){
        System.out.println(searchWords(ex1));       
    }

    /**
     * Find the number of matches in the puzzle
     * 
     * @param puzzle        multidimensional array of characters representing puzzle
     * @return              number of matches found
     */

    public static int searchWords(char[][] puzzle){
        puz = puzzle;
        height = puzzle.length; //attain height of puzzle
        width = puzzle[0].length; //attain width of puzzle

        SEARCH_LIST2 = fixDictionary(); //convert DICTIONARY to ArrayList of char[]

        int numMatches = 0;

        for (int i1 = 0; i1 < height; ++i1){
            for (int i2 = 0; i2 < width; ++i2){
                for (char[] w : SEARCH_LIST2){
                    numMatches = numMatches + scanSpaceForWord(i1, i2, w);
                }
            }
        }

        return numMatches;
    }

    /**
     * Converts String[] DICTIONARY of words to be searched into an ArrayList of char[]
     * 
     * @return      The converted ArrayList of char[]
     * @see         PuzzleSolver#SEARCH_LIST
     */
    private static ArrayList<char[]> fixDictionary(){
        ArrayList<char[]> result = new ArrayList<char[]>();

        for (int i = 0; i < SEARCH_LIST.length; ++i){
            result.add(SEARCH_LIST[i].toCharArray());
        }

        return result;
    }

    /**
     * Scan space for instances of a single word
     * 
     * @param i1        First index of space
     * @param i2        Second index of space
     * @param word      Word to search for
     * @return          Number of occurrences of word
     */
    private static int scanSpaceForWord(int i1, int i2, char[] word){
        if (word.length > 1){
            //if word length is greater than 1
            int numMatches = 0;

            //Find word for each of 8 directions from the space. 
            //Directions numbered 1 - 4 and 6 - 9. 5 is the space itself.
            for (int x = 0; x < 4; ++x){
                numMatches = numMatches + findDir(i1, i2, word, directions[x]);
            }

            if (!isPalindrome(word)){
                for (int x = 4; x < 8; ++x){
                    numMatches = numMatches + findDir(i1, i2, word, directions[x]);
                }           
            }

            return numMatches;
        }
        else{
            //if word is only a single character
            if (word[0] == puz[i1][i2]){
                return 1;
            }
            else return 0;
        }       
    }

    /** 
     * Determine if word is a palindrome
     *
     * @param word      word to be evaluated
     * @return          true if word is palindrome
     */
    private static boolean isPalindrome(char[] word){
        int len = word.length;
        int half = len/2;

        for (int i = 0; i < half; ++i){ //for each first half of elements
            if (word[i] != word[len - 1 - i]) return false; //if a nonmatch found
        }

        return true; //no nonmatches found
    }

    /**
     * Finds a word moving a specific direction from a space
     * 
     * @param i1        First index of space
     * @param i2        Second index of space
     * @param word      Word to be searched
     * @param dir       Direction (Up Right, Up, Down, Down Right, etc.) to evaluate. 
     * @return          Return 1 if match found, otherwise 0
     * 
     * @see             PuzzleSolver#directions
     */   
    private static int findDir(int i1, int i2, char[] word, int[] dir){
        int h = (dir[0] * (i1 + 1)) + (dir[1] * (height + 1));
        int w = (dir[2] * (i2 + 1)) + (dir[3] * (width + 1));   

        //verify that there exists enough grid room
        if (h > 0 && w > 0){
            if (word.length > h || word.length > w){ //if word is longer than grid room         
                return 0; 
            }           
        }
        else if (h > 0 && w == 0){
            if (word.length > h){ //if word is longer than grid room        
                return 0; 
            }           
        }
        else if (h == 0 && w > 0){
            if (word.length > w){ //if word is longer than grid room        
                return 0; 
            }           
        }
        else if (h == 0 && w == 0){ //if there is no grid room      
            return 0;           
        }
        else {
            System.out.println(("findDir() - invalid h and w values"));
            System.exit(1);
        }

        //search for mismatches
        for (int i = 0; i < word.length; ++i){ //if mismatch is found
            if (word[i] != puz[i1 + (i * dir[4])][i2 + (i * dir[5])]) return 0;
        }

        return 1; //if no mismatch found

    }
}

How could this program be improved? What are problems with the coding style? What are some better data structures to use? Etc.

Answer 1

General

This is a nice challenge. Your algorithm/approach to the solution is a good one in general (it can be tweaked a bit), but your implementation is a little ... spoiled... by using the static variable space for storing state. Your mixed-up use of naming conventions for variables does not help either. Some of the content belongs in the static space, like SEARCH_LIST, ext1, and directions, but the other static variables are not statics, or should not be.

You should consider creating an instance of your PuzzleSolver class for the problem, and then using that instance to manage state, instead of keeping things static. For example, if your main method was:

public static void main() {
    PuzzleSolver solver = new PuzzleSolver(SEARCH_LIST, SEARCH_GRID);
    Map<String, Integer> solutions = solver.solve();
    int count = 0;
    String detail = "Solutions: "
    for (Map.Entry<String, Integer> entry : solutions.entrySet()) {
        detail += entry.key() + ": " + entry.Value();
        count += entry.value();
    }
    System.out.println(count);
    System.out.println(detail);
}

I know that's not the expected output of the test, but it helps to show you that the solution should be done in one place (the PuzzleSolver instance) and as a reusable mechanism (so that you can create different instances of PuzzleSolver for different word lists, or grids.

Now, about the algorithm. Your logic for building the search query arrays is a good one... but the implementation needs some small tweaks, and the input should be parameterized. Basically, this code is OK, but could be better:

private static ArrayList<char[]> fixDictionary(){
    ArrayList<char[]> result = new ArrayList<char[]>();

    for (int i = 0; i < SEARCH_LIST.length; ++i){
        result.add(SEARCH_LIST[i].toCharArray());
    }

    return result;
}

First up, let's reduce "concrete" collections to their interfaces. The ArrayList return and variable declarations should be just List. There's no need to specify the generic type of an object on the right-side of an assignment if the type can be inferred - you can use the <> "diamond operator" instead. Note, you can also use an "enhanced for loop" instead of the i iteration. The SEARCH_LIST should be a parameter too:

private static List<char[]> fixDictionary(String[] words){
    List<char[]> result = new ArrayList<>();

    for (String word : words){
        result.add(word.toCharArray());
    }

    return result;
}

Now you can get the same result by calling:

List<char[]> tofind = fixDictionary(SEARCH_LIST);

Algorithm

Your code is searching the grid in all directions for each word. That's not a bad approach (it gets the right answer), but it becomes complicated because of the palindromes aspect of the problem, and because you have to search in each direction for each word.

There's a relatively simple trick you can do to drastically reduce the search cost of the problem.... you can search only right, down, and diagonally down and diagonally up to the right (i.e. half of the directions to search), and you can remove the palindrome checking, if you compute the palindromes before searching. So, for example, instead of searching for nine in all directions, search for nine in half the directions, and enin in those same directions too. If the search word is a palindrome (racecar) then only search for it once....

You can put all that logic in to the fixDictionary method too:

private static List<char[]> fixDictionary(String[] words){
    List<char[]> result = new ArrayList<>();

    for (String word : words){
        result.add(word.toCharArray());
        String reverse = new StringBuilder(word).reverse().toString();
        if (!reverse.equals(word)) {
            result.add(reverse.toCharArray());
        }
    }

    return result;
}

Now your search arrays contain the forward, and if the word is not a palindrome, it also contains the backward versions of the search list.

Now you can remove half the directions to check, and you can remove your post-search palindrome removal logic.