Оптимизация NYT Spelling Bee: агрегация битмасок и быстрый перебор 7 букв

Как ускорить NYT Spelling Bee в Python сжать словарь до уникальных битмасок, агрегировать очки и быстро перебирать наборы из 7 букв без лишнего графового поиска

Максимизировать очки в NYT Spelling Bee кажется простым: выбрать семь букв, посчитать все допустимые слова, которые используют только эти буквы, оценить их по правилам игры и найти лучший набор. Подвох — в способе обхода и оценки пространства поиска. Наивный перебор масок с повторным пересчетом всей словарной базы остановится задолго до того, как вы увидите оптимальный ответ.

Базовый подход и его слабые места

Базовый вариант ниже строит словарь, отфильтрованный по словам не более чем с семью различными буквами, представляет слова 26-битными масками и исследует наборы букв как маски в поиске с равной стоимостью. Функция подсчета для каждой маски просматривает все слова. Логика верная, но производительность рушится, потому что подсчет многократно повторяет один и тот же объем работы.

from string import ascii_lowercase
from heapq import heappush, heappop

ALPH = ascii_lowercase  # Σ

with open("words.txt") as fh:
    raw_words = fh.read().splitlines()

# Оставляем слова, в которых не больше 7 различных букв
pool = list(filter(lambda w: len(set(w)) <= 7, raw_words))

# Преобразуем каждое слово в 26-битную маску
word_masks = [0] * len(pool)
for idx in range(len(pool)):
    for ch in pool[idx]:
        word_masks[idx] |= 1 << (ord(ch) - ord('a'))

# Подсчет очков: слова из 4 букв — 1 балл, длиннее — по длине
def score_of(w):
    return 1 if len(w) == 4 else len(w)

# Подсчитать очки для заданной маски набора букв, просканировав все слова
def tally_for(msk):
    total = 0
    for i in range(len(pool)):
        if (msk | word_masks[i]) == msk:
            total += score_of(pool[i])
    return -total  # отрицательное значение для использования с min-кучей

# Обход масок по Дейкстре: на каждом шаге убираем одну букву
root_mask = (1 << len(ALPH)) - 1
root_entry = (tally_for(root_mask), root_mask)

frontier = [root_entry]
seen = set()

while True:
    val, msk = heappop(frontier)

    print(val, "".join(ALPH[i] if msk & (1 << i) else ' ' for i in range(26)))

    if msk.bit_count() == 7:
        break

    for i in range(len(ALPH)):
        if msk & (1 << i):
            nxt = msk & ~(1 << i)
            if nxt in seen:
                continue
            heappush(frontier, (tally_for(nxt), nxt))
            seen.add(nxt)

Основной узкий момент — пересчет очков для каждой маски. Каждый вызов функции проходит весь список слов и заново считает очки по словам, хотя сами очки для слова не меняются. Поиск тоже натыкается на большие плато, где у множества масок одинаковый счет, из‑за чего резко растет число рассматриваемых состояний.

Ключевая идея: агрегировать по уникальной битовой маске

Два наблюдения снимают проблему. Во‑первых, очки слова не зависят от маски, значит их можно посчитать один раз и переиспользовать. Во‑вторых, у многих слов совпадает битовая маска набора букв. Если сжать словарь до уникальных масок и просуммировать очки слов по каждой маске, то при оценке маски набора букв можно перебирать не слова, а эти уникальные маски.

Рассмотрим abalones и seasonable. Обе дают одну и ту же маску для {a, b, e, l, n, o, s}. Вместо того чтобы каждый раз считать эти слова по отдельности, сверните их в одну запись с ключом по этой маске и суммарными очками. На типичном словаре (wamerican) это сокращает данные с 40940 слов до 20818 уникальных битмасок. Одно только это пополам резко уменьшает объем работы при подсчете и делает простой полный перебор всех сочетаний 26 по 7 вполне реальным.

С такой агрегацией реализация на Python может вызвать функцию подсчета 1000 раз примерно за 1,4 секунды на полной 26-буквенной маске на одной машине — этого достаточно, чтобы перебором найти лучший набор из семи букв.

Переработанное решение: предварительные вычисления и сжатие

Ниже — код, который строит отображение от битовой маски к суммарным очкам всех слов с этой маской. Функция подсчета затем итерируется по этому отображению. Логика программы не меняется; оптимизированы лишь структура данных и цикл подсчета.

from string import ascii_lowercase
import timeit

ALPH = ascii_lowercase

with open("words.txt") as fh:
    raw = fh.read().splitlines()

# Оставляем только слова, использующие не более 7 уникальных букв
filtered = list(filter(lambda w: len(set(w)) <= 7, raw))

# Преобразуем каждое слово в 26-битную маску
bm_list = [0] * len(filtered)
for i in range(len(filtered)):
    for ch in filtered[i]:
        bm_list[i] |= 1 << (ord(ch) - ord('a'))

# Подсчет очков: за слово из 4 букв — 1, иначе — длина
def points(w):
    return 1 if len(w) == 4 else len(w)

# Агрегация: битовая маска -> сумма очков всех слов с этой маской
bm_to_score = {}
for i in range(len(filtered)):
    bm_to_score.setdefault(bm_list[i], 0)
    bm_to_score[bm_list[i]] += points(filtered[i])

print(f"bm_count={len(bm_to_score)}, words_filtered={len(filtered)}, words_total={len(raw)}")

# Оценить маску набора букв суммированием совместимых битовых масок
def total_for(msk):
    s = 0
    for bm, acc in bm_to_score.items():
        if (msk | bm) == msk:
            s += acc
    return -s

# Пример замера: многократный подсчет для маски полного алфавита
print(timeit.timeit("total_for(0b11111111111111111111111111)", number=1000, globals=globals()))

Одного этого изменения достаточно, чтобы практически пройти по всем 657800 семибуквенным маскам и выбрать маску с максимальным счетом. Та же схема легко расширяется позднее под требование центральной буквы и бонус за панграмму; эти корректировки накладываются поверх предварительной агрегации без изменения общего подхода.

Почему это важно

Подсчет по каждому слову для каждой маски масштабируется линейно по числу слов — и при многократном повторении это губительно. Сведение слов к уникальным битмаскам уменьшает данные, убирает повторяющиеся вычисления и превращает задачу в быстрые побитовые проверки по набору на порядок меньшего размера. На практике это делает прямой перебор всех комбинаций из семи букв жизнеспособным, без зависимых от пути стратегий поиска, блуждающих по огромным плато одинаковых оценок.

Дополнительная практическая заметка из экспериментов на C++: плоский массив int размером 2^26 для таблицы «битмаска → очки» может быть намного быстрее, чем unordered_set, даже несмотря на больший размер. Возможно, у хеш-таблицы плохая работа с кэшем, тогда как у массива — очень хорошая, или же само хеширование просто отнимает время. Это не профилировалось, но согласуется с идеей, что предсказуемая непрерывная память может выигрывать, несмотря на больший номинальный объем.

Итоги

Предварительно вычисляйте все, что не зависит от кандидатной маски, и убирайте избыточность через агрегацию одинаковых битмасок. При таком подходе оценка маски превращается в плотный цикл по уникальным маскам, а перебор всех сочетаний 26 по 7 становится прямолинейным. При необходимости правило центральной буквы и бонус за панграмму легко встроить в ту же схему. В итоге получается эффективный, основанный на данных конвейер, который избегает дорогого графового поиска и выводит на поверхность оптимальный набор букв.

Заключение

Если алгоритм тратит большую часть времени на пересчет одних и тех же фактов, стоит остановиться и поменять представление данных. Для подсчета в Spelling Bee правильная форма данных — «битмаска → суммарные очки», однажды построенная и переиспользуемая повсюду. Это превращает неразрешимый перебор масок в простой, быстрый проход по сжатым структурам — ровно то, что нужно, чтобы найти оптимальный семибуквенный набор.