Sequências de identidade no cubo de Rubik

32

Uma sequência de movimentos é uma sequência de movimentos (voltas) no Cubo de Rubik (para a notação, veja abaixo). Além da sequência de movimentação vazia, há muitas outras seqüências de movimentação que não têm nenhum efeito no cubo. Chamamos essas seqüências de movimento de sequências de identidade.

Algumas dessas seqüências de identidade são óbvias para determinar, como U2 R R' U2ou U D2 U' D2. No primeiro, dois movimentos aleatórios são feitos U2 Re depois desfeitos imediatamente R' U2. O segundo é semelhante. Primeiros dois movimentos aleatórios U D2e depois são desfeitos, mas em ordem inversa U' D2. Isso só funciona, porque o movimento Uafeta apenas as partes da camada superior e o movimento D2afeta apenas as partes da camada inferior. Você pode ver uma visualização dessas duas seqüências de movimento.

U2 RR 'U2 U D2 U 'D2

Outras sequências de identidade podem não ser óbvias. Por exemplo, a sequência R' U' R' F' U F U' R' F R F' U' R U2 R. É bem longo, mas também não tem efeito no cubo.

insira a descrição da imagem aqui

Mover notação

Um movimento descreve a volta de uma camada de uma das seis faces do cubo. Um movimento consiste em uma letra representando a face seguida por um sufixo opcional representando o ângulo de virada.

As letras e suas faces correspondentes são U (Para cima - o lado voltado para cima), D (Para baixo - o lado voltado para baixo), R (Direita - lado voltado para a direita), L (Esquerda - lado voltado para a esquerda) , F (Frente - o lado voltado para você) e B (Traseira - o lado voltado para você).

Se não houver sufixo, o rosto será girado 90 graus no sentido horário, o sufixo 'significa, o rosto será girado 90 graus no sentido anti-horário e o sufixo 2significa que o rosto será girado 180 graus no sentido horário.

Se você tiver algum problema com a notação, basta usar http://alg.cubing.net , onde você pode visualizar essas seqüências de movimento.

O desafio

Sua tarefa é escrever um programa que determine se uma sequência de movimentação é uma identidade ou não.

Você pode escrever um programa completo ou uma função. Ele deve receber uma sequência contendo uma sequência de movimentação (as movimentações são separadas por espaços) como entrada (via STDIN, argumento da linha de comandos, argumento de prompt ou função) e saída (via valor de retorno ou STDOUT) um valor booleano ou um número inteiro correspondente ( Verdadeiro - 1 - sequência de identidade / Falso - 0 - não sequência de identidade).

Se o sufixo 'criar problemas na sua linguagem de programação, você poderá usar um símbolo diferente, mas não no dígito. R F2 U3não é permitido.

Este é um codegolf, portanto o código mais curto (em bytes) vence.

Casos de teste

"" -> 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
fonte
O que há de errado R F2 U3?
John Dvorak
2
Eu só quero ter certeza de que todos tenham as mesmas condições prévias. Se eu permitir U3, você pode simplesmente converter o sufixo em um dígito.
Jakube 21/01
3
Estou mais acostumado com a notação que usa T-Top, B-Bottom e P-Posterior (traseira). As pessoas provavelmente só gostaram de ver a sequência R2 D2.
mbomb007
2
@ mbomb007 eu posso entender T para cima, mas eu nunca vi P para posterior e eu não compreender o seu significado se não fosse pelo seu comentário ...
John Dvorak
2
@ mbomb007 Também vi essa notação, mas ela não é tão comum nem tão antiga quanto a notação Singmaster original, e não sei por que as pessoas querem mexer com a original. Embora David Singmaster (até onde eu saiba) não tenha mencionado isso, observei que todos os rostos são perfeitamente consistentes e sem conflitos, se considerados como direções e não como posições. That is F(orward), B(ackward), L(eft), R(ight), U(p), D(own)
Level River St

Respostas:

14

Haskell, 263 261 247 243 caracteres

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)

Algoritmo bastante direto; cada cubeta é feita de 1,2,4 ou 8 pedaços que codificam sua posição e orientação; 4 pedaços por cubeta de borda, 8 por cubeta de canto, 7 cubelets são estacionários.

c c hompa cada palavra da entrada em uma sequência de curvas CW e !envia cada parte de acordo com uma curva. ié o i posição dentidade.fé o principal f unção.

Não estou muito feliz com a cfunção homp, mas também não consigo encontrar uma maneira de reduzi-la (@Nimi, no entanto)

John Dvorak
fonte
Que tal c(x:"2")=[x,x]e c(x:_)=[x,x,x]. Salva 2 bytes.
nimi 21/01
Se você usar i=sequence[s,s,s]e alterar todas as tuplas para listas (ou seja: (x,y,z)torna - se [x,y,z]), ele salvará ~ 9 caracteres. Inlining, economiza mais 4. Largando o _caso de !salva outra 11.
MtnViewMark
@MtnViewMark pronto e aprimorado i, obrigado. Não sabe ao certo o que você quer dizer com inlining i- observe que ele aparece duas vezes na definição de f. Não sei ao certo o que você quer dizer com retirar a _caixa - deixar _->acompletamente de fora ou movê-lo para o topo gera uma exceção de padrão não exaustiva, e movê-lo para o topo não salva nenhum caractere. Eu consegui salvar 5 caracteres lá, no entanto.
John Dvorak
Ótima solução. Eu verifiquei todos os casos de teste.
Jakube 22/01
Mais uma vez, parabéns pela sua solução. Como você apresentou o código mais curto, você recebe a recompensa no valor de 100 reputação.
Jakube
4

Cubicamente , 6 4 bytes

¶=8%

Eu ganho: P

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

O bloco de notas é inicializado em zero. A oitava "face" contém 1 se o cubo não for resolvido e 0 caso contrário.

Experimente online!

MD XF
fonte
3
Parece uma linguagem interessante. Mas como o idioma foi criado após o lançamento do desafio, ele não é elegível para ganhar.
Jakube
2
@Jakube Concordo que não deve ser aceito, apenas pelo fato de ser uma linguagem com os cubos de Rubik embutidos postados tão tarde após o desafio e dizimar totalmente as outras respostas. Mas é tecnicamente elegível para ganhar de acordo com a meta (a regra de não concorrência foi revogada um pouco).
MD XF
3

J - 232, 220, 381, 315 296 bytes

Essa solução codifica todas as operações como permutações de face e funciona com base no fato de que todas as torções de face são realmente as mesmas, sob uma rotação de todo o cubo.

Edit : um pouco mais de golfe

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'

Além das tentativas anteriores, isso não ter rotação canto em conta.

f é apenas uma função auxiliar. rfaz a rotação de uma face. um rosto é codificado da seguinte maneira:

  1. todos os cantos em etapas de 6
  2. todas as arestas em etapas de seis

essa ordem facilita a codificação de rotações e torções. té um advérbio que torce a face sob uma determinada rotação do cubo, selecionando a face.

Xe Ysão advérbios que tomam como argumento esquerdo o número nessa direção de todo o cubo.

A próxima linha define todas as rotações: 3 caracteres por rotação: o nome, o número de rotações e a direção.

A última linha define o verbo de teste T, convertendo 3 e 'para notação Power, invertendo a ordem de operação anexando o vetor de teste e, finalmente, extraindo a coisa toda.

Mais detalhes mediante solicitação.

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
fonte
11
"como os resultados dos meus testes não correspondem aos dados fornecidos ..." como em, sua solução não funciona? Eu não postá-lo então ...
John Dvorak
Você está certo. Corrigido agora.
Jspjacobs
Eu adicionei 4 casos de teste adicionais. Dois deles ainda retornam o resultado falso. Parece que você ignora a orientação dos cantos.
Jakube
@jpjacobs Há uma recompensa de 100 representantes na questão agora. Deseja corrigir seu código?
Jakube
Voila, pronto. Agora apenas reduzi-lo.
jpjacobs
2

Python 3: 280 caracteres

Este não é um participante do desafio. Em primeiro lugar, porque eu próprio o desafio e, em segundo lugar, porque não é o meu código. Todos os créditos pertencem a Stefan Pochmann , que descobriu essa maneira impressionante de simular um cubo de Rubik. Eu só pratiquei golfe e algumas pequenas mudanças em relação ao desafio.

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

A idéia por trás disso é a seguinte. srepresenta a localização das peças de UF, URe assim por diante. Por exemplo: s = ['DF', 'BL', ...]significa que a peça UFestá na posição DF, a peça URestá na posiçãoBL , ...

Como a posição de uma peça muda, ao fazer um movimento. Se você fizer uma U-move, todos os carros (cores) da U-layer, que enfrentou a face frontal, movimento para a face esquerda. Os adesivos da face esquerda movem-se para trás, para a direita e para a frente. Codificado por FLBR. Alguns exemplos: UFmove para UL, UFRmove para ULFe assim por diante. Portanto, aplicar um movimento é simplesmente traduzir as faces das peças na camada correspondente.

Jakube
fonte