The timeline for Google Summer of Code is coming to an end, and us interns are piecing together the final touches to our projects for submission. Thanks to the help of my mentors, and the duck sitting on my monitor, the algorithm that beats the heart of Vocab Crosswords in GNOME Crosswords has been tremendous strides in accuracy and testability. The primary focus shifted to getting the algorithm landed by the end of the summer, and working on the frontend of the application post-GSoC.

Unit Tests

At GUADEC, with the help of Federico, I created unit tests to see how my functions reacted in a given circumstance. Jonathan and I worked on creating different circumstances for the run and helper functions.

Optimization

For user optimization, we don’t want to keep the board at a strict 30×30 grid and only allow for the first viable option. We decided to incorporate a new function to trim the dimensions of the generated grids based on the outermost edges of the letters, create a new board based on the newly calculated dimensions, trim that board down respectively, and copy the words over in the exact respective format. This is due to the libipuz grid’s origin point (0, 0) being fixed at the uppermost left corner cell. All in all, the trimming function essentially does this:

Additionally, it is pretty ideal to have some leeway of choice on how you want your puzzle to look. Some puzzles might generate lanky, while others extensively branched out all the way to the maximum borders, and the rest perhaps condensed together. The ability to rearrange the ordering of the words is already a feature in Crosswords thanks to PuzzleTask. But, it is for known grids of typically 15×15 sandwiched together. What is different with the vocab puzzle is that the rearrangement must still respect the same constraints of intersecting at a single letter nodal point, words cannot be on top of nor right next to each other (edge of nodes must respect space), and no islands (all words must share at least one node with another word). For instance, grids A and B here pertain the same words 1 through 6, but these words can connect differently on the graph, producing two options to choose from.

Tested, I achieved these 3 different versions of grids based off the same word bank:

Island Checking

The final component I will implement within GSoC’s timeline is checking for islanding words. Say a user provides a list of words and one word absolutely cannot intersect with any other word, it shares no node. The backtracking algorithm will spend a lot of time trying to place it, or invalidate any graph generation at all. We want to check beforehand if a word would not belong along the rest, and warn the user about it. Because there are many alphabets that exist, we are going to analyze the sets of characters as guint64 bitsets and GHashTable. Every unique character gets its own bit-slot, and every word’s 64-bit mask is compared to available words using bit operations.