"Word Search" Program

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 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(searchW

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 solutions = solver.solve();
    int count = 0;
    String detail = "Solutions: "
    for (Map.Entry 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 fixDictionary(){
    ArrayList result = new ArrayList();

    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 fixDictionary(String[] words){
    List result = new ArrayList<>();

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

    return result;
}

Now you can get the same result by calling:

List 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 fixDictionary(String[] words){
    List 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.

StackExchange Code Review Q#154852, answer score: 3