Cheatle

Creating the Dictionary

Cheatle is a word game, and like all word games the list of valid words you choose to accept will have an impact on how fun the game is to play. Make the list too complex and players will feel frustration at never getting a chance. Make the list too easy and players won't feel the satisfaction of winning, so finding the right dictionary was something I spent a lot of time on. My eventual solution was to take the Scrabble dictionary and filter it to comply with the rules of Boggle:

• Words have a minimum length of 3
• Words have a maximum length of 16 (or 17 if using 'QU')
• Words with a 'Q' must be followed by a 'U'

I then needed a way to efficiently store this list of valid words, I used a prefix tree representation so that words sharing the same prefix are stored as efficiently as possible. Every word in the list of valid words is parsed character by character, and inserted into the tree as a child node of the letter before it (or the root node for the first character). The node of the last letter in the word is marked as terminal to indicate a valid word is spelt at that point.

The graph below stores "arc", "art", "arch", "arcs", "arts", and "arty".

Originally I used a more expansive dictionary but the top words were often complex, or non-english. I then tried fixing this problem by creating my own dictionary from the top 20,000 most used english words, then leminizing, adding synonyms, and then comparing to a full dictionary to expand it to include related words. This did solve the problem of solution complexity but there would normally be a few valid words a game that were not present which was very noticeable as a player.

In the end using a Scrabble dictionary seemed like the best balance for the least work.

Generating Game Data

Cheatle is played on a 4x4 grid, with a set of 16 dice which are "rolled" each day to make the game board. The letters on the dice are arranged so that your chance of getting each letter is roughly similar to the distribution of letters in the English language. Tiles like "E", and "A" are more likely to appear, while "Z" and "QU" are rarer.

Once the board is generated, we need to find which words can be spelt on that board. This is done by iterating over the board and performing a Depth First Search starting from each tile. At each step, the prefix tree of valid words is traversed using the tile’s letter. If the current node is a valid word, it is added to a list of possible words.

Once the list of possible words has been collected, quicksort is run on it to find the 5th highest scoring element, and it's score: x. A second linear run is then performed on the list to collect all words with a score greater than or equal to x. A heap would likely perform better here but there are usually only around 100-200 words anyway.

Once we have the board, the list of possible words, and the list of highest scoring words, we are ready to serve this data on GET requests to the server.

Saving User Progress

Cheatle is a 10-minute game, but people don't always have a block of 10 uninterrupted minutes to play, so I thought it would be beneficial to add progress saving.

Every time the board is fetched from the server, a key is generated from that day’s letters. This key is then used to query localStorage. If a match is found, the stored game state is loaded, allowing the user to continue where they left off. If the key doesn’t match, the local storage data is cleared to avoid stale data.

Whenever the user leaves the page (detected via beforeunload and visibilitychange event listeners) the progress saving hook collects the game state from various sources using observer pattern callbacks, combines them, and then adds them into local storage.

This hook in particular highlighted the weakness of my design which uses multiple nested hooks to manage game state. If I was remaking the project today I would likely use a single gameState hook to mange the timer, hint system, and gameData.

Deployment

The backend is deployed on a DigitalOcean VPS, running under pm2, with a dedicated user to manage responsibilities. The frontend is deployed via GitHub pages using a GitHub Actions to manage auto-updates.