Cryptolexo, playing with string arrays

Hello everyone! Long time no see…

So, the last few days I was playing with the idea of creating a random word-search puzzle based on a set of words.

For the ones that don’t know what a word-search puzzle is, let me quote Wikipedia:

A word search, word find, word seek, word sleuth or mystery word puzzle is a
word game that consists of the letters of words placed in a grid, which usually
has a rectangular or square shape. The objective of this puzzle is to find and
mark all the words hidden inside the box. The words may be placed horizontally,
vertically, or diagonally. Often a list of the hidden words is provided, but
more challenging puzzles may let the player figure them out.

from Wikipedia

Now, all of us know what a word-search puzzle is! My naive implementation creates a word-search puzzle from a given set of words, with vertically and horizontally hidden words read from left to right.

The name Cryptolexo comes from the Greek word Κρυπτόλεξο which is used to describe that kind of games.

Above, I am going to introduce you the goals of the implementation and some of the challenges.

Challenge

For starters, when the 2D array is empty it is easy to add a word. We can surely guarantee that it will fit unless the word’s length excess the array’s length. It is also pretty trivial to choose at random if the world will be placed vertically or horizontally and also choose at random a starting place.

So, let’s say we have a 10x10 array and we want to add the word test. An accepted solution could place the word in the 3rd row from the 2 to 5 column but it couldn’t place the word to the 3rd row from the 9 to 12 column because the array isn’t so big.

That was the easy part. What if when we add a word to a populated array a collision happens? That’s the challenge and in the next section I am going to describe my approach.

Handling the Collisions

Here I am going to enumerate the possible cases that we may face with examples!

Adding a Word that Fits after Another

word after another

Adding a Word that Fits before Another

word before another

Failing to Add a Word

word fails to fit

Merging Words

merging words

Add Word to Row Algorithm

public static int getColInRowWithCollision(char[][] array, String word, int r) {
  // start from all possible places
  for(int i=0;i<array[0].length-word.length();i++) {
    int arrayPointer = i;
    int wordPointer = 0;
    while(wordPointer < word.length() && arrayPointer < array[0].length) {
      if(array[r][arrayPointer] == 0 ||
          array[r][arrayPointer] == word.charAt(wordPointer)) {
        wordPointer++;
        if(wordPointer==word.length()) {
          return arrayPointer - word.length() + 1;
        }
      } else {
        wordPointer = 0;
      }
      arrayPointer++;
    }
  }
  return -1;
}

As you can see this method returns the column where is possible to place the word even by merging it and -1 otherwise. It needs to run (N-W)*W times, where N the length of the array and W the length of the word. In the worst case scenario it needs to run N^2/2 times which is bad but pretty acceptable for this size of problems. Even a 60x60 array can be filled very quickly.

I was using originally a String array[] because I wrongly thought it to be more convenient. I was wrong and more importantly char[] uses less memory and the character check is much faster.

Here is a simple demo from the getColInRowWithCollision() in usage:

algorithm demo

Conclusion

With that building blocks ready the construction of a word puzzle is very easy. In my implementation the code that creates the puzzle tries X times to place a word in a random place and if it fails then it searches exhaustively all the possible places.

This is relatively very slow but the array is also small and in practice it won’t happen frequently except if the puzzle is too small and/or the word list very large.

Fill free to take a pick at Cryptolexo here. Inside the main method there are a few examples of usage! The code is licensed under GPLv3.