Motivation

This project aims to provide a simple method for creating and sharing custom strands boards based on the NYT game strands. In my spare time, I noticed that while humans could create a strands board easily, it might be challenging for an algorithm to do so: automatically generating a legal board given a list of words totaling 48 letters.

Design

This website uses a Django backend, with a pure javascript frontend deployed on Heroku. Beyond the four main view pages (home, create, about, play), there are three endpoints exposed (generate, save, url_check), used for obvious purposes. In the database, each custom game created from save are identified with a unique url, enforced by url_check. Then, upon pattern matching in the play url, the appropriate game is fetched and displayed.

Algorithm

The goal of the creation of the custom strands is to be user-friendly, meaning the creator should need only to provide what words relate to the theme and spangram, and the tedious letter placement should be done automatically. The following algorithm is called about pinging the generate endpoint and is developed as a result of countless iterations.

1. Ensure that all letters in words sum to 48 and that the spangram is length \(\geq 6\)
2. Create the grid as a graph \(G\) with all edges. For every pair of diagonals, randomly remove one.
3. Place the spangram \(S\) on the board:
   1. Randomly decide horizontal or vertical spangram
   2. Run BFS on \(G\) from the one border to represent minimum edges required to reach other side. Store this in a grid \(M\)
   3. On each iteration, place a letter on \(G\) and choose a neighbor \(N\) if remaining characters in \(S \leq M[N]\). Then update \(M\) by re-running BFS.
   4. Let \(W\) be the set of words. After placing \(S\) in \(G\), run BFS on either side of \(S\) to get the availible spots \(G_1, G_2\).
   5. Run subset sum (see below) with \(W\) as the array, and \(|G_1|\) being the target.
   6. If subset sum returns false, reset \(G, S\) and restart
4. Place the words \(W\)
   1. Partition \(W\) into \(W_1, W_2\) based on subset sum.
   2. Spawn new threads \(T_1, T_2\) with a timeout of 5 seconds with an instance of longest path on the subsection of the graph \(G_1, G_2\), which returns \(LP_1, LP_2\), respecitvely.
   3. If \(T_1, T_2\) times out, \(LP_1 \neq |G_1|\), or \(LP_2 \neq |G_2|\), restart from the beginning.
   4. Otherwise, place the words \(W_1, W_2\) along \(LP_1, LP_2\), randomlly shuffling the words and randomly reversing the words.
5. Return \(G\) to the user.

Subset Sum Algorithm

1. Initialize a boolean table \(DP\) with size \(i=|W|\) by \(j=|G_1| + 1\)
2. Fill in the base cases:
   1. True if \(j=0\)
   2. False if \(i=0 \text{ and } j \neq 0\)
   3. False if \(j < 0\)
3. Iterate through the array left to right, top to bottom, filling the table using the following recursive relation:
   1. True if \(DP[i-1][j] \text{ or } DP[i-1][j-W_i]\)
   2. False else
4. Return \(DP[-1][-1]\), i.e. the last element

Development Team

• Andy He, Computer Science graduate of Duke University.

Change Log

April 25, 2024

Switched to Uppercase letters, Updated "Create" UI, Backtracking in Play, Theme Card v2, Donations Implemented, Hints

April 2, 2024

Archive created for past strands, Change Log Created, Sharing

March 30, 2024

Fixed database bugs, added "auto-correct" to eliminate "Right word, wrong place", About Page, Better "create" page input handling (no spaces in url, no blank words), logo created (credit Bob Qian), Confetti (idea Jason Lin)

March 17, 2024

Deployment to web, https SSL config, create functionality, play functionality, canvas objects (credit: Sam Borremans).