Привет Хабр! Меня зовут Илья и сегодня мы поговорим про кроссворды.

Если когда-то будет противостояние человечества и машин, то последнее что позволит нам, кожаным мешкам, отличить своих собратьев от бездушных киборгов - это искусство составления кроссвордов. GPT ужасно составляет кроссворды.

А вот так с задачей справляется GPT-4 Omni

Prompt> Составь пожалуйста небольшой кроссворд про машинное обучение.

GPT-4O> Конечно! Вот пример кроссворда на тему машинного обучения с 10 словами.

Сетка кроссворда

 | _ _ _ _ _ _ _
 | _ _ _
 | _ _ _ _ _ _ _ _ _ _ _ _ _
 | _ _ _     _ _ _ _ _     _ _ _ _ _
 | _ _ _ _ _ _ _ _ _ _
 | _ _ _ _ _ _
 | _ _ _ _ _ _ _ _ _
 | _ _ _ _ _    _ _ _ _ _ _ _ _ _
 | _ _ _ _ _ _ _ _
 | _ _ _ _ _ _ _ _ _ _ _ _ _

Ответы

S U P E R V I S E D
P C A
R E G U L A R I Z A T I O N
R O C   C U R V E
R A N D O M F O R E S T
K M E A N S
S C I K I T L E A R N
C R O S S   V A L I D A T I O N
E N S E M B L E
H Y P E R P A R A M E T E R

Не очень похоже на кроссворд, не правда ли?

10  | O | V | E | R | F | I | T |
 I  |   |   |   | D |   |   | S |
 N  |   | P | I |   |   |   |   |
 S  |   | R | - | H | V | A | R |
 E  | A | G | G | R | E | P | I |
 T  |   | E | I | L | I | O | U |
   4| E | L | M | A | I | N | C | V 
 |

Раз GPT с задачей справиться не может, придётся придумать как ей помочь. В этой статье я расскажу как как это сделать.
Весь код можно найти в репозитории.

TL; DR Кроссворд про ML

Вот ссылка на кроссворд.
На отгадывание у вас уйдёт минут 20-30. Он точно разгадываемый, проверено на живых программистах.
N.B. Кроссворд на английском, потому что почто весь профессиональный жаргон - сплошные англицизмы и я решил что странно если вопросы будут на русском, а ответы на английском.

Шаг №1 Собираем базу слов

Сначала я хотел написать каких-нибудь ML терминов из головы, но моей фантазии хватило на 30 слов. Пришлось вооружиться data-driven подходом.

1. Я нашел на GitHub справочник по ML терминам - https://github.com/bfortuner/ml-glossary

2. Написал скрипт который парсит уникальные слова - их получилось около 3000.

3. Отсмотрел вручную и оставил только те, что подходят для использования в кроссворде: существительные или глаголы в нормальной форме, если слово встречается в нескольких вариантах написания, то оставляю “самую нормальную”.

4. В итоге у меня получился список из 242 слов

Отсмотреть 3 тысячи слов заняло у меня около получаса реального времени.
По идее базу можно было бы отфильтровать в автоматическом режиме, используя расстояние между эмбедингами слов и что-то вроде TF-IDF.

Шаг №2 Собираем их в кроссворд

В интернете много сайтов, которые позволяют собрать свой кроссворд из списка слов, например Crossword Labs, но итоговый кроссворд получается очень "разреженным", хочется сделать его покомпактнее.

Я написал небольшую программу на C++ которая случайным способом пытается собрать максимально компактный кросворд, работает так:

1. Размещаем слово в случайном месте поля по горизонтали

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

3. Дальше опять размещаем слово по горизонтали c хотя бы одним пересечением. GOTO п2

4. Если слово разместить не удаётся - смотрим метрику “занятости” (количество занятых клеток поделить на количество свободных клеток).

5. Повторяем шаги с 1 по 4 несколько раз, выбираем кроссворд с максимальной "занятостью".

Шаг №3 Делаем вопросы с помощью ChatGPT

Хвала LLM, еще раньше эта стадия была самая сложная для автоматизации, сейчас всё делается довольно тривиально. Прогоняем каждое слово через API от OpenAI (суммарно за 242 слова мне это стоило меньше 10 центов).

Шаг №4 Собираем всё вместе в web страницу

Я не знаю ничего в web разработке, поэтому я попытался заниматься реверс инжинирингом нескольких сайтов что бы “занять” у них движок для отрисовки кроссвордов, к сожалению у меня ничего не вышло. Зато где то после 3х часов поисков в интернете удалось найти великолепный репозиторий на GitHub который делал то что мне нужно https://github.com/jweisbeck/Crossword

К сожалению, там была куча багов, но кое-как мне удалось их пофиксить. Ещё один скрипт на питоне что бы собрать всё воедино и ...

Вуаля - кроссворд готов https://udalovilia.com/crossword/

Вместо заключения

Если вам понравилось - то поделитесь с друзьями, вот ссылка на кроссворд.
И можете поставить звёздочку моему GitHub репозиторию.