4
\$\begingroup\$

This is a boggle solver in Java. I would like code reviewers to optimize the code, suggest better coding practices, and help make it cleaner.

I am also unsure of the complexity and would appreciate an explanation of it.

public final class Boggle {

    private static final NavigableSet<String> dictionary;
    private final Map<Character, List<Character>> graph = new HashMap<Character, List<Character>>();


    static {
        dictionary = new TreeSet<String>();
        try {
            FileReader fr = new FileReader("/Users/ameya.patil/Desktop/text.txt");
            BufferedReader br = new BufferedReader(fr);
            String line;
            while ((line = br.readLine()) != null) {
                dictionary.add(line.split(":")[0]);
            }
        } catch (Exception e) {
            throw new RuntimeException("Error while reading dictionary");
        }
    }

    private Boggle() {}

    public static List<String> boggleSolver(char[][] m) {
        if (m == null) {
            throw new NullPointerException("The matrix cannot be null");
        }
        final List<String> validWords = new ArrayList<String>();
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[0].length; j++) {
                solve(m, i, j, m[i][j] + "", validWords);
            }
        }
        return validWords;
    }

    private static void solve(char[][] m, int i, int j, String prefix, List<String> validWords) {
        assert m != null;
        assert validWords != null;

        for (int i1 = Math.max(0, i - 1); i1 < Math.min(m.length, i + 2); i1++) {
            for (int j1 = Math.max(0, j - 1); j1 < Math.min(m[0].length, j + 2); j1++) {
                if (i1 != i || j1 != j) {
                    String word = prefix+ m[i1][j1];

                    if (dictionary.contains(word)) {
                        validWords.add(word);
                    }

                    if (dictionary.subSet(word, word + Character.MAX_VALUE).size() > 0) {
                        solve(m, i1, j1, word, validWords);
                    }
                }
            }
        } 
    }

    public static void main (String[] args) {
          char[][] board = { {'a', 'b', 'c', 'd' },
                             {'n', 'x', 'p', 'q' },
                             {'k', 't', 'i', 'w' },
                             {'e', 'f', 'g', 's' },
                          };

          List<String> list = Boggle.boggleSolver(board);
          for (String str :  list) {
              System.out.println(str);
          }
    }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Rule of thumb: If you need to suffix your variable names with numbers, you're doing something wrong. \$\endgroup\$ – Bobby Oct 22 '13 at 8:22
  • \$\begingroup\$ not too sure that I understand yoru point. please elaborate. \$\endgroup\$ – JavaDeveloper Oct 22 '13 at 16:57
  • 1
    \$\begingroup\$ @JavaDeveloper: Usually, numbers at the end of a variable name are an indication that you really want an array instead of a bunch of separate variables with numbers at the end. Your i1, j1 doesn't fall into this pattern, but it would be better to use i, j for those and something else for the i, j parameters for solve(). (Maybe x/y, height/width, or horizontal_offset/vertical_offset?) \$\endgroup\$ – Michael Shaw Oct 22 '13 at 19:59
5
\$\begingroup\$

According to the rules, you can only use each tile once per word. You haven't attempted to keep track of tile usage.

Consider storing your dictionary using a trie, such as the implementation in Apache Commons. It should provide an efficient .prefixMap(), which is like your dictionary.subSet().

You defined graph, but you never use it.

I think that an object-oriented interface would feel natural. Create a new instance of Boggle by passing the char[][] matrix to the constructor.

Method names should be verbs, and shouldn't be redundant with the class name. Therefore, .boggleSolver() should just be .solve().

The purpose of the loop…

for (int i1 = Math.max(0, i - 1); i1 < Math.min(m.length, i + 2); i1++) {
    for (int j1 = Math.max(0, j - 1); j1 < Math.min(m[0].length, j + 2); j1++) {
        if (i1 != i || j1 != j) {
            // loop body
        }
    }
}

… is to iterate through all the neighbours of tile (i, j). A comment to that effect would be appreciated. Also, I would invert the if-condition to avoid a level of nesting:

// Iterate through the neighbours of tile (i, j)
for (int i1 = Math.max(0, i - 1); i1 < Math.min(m.length, i + 2); i1++) {
    for (int j1 = Math.max(0, j - 1); j1 < Math.min(m[0].length, j + 2); j1++) {
        // Skip the tile (i, j) itself
        if (i1 == i && j1 == j) continue;

        String word = prefix+ m[i1][j1];
        if (!dictionary.subSet(word, word + Character.MAX_VALUE).isEmpty()) {
            if (dictionary.contains(word)) {
                validWords.add(word);
            }
            solve(m, i1, j1, word, validWords);
        }
}

Note that the dictionary.contains(word) check can be moved inside the !dictionary.subSet(...).isEmpty() check.

\$\endgroup\$
  • \$\begingroup\$ Appreciate all suggestions except the one for using "Trie" what benefit would it provide compared to TreeSet ? Instead treeSet provides a constant lookup time. \$\endgroup\$ – JavaDeveloper Oct 22 '13 at 16:59
  • \$\begingroup\$ No, HashSet provides O(1) lookup time. TreeSet does lookup in O(log n) (where n = number of words), and subset in O(s) (where s = size of subset). A trie does lookup in O(c) (where c = number of characters in word), and subset in O(1). I would say that a trie is the perfectly natural data structure for this problem. \$\endgroup\$ – 200_success Oct 22 '13 at 18:18
0
\$\begingroup\$

Use a factory

Your static initializer for the dictionary has a couple of different ideas trying to come out of it

1) You have non trivial logic to create the object, which implies the existence of a Factory 2) Your current method is really several different ideas

  1. read lines from a file
  2. parse the lines to find words
  3. add the words to a collection
  4. use the collection of words to create the dictionary

So it looks to me as though there ought to be Factory.create(Collection) somewhere to build that dictionary object. There might also be Factory.create(File) to allow you to change what the default file is, Factory.create(BufferedReader) because you really don't care where that reader comes from, and so on.

Neighbors

Your double loop is really trying to express the idea that the next letter in a candidate word must come from one of the neighboring tiles. So the code should say that:

for (GridPosition nextGridPosition : findNeighbors(crntGridPosition)) {
    ...
}

Of course, you don't have the GridPosition(x,y) abstraction teased out yet, so you need to find that as well. Using the char[][] array to specify your test configuration is fine (not my choice, but it gets the job done), but you have either a Factory that creates the board from the array, or a Board object that can set the state of its Dice (depending on how you choose to represent a new game).

If you were really modeling Boggle, rather than just a generic word finding exercise, then you would need 16 Die objects that are each capable of representing 6 Faces (as only the top face matters, you don't need to worry about the geometry of the faces), and your factory method might need to recognize invalid configurations. If you are ignoring those concerns, then Tile is probably a better abstraction than Die/Face

@200_success points out that the rules prevent you from using a tile more than once. In other words, your word search has state. You might keep track of which die you have used by pushing and popping them out of a stack, or you might notice that what you really have going is a state machine, where the states track what other states are allowed. So the state machine probably knows which positions you have visited, and where the valid neighbors are.

It's probably easiest if the state is also tracking the values of the tiles, but that concern could be separated.

solve() should be iterating through states, not calling itself recursively. You are "doing the same thing until the search space is exhausted", not "breaking the problem into smaller sub problems". With only 16 tiles, it doesn't matter much, but thinking clearly about what you are really doing may help make the implementation cleaner.

Stack<State> remainingStates = Stacks.create(Board.initialState());
while(! remainingStates.isEmpty()) {
    State state = remainingStates.pop();

    String candidate = state.getWord();

    if (! dictionary.subSet(candidate, candidate + Character.MAX_VALUE).isEmpty()) {
        if (dictionary.contains(candidate)) {
            validWords.add(candidate);
        }
        remainingStates.pushAll(state.getNeighbors());
    }
}

Bleah, why should the Board code care how dictionary is implemented? The Board wants to know if candidate is a valid word, and if there are any words that begin with candidate. So tease those two ideas into a Dictionary abstraction

    if (! dictionary.hasWordsWithPrefix(candidate) {
        if (dictionary.containsWord(candidate)) {
            validWords.add(candidate);
        }
        remainingStates.pushAll(state.getNeighbors());
    }

With that abstraction in place, the Board code is insulated from Dictionary and Dictionary, so you can experiment as you like.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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