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 for game creation (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.

In addition, to support users, a CustomUser model is created (extending Django's AbstractBaseUser for data security), and a one-to-one Profile model is created. The profile is identified using a unique email, and a display_name is used for displaying on the web. To support authors, a Profile object is stored on each StoredGame, representing the author.

For completions, a join table is used, joining Profile and StoredGame objects. This is for future meta-data to be able to be stored, potentially fields like time to completion, likes, dislikes, etc. When a non-user completes a game, simply a field in the corresponding StoredGame object is updated. Having completions allows for statistics to be displayed for the StoredGame and during random play, for games not to be shown again.

This schema allows for complex queries, like retrieving all anonymous and profiled completions to rank authors. The following SQL query retrieves the authors with the most total completions over all public games and is an example of how the above schema can be used for data insights. Toggle PostgreSQL Query

    WITH games AS (
      SELECT id, anonymous_completions, author_id
      FROM cstrandsapp_storedgame
      WHERE "order" > -1 AND is_archive = False
    ),
    completions AS (
        SELECT stored_game_id, COUNT(*) AS count
        FROM cstrandsapp_completion
        GROUP BY stored_game_id
    ),
    total AS (
        SELECT
            games.author_id,
            SUM(games.anonymous_completions) + COALESCE(SUM(completions.count), 0) AS total_sum
        FROM games
        LEFT JOIN completions
        ON games.id = completions.stored_game_id
        GROUP BY games.author_id
    )
    SELECT 
        display_name, 
        url, 
        total_sum
    FROM total
    JOIN cstrandsapp_profile
    ON cstrandsapp_profile.id = total.author_id
    ORDER BY total_sum DESC
    LIMIT 5;
  

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 with \(W\) as the array, and \(|G_1|\) being the target.
   1. Initialize a boolean table \(A\) 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 filling it using the following recursive relation:
      1. True if \(A[i-1][j] \text{ or } A[i-1][j-W_i]\)
      2. False else
   4. Return \(A[-1][-1]\), i.e. the last element
   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 \(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.

Change Log

August 1, 2024

Authenticated users see no inline ads. Password Reset implemented.

July 9, 2024

Archive Quick Navigate (for authenticated users)

July 1, 2024

Manual Mode Creation of Puzzles. Modularity of displayed table in create page, manual mode, MANUAL_DICT state. Added errors and warnings to create page for better usability. Play Random now does a random choice weighted by normalized completions. Archive games have their completions divided by 10 in the weighting to give creators more opportunity.

June 25, 2024

Updated Top Creator Statistic to get total completions over all authored games

June 5, 2024

Archive now has original boards from NYT games, NYT authors, automatic profiles, updated titles.

May 23, 2024

Updated Player: Click + Click interation, Multicolor mode for sharing: ⭐ for spangram, colors for regular words. Feature List. How to play modal.

May 20, 2024

Users: Public games, profiles, editing profiles, completions, random_play, create page database optimizations / changing user flow, statistics.

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).