Получите набор данных, выполните предварительную обработку, определите переменные ограничений и позвольте решателю Wordle делать свое дело

Тл; др. Два лучших слова для начала Wordle — это «один» и «рубашка».

Когда я увидел Wordle (понедельник, 31 января), я подумал, а не будет ли программирование с ограничениями превосходным решением этой проблемы. При выполнении математических расчетов, если бы у нас было 500 слов на выбор, и мы хотели бы найти 2 лучших слова, нам нужно было бы проверить в худшем случае 6,2 миллиарда сравнений. Мы собираемся поднять его на несколько ступеней и установить цель в 2000 слов :)

Математика, если кому интересно. Я могу ошибаться, но здесь я предполагаю худший случай:

1st word: 500 possibilities
2nd word: 499 possibilities
Then we will need to check how each of these words compares to all the other words 498 and each word contains 5 letters so we would need to compare all 2words each with 5 letters to those 5 letters.
Thus: 500*499*498*2*5*5=~6.2 billion Operations

Программирование с ограничениями вам в помощь! Для тех, кто не знаком с программированием с ограничениями, я буду использовать слова Google:

Оптимизация с ограничениями или программирование с ограничениями (CP) — это название, данное идентификации возможных решений из очень большого набора кандидатов, где проблема может быть смоделирована в терминах произвольных ограничений. Проблемы CP возникают во многих научных и инженерных дисциплинах. (Слово программирование немного неправильное, подобно тому, как компьютер когда-то означал человека, который вычисляет. Здесь программирование относится к составлению плана, а не к программированию на компьютерном языке.)
— Источник

Чтобы упростить программирование ограничений, вы определяете, каковы параметры задачи, и определяете ограничения этих параметров.

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

  1. Получите набор данных английских слов.
  2. Предварительно обработайте эти слова до нужного нам размера (слова из 5 букв).
  3. Преобразуйте эти слова во что-то, что может понять Решатель.
  4. Определите переменные ограничений.
  5. Выберите эвристику, которая будет выбирать лучшие слова и создавать ограничения.
  6. Запустите решатель и преобразуйте результат обратно в слова.

1. Получите набор английских слов.

Чтобы победить wordle, мы должны найти список английских слов, к счастью, после поиска в GitHub я попал на эту красоту.

В соответствии с рекомендациями репозитория я выбираю words_alpha.txt, не стесняйтесь выбирать свой собственный. Теперь у нас есть список английских слов, мы можем перейти к следующему шагу.

2. Предварительно обработайте эти слова до нужного нам размера (5-буквенные слова).

Итак, теперь у нас есть несколько слов, давайте импортируем их в Python и посмотрим на них. Для этого мы можем использовать Pandas для чтения данных.

Это очень круто, мы видим, что у нас есть 370 103 слова. Теперь давайте просто получим слова из 5 букв.

Ура! Теперь у нас есть 15 918 слов для игры, некоторые из этих слов я никогда не слышал, например aalii, что означает "густой сапиновый куст".

3. Превратите эти слова во что-то, что может понять Решатель.

Теперь у нас есть много слов, и нам нужен способ их понимания решателем. Решатель CSP может понимать несколько типов данных, таких как целые числа и логические значения. Но решатель, который я буду использовать, не понимает символы, поэтому нам нужно преобразовать символы во что-то, что они могут понять.

Мы могли бы использовать горячее кодирование. Или мы могли бы сделать это проще и присвоить каждой букве номер (например, буква a → 0, b → 1 … z → 25), что намного проще. Итак, давайте сделаем это.

Когда мы запускаем этот код, мы получаем переменную с именем words, которая представляет собой список слов, представленных целыми числами. Например, [0,0,7,4,3] означает «ахед».

4. Определите переменные ограничений.

Теперь нам нужно немного проникнуть в сорняки. Мы хотим определить некоторые переменные для понимания нашего решателя ограничений. Решатель ограничений, который мы собираемся использовать, называется Cadical — это один из самых современных решателей.

Написание для Cadical на самом деле занимает много времени, поэтому вместо этого мы будем использовать абстракцию под названием SavileRow, которая работает на языке Essence Prime, а затем сможет перевести наш код в Cadical, который затем сможет решить.

Во-первых, нам нужно сообщить SavileRow, какие у нас параметры. Чтобы сделать это эффективным, мы можем написать функцию Python, которая будет принимать переменную words и выдавать .param файл, понятный SavileRow.

В этой функции мы передаем SavileRow количество слов, количество букв слов и количество слов, которые мы хотим, чтобы решатель выбрал для нас.

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

random.shuffle(words)

Теперь мы можем передать words в функцию. И мы получаем это как наш файл параметров:

5. Выберите эвристику, которая будет выбирать лучшие слова и создавать ограничения.

Чтобы решатель выбрал лучшие слова, нам нужно сообщить решателю, что искать. Мы можем указать решателю, что искать, с помощью команды find. В этом случае мы хотим найти индексы лучших слов, которые обладают лучшими характеристиками для нахождения слова-слова. Мы можем назвать этот массив best_words

heuristic является самым важным в программировании с ограничениями, это то, что мы пытаемся оптимизировать. Здесь мы пытаемся оптимизировать вероятность того, что два слова охватывают целевое слово. По сути, мы хотим подсчитать, сколько раз обе буквы этих слов встречаются в каждой другой букве. Мы можем назвать это переменной cost мы можем указать решателю maximise это.

Что касается ограничений, мы хотим убедиться, что все слова, выбранные решателем, разные, для этого мы можем использовать ограничение AllDiff. Мы также хотим убедиться, что решатель не выдает одно и то же решение дважды, например. если выбраны индексы: [1,3], то [3,1] - это то же решение, только в другом порядке. Мы можем навязать порядок, установив, что больший индекс всегда будет первым.

Со всем этим мы можем создать модель SalvileRow:

7. Запустите решатель и преобразуйте результат обратно в слова.

После запуска решателя с помощью команды:

savilerow words.eprime words.param -run-solver -sat

Мы получаем результат [414, 129] , это индексы слов, которые имеют наивысший балл по эвристике. Если мы затем посмотрим на эти слова, мы получим [11, 0, 20, 13, 3] и [14, 18, 8, 4, 17], а при обратном переводе в символы мы получим «лаунд» и «верба».

L̶i̶m̶i̶t̶a̶t̶i̶o̶n̶s̶

̶S̶o̶m̶e̶ ̶o̶f̶ ̶t̶h̶e̶ ̶w̶o̶r̶d̶s̶ ̶i̶n̶ ̶t̶h̶e̶ ̶w̶o̶r̶d̶s̶_̶a̶l̶p̶h̶a̶.̶t̶x̶t̶ ̶d̶o̶ ̶n̶o̶t̶ ̶a̶p̶p̶e̶a̶r̶ ̶t̶o̶ ̶b̶e̶ ̶c̶o̶m̶p̶a̶t̶i̶b̶l̶e̶ ̶w̶i̶t̶h̶ ̶W̶o̶r̶d̶l̶e̶,̶ ̶s̶o̶ ̶i̶t̶ ̶m̶a̶y̶ ̶n̶o̶t̶ ̶b̶e̶ ̶a̶c̶c̶u̶r̶a̶t̶e̶ ̶f̶o̶r̶ ̶w̶o̶r̶d̶l̶e̶.̶ ̶I̶f̶ ̶a̶ ̶d̶a̶t̶a̶s̶e̶t̶ ̶o̶f̶ ̶w̶o̶r̶d̶l̶e̶ ̶w̶o̶r̶d̶s̶ ̶t̶h̶a̶t̶ ̶a̶r̶e̶ ̶u̶s̶e̶d̶ ̶i̶s̶ ̶e̶v̶e̶r̶ ̶r̶e̶l̶e̶a̶s̶e̶d̶ ̶t̶h̶e̶n̶ ̶a̶n̶ ̶a̶c̶c̶u̶r̶a̶t̶e̶ ̶a̶n̶s̶w̶e̶r̶ ̶c̶a̶n̶ ̶b̶e̶ ̶r̶e̶a̶c̶h̶e̶d̶ ̶o̶n̶ ̶w̶h̶i̶c̶h̶ ̶w̶o̶r̶d̶s̶ ̶a̶r̶e̶ ̶b̶e̶s̶t̶ ̶f̶o̶r̶ ̶W̶o̶r̶d̶l̶e̶.̶

Обновлять

Я нашел лучший список слов, который вы можете извлечь из оксфордского словаря.

Я выполнил те же шаги, что и выше, и придумал два более вероятных слова, которые появятся в Wordle: «один» и «рубашка».