Уважаемое время прохождения педантов означает, что картины "Кубиков Рубика" (на футболках, плакатах и т. Д.) На самом деле не разрешимы.
Первое, что следует проверить, это то, что куб состоит из правильных частей. Чтобы быть разрешимым, кубу нужно шесть цветов каждый с девятью квадратами. Кубу также необходимо, чтобы каждый край и угловая единица (это кубы меньшего размера, составляющие куб) были уникальными. Мало того, что они должны быть уникальными, но если две центральные части расположены напротив друг друга, ни одна из краев или угловых частей не может содержать оба этих цвета.
Если у вас есть куб, состоящий из всех правильных частей, вам все еще нужно убедиться, что он может быть решен. Здесь есть пара правил, поэтому я опрошу эксперта, чтобы объяснить их, спойлер ниже объясняет, как мы можем это сделать. Если вы заинтересованы в решении проблемы самостоятельно, вам не нужно посещать сайт, чтобы понять или принять участие в этой задаче.
Ваша задача - взять шаблон в качестве входных данных и определить, является ли он на самом деле решаемым кубиком Рубика. Чтобы быть разрешимым, должен быть способ выполнения допустимых перемещений куба, чтобы куб имел только один цвет на каждой грани (а разные грани имели разные цвета). Большинство кубиков Рубика имеют стандартную раскраску (белый напротив желтого и т. Д.), Вы не можете предполагать, что состояние разрешения следует за этой конкретной раскраской.
Действительным движением является вращение одной или нескольких граней куба по часовой стрелке или против часовой стрелки. При вращении грани куба все квадраты, граничащие с гранью, также вращаются, оставаясь на связи с гранью, которой они ранее касались.
IO
Вы можете взять куб любым разумным способом. Если у вашего языка есть какой-то встроенный тип «кубическое лицо», подходящий для ввода, который отлично подходит для ввода, в противном случае вы можете взять двумерный массив сети куба, 1 3 на 3 списка для каждого лица. Просто будь разумным. Если вы хотите узнать, является ли определенный формат приемлемым, прокомментируйте или напишите мне в чате, и я добавлю к запросу, чтобы заявить о его действительности.
Ваш входной формат должен поддерживать только до 9 возможных цветов.
Для вывода это проблема решения, поэтому вы должны вывести одно постоянное значение для «Да, это действительный кубик Рубика» и одно другое постоянное значение для «Нет, это не допустимый куб Рубика».
Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.
Тестовые случаи
Вот тестовые случаи. Они отформатированы как сеть куба с каждым квадратом в виде одной буквы. Разные буквы представляют разные цвета. Любые дополнительные тестовые случаи могут быть добавлены по запросу.
разрешимый
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YYY
YYY
YYY
GRR
GRR
ORW
WWRBWYBOOGGY
GGRBWGYBBOOO
OOGRWGYWWRBB
WYO
YYB
YYB
неразрешимый
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWYWBBBOOO
YWY
YYY
YYY
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YWY
YYY
YYY
RRR
RRR
GGG
GGYWYWRBBOBO
GGYWWWROBOOO
GGYWWWRBBOOO
BBB
YWY
YYY
RRW
RRW
GGG
GGYWWYEOBROO
GGYWWYEBBROO
GGOWWYWBBROO
BBB
YYW
YYO
источник
Ответы:
Кубы ,
166416311089 байтВывод, если решаемо:
Solved!
Вывод, если неразрешимо: (пусто, без вывода)
Ввод должен быть отформатирован как кубический дамп куба (см.
Debug
Раздел). Это было явно разрешено ФП.объяснение
Эта программа использует подход с использованием алгоритма дьявола для итерации по каждому возможному состоянию куба в той же группе, что и решенный куб. Если куб разрешим, он будет решен в какой-то момент до завершения работы алгоритма (при условии, что алгоритм, который я использовал, работает правильно).
Каждая строка, начинающаяся с
⇒
(0x84 в кодовой странице Cubically), является определением функции; эти функции строятся друг от друга, чтобы составить настоящий алгоритм дьявола. Первая строка, которая будет выполнена, является последней:r
читает куб из stdin и устанавливает для него куб памяти.s
переводит интерпретатор в «resolmode», что означает, что он выходит и печатает,Solved!
если куб решается (после того, как не решен) в любой точке. Остальные команды (которые просто повторяютсяf36f71
8 раз) соответствуют окончательному алгоритму внизу связанной страницы:Как я могу запустить его?
Вы можете попробовать это онлайн , но эта ссылка не работает. TIO почти наверняка истечет время ожидания до завершения работы этого алгоритма (максимальное время выполнения для интерпретатора составляет 60 секунд). Если куб не разрешим, для этого кубического алгоритма потребуется 11 миллионов лет (около 15,2 миллиона ходов в секунду, что и получается в моей среде Cloud9 IDE ).
Кроме того, вам нужно много памяти для выполнения 3-х ходов секстиллиона. Кубически может выполнять около 4 миллионов ходов в секунду, но процесс, скорее всего, будет остановлен из-за переполнения памяти . Он умирает через 15 секунд на моей виртуальной машине с 512 МБ памяти.Зачем выполнять перемещения в уже выделенной памяти с плоским массивом? Нашел утечку памяти (или двадцать) и исправил ее .Вот гораздо более читаемая версия, которая ведет себя так же.
Но я очень хочу увидеть, что это работает!
Первый фактический ход, который выполняется в алгоритме этого дьявола
F2
, так что самый быстрый куб, который нужно решить, был бы зашифрован сF2
:Это действительно выполняется за 0,007 секунды на TIO .
Как это можно улучшить?
Есть конечно больше алгоритмов дьявола; Я нашел тот, который использует менее тридцати ходов, которые делает этот. Однако это обойдется в несколько тысяч байт (примерно на 100 МБ) и несколько десятков часов преобразования сложной гамильтоновой схемы в кубический код.
Также возможно удалить некоторые функции и поместить их прямо в цикл внизу. Тем не менее, я собираюсь пожертвовать некоторыми байтами для удобства чтения.
Кроме того, я рассматриваю модификацию циклического поведения Cubically, чтобы можно было легче повторять алгоритмы 7 или 8 раз (вместо простого их кодирования с помощью вызовов функций, повторяемых 7 или 8 раз в источнике). Или я поработаю над волшебством с помощью блокнота и играю в гольф, используя больше петель.
Обратите внимание, что я буду продолжать оптимизировать все, что возможно в интерпретаторе, так что это может сработать на среднем ПК в будущем!
Кубически, 2 байта
Мне больше нравится ответ выше, поэтому я добавляю это как альтернативное решение. Это занимает менее секунды, а не несколько миллионов лет.
Выведите, если куб разрешим: (ничего)
Выведите, если куб неразрешим:
Error: The cube has reached an unsolvable state.
источник
APL (Dyalog Classic) ,
190174 байтаПопробуйте онлайн!
Аргумент представляет собой матрицу 3x2 (row0: спереди назад, row1: слева направо, row2: вверх вниз) из матриц 3x3 символов. Возвращает 1 для разрешимого кубика Рубика, 0 в противном случае.
В ссылке TIO функция
t
, которая не включена в число символов, читает 9 строк ввода, преобразует их из формата ввода по умолчанию (нетто) в требуемую матрицу 3x2 x 3x3, вызывает решение и печатает OK, если результат как и ожидалось.Алгоритм разбивает данный куб на 26 кубов - строки длиной 3 (углы), 2 (ребра) и 1 (центры). Он также генерирует 26 кубов решенного куба с теми же 6 центральными кубами. Все следующие критерии должны быть выполнены:
среди 6 центров дубликатов нет
наборы заданных / решенных кубов совпадают, вплоть до вращения - например, рассмотреть
'WBR'
и'BRW'
тот же куб, но не'BWR'
четности как перестановки углов, так и перестановок ребер четны
сумма по модулю 3 индексов вращения угловых (например , принимая «наименьшее» письмо в
B
качестве точки отсчета мы имеем:'BRW'→0
,'WBR'→1
,'RWB'→2
) совпадают между данными и решенных кубов; то же самое для углов по модулю 2источник