Strands from New York Times Assistant

README.md

Assistant for New York Times Puzzle - Strands

This is a super primitive assistant to help you solve Strands from New York Times

Explanation

• Read words from /usr/share/dict/words
• Build Trie
• BFS on each coordinate, only search when neighbor is not seen, and its letter can make up a word

How to cheat

$ curl 'https://www.nytimes.com/games-assets/strands/2024-04-09.json'
{
  "printDate": "2024-04-09",
  "id": 22,
  "editor": "Joel Fagliano",
  "spangram": "REDACTED",
  "clue": "Can I have my quarter back?",
  "startingBoard": [
    "DYOBWO",
    "TOLERC",
    "NEPYTS",
    "EANHAI",
    "VMILRT",
    "ARPTEA",
    "APIOHN",
    "TRPANT"
  ],
  "solutions": [
    ...
  ],
  "themeCoords": {
    "SOLUTION": [
      [0, 0],
      ...
    ],
    ...
  }
}
  

main

#!/usr/bin/env python3

import datetime
import json
import urllib.request

from collections import deque


class Trie(object):
    _WORD_END = '.'

    def __init__(self) -> None:
        self.trie = {}
        self._build_trie()

    def _build_trie(self):
        words = self._load_words()
        for word in words:
            if not all(c.isalpha() for c in word):
                continue
            t = self.trie
            for c in word:
                if c not in t:
                    t[c] = {}
                t = t[c]
            t[Trie._WORD_END] = ''

    def neighbors(self, cs):
        t = self.trie

        for c in cs:
            if c not in t:
                return []
            t = t[c]

        return [k for k in t if k != Trie._WORD_END]

    def __contains__(self, word):
        t = self.trie
        for c in word:
            if c not in t:
                return False
            t = t[c]
        return Trie._WORD_END in t

    def _load_words(self):
        words = set()
        with open('/usr/share/dict/words') as words_file:
            for line in words_file.readlines():
                words.add(line.strip().upper())
        return words


class Puzzle(object):
    def __init__(self, letters) -> None:
        self.letters = letters

        self.height = len(self.letters)
        self.width = len(self.letters[0])

        self.trie = Trie()
        self.seen = set()

    def is_coordinate_valid(self, x, y):
        return 0 <= x < self.height and 0 <= y < self.width

    def neighbors(self, x, y):
        candidates = [
            (x - 1, y - 1),
            (x - 1, y),
            (x - 1, y + 1),
            (x, y - 1),
            (x, y + 1),
            (x + 1, y - 1),
            (x + 1, y),
            (x + 1, y + 1),
        ]

        return [(xx, yy) for xx, yy in candidates if self.is_coordinate_valid(xx, yy)]

    def search_all(self):
        for x in range(self.height):
            for y in range(self.width):
                self.search_coordinate(x, y)

    def search_coordinate(self, x, y):
        '''
        Essentially a BFS on `(x, y)`

        Search neighbors only when the neighbor's letter is in the Trie
        '''
        states = deque()
        states.append((self.letters[x][y], [(x, y)]))

        while states:
            word, path = states.popleft()
            xx, yy = path[-1]

            # Anything less than 3 letters will not count per game's logic.
            if len(word) > 3 and word in self.trie and word not in self.seen:
                print(word, path)
                self.seen.add(word)

            for xxx, yyy in self.neighbors(xx, yy):
                c = self.letters[xxx][yyy]
                # Won't search if neighor has been visited, and if the neighbor's letter can make up some words in the dictionary
                if (xxx, yyy) not in path and c in self.trie.neighbors(word):
                    states.append((word + c, path + [(xxx, yyy)]))


def main():
    with urllib.request.urlopen(f'https://www.nytimes.com/games-assets/strands/{datetime.datetime.now().date().isoformat()}.json') as req:
        game = json.loads(req.read().decode('utf-8'))
    board = game['startingBoard']
    Puzzle([list(line) for line in board]).search_all()


if __name__ == '__main__':
    main()