https://solver.0xcaff.me/view/valentine
I spent my thanksgiving polishing up this word search solver I built a while back. I originally built it back in high school because I hated word searches. I haven?t had much use for it, but it is a fun project to try new things on. Here are some of the things it can do and how it does them.
The Solver
A word search solver with a nice UI.
solver.0xcaff.me
Solving Word Searches Fast
The problem of solving a word search seems pretty simple. Given a bunch of letters in a grid and a list of words to find, find all positions and orientations of each word in the grid.
Originally, I implemented a brute force algorithm. For every row, column and word it would try to match the word in each of the possible directions until the word no longer matches or an edge of the grid was hit. The time complexity comes out to O(rows * cols * words * directions). In practice, this is pretty fast. The puzzle above is solved in less than 0.2ms. A more complex puzzle with a longer word list like the one below takes a bit over 9ms.
The States. https://solver.0xcaff.me/view/states
I recently learned (in class yes) that there?s a data structure which can make this way faster: tries. A trie can tell you whether a string is a prefix of a value stored in the trie in O(length of prefix). In most cases, it is faster.
A trie is a n-ary tree. Each node holds two pieces of information, whether the node constitutes a complete match and all of the nodes which share the same prefix.
Here orange nodes mean the prefix leading up to this node is a value in the trie.
Once a trie has been constructed checking whether a value is a prefix or entry or both is just a matter of traversing the tree and checking whether you end up at a complete node and whether there are more nodes below the current node.
For example, in the trie with apple, app and apps, the root node is incomplete and has a single child of a. The node 3 deep from the root node is complete meaning ?app? is both in the trie and that ?app? is a prefix to other values in the trie. The right branch below that node is complete and has no children meaning that ?apps? is in the trie, but isn?t a prefix for more values.
Here?s the code for my trie implementation.
The new algorithm builds a trie with the words in the word list. It then goes through every row, column and direction checking if a potential match is a prefix or a value in the trie. This algorithm is practically 2?5x faster for most common puzzles. The improvement becomes much more significant as the size of the word list increases. With over 400k words, the brute force solution takes 25 seconds while the trie solution takes around 2 seconds. This will be useful when adding support for throwing the dictionary at word searches.
There?s still room for improvement here. The trie should probably be using a Tree based map instead of a hash based map. It could also discard higher levels of the trie as we get to deeper levels. It is fast enough for now.
CSS Paint API for Rounded Corners
Matches didn?t always look this nice. Previously, they looked more blocky.
Blocky. Like Minecraft.
This was OK for most cases. But sometimes it was confusing.
The it isn?t clear whether the giant highlighted areas are a stack of horizontal, vertical or diagonal matches. I wasn?t aware of a performant, non-hacky way to accomplish this. Then came the CSS Paint API.
CSS Paint API allows you to programmatically generate an image whenever a CSS property expects an image. Properties like background-image or border-image are usually used with url() to load an image file or with CSS built-in functions like linear-gradient(). Instead of using those, you can now use paint(myPainter) to reference a paint worklet.
https://developers.google.com/web/updates/2018/01/paintapi
The CSS Paint API just landed in Chrome Stable and was the perfect solution to highlight matches with rounded corners. To use CSS Paint, you first register a paint worklet then specify paint(my-painter-name) wherever CSS accepts a background image. The paint worklet exposes a paint function which takes a canvas 2d rendering context, some sizing information and any CSS properties you depend on. The paint function will render stuff to the rendering context and is called whenever an dependent CSS property is changed or when the element is resized.
I wrote a worklet which handles displaying both the matches and the highlighted matches. It takes in a array of arrays specifying matches ([startRow, startCol, endRow, endCol]) and an array of indices of matches which should be highlighted. This information is passed through CSS properties as strings and encoded and decoded using JSON.parse/JSON.stringify.
Now, there are rounded corners.
Much Better.
Here?s the code for the paint worklet.
Unfortunately, only Chrome supports the CSS Paint API right now. There is a polyfill, but I couldn?t get it to work consistently and it seemed kinda slow for this DOM intensive application when it did work. In non-Chrome, you?ll see the blocky version.
Handling Complex State
One of the thing which annoyed me about existing word search solvers is that they all had terrible interfaces. They were ugly, didn?t clearly show the association between words and matches, and used basic textboxes to input word searches. Here?s how I solved the association problem.
So interactive!
Whenever you mouse over a cell in the puzzle, the words for matches over that cell are highlighted, along with the matches. When you mouse over a word in the word list, all of its matches are highlighted.
This app is built with React and the puzzle is rendered using CSS Grid. Early on, I realized that calling render on every node in the puzzle caused considerable jank, even if the nodes didn?t change.
React Dev Tools With Highlight Updates Option
This happened because even though the component tree?s for each node were small, there were a lot of nodes. Work needed to be done to render and diff the virtual DOM. The solution was to move rendering of the nodes in the puzzle to its own component, override shouldComponentUpdate and avoid updating the props on this component at all costs. I did this using React?s new memo helper for functional components.
To avoid updating props on the <PuzzleNodes /> component, the highlight was rendered outside <PuzzleNodes />. In the rounded matches version, matches and highlighted matches are rendered in the background of the container which holds all the elements. In the highlighted matches were rendered along side the nodes in the CSS grid container with some z-index fiddling to get the highlight to go above the match but below the text.
Input Interface
When using existing wordsearch solvers, one problem I faced was that I?d lose track of where I was when entering my puzzle.
To fix this problem, I made sure this word search solver displayed the input box in a square grid instead of a rectangular grid and had sufficient padding around letters. This is closer to the format word searches are commonly represented in making it easier to spot differences between the puzzle and what you typed.
Image Selector Gone
If you?ve checked this thing out before, you might notice the image selector is gone.
Rest In Peace.
The image selector is gone. Though it was awesome when it worked, it only worked sometimes. There were issues with canvas dependencies not installing in CI, a bug in rbush causing the drag selection gesture to not work on some inputs and some change in the coordinates returned by Google Cloud Vision which caused it to stop working for a bunch of test puzzles shortly after I initially released it.
This is cool and definitely saves time, but entering a wordsearch by hand isn?t that hard especially with the awesome input interface and it isn?t like people are solving 1000s of wordsearches a day with this thing so the time saved is collectively a few minutes a year. It is not worth the complexity considering it only works sometimes. Maybe I?ll add it back when I figure out a way to select word searches from images consistently.
Persistence
In an effort to advertise this, I planned to solve word searches which people posted on Reddit and post a link to the solution. A good way to do this would be to add the ability for users to share word searches which they entered. I implemented this using Firebase Firestore.
I was looking forward to trying to use React Hooks with Suspense to make the code as simple as possible, but decided against it because the API for that react cache thing is very unstable. It works well, but the React team has reserved the ability to change it without warning. I ended up just writing some wrapper components to abstract the async parts.
http://solver.0xcaff.me/view/80Tx7pnoO06OfihUb8Ch
Unfortunately, after I implemented the feature, I realized that no one posts word searches on Reddit or even imgur. At least it will be a good way to measure engagement.
Final Words
It doesn?t seem to be dominating the word search world yet. Please help by telling your friends about it.
The Solver
A word search solver with a nice interface.
solver.0xcaff.me
If you want to see the code, check out the project on GitHub. I think the code is clean and beautiful but probably needs more documentation.
0xcaff/wordsearch
A fast, usable wordsearch solver with an interactive, responsive UI. – 0xcaff/wordsearch
github.com
0xcaff/wordsearch-algo
A collection of algorithms for solving wordsearches. – 0xcaff/wordsearch-algo
github.com
If you got here, you probably now know more about word searches than you ever wanted to. Thank you for reading.
