Séquences d'identité sur le cube de Rubik

32

Une séquence de mouvements est une séquence de mouvements (tours) sur un Rubik's Cube (pour la notation, regardez ci-dessous). À côté de la séquence de déplacement vide, il existe de nombreuses autres séquences de déplacement, qui n'ont aucun effet sur le cube. Nous appelons ces séquences d'identité des séquences de mouvements.

Certaines de ces séquences d'identité sont évidentes à déterminer, comme U2 R R' U2ou U D2 U' D2. Dans le premier, deux mouvements aléatoires sont effectués U2 Ret ensuite immédiatement annulés R' U2. Le second est similaire. Deux premiers mouvements aléatoires U D2et ensuite ils sont annulés, mais dans l'ordre inverse U' D2. Cela ne fonctionne que parce que le déplacement Un'affecte que les morceaux du calque supérieur et que le déplacement n'affecte D2que les morceaux du calque inférieur. Vous pouvez voir une visualisation de ces deux séquences de mouvements.

U2 RR 'U2 U D2 U 'D2

D'autres séquences d'identité peuvent ne pas être évidentes du tout. Par exemple la séquence R' U' R' F' U F U' R' F R F' U' R U2 R. Il est assez long, mais n'a aucun effet sur le cube.

entrez la description de l'image ici

Déplacer la notation

Un coup décrit le tour d'une couche de l'une des six faces du cube. Un mouvement consiste en une lettre représentant le visage suivie d'un suffixe facultatif représentant l'angle de virage.

Les lettres et leurs faces correspondantes sont U (Haut - le côté tourné vers le haut), D (Bas - le côté tourné vers le bas), R (Droite - le côté tourné vers la droite), L (Gauche - le bord tourné vers la gauche) , F (avant - le côté face à vous) et B (arrière - le côté face à vous).

S'il n'y a pas de suffixe, le visage est tourné de 90 degrés dans le sens des aiguilles d'une montre, le suffixe 'signifie, le visage est tourné de 90 degrés dans le sens inverse des aiguilles d'une montre, et le suffixe 2signifie, le visage est tourné de 180 degrés dans le sens des aiguilles d'une montre.

Si vous avez des problèmes avec la notation, utilisez simplement http://alg.cubing.net , où vous pouvez visualiser de telles séquences de mouvement.

Le défi

Votre tâche consiste à écrire un programme, qui détermine si une séquence de mouvement est une identité ou non.

Vous pouvez écrire un programme complet ou une fonction. Il doit recevoir une chaîne contenant une séquence de déplacement (les déplacements sont séparés par des espaces) en entrée (via STDIN, argument de ligne de commande, invite ou fonction) et sortir (via la valeur de retour ou STDOUT) une valeur booléenne ou un entier correspondant ( Vrai - 1 - séquence d'identité / Faux - 0 - pas de séquence d'identité).

Si votre suffixe 'crée des problèmes dans votre langage de programmation, vous pouvez utiliser un symbole différent, mais pas à digit. R F2 U3n'est pas autorisé.

C'est codegolf, donc le code le plus court (en octets) l'emporte.

Cas de test

"" -> 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
la source
Quel est le problème avec R F2 U3?
John Dvorak
2
Je veux juste m'assurer que tout le monde a les mêmes conditions préalables. Si je le permets U3, vous pouvez simplement transposer le suffixe en chiffres.
Jakube
3
Je suis plus habitué à la notation qui utilise T-Top, B-Bottom et P-Posterior (arrière). Les gens ont probablement juste aimé voir la séquence R2 D2.
mbomb007
2
@ mbomb007 Je peux comprendre T pour top, mais je n'ai jamais vu P pour postérieur et je ne comprendrais pas sa signification sans votre commentaire ...
John Dvorak
2
@ mbomb007 J'ai également vu cette notation, mais elle n'est ni aussi courante ni aussi ancienne que la notation Singmaster originale, et je ne sais pas pourquoi les gens veulent jouer avec l'original. Bien que David Singmaster (pour autant que je sache) ne l'a pas mentionné, j'ai observé que tous les visages sont parfaitement cohérents et sans heurts s'ils sont considérés comme des directions plutôt que des positions. That is F(orward), B(ackward), L(eft), R(ight), U(p), D(own)
Level River St

Réponses:

14

Haskell, 263 261 247 243 caractères

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)

Algorithme plutôt simple; chaque cubelet est constitué de 1,2,4 ou 8 morceaux codant sa position et son orientation; 4 morceaux par cubelet de bord, 8 par cubelet d'angle, 7 cubelet sont stationnaires.

c c homps chaque mot de l'entrée dans une séquence de tours CW, et !envoie chaque bloc selon un tour. iest la position i dentity. fest la principale fonction .

Je ne suis pas trop satisfait de la cfonction homp, mais je n'arrive pas à trouver un moyen de la raccourcir non plus (@Nimi l'a fait, cependant)

John Dvorak
la source
Que diriez-vous c(x:"2")=[x,x]et c(x:_)=[x,x,x]. Enregistre 2 octets.
nimi
Si vous utilisez i=sequence[s,s,s]et changez tous les tuples en listes (c'est-à-dire: (x,y,z)devient [x,y,z]) - cela économisera ~ 9 caractères. En l'inclinant, vous en économisez 4 de plus. La suppression de l' _affaire en !sauve encore 11.
MtnViewMark
@MtnViewMark terminé et amélioré i, merci. Je ne sais pas exactement ce que vous entendez par insertion i- veuillez noter qu'il apparaît deux fois dans la définition de f. Vous ne savez pas ce que vous voulez dire en supprimant le _cas - soit en le laissant _->acomplètement ou en le déplaçant vers le haut génère une exception de modèle non exhaustive, et le déplacer vers le haut ne sauvegarde de toute façon aucun caractère. Cependant, j'ai réussi à enregistrer 5 caractères.
John Dvorak
Excellente solution. J'ai vérifié tous les cas de test.
Jakube
Encore une fois, félicitations pour votre solution. Puisque vous avez présenté le code le plus court, vous recevez la prime d'une valeur de 100 points de réputation.
Jakube
4

Cubiquement , 6 4 octets

¶=8%

Je gagne: P

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

Le bloc-notes est initialisé à zéro. La 8ème "face" contient 1 si le cube n'est pas résolu et 0 sinon.

Essayez-le en ligne!

MD XF
la source
3
On dirait une langue intéressante. Mais parce que la langue a été créée après la publication du défi, elle n'est pas éligible pour gagner.
Jakube
2
@Jakube Je suis d'accord qu'il ne devrait pas être accepté, juste parce que c'est un langage avec les buildins de Rubik's Cube publiés si tard après le défi et décimant ainsi complètement les autres réponses. Mais il est techniquement éligible pour gagner selon la méta (la règle de non-compétition a été quelque peu abrogée).
MD XF
3

J - 232, 220, 381, 315 296 octets

Cette solution code toutes les opérations en permutations de faces et fonctionne en se basant sur le fait que toutes les torsions de faces sont en fait les mêmes, sous une rotation de tout le cube.

Edit : un peu plus de golf

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'

Outre les essais précédents, cela ne prend la rotation d'angle en compte.

fest juste une fonction d'aide. rfait la rotation d'une face. un visage est codé comme suit:

  1. tous les coins par pas de 6
  2. tous les bords par pas de six

cet ordre facilite l'encodage des rotations et des torsions. test un adverbe qui tord le visage sous une certaine rotation de cube, sélectionnant le visage.

Xet Ysont des adverbes qui prennent comme argument de gauche le nombre de dans cette direction du cube entier.

La ligne suivante définit toutes les rotations: 3 caractères par rotation: le nom, le nombre de rotations et la direction.

La dernière ligne définit le verbe de test T, convertissant 3 et 'en notation Power, inversant l'ordre des opérations en ajoutant le vecteur de test et en excutant finalement le tout.

Plus de détails sur demande.

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
la source
11
"car mes résultats de test ne correspondent pas à ceux donnés ..." comme dans, votre solution ne fonctionne pas? Je ne le posterais pas alors ...
John Dvorak
Tu as raison. Fixé maintenant.
jpjacobs
J'ai ajouté 4 cas de test supplémentaires. Deux d'entre eux renvoient toujours le faux résultat. On dirait que vous ignorez l'orientation des coins.
Jakube
@jpjacobs Il y a maintenant une prime de 100 représentants sur la question. Voulez-vous corriger votre code?
Jakube
Voila, c'est fait. Maintenant, il suffit de le réduire.
jpjacobs
2

Python 3: 280 caractères

Ce n'est pas un participant au défi. D'abord parce que j'ai moi-même posé le défi et ensuite parce que ce n'est pas mon code. Tous les crédits appartiennent à Stefan Pochmann , qui a découvert cette façon géniale de simuler un Rubik's Cube. Je n'ai fait que du golf et quelques changements mineurs par rapport au défi.

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

L'idée derrière cela est la suivante. sreprésente l'emplacement des pièces de UF, URet ainsi de suite. Par exemple: s = ['DF', 'BL', ...]signifie que la pièce UFest à la position DF, la pièce URest à la position BL, ...

Comment la position d'une pièce change-t-elle lors d'un mouvement. Si vous effectuez un Udéplacement, tous les autocollants (couleurs) du Ucalque, qui faisaient face à la face avant, se déplacent vers la gauche. Les autocollants de la face gauche se déplacent vers l'arrière, ceux-ci vers la droite et ceux-ci vers la face avant. Encodé par FLBR. Quelques exemples: UFse déplace vers UL, UFRse déplace vers ULFet ainsi de suite. Par conséquent, appliquer un mouvement, c'est simplement traduire les faces des pièces dans le calque correspondant.

Jakube
la source