Соревнование закончилось больше 2 недель назад, пора подвести итоги:

Под конец соревнования объединился в команду, заняли в итоге 132/1054 место, до медальки не дотянули. Ну и ладно.
Основным нашим методом оказался алгоритм Минквица, с помощью которого мы оптимизировали имеющиеся решения. Strong generating sets и bases считались в GAP очень быстро с пакетом genss, в отличие от вычисления копредставления, о чем я писал в прошлом посте: как и ожидалось, для больших групп найти соотношения было очень тяжело.

Также оказалось, что собирать кубик Рубика/решать permutation puzzle можно с помощью целочисленного линейного программирования! А именно, можно сформулировать задачу сборки кубика как некоторую задачу минимизации, грубо говоря, числа шагов сборки, с кучей ограничений, которые и кодируют разрешенные движения/перестановки. Впрочем, лп-солверы тоже не идеальны, и на многих примерах не находили решение за какое-то разумное время.

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

В итоге, в рамках соревнования я сделал 4 тетрадки:
1. Group Theory of Santa Puzzles - теория групп 101, пару слов про копредставление, про общий подход к оптимизации решений на основе соотношений в группе
2. Group Theory via GAP - логическое продолжение предыдущей тетрадки с установкой GAP, подсчетом соотношений и вычислением bases и strong generating sets для групп паззлов
3. Permutation Puzzles as Integer Linear Programs - представление permutation puzzles как задачек целочисленного программирования и их решение с помощью PySCIPOpt
4. Stable Baselines for Cubes - небольшая попытка завести RL модельки в рамках соревнования (ultimately failed, но все равно вышло познавательно)

Сегодня в 19:00 по Мск на вебинаре Сберлоги будем обсуждать это соревнование тут, заходите, если интересно!