Solving a word search puzzle

Written by (royvanrijn.com) on

Solving a word search puzzle

In the previous post I showed a nice snippet/trick at the bottom of the post to find all the neighbors in a 2D array.

Last week I used this snippet to solve a word search puzzle a colleague created for us as a “Back to work in 2019”-challenge:

The word search puzzle

(Note: Some fellow developer colleagues think that solving the puzzle with code is unfair… heh. really?!)

Reading the lexicon

Here is the complete code:

First we’ll need to read in all the possible words we’re looking for. And using the new Java streams this is very easy. Just download one of the many online word-lists and do the following:

    public static void main(String[] args) throws Exception {

        // Store the words we find here:
        Set<String> foundWords = new HashSet<>();

        // Read in the lexicon, the list of possible words:
        Set<String> lexicon = Files.readAllLines(FileSystems.getDefault().getPath(("Lexicon.txt"))) 
                .stream()                        // Open the file as a stream
                .map(line -> line.toUpperCase()) // Convert all the lines (one word per line) to uppercase
                .collect(Collectors.toSet());    // Store this in a list.

It was never easier in Java to do File IO and manipulate collections. Next I embedded the entire puzzle and turned it into an array of Strings.

        // The puzzle: (yeah, hardcoded, sue me.)
        String[] lines = ("TZKRAMONHSMARIONRDBU\n" +
                          "ARNOSTIASSTUNODJEOFN\n" +
                          "FMAMLAPCNNTPIKETYKXA\n" +
                          "UDHBISMUHBALTIGLCCSK\n" +
                          "HKLANTGERICHTEBBOAER\n" +
                          "YCHAVFCONTEAMSHUFFLE\n" +
                          "MIPXRETHNWSLIISIAEIS\n" +
                          "ZRSEKANFEIEUWUTLBQGW\n" +
                          "RTNPCIHBNLBRDOEDRGAO\n" +
                          "UANRIANAEMLOKLFSIETR\n" +
                          "UPEDMDGCODZUWEATCWCB\n" +
                          "TMOISREKIURBEGNREKGX\n" +
                          "UASROCSRPDWIUNPADOXJ\n" +
                          "JGRFTKIXMLENJRMAGDRU\n" +
                          "CNLBLMRSAAKNYFATMGCS\n" +
                          "GEOOYBAVKNNETXCKXOPT\n" +
                          "ZTVRUNLPVOENIREVLOWU\n" +
                          "COHRDBONSRHVEUDMURCS\n" +
                          "QIBEOVPAPPFACTORYDJO\n" +
                          "MRRLNYTRAPNALGCARIJB\n" +
                          "DIUEGIPHYJEROENAGRUK\n" +
                          "KSCNADINEELTHRANABIK")
                .split("\n");

Finding all the words

Finally we need to traverse all the possible combinations a word can be made and check against the Set of target words. I’m doing this the dumbest way possible.

First I go over each possible start location by enumerating all x/y combinations:

        for(int y = 0; y < lines.length; y++) {
            for(int x = 0; x < lines[0].length(); x++) {

Next I check each direction using the neighbor algorithm from the previous post.

                for(int direction = 0; direction < 9; direction++) {
                    if(direction == 4) continue; // direction 4 is staying still, invalid.

Now we start building the possible word, using two new pointers (tx and ty):

                    int ty = y, tx = x;                      // Create two new pointers
                    String word = "" + lines[ty].charAt(tx); // Start with the initial character

While we are within the bounds of the puzzle we must travel in the current ‘direction’. This is done by adding the direction offset (from previous post) to the tx and ty pointers.

If the word in-progress matches one we’re searching for, add it to the found words list!

                    while(tx > 0 && tx < lines[ty].length() - 1 && ty > 0 &&  ty < lines.length - 1) {

                        // Move in the direction:
                        ty += ((direction%3) - 1);
                        tx += ((direction/3) - 1);

                        // Update the word:
                        word += lines[ty].charAt(tx));

                        // Check against the lexicon:
                        if(lexicon.contains(word)) {

                            // Store the words we found (for later reference):
                            foundWords.add(word);
                        }
                    }

Finally let’s close everything off, for developers with OCD like me:

                }
            }
        }
        // Print the words:
        foundWords.stream().sorted().forEach(System.out::println);
      }

This prints the words, sorted, just as we want. Q.E.D..

Improvements

The way we now iterate over all the possible word hiding places is very very dumb.

There are some obvious improvements to be made here, for example one could place the entire lexicon in a tree-like structure instead of a set of words and stop iterating if the certain branch doesn’t exist.

However, for this puzzle, this challenge, the speed it runs at is good enough!

Entire code:

You can download the complete listing here: PuzzleSolver.java