Идентификационные последовательности на кубике Рубика

32

Последовательность ходов - это последовательность ходов (поворотов) кубика Рубика (обозначения см. Ниже). Помимо пустой последовательности ходов, есть много других последовательностей ходов, которые никак не влияют на куб. Мы называем эти ходовые последовательности идентичными последовательностями.

Некоторые из этих последовательностей идентичности очевидно для определения, как U2 R R' U2или U D2 U' D2. В первом случае два случайных хода выполняются, U2 Rа затем сразу же отменяются R' U2. Второй похож. Первые два случайных хода, U D2а затем они отменяются, но в обратном порядке U' D2. Это работает только потому, что движение Uвлияет только на части верхнего слоя, а движение D2влияет только на части нижнего слоя. Вы можете увидеть визуализацию этих двух последовательностей ходов.

U2 RR 'U2 U D2 U 'D2

Другие идентичные последовательности могут быть не очевидны вообще. Например, последовательность R' U' R' F' U F U' R' F R F' U' R U2 R. Это довольно долго, но также никак не влияет на куб.

введите описание изображения здесь

Переместить нотацию

Ход описывает поворот одного слоя одной из шести граней куба. Ход состоит из одной буквы, представляющей грань, за которой следует необязательный суффикс, представляющий угол поворота.

Буквы и соответствующие им грани: U (вверх - сторона, обращенная вверх), D (вниз - сторона, обращенная вниз), R (справа - сторона, направленная вправо), L (слева - сторона, обращенная влево) , F (передняя сторона - сторона, обращенная к вам) и B (задняя сторона - сторона, обращенная от вас).

Если суффикса нет, грань поворачивается на 90 градусов по часовой стрелке, суффикс 'означает, грань поворачивается на 90 градусов против часовой стрелки, а суффикс 2означает, что грань поворачивается на 180 градусов по часовой стрелке.

Если у вас есть какие-либо проблемы с обозначениями, просто используйте http://alg.cubing.net , где вы можете визуализировать такие последовательности перемещения.

Соревнование

Ваша задача - написать программу, которая определяет, является ли последовательность перемещения идентификатором или нет.

Вы можете написать полную программу или функцию. Он должен получить строку, содержащую последовательность перемещений (перемещения разделяются пробелами) в качестве входных данных (через STDIN, аргумент командной строки, аргумент приглашения или функции) и вывести (через возвращаемое значение или STDOUT) логическое значение или соответствующее целое число ( True - 1 - идентификационная последовательность / False - 0 - не идентификационная последовательность).

Если суффикс 'создает проблемы в вашем языке программирования, вы можете использовать другой символ, но не цифру. R F2 U3не разрешено.

Это Codegolf, поэтому выигрывает самый короткий код (в байтах).

Тестовые случаи

"" -> True
"U2 R R' U2" -> True
"U D2 U' D2" -> True
"U2 R U2 R'" -> False
"R' U' R' F' U F U' R' F R F' U' R U2 R" -> True
"L'" -> False
"B B2 B' B2" -> True
"D D2 D'" -> False
"R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'" -> True
"D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2" -> False
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'" -> True
"R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'" -> False
"B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2" -> True
"R U2 R' U R' U2 R U2 R U R' U' R' U R U2" -> False
"U F B' R' U F' R U' F' B L U' F L'" -> False
"R2 U' R' U' R U R U R U' R" -> False
"R' F R' B2 R F' R' B2 R2" -> False
code-golf rubiks-cube Jakube
источник
Что не так с R F2 U3?
Джон Дворак
2
Я просто хочу убедиться, что у всех одинаковые предпосылки. Если бы я позволил U3, то вы могли бы просто преобразовать суффикс в цифру.
Якуб
3
Я больше привык к обозначениям, которые используют T-Top, B-Bottom и P-Posterior (сзади). Людям, вероятно, просто нравилось видеть последовательность R2 D2.
mbomb007
2
@ mbomb007 Я могу понять T для top, но я никогда не видел P для posterior, и я бы не понял его значения, если бы не ваш комментарий ...
Джон Дворжак
2
@ mbomb007 Я тоже видел эту запись, но она не так распространена и не так стара, как оригинальная запись Singmaster, и я не знаю, почему люди хотят возиться с оригиналом. Хотя Дэвид Сингмастер (насколько мне известно) не упомянул об этом, я заметил, что все лица совершенно последовательны и без столкновений, если рассматривать их как направления, а не как позиции. That is F(orward), B(ackward), L(eft), R(ight), U(p), D(own)
Уровень Река St

Ответы:

14

Haskell, 263 261 247 243 персонажа

c[x]=[x]
c(x:"2")=[x,x]
c(x:_)=[x,x,x]
s!a@[x,y,z]=case s of
 'R'|x>0->[x,-z,y]
 'B'|y>0->[z,y,-x]
 'U'|z>0->[-y,x,z]
 'L'|x<0->[x,z,-y]
 'F'|y<0->[-z,y,x]
 'D'|z<0->[y,-x,z]
 _->a
r=[-2..2]
i=mapM id[r,r,r]
f w=i==foldr(map.(!))i(c=<<words w)

Скорее простой алгоритм; каждый кубет состоит из 1,2,4 или 8 кусков, кодирующих его положение и ориентацию; 4 кусочка на ребро кубе, 8 на угол кубета, 7 кубетов неподвижны.

c c переводит каждое слово ввода в последовательность CW витков и! отправляет каждый фрагмент в соответствии . iэто я позиция dentity. fявляется основным е соборование.

Я не слишком доволен c функцией homp, но, похоже, не могу найти способ ее укоротить (однако @Nimi сделал)

Джон Дворжак
источник
Как насчет c(x:"2")=[x,x]и c(x:_)=[x,x,x]. Сохраняет 2 байта.
Ним
Если вы используете i=sequence[s,s,s]и меняете все кортежи на списки (то есть: (x,y,z)становитесь [x,y,z]) - это сохранит ~ 9 символов. Inlining это экономит еще 4. Отказ от _дела !спасает еще один 11.
MtnViewMark
@MtnViewMark сделано и улучшено i, спасибо. Не уверен, что вы подразумеваете под встраиванием i- пожалуйста, обратите внимание, что оно появляется дважды в определении для f. Не уверен, что вы имеете в виду, отбрасывая _регистр - либо _->aполное исключение, либо перемещение его наверх приводит к неисчерпывающему исключению шаблона, а перемещение наверх не сохраняет никаких символов в любом случае. Однако мне удалось сохранить там 5 символов.
Джон Дворак
Отличное решение. Я проверил все тестовые случаи.
Якуб
Еще раз поздравляю с вашим решением. Поскольку вы представили самый короткий код, вы получаете награду в 100 репутации.
января
4

Кубы , 6 4 байта

¶=8%

Я выигрываю: P

¶=8%
¶     read a string, evaluate as Cubically code
 =8   set notepad to (notepad == 8th face)
   %  print notepad

Блокнот инициализируется на ноль. Восьмое «лицо» содержит 1, если куб не решен, и 0 в противном случае.

Попробуйте онлайн!

MD XF
источник
3
Похоже, интересный язык. Но поскольку язык был создан после публикации заявки, он не имеет права на победу.
Якуб
2
@Jakube Я согласен, что это не должно быть принято, просто потому, что это язык со встроенными кубиками Рубика, опубликованными так поздно после вызова и полностью уничтожающими другие ответы. Но технически он имеет право на победу в соответствии с мета (не конкурирующее правило было несколько отменено).
MD XF
3

J - 232, 220, 381, 315 296 байт

Это решение кодирует все операции как перестановки граней и работает на основе того факта, что все скручивания граней фактически являются одинаковыми при вращении всего куба.

Редактировать : еще немного игры в гольф

f=:+/~6&*
r=:4 :'y f&.>(]{^:x~)&.C.;/i.2 4'"0
t=:((r~0),_4<\44#.inv 1478253772705907911x)&C.&.
Y=:(C.(,0 2 r 4 5),;/4 f&i.8)&{^:t
X=:((,1 1 0 2 r 2 4 3 1)C.C.;/0 4 2 5 f i.8)&{^:t
61".@A."1'=: ',"#~6 3$'D0XR1YF1XU2YB3XL3Y'
T=:[:(_2".@}.'(i.48)-:'&(,,[))[:(,'^:',])/&.>@|.&.;:[:''''&=@{.`]},:&'3'

Кроме предыдущих попыток, это делает принять поворот угла во внимание.

fэто просто вспомогательная функция. rделает вращение одного лица. лицо кодируется следующим образом:

  1. все углы в шагах 6
  2. все края в шагах по шесть

этот порядок облегчает кодирование поворотов и поворотов. tэто наречие, которое поворачивает лицо под определенным вращением куба, выбирая лицо.

X а также Y являются наречиями, которые принимают в качестве левого аргумента число в этом направлении всего куба.

Следующая строка определяет все повороты: 3 символа на оборот: имя, количество поворотов и направление.

Последняя строка определяет тестовый глагол T, преобразовывая 3 и' в нотацию Power, переворачивая порядок операций, добавляя тестовый вектор и, наконец, исключая всю вещь.

Более подробная информация по запросу.

tests =: (] ;. _2) 0 : 0

 U2 R R' U2
 U D2 U' D2
 U2 R2 R'
 R' U' R' F' U F U' R' F R F' U' R U2 R
 L'
 B B2 B' B2
 D D2 D'
 R F' D2 U B' F2 B' U2 D2 F2 B2 U F R'
 D2 U' R2 U F2 D2 U' R2 U' B' L2 R' B' D2 U B2 L' D' R2
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U R2 U' R2 U' D R2 U' R2 U R2 D'
 R U R' U' R' F R2 U' R' U' R U R' F' R2 U' R2 U R2 U' D R2 U' R2 U R2 D'
 B2 F2 U' F2 U R2 F2 U2 B D' R' D' R2 D' F2 U' F U R2 U R B D B D2 L2 D' F2 U D' R' D B R2 D2 F2 R' F2 D2
 R U2 R' U R' U2 R U2 R U R' U' R' U R U2
 U F B' R' U F' R U' F' B L U' F L'
 R2 U' R' U' R U R U R U' R
 R' F R' B2 R F' R' B2 R2
)
res =: 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
res ([,],:=) T"1 tests NB. passes all tests.
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

NB. some handy display methods:
dispOrig=: (". ;._2) 0 :0
   _   _   _   5  29  11   _   _   _   _   _   _
   _   _   _  47  _1  35   _   _   _   _   _   _
   _   _   _  23  41  17   _   _   _   _   _   _
   3  27   9   0  24   6   1  25   7   2  26   8
  45  _3  33  42  _6  30  43  _5  31  44  _4  32
  21  39  15  18  36  12  19  37  13  20  38  14
   _   _   _   4  28  10   _   _   _   _   _   _
   _   _   _  46  _2  34   _   _   _   _   _   _
   _   _   _  22  40  16   _   _   _   _   _   _
)
ind =: dispOrig i.&, i. 48 NB. indices of i.48 in the original display

disp =: (9 12$(,dispOrig) ind}~ ])
changed =: 1 : '(u ~:&disp ]) i.48' NB. use to debug permutation verbs: L ch
vch =: 1 :'disp  ((]+_*=) u)'
NB. viewmat integration RGB
cm =: 255 * 1 0 0 , 1 1 1, 0 1 0, 1 1 0, 1 0.5 0, 0 0 1,: 0 0 0 NB. colormap
NB. use as:  "cube i. 48" for seeing a nice folded out cube.
cube =: cm viewmat (>&7 + >&15 + >&23 + >&31 + >& 39 + >&47)@|@disp@]
jpjacobs
источник
11
«поскольку результаты моих тестов не соответствуют приведенным ...» как, например, ваше решение не работает? Тогда я не стал бы это публиковать ...
Джон Дворак
Вы правы. Исправлено сейчас.
jpjacobs
Я добавил 4 дополнительных теста. Двое из них все еще возвращают ложный результат. Похоже, вы игнорируете ориентацию углов.
Якуб
@jpjacobs Теперь у нас есть награда в 100 представителей. Хотите исправить свой код?
Якуб
Вуаля, сделано. Теперь просто уменьшаем его.
jpjacobs
2

Python 3: 280 символов

Это не участник соревнования. Во-первых, потому что я сам задал вызов, а во-вторых, потому что это не мой код. Все кредиты принадлежат Стефану Пухману , который обнаружил этот удивительный способ симуляции кубика Рубика. Я только сделал некоторые игры в гольф и некоторые незначительные изменения в отношении проблемы.

def f(a):
 s=t="UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR".split()
 for m in a.split():q="FLBR FRBL FDBU FUBD URDL ULDR".split()['UDLRFB'.index(m[0])];n=2+"2'".find(m[-1]);s=[[p,p.translate(str.maketrans(q,q[n:]+q[:n]))][m[0]in p]for p in s]
 return s==t

Идея этого заключается в следующем. sпредставляет расположение частей UF, URи так далее. Например: s = ['DF', 'BL', ...]означает, что кусок UFнаходится в позиции DF, кусок URнаходится в позицииBL , ...

Как меняется положение фигуры при выполнении хода. Если вы делаете Uперемещение, все наклейки (цвета) Uслоя, которые обращены к передней грани, перемещаются в левую сторону. Наклейки с левой стороны перемещаются назад, справа и вот так. Закодированные с помощью FLBR. Некоторые примеры: UFперемещается в UL, UFRперемещается в ULFи так далее. Поэтому применение перемещения - это просто перевод граней кусков в соответствующем слое.

Jakube
источник