Kaggle. Собираем кубик Рубика NxNxN.
Вчера закончилось соревнование на Kaggle, в котором нужно было за наименьшее количество шагов собрать различные вариации кубика Рубика. Скор считался как сумма длин решений по всем тестам, поэтому важно было научиться хорошо решать самые большие кубики (33х33х33), а маленькие играли второстепенную роль.
Проблема сборки кубика Рубика довольно хорошо изучена и есть много готовых алгоритмов. Но большинство из них работают только для 3х3х3. Я нашел только два готовых солвера, которые умеют решать NxNxN. Один из них был совсем не оптимальным. А второй оптимизировал количество шагов в другой метрике. Он был сделан для роботов, которые автоматически собирают кубик, поэтому считает, что можно повернуть несколько внешних слоев за один шаг.
На протяжении всего контеста я думал, что путь к успеху это переписать второй солвер на правильную метрику. Но каждый раз, когда я собирался это сделать, я смотрел на десятки тысяч строк кода этого солвера, и понимал, что шансы на успех довольно малы. Я потратил где-то неделю на то, чтобы написать солвер для 3х3х3 и начал писать 4х4х4, но это выглядело слишком сложно.
В итоге я решил реализовать хоть какое-то решение, которое основано на той же идее, что и первый неоптимальный солвер. Все клетки можно разбить на множества по 24 штуки таким образом, что при любом движении клетка остается только в своем множестве. Существуют последовательности из 8 действий, которые переставляют по циклу 3 клетки из одного множества и никак не трогают остальные. Поэтому можно решать каждое множество независимо.
Потом я еще улучшил эту идею за счет того, что можно объединить две (и даже больше) такие последовательности и переиспользовать часть ходов. Но меня все еще не покидало ощущение, что делать 8 действий, чтобы передвинуть 3 клетки, это очень дорого.
В итоге соревнование закончилось, читаю решение участников с первого места, а у них все те же самые идеи про циклы длины 3, но скор почему-то в два раза лучше 😐.
Вчера закончилось соревнование на Kaggle, в котором нужно было за наименьшее количество шагов собрать различные вариации кубика Рубика. Скор считался как сумма длин решений по всем тестам, поэтому важно было научиться хорошо решать самые большие кубики (33х33х33), а маленькие играли второстепенную роль.
Проблема сборки кубика Рубика довольно хорошо изучена и есть много готовых алгоритмов. Но большинство из них работают только для 3х3х3. Я нашел только два готовых солвера, которые умеют решать NxNxN. Один из них был совсем не оптимальным. А второй оптимизировал количество шагов в другой метрике. Он был сделан для роботов, которые автоматически собирают кубик, поэтому считает, что можно повернуть несколько внешних слоев за один шаг.
На протяжении всего контеста я думал, что путь к успеху это переписать второй солвер на правильную метрику. Но каждый раз, когда я собирался это сделать, я смотрел на десятки тысяч строк кода этого солвера, и понимал, что шансы на успех довольно малы. Я потратил где-то неделю на то, чтобы написать солвер для 3х3х3 и начал писать 4х4х4, но это выглядело слишком сложно.
В итоге я решил реализовать хоть какое-то решение, которое основано на той же идее, что и первый неоптимальный солвер. Все клетки можно разбить на множества по 24 штуки таким образом, что при любом движении клетка остается только в своем множестве. Существуют последовательности из 8 действий, которые переставляют по циклу 3 клетки из одного множества и никак не трогают остальные. Поэтому можно решать каждое множество независимо.
Потом я еще улучшил эту идею за счет того, что можно объединить две (и даже больше) такие последовательности и переиспользовать часть ходов. Но меня все еще не покидало ощущение, что делать 8 действий, чтобы передвинуть 3 клетки, это очень дорого.
В итоге соревнование закончилось, читаю решение участников с первого места, а у них все те же самые идеи про циклы длины 3, но скор почему-то в два раза лучше 😐.