Инженерия в решении головоломок

Есть особая магия в головоломках, обладающих большим комбинаторным потенциалом. В то же время, именно в рутинных операциях полностью раскрывается потенциал ЭВМ. Соединяясь в рамках одной задачи, эти два тезиса будоражат как предстоящее путешествие: что-то из приключенческих фильмов с подбором шифров и разгадыванием кодов.

Постановка задачи

Есть двумерное игровое поле, вида:


Требуется, используя плоские фигуры, идущие в комплекте (напоминающие фигуры из тетриса) закрыть все участки поля, кроме недоступных (отмеченных маркером «х») и двух клеток, соответствующих текущему месяцу и дню.

Решение

При первом знакомстве эта головоломка кажется настолько сложной, что надеешься получить хоть какую-нибудь раскладку: хоть «фев 31», хоть «янв дек».

Никакой стратегии не вырисовывается, а сама задача начинает казаться не проверенной на наличие решений. Хорошо, что есть Си++ и поиск в глубину.

Всего в комплекте 8 фигур, имеющих, в общем случае, 4 состояния вращения. Плюс: детали можно перевернуть тыльной стороной («рубашкой») вверх – что даёт ещё одну степень свободы с двумя состояниями. Если не закапываться в геометрию поля и фигур, можно – упрощённо – считать, что для размещения доступны 7х7 = 49 клеток. Итого:


Это довольно-таки внушительное число: если представить, что каждую комбинацию мы будем изображать на листе бумаги для офисного принтера (толщина – 104 мкм), то высота «башни» из такого количества листов будет равна:


Расстояние от Земли до Марса – всего 55 млн. км.

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

Потому – только Си++. И никаких вращений с поворотом растра фигуры: вместо этого будем вращать наблюдателя вокруг фигуры, путём смены интерпретации осей. Также поколдуем над откатом до предыдущих состояний поля, контролем за априорными ситуациями, оптимизацией передачи аргументов и подстановкой тел функций.

Поехали!

Наблюдать за перебором – отдельное удовольствие: завораживает и не отпускает, но надо найти в себе силы встать, выключить дисплей терминала и пойти гулять.

Не считая двух часов работы антивируса (про расписание которого я забыл), на стендовой машине программа работала без дефицита ресурсов около 40 часов. Ах, сон под шум вентиляторов и хруст жесткого диска – яркие картины юности.

Немного трюков или ускорение в 8 раз из ничего

Визуализировать результаты я решил на Blitz Basic.

Результатом работы переборщика стал огроменный CSV-файл (я решил дампить результаты в формате, воспринимаемом человеком) в 92 Мб. Всего нашлось около 800 000 комбинаций. Выискивать дубли, образованные формально разными раскладками я и не собирался, но даже чтение и парсинг файла занимали немалое время.

Когда ещё представится возможность заняться оптимизацией кода? Отмечу, что с точки зрения методики проведения эксперимента, данный раздел можно покритиковать (см. заметку на эту тему), но здесь замеры времени (я привожу среднее за 3-4 итерации) проводятся с аналитическим подкреплением наблюдаемого эффекта. Далее кратко опишу предпринятые модификации кода.

Для маркировки раскладок я использовал хеш-функцию, определяющую: для какой даты данная раскладка подойдёт.

Вместо превращения файловой проекции (буфера, содержащего тело файла полностью «одним куском»), в массив сепарированных объектов пользовательского типа «матрица», я оставлял прочитанный массив, реализуя для более удобной работы с абстракцией «матрица» набор методов нового пользовательского типа «вектор матриц». Смещения до каждой матрицы рассчитывались единожды в конструкторе и сохранялись в массив индексов. Такой доступ не только избавляет от лишних вычислений, но и позволяет исключать отдельные матрицы, никак не корректируя тело вектора и не создавая оверлейный контейнер (типа связанного списка) с указателями на участки вектора – достаточно просто запретить доступ, заменив индекс удалённой матрицы заглушкой (архитектура на будущее).

Этот подход позволил уменьшить время загрузки примерно в два раза.

Дальнейшее увеличение скорости достигалось в двух направлениях: «оставление надежды на оптимизацию транслятора» и «локальные оптимизации исходя из семантики». Оба направления сходны в одном: это та самая финальная шлифовка, которая уменьшает переносимость и лаконичность кода.

Мелочные вычисления/трансформации, которые, ожидается, будут оптимизированы при трансляции (или под которые не хочется громоздить отдельные переменные), выполнены в явном виде. Например, преобразование счётчика цикла в адрес начала числа в массиве , сведено к созданию отдельного счётчика с шагом 4 (умножение сведено к сложению). Арифметика (например, связанная с переходом от категории «количество» к категории «индекс») – так же рассчитывается явно и единожды, если это возможно. Логика сведена к маршруту, требующему минимальное количество приведения типов, при этом возможное трансформируется заранее.

Хеш-функция преобразована от человекопонятной последовательности байт, в целое число – если раньше она имела вид:


и 12 марта кодировалось как 3:12, то теперь:


и 12 марта кодируется как 3 * 31 + 12 = 105.

По сути, теперь хеш представлял собой число, близкое (не меньшее) к порядковому номеру дня внутри года.

Пачка этих улучшений сократила время ещё в два раза.

Далее под оптимизацию попала логика, отвечающая за формирование хеша матрицы.

Во-первых: ранний останов. Как только определен номер месяца, можно сразу переходить к определению номера дня (смещать курсор чтения на третью строку), а как только определён номер дня – можно прекращать читать матрицу и переходить к вычислению хеша. Здесь пришлось немного поотлаживать, так как мы скачем внутри конструкции из вложенных циклов вперёд, вручную меняя значения итераторов.

Во-вторых: учитывая малый диапазон номеров месяца и дня, мы можем просто «запечь» их в 4 байта памяти целого числа, не прибегая к арифметике. Теперь:


и 12 марта кодируется как (00000011₂ 5) 00001100₂ = 01101100₂ = 108.

На этой же волне, к битовым операциям сведена некоторая арифметика, где это было уместно.

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

Таким образом, среднее время загрузки (не считая чтение файла в память – атомарные операции языка) и разметки хешем, снизилось с двух минут до 15 секунд. С выключенным отладчиком, ожидается, что время выполнения будет ещё меньше, поэтому переформулирую: «оптимизация позволила сократить время загрузки в 8 раз». Бонусом мы получаем низкую фрагментацию памяти и быстрое уничтожение используемых объектов.

Нас зовут новые приключения

Всё ещё можно вынести тяжёлые участки в DLL, написанную на Си. Сравнивать матрицы лучше не по элементам (байт с байтом), а сразу словами: например, int-ами по 4 байта. Использование Си позволит написать более гибкую реализацию чтения файла, что избавит проекцию от унаследованных из CSV разделителей и форматирования, абсолютно не нужных в ограниченной семантике конкретного приложения: сэкономим память и упростим (и ускорим) работу с ней.

Но, нас зовут новые приключения…

Ответы

От щедрот переборщик нашёл и 31 февраля и любые другие пары «месяц-день». В квадратных скобках указано: сколько всего раскладок для этой пары найдено.