Для избегания подобного иногда усложняют эту игру добавлением помощника. Помощник тоже участвует в игре, но не приносит победы игроку. Если игра проходит в несколько раундов, то игроку, помощник которого победил, запрещается использовать помощника в дальнейшем.
Разумеется я знаю эту и некоторые другие реализации пузырька. Меня интересует одна конкретная реализация пузырька — «референсная», которая настолько интересна, что инициатор ветки предлагает добавить ее в список выше.
Ну если открыть ссылку, можно узнать, что алгоритмы преимущественно закодированы в C++ из-за библиотеки шаблонов, а структуры данных — на Java из-за Collections и сборщика мусора.
UPD. уже не актуально :(
Не надо считать все расстояния, надо лишь найти минимальное. Для этого достаточно для каждой пары совпадающих чисел проверить два варианта расположений точек и выбрать минимальный.
1. Можно текущий путь хранить в setе, а не в массиве, уже должно неплохо помочь.
2. Я вижу такую строчку: «Таким образом, если мы начнем двигать одну из парных фишек не на свое место, мы, скорее всего, не сможем решить головоломку». Единственная проблема — в подсчете расстояния до ответа, т.к. непонятно, до какого места считать расстояние. Можно в качестве оценки считать до ближайшего (тогда придется каждый раз пересчитывать расстояние заново), либо вообще забить. Итак, мы теряем отсечение по расстоянию. Посмотрим на то, что мы получим взамен. В оригинальных пятнашках позиций 16!=2.09×10¹³. В нашей игре — 16!/2⁷ =1.63×10¹¹. Получается, что действительно неочевидно, какой подход лучше, хотя чисто интуитивно мне кажется, что этот способ таки немного ускорит решение.
Простые оптимизации, которые должны заметно ускорить процесс:
1. Можно завести set, в котором хранить вообще все позиции, в которых мы побывали. Но тогда надо уверенность в том, что в каждую позицию мы приходим за минимальное число ходов, поэтому придется поиск в глубину заменить на поиск в ширину. Как вариант, можно set заменить на map, который отображает позицию в ее глубину, тогда надо идти в рекурсию только если новая найденная глубина меньше старой.
2. Я не очень понял, зачем перенумеровывать фишки. Вроде бы без перенумерации задача сильно проще. А если в endPos хранится правильно заполненное поле, то алгоритм не будет смотреть, какую из одинаковых фишек он помещает на подходящее поле и проблемы не возникнет.
Это кажется еще более простой задачей. Это просто рефлекс, а рефлексы легче всего ломаются именно таким спринтерским рывком, постепенно рефлекс тяжело сбить. А добавляя по одной-двум буквам можно постепенно обучить мозг не смотреть на конкретно эти кнопки. Ведь казалось бы, нажимать не глядя две кнопки легко научиться, а если наизусть знаешь положение N кнопок, добавить к ним еще одну тоже кажется не очень сложным. Это примерно так же сложно, как выучить новую комбинацию клавиш в какой-нибудь IDE.
Я ведь не от балды взял 4 часа, а потому что у меня самого ушло как раз столько. Основная фишка в том, что у нас в голове уже лежит информация о том, где находится какая кнопка, потому что печатаем мы часто. Ведь, даже люди, которые печатают двумя пальцами, но постоянно, не ищут, где находится та или иная кнопка. Их мозг уже содержит информацию об этом и умеет ее доставать в нужное время. Все, что нам надо — сопоставить палец каждой кнопке. Это очень простая задача, ведь положение кнопок мы уже знаем и надо просто вбить в голову шаблон нажимать каждую кнопку ближайшим пальцем. За 4 часа сосредоточенной работы вполне можно добиться успеха, если не отвлекаться.
А никто не пробовал просто сесть за любой клавиатурный тренажер, который подкидывает по паре клавиш за раз (типа стамины или ktouch) и непрерывно сидеть на нем до достижения эффекта? Мне кажется, что так можно научиться печатать вслепую часа за 4.
Насчет этого контеста не знаю, но вот, например, по Google Code Jam статистика есть: статистика. Можете посмотреть, на каких языках писалась квалификация, на каких первый тур и т.п.
По факту: языки типа Ruby неплохо работают, но довольно сильно проигрывают по скорости. Бывает даже так, что задачу на Python или Ruby надо писать алгоритмом другой сложности, т.к. обычный алгоритм работает в 5 раз медленнее и не проходит в ограничения. В Code Jam скорость не так важна, т.к. есть целых 8 минут на тесты, так что на этом соревновании все будет еще хуже. С другой стороны статистика не очень честная, т.к. понятно, что в финал проходят опытные участники, а они привыкли к C++ и Pascal, т.к. на многих олимпиадах нет Ruby.
Возможно стоит добавить следующие ссылки: Template metaprogramming на википедии Boost.MPL — фреймворк для создания программ, которые производят вычисления во время компиляции с помощью шаблонов.
UPD. уже не актуально :(
2. Я вижу такую строчку: «Таким образом, если мы начнем двигать одну из парных фишек не на свое место, мы, скорее всего, не сможем решить головоломку». Единственная проблема — в подсчете расстояния до ответа, т.к. непонятно, до какого места считать расстояние. Можно в качестве оценки считать до ближайшего (тогда придется каждый раз пересчитывать расстояние заново), либо вообще забить. Итак, мы теряем отсечение по расстоянию. Посмотрим на то, что мы получим взамен. В оригинальных пятнашках позиций 16!=2.09×10¹³. В нашей игре — 16!/2⁷ =1.63×10¹¹. Получается, что действительно неочевидно, какой подход лучше, хотя чисто интуитивно мне кажется, что этот способ таки немного ускорит решение.
1. Можно завести set, в котором хранить вообще все позиции, в которых мы побывали. Но тогда надо уверенность в том, что в каждую позицию мы приходим за минимальное число ходов, поэтому придется поиск в глубину заменить на поиск в ширину. Как вариант, можно set заменить на map, который отображает позицию в ее глубину, тогда надо идти в рекурсию только если новая найденная глубина меньше старой.
2. Я не очень понял, зачем перенумеровывать фишки. Вроде бы без перенумерации задача сильно проще. А если в endPos хранится правильно заполненное поле, то алгоритм не будет смотреть, какую из одинаковых фишек он помещает на подходящее поле и проблемы не возникнет.
По факту: языки типа Ruby неплохо работают, но довольно сильно проигрывают по скорости. Бывает даже так, что задачу на Python или Ruby надо писать алгоритмом другой сложности, т.к. обычный алгоритм работает в 5 раз медленнее и не проходит в ограничения. В Code Jam скорость не так важна, т.к. есть целых 8 минут на тесты, так что на этом соревновании все будет еще хуже. С другой стороны статистика не очень честная, т.к. понятно, что в финал проходят опытные участники, а они привыкли к C++ и Pascal, т.к. на многих олимпиадах нет Ruby.
Template metaprogramming на википедии
Boost.MPL — фреймворк для создания программ, которые производят вычисления во время компиляции с помощью шаблонов.