Topcoder Marathon Match 54
Буквально только что завершился двухнедельный Marathon Match 54. Задачка называлась TilesPuzzle и являлась практически копией головоломки Eternity II.
Этот матч собрал очень большое количество участников — 262 активных участника (для сравнения, в прошлом Marathon Match 53 их было ровно в два раза меньше — 131).
Я уделил соревнованию гораздо меньше времени, чем обычно — заказчики завалили проектами, плюс на время проведения этого матча пришелся ICFPC 2009, на который я потратил примерно сутки.
О задаче. Собрать всю головоломку за обозримое время практически невозможно, но частично собрать — процентов на 80-90 — довольно просто.
Первый мой подход заключался в попытке собрать периметр, зная, каких цветов всего четное количество и каких нечетное — а следовательно, на периметре это тоже должно соблюдаться. В общем, оказалось, что практического смысла в этом нет, и метод perimeter_solve() был попросту удален.
Далее была попытка методом Backtracking собирать полное решение. Для поля размера 3x3 метод отлично работал, но для большого поля мне было не совсем ясно, как с выгодой обрывать работу алгоритма при завершении выделенного времени.
В итоге я применил такой, с позволения сказать, алгоритм.
В левый верхний угол ставится случайная фишка.
Далее к предыдущей фишке подставляется следующая, чтобы не было несовпадения цветов.
Если несовпадения цветов (т.е. совпадения двух цветов — с фишкой слева и с фишкой сверху) не избежать, то выбирается фишка, чтобы совпадал хоть один цвет.
Если и это не получается, ставится любая фишка.
И так пока не заполнится все поле.
Эта процедура повторяется много раз с различной случайной первой фишкой и порядком выбора фишек из кучи, и выбирается лучший вариант.
Ну еще иногда ищется возможность поставить сразу несколько фишек с полным совпадением, типа думать на несколько ходов вперед, но тут есть риск нерезультативно потратить время. Подобрать параметры для этой штуки я толком не успел.
Сейчас я на 74 месте в таблице предварительных результатов, но мой алгоритм сильно зависит от случая, и пару десятков мест вверх/вниз — это запросто. Как повезет.
Очевидный алгоритм, который я так и не успел попробовать: если не получается избежать несовпадения цветов, не ставить в эту клетку фишку с одним совпадающим цветом, а пропускать до лучших времен. Вроде бы это должно быть более эффективно.
Этот матч собрал очень большое количество участников — 262 активных участника (для сравнения, в прошлом Marathon Match 53 их было ровно в два раза меньше — 131).
Я уделил соревнованию гораздо меньше времени, чем обычно — заказчики завалили проектами, плюс на время проведения этого матча пришелся ICFPC 2009, на который я потратил примерно сутки.
О задаче. Собрать всю головоломку за обозримое время практически невозможно, но частично собрать — процентов на 80-90 — довольно просто.
Первый мой подход заключался в попытке собрать периметр, зная, каких цветов всего четное количество и каких нечетное — а следовательно, на периметре это тоже должно соблюдаться. В общем, оказалось, что практического смысла в этом нет, и метод perimeter_solve() был попросту удален.
Далее была попытка методом Backtracking собирать полное решение. Для поля размера 3x3 метод отлично работал, но для большого поля мне было не совсем ясно, как с выгодой обрывать работу алгоритма при завершении выделенного времени.
В итоге я применил такой, с позволения сказать, алгоритм.
В левый верхний угол ставится случайная фишка.
Далее к предыдущей фишке подставляется следующая, чтобы не было несовпадения цветов.
Если несовпадения цветов (т.е. совпадения двух цветов — с фишкой слева и с фишкой сверху) не избежать, то выбирается фишка, чтобы совпадал хоть один цвет.
Если и это не получается, ставится любая фишка.
И так пока не заполнится все поле.
Эта процедура повторяется много раз с различной случайной первой фишкой и порядком выбора фишек из кучи, и выбирается лучший вариант.
Ну еще иногда ищется возможность поставить сразу несколько фишек с полным совпадением, типа думать на несколько ходов вперед, но тут есть риск нерезультативно потратить время. Подобрать параметры для этой штуки я толком не успел.
Сейчас я на 74 месте в таблице предварительных результатов, но мой алгоритм сильно зависит от случая, и пару десятков мест вверх/вниз — это запросто. Как повезет.
Очевидный алгоритм, который я так и не успел попробовать: если не получается избежать несовпадения цветов, не ставить в эту клетку фишку с одним совпадающим цветом, а пропускать до лучших времен. Вроде бы это должно быть более эффективно.
Add post to:
Comments