2
\$\begingroup\$

The following is my wordsearch solving algorithm. I'd greatly appreciate tips on how to improve it (e.g. improve efficiency, better approach, etc.):

public boolean traverse(Grid grid) {
    for (int r = 0; r < grid.getRows(); r++) {
        for (int c = 0; c < grid.getCols(); c++) {
            for (Direction direction : Direction.values()) {
                currentPoint.y = r;
                currentPoint.x = c;
                this.direction = direction;

                if (find(grid, currentPoint, 0)) {
                    for (Point point : consideredPoints) {
                        grid.markLetterAt(point);
                    }

                   return true;
                }
            }
        }
    }

    return false;
}

Direction is an enum with all the cardinal directions (N, NE, S, NW, etc...). It has a method (updatePoint()) which changes a Point to the direction (e.g. NE does point.y -= 1, point.x += 1)

Here is find:

private boolean find(Grid grid, Point point, int count) {
    if (!grid.isValidLetter(point)) { // Checks if the point is valid (e.g not < 0)
        consideredPoints.clear();
        return false;
    }

    if (grid.getLetterAt(point).equals(word.substring(count, count + 1))) {
        consideredPoints.add(new Point(point));

        if (count == word.length() - 1) {
            return true;
        }

        direction.updatePoint(point);
        return find(grid, point, count + 1);
    }

    consideredPoints.clear();
    return false;
}
\$\endgroup\$
5
\$\begingroup\$
  • You are creating lots of Point() objects. For performance optimization in Java the very first thing is to avoid pressure on the garbage collector.
  • You are doing lots of repeated calculations just for traversing the grid (in several directions). Performance wise it would be much better to transform the whole grid in advance to simplify the traversal calculation. E.g. it is very simple to search only words in East direction in a grid. And searching words in West direction could then be done by mirroring the grid against a vertical axis and searching again in East direction only.
  • For just finding words, you can ignore the grid structure entirely. Take the complete first row as String, append a space, append the complete second row as String and so forth. You get one huge string representing the grid for searching in East direction. Your matching code is simply hugeString.contains(searchWord) (with a bit more complicated calculation of the original row and column information). You can do the same transformation from grid to a single String also for all other directions.
\$\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.