Твое задание
... сделать то, что Брайан Фантана, очевидно, не смог, и решить кубик Рубика 2x2x2.
Расположение
- - A B - - - -
- - C D - - - -
E F G H I J K L
M N O P Q R S T
- - U V - - - -
- - W X - - - -
И будет передан вам через стандартный ввод или командную строку (ваш выбор - укажите в своем ответе) в формате:
ABCDEFGHIJKLMNOPQRSTUVWX
Обратите внимание, что AD составляет U-грань (вверх), EFMN составляет L-грань (слева), GHOP - F-грань (спереди), IJQR - R-грань (справа), KLST - B-лицо (спина) и UX составляют D-лицо (вниз).
Будет шесть уникальных символов, представляющих каждый цвет, но они могут различаться, поэтому подготовьтесь к любой комбинации из 6 символов ascii, которые будут использоваться для каждого цвета.
Характеристики
- Ваш код должен выводить решение, используя только правую (R), верхнюю (U) и переднюю (F) грани, и должно использовать стандартные обозначения: R, R ', R2, U, U', U2, F, F ', F2. Вы можете найти больше информации здесь . Ограничение на подмножество RUF является стандартным для куба 2x2 (Совет: обрабатывайте нижний задний левый угол как фиксированное основание для работы).
- Ваш код должен быть способен решить все возможные перестановки карманного куба.
- Каждое решение должно занять менее 30 секунд.
- Каждое решение должно быть менее 30 ходов.
- Бонус -20% будет предоставлен для решений, всегда предоставляющих ответы менее чем за 20 ходов (пожалуйста, опубликуйте его в своем ответе, чтобы я мог тщательно его проверить)
- Бонус -50% будет предоставлен за код, который всегда обеспечивает оптимальное решение. - Опять же, пожалуйста, рекламируйте в своем ответе
- Решения не должны содержать два последовательных движения на одной и той же грани, потому что их можно легко объединить в одно движение.
- Решения могут содержать один пробел - и только один пробел - между каждым ходом.
- Вся последовательность решения, если необходимо, может содержаться в паре скобок, кавычек, фигурных скобок, скобок или вставок, но никакой другой посторонний вывод не допускается.
- Пожалуйста, предоставьте кратко прокомментированную версию вашего кода или подробное объяснение вашего кода.
- Нет использования внешних файлов. Это включает в себя Интернет, таблицы данных и библиотеки / пакеты, созданные для такого рода проблем.
- Самый короткий код по количеству байтов выигрывает.
- Победителя выбирают в среду (30 июля 2014 г.).
code-golf
puzzle-solver
permutations
rubiks-cube
Кайл Маккормик
источник
источник
Ответы:
Python 2.7: 544 байта -50% = 272 байта **
Stackexchange заменяет вкладки несколькими пробелами. Так что техническая версия имеет 549 байтов. Просто замените первые два пробела в строках 6-10 на табулятор.
Идея, лежащая в основе моей программы: моей первой идеей был поиск в дыхании. Но это заняло слишком много времени. Около 2 минут для тяжелой (11 ходов оптимальной) схватки. Поэтому я решил подойти к проблеме с обеих сторон. Я использую два комплекта. Я генерирую последовательно все состояния с расстоянием 1,2,3, ... до скремблирования и сохраняю их в set1, и в то же время все состояния с расстоянием 1,2,3, ... до решенного состояния и сохраняю их в наборе 2. В первый раз, когда состояние находится в обоих наборах, мы нашли решение.
Для этого мне нужны цвета решенного куба, которые не известны. Символы 13, 20 и 23 определяют цвет слева, сзади и вниз. Но этих трех цветов достаточно, чтобы представить куб. Я просто заменяю 3 других цвета пробелами и могу представить свое решенное состояние как «____ll____bbll____dddd».
Да, и для сокращения перестановок я использовал идею из /codegolf//a/34651/29577
Безголовая версия:
Я очень доволен результатом, потому что я новичок в Python. Это одна из моих первых программ на Python.
изменить: через полгода: 427 - 50% = 213,5
Получил немного больше опыта в Python и в гольф. Поэтому я пересмотрел свой оригинальный код и смог сохранить более 100 символов.
Я в основном использую точно такой же подход. Самое большое изменение в том, что я больше не определяю функцию. Вместо того
я могу сделать
Также я немного изменил ход лямды. Сначала сокращаем, а затем напрямую интегрируем код, поскольку вызов функции появляется только один раз.
Я сохраняю для каждого состояния список чисел от 0 до 11, чтобы представлять ходы, вместо строки, содержащей ходы. Числа конвертируются в самом конце.
Также я объединил два цикла for
'for k in r(3):for j in r(3):
в одинfor y in r(12)
. Поэтому я тоже должен делать ходыU4, R4, F4
. Конечно, такой шаг не появляется в кратчайшем решении, поэтому" 2'"[x%4]
работает. (Еслиx % 4 == 3
будет исключение индекса вне диапазона)Это также немного быстрее, так как я ищу запись во втором сете ранее. Около 0,5 секунды для решения 11 ходов.
источник
C 366 - оптимальный бонус 50% = 183
Используя рекурсию, программа выполняет поиск по дереву глубиной до 11 шагов (максимальная длина оптимального солютона согласно http://en.wikipedia.org/wiki/Pocket_Cube и странице, упомянутой ниже) и когда она находит решение он печатает его (длиной до 22 символов, отслеживается аргументом функции
m
.) Используемый порядок является своего рода словарным порядком, где все маршруты, начинающиеся с U, U2, U ', ищутся до того, как будут найдены любые маршруты, начинающиеся с R или F. Таким образом, он не обязательно сначала находит оптимальное решение.Когда решение печатается,
r
делается равным,m
что гарантирует, что впоследствии будут напечатаны только равные или более короткие решения. Размещениеr=m-2
стоит дополнительно 2 символа, но обеспечивает печать только одного решения каждой найденной длины (вплоть до оптимального). Если вы хотите, чтобы оно ТОЛЬКО показывало оптимальное решение, лучшее найденное решение должно быть сохранено в переменной, а оптимальное решение должно быть напечатано в конце программы (это будет стоить около 15 дополнительных символов).входные данные считываются в массив
c[]
с индекса 64 и далее. Это необходимо для использования букв алфавита в подвижной таблице. Символы@
черезW
используются вместо A через X в вопросе, потому что необходимо начать с четного числа, чтобы сделать тест для решения решений.c['Z']
также используется для временного хранения, потому что для выполнения 4-кратного поворота требуется всего 5 назначений. Поскольку первая частьc[]
не используется, она доступна для хранения решения (которое заканчивается нулевым байтом, как и все строки Си).for(i..)
проходит последовательность из четырех четвертей лица, указанногоn
.Первый
for(j..)
выполняет фактическую замену в соответствии с таблицейt[]
.Чтобы проверить, решен ли куб, необходимо проверить только четыре боковые грани. Части URF и DFR можно различить даже при удаленных наклейках U и D, потому что одна часть читает XRF по часовой стрелке, а другая XFR. Если две части взаимозаменяемы так, что U показывает на нижней грани, и наоборот, цвет F будет отображаться на правой грани, и наоборот.
Вторая
for(j..)
подсчитывает количество несоответствий на четырех боковых гранях. Например, для передней грани сравниваются G & O, H & P и G & H (дважды). Еслиe
== 0, куб решается. Еслиe
<9 илиe
<13, может быть возможно решить куб за следующий ход или 2 хода соответственно. Иначе определенно невозможно решить куб за это количество ходов. Чтобы сэкономить время, эта эвристика используется для обрезки дерева поиска и предотвращения потери времени на многих ветвях глубины 10 или 11, которые будут безуспешными. Выражается в формуле, это становитсяe<45-m*2
.Код без правил
Производительность
Программа была протестирована с шаблонами с 1 по 13 на http://www.jaapsch.net/puzzles/cube2.htm
Следующие результаты дают время на моей машине, чтобы найти ВСЕ оптимальные решения (для любопытных.) Также для более сложных позиций, время дается для упомянутой выше 2-байтовой модификации, которая находит только одно оптимальное решение. Для этого даются сроки как для поиска первого решения, так и для завершения программы. Указанные решения (которые обычно отличаются от решений, полученных путем обращения генераторов на связанной странице) были проверены с помощью онлайн-симулятора кубов.
источник