Ruzzle — это популярная игра в слова, цель которой найти как можно больше слов в сетке 4×4, например:
В поезде, отправлявшемся в Рим на прошлой неделе, я и мои коллеги из команды Onebip тренировались с новым ката: решатель для Рузл, который бы нашел как можно больше слов в данный период времени.
Некоторые определения
Слова должны быть действительными на выбранном языке, который для нас был итальянским, но это не имеет значения для целей ката. Каждый решатель может предполагать наличие списка всех допустимых слов для языка, сохраненного в файле: эта информация является необходимым условием для создания решателя.
Все 26 букв могут быть использованы, и могут быть повторены внутри сетки. Слова могут быть созданы путем перемещения из одной ячейки в (самое большее) 8 соседних, но без использования ячеек более одного раза в каждом слове. Оценка рассчитывается способом скрэббл, суммируя вес всех букв, используемых в ваших словах (но в этом ката не учитывается оценка).
Спойлеры впереди
Эта ката имеет среднюю алгоритмическую сложность: основная проблема, которую необходимо решить, — это создание допустимых путей внутри графа, состоящего из 16 ячеек. Мы не вдавались в маршрут грид-как-граф, но я думаю, что из этой модели могут быть получены хорошие результаты благодаря широкой доступности алгоритмов, которые работают с графами.
Однако самым сильным требованием является поддержание приемлемой производительности, поскольку Ruzzle — игра с ограниченным временем (2 минуты).
Самое простое решение, которое приходит на ум и в которое каждый из нас погружался, — это сгенерировать все возможные пути, начиная с каждой ячейки, и проверить, является ли какой-либо путь длины L допустимым словом в данном словаре.
Прежде всего, необходима осторожность для реализации этой стратегии: поиск в ширину, вероятно, будет работать лучше и позволит вам определить произвольную максимальную длину слова.
Тем не менее, каждая ячейка имеет в среднем 5,25 соседей (от максимум 8 в середине до всего 3 в углах); поэтому, когда этот поиск достигает 7-буквенных слов, это уже число путей 16 * 5,25 ^ 7 = 1,7M, что больше, чем количество слов в английском языке (менее 1M).
Таким образом, чтобы избежать этого взрыва в сложности, мы перевернули проблему и начали искать каждое слово в словаре в сетке. Это проблема, склонная к оптимизации, так как вы можете исключить много слов, не начав их искать (если они содержат букву, которой нет в сетке) или даже в первых нескольких ветвях дерева, когда нет пути к 2 ячейкам их.
Например, эта сетка:
AB CD
позволяет исключить все слова, содержащие буквы от E до Z без начала нового поиска, а также такие слова, как Аарон, всего за два шага.
Результаты
Вот несколько скудных выводов о нашем опыте разработки решателя в TDD и шоке от необходимости отказаться от нынешнего подхода.
- Эта ката идеально подходит для тренировок по оптимизации производительности . Существует много моментов, когда возникает сложность вычислений: разработка или повторное использование структур данных, таких как наборы или хеш-таблицы; возможности кеширования; использование профилировщика для поиска узких мест и проверки теоретической сложности алгоритмов.
- Немного программной инженерии способен поглотить часть шока . Даже если мы отбрасываем внешнюю часть алгоритма поиска, когда начинаем искать слова, а не генерируем пути, большую часть кода можно использовать повторно (например, классы Cell и CellSet). Та же логика предметной области была все еще необходима, но она должна была быть составлена по-другому.
- TDD всегда нужны тесты на уровне модулей , особенно в незнакомой области. Когда алгоритм не работает, последнее, что вы хотите сделать, это запустить отладчик или вставить операторы echo: даже если можно просто отладить с помощью print () в наборе тестов, модульные тесты скажут вам, где именно проблему нужно решить вместе с красной полосой, в то время как сквозные тесты покажут вам только «что-то не так».
Некоторые тестовые случаи
Если вы хотите попробовать этот ката, вот набор бесплатных тестовых примеров для начала. Я понимаю, что делаю некоторые аналитические работы для вас, но когда у вас просто есть временное окно, я предпочитаю выдавать серию сценариев, которые должны быть рассмотрены по одному, чтобы позволить кодировщикам сосредоточиться на интересных алгоритмических аспектах проблемы. вместо того, чтобы придумывать слова.
Given a 1x1 grid And an empty word set Then no word is found Given a 1x1 grid 'a' And a word set containing 'a' Then the 'a' word is found Given a 2x1 grid 'ab' And a word set containing 'a' Then only the 'a' word is found Given a 2x1 grid 'ab' And a word set containing 'ab' Then only the 'ab' word is found Given a 2x1 grid 'ab' And a word set containing 'a', 'ab' Then the 'a' and the 'ab' word are found
Затем вы можете распространить эти сценарии на случаи 2×2, 3×3 и 4×4, пропуская промежуточные шаги в зависимости от вашей реализации. Не только тесты дают обратную связь с кодом, но и код говорит вам, какие следующие тесты написать.
Если у вас есть предложения о том, как наилучшим образом решить проблему, не стесняйтесь рассказать мне о некоторых дополнительных сценариях, которые нужно вставить в эти сценарии, чтобы сделать шаги по рефакторингу и модификации решения более короткими.