43 quintillions de permutations

Nous pouvons représenter un Rubik's Cube comme un filet comme suit (une fois résolu):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Chaque lettre représente la couleur correspondante ( Wblanc, Gvert, etc.)

Il a été démontré qu'il existe exactement (~ quintillions) de permutations différentes dans lesquelles un Rubik's Cube peut se trouver. $43,252,003,274,489,856,000$ $43$

Votre tâche consiste à prendre un entier compris entre et et à générer la permutation correspondante, de la manière indiquée ci-dessus. Vous pouvez choisir la façon dont les permutations sont ordonnées, mais l'algorithme que vous utilisez doit être montré pour générer une permutation unique et correcte pour chaque entrée possible. $1$ $43,252,003,274,489,856,000$

Règles de permutation non valides

_{Tiré de cette page}

Pour commencer, le centre de chaque face 3x3 doit rester le même, car le carré central d'un Rubik's Cube ne peut pas être tourné. Le cube entier peut être tourné, changeant où une face semble se trouver, mais cela n'affecte pas le filet du cube.

Si nous disons que chaque permutation a une parité, basée sur la parité du nombre de swaps pour atteindre cette permutation, nous pouvons dire

Chaque pièce d'angle a trois orientations possibles. Il peut être orienté correctement (0), dans le sens horaire (1) ou antihoraire (2). La somme des orientations des coins reste toujours divisible par 3
Chaque rotation légale sur le Rubik's Cube retourne toujours un nombre pair d'arêtes afin qu'il ne puisse y avoir qu'une seule pièce mal orientée.
Compte tenu de la permutation de tous les coins et bords, la parité globale doit être paire, ce qui signifie que chaque mouvement légal effectue toujours l'équivalent d'un nombre pair de swaps (en ignorant l'orientation)

Par exemple, les trois réseaux suivants sont des sorties non valides:

   WWW
   WWW
   WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

(Too many whites/not enough reds)

   WRW
   WRW
   WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
   YYY
   GGY
   YYY

(There are two red/green center squares and no white/yellow center squares.
 In all valid permutations, the center squares are all different colours)

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBOYOO
   YYY
   YYY
   YYB

(The yellow/orange/blue corner is rotated into an impossible permutation)

Règles

Vous devez prouver, comme vous le souhaitez, que l'algorithme est valide. Vous n'avez pas à énumérer chaque permutation, tant que vous prouvez la validité de votre algorithme.
$1$ $43,252,003,274,489,856,000$
- $2^{53}-1$ $2^{53}-1$
- $27,946,105,037,114,827,095$
Vous devez inclure une sorte de preuve de validité dans votre réponse. Cette preuve peut prouver la validité dans n'importe quelle méthode de preuve acceptée, sauf pour énumérer toutes les possibilités.
Vous pouvez choisir d'utiliser une autre méthode de saisie si vous le souhaitez, tant que:
- L'entrée est bornée
- Chaque entrée correspond à une sortie unique
- Vous expliquez clairement le format d'entrée et comment il correspond à chaque sortie
Vous pouvez modifier les caractères utilisés pour utiliser 6 caractères ASCII différents, entre 33 ( !) et 126 ( ~), au lieu deWGRBOY
Vous pouvez sortir de la manière que vous souhaitez, tant qu'il forme une représentation claire d'un cube où les 6 faces peuvent être affichées, y compris n'importe quel filet de cube valide, une chaîne simple ou un rendu 3D. Si vous n'êtes pas sûr d'un format spécifique, n'hésitez pas à demander dans les commentaires.

Il s'agit d'un code-golf donc le code le plus court, en octets, dans chaque langue l'emporte.

Exemples de sorties valides

   YYY
   YYY
   YYY
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   WWW
   WWW
   WWW

(The `W` and `Y` faces have been swapped)

   ZZZ
   +++
   +}}
+[[}77ZZ7bbb
bb[}[[7}}+Z7
bb[}++[}}+Z7
   7bb
   [7Z
   [7Z

(To start with, the colours have been mapped W -> +, G -> b, R -> [, B -> }, O -> Z and Y -> 7.
 Then, the moves L, R, U and F' have been applied, in that order.
 Notice that each centre square is different, and corresponds to the same colour as in the mapping)

code-golf rubiks-cube caird coinheringaahing
la source

Dans le troisième exemple invalide, ce n'est pas seulement que le coin est dans une configuration invalide, le coin r / y / o est un coin impossible car r et o sont en face l'un de l'autre

fəˈnɛtɪk

Correction du troisième exemple non valide (CC @ fəˈnɛtɪk)

Jonathan Allan

Le même problème était également dans le deuxième exemple invalide mais je ne l'avais pas remarqué. Cela importe moins parce que les couleurs sont

gâchées de

(a_{1}, a_{2}, a_{3}, a_{4})

$(a_1,a_2,a_3,a_4)$

a_{1} \leq 8!

$a_1\leq 8!$

a_{2} \leq 3^{7}

$a_2\leq3^7$

a_{3} \leq 12! / 2

$a_3\leq 12!/2$

a_{4} \leq 2^{11}

$a_4\leq 2^{11}$

@Shaggy Oui, une chaîne d'une seule ligne est très bien

caird coinheringaahing

Réponses:

Fusain , 334 297 octets

Ｎθ≔×³﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘ε³¦³ε≧÷²¹⁸⁷θ≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘η²¦²η≧÷²⁰⁴⁸θＦ⪪”B"↷:μêKＯ″ＫW#})”³«Ｊ⌕α§ι⁰Ｉ§ι¹§ι²»≔⁰ω≔⪪”A‽}y≔Ｗ⊞≦≦⧴!O×➙⟧ï!Ｙ9⁺`↙1δQ1ξzＴ”⁶υ≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δＦ²«Ｆδ«≔§υ⎇⁼Ｌυ⊗ιωζδ≧÷Ｌυζ≧⁺⌕υδω≔Φυ¬⁼λδυＦＬκ«Ｊ⌕α§δ⊗⁺λεＩ§δ⊕⊗⁺λε§κλ»≧÷Ｌκε»≔⪪”A‽}R›Ｋ<≡^μ≡⟦σＤ⎚+πη±t¿e∧Ｌ⸿~↑�w”⁴υ≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ≔θζ≔ηε

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

Ｎθ

Saisissez l'entier dans la variable q.

≔×³﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘ε³¦³ε≧÷²¹⁸⁷θ

Divisez qpar 3⁷, en mettant le reste e. Puis, en considérant ecomme un nombre en base 3, suffixez un chiffre à epour que ses chiffres (en base 3) totalisent un multiple de 3. Cela permet ede définir les rotations des coins.

≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ

Divisez qpar 8 !, en mettant le reste z. (8! Est temporairement stocké dpour enregistrer un octet.) Cela permet zde définir les positions des coins.

≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘η²¦²η≧÷²⁰⁴⁸θ

Divisez qpar 2¹¹, en mettant le reste h. Puis, en considérant hcomme un nombre en base 2, suffixez un chiffre à hpour que ses chiffres (en base 2) totalisent un multiple de 2. Cela permet hde définir les retournements des bords.

Ｆ⪪”B"↷:μêKＯ″ＫW#})”³

Boucle sur une représentation sous forme de chaîne des centres.

«Ｊ⌕α§ι⁰Ｉ§ι¹§ι²»

Sautez à la position de chaque centre et imprimez-le.

≔⁰ω

Gardez une trace de la parité des positions de coin en variable w.

≔⪪”A‽}y≔Ｗ⊞≦≦⧴!O×➙⟧ï!Ｙ9⁺`↙1δQ1ξzＴ”⁶υ

Créez un tableau de positions d'angle.

≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δ

Créez un tableau de couleurs d'angle.

Ｆ²«

Boucle deux fois, une fois pour les coins, une fois pour les bords, ci-après dénommés "cubes".

Ｆδ«

Faites une boucle sur le tableau des couleurs du cube.

≔§υ⎇⁼Ｌυ⊗ιωζδ≧÷Ｌυζ≧⁺⌕υδω≔Φυ¬⁼λδυ

Extrayez la position de cube suivante de z, en mettant à jour la parité dans w. Utilisez cette parité pour le dernier mais un bord. Cela garantit que la somme de la parité des bords et des coins est uniforme.

ＦＬκ«Ｊ⌕α§δ⊗⁺λεＩ§δ⊕⊗⁺λε§κλ»

Imprimez le cube à cette position, ajusté pour la rotation suivante ou retournez selon le cas.

≧÷Ｌκε»

Retirez la rotation ou le retournement de e.

≔⪪”A‽}R›Ｋ<≡^μ≡⟦σＤ⎚+πη±t¿e∧Ｌ⸿~↑�w”⁴υ

Créez un tableau de positions de bord. Ce sera utilisé la deuxième fois dans la boucle.

≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ

Créez un tableau de couleurs de bord.

≔θζ≔ηε

Remplacez les variables de coin zet eles variables de bord correspondantes qet de hsorte que les bords soient permutés et inversés lors du deuxième passage de la boucle.

Neil
la source

Conseillez-moi: si quelque chose joué au charbon de bois fait 330 octets, ne l'essayez pas en PHP!

Night2

@ Night2 Malheureusement 334 maintenant, en raison d'un correctif (calcul de parité incorrect).

Neil

Ruby , 570 408 octets

->g,h{z=[]
c=a="\x19)!$'%\x177\x1F495.)@7g~yp"
20.times{|i|z<<a[k=g%r=12+i/12*8-i];a[k]="";g/=r}
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18,2])
h+=h+("%b"%(h%2048)).sum%2
j=0
b="023451"
20.times{|i|b<<("%0*o"%[r=2+i/12,z[i].ord-20]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s["<QTWZo;MP[ngD@RS^k=GVUpaJ8XYdsAFE?CN7LK9IHl_`jh]reftbc"[i].ord-55]=b[i]}
s}

Essayez-le en ligne!

Version originale, avec des tableaux de nombres magiques au lieu de chaînes magiques

->g,h{z=[]
a=[05,025,015,020,023,021,03,043,013,040,045,041,   032,025,054,043,0123,0152,0145,0134]
#PERMUTE
20.times{|i|r=12+i/12*8-i;z<<a.delete_at(g%r);g/=r}
c=1
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18],z[19])
#ROTATE
h+=h+(h%2048).to_s(2).sum%2
j=0
b="023451"
20.times{|i|r=2+i/12;b<<("%0*o"%[r,z[i]]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
#DISPLAY
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s[
[5,26,29,32,35,56,
4,22,25,36,55,48, 
13,9,27,28,39,52,
6,16,31,30,57,42,
19,1,33,34,45,60,
10,15,14,8,12,23,0,21,20,2,18,17,
53,40,41,51,49,38,59,46,47,61,43,44][i]]=b[i]}
s}

Essayez-le en ligne!

Une fonction anonyme qui, dans sa forme actuelle, prend une entrée de deux nombres entiers, ce qui semble être autorisé: "vous pouvez choisir une autre méthode de saisie". La première est la permutation dans la plage de 0 à 12!*8!/2 - 1et la seconde est l'orientation des pièces dans la plage de 0 à 2**11 * 3*7 - 1. La sortie à l'état résolu est la chaîne suivante:

000
000
000
222333444555
222333444555
222333444555
111
111
111

Golf supplémentaire

Il y a environ 10 caractères supplémentaires à enregistrer en ajustant le format de sortie à la forme suivante. Mais cela réduirait la lisibilité, donc je ne le ferai pas pour le moment

      #########
      #########
      #########
#########
#########
#########

Explication

Permutation

En interne, l'état résolu est représenté par la série de nombres octaux dans le tableau a. L'entrée gest divisée par les nombres, 12..1le module étant utilisé pour sélectionner et retirer un bord aet le placer z. Une fois cela fait, seuls les coins restent a, donc gest divisé par les nombres 8..1avec le module utilisé pour retirer un coin aet le placer dedans z.

Comme il n'y a pas d'informations suffisantes pour déterminer l'ordre des deux derniers virages, la valeur de gaura été divisée à zéro au moment où elle les atteindra, ils seront donc toujours ajoutés zdans leur ordre d'origine. Une vérification est ensuite effectuée pour déterminer si la permutation globale est paire ou impaire, et si nécessaire, les deux derniers coins sont inversés pour rendre la permutation uniforme.

Orientation

Il existe différentes manières de décider si un coin ou une arête est dans la bonne orientation s'il n'est pas à son emplacement résolu. Aux fins de cette réponse, un coin est considéré dans son orientation correcte s'il apparaît 0ou 1sur la face supérieure ou inférieure. Par conséquent, la rotation de la face supérieure ou inférieure ne modifie pas l'orientation des coins. La rotation des autres faces modifie l'orientation, mais de telle manière que la somme de parité globale reste inchangée. Les bords sont considérés dans le bon sens s'ils montrent un 2ou 4vers l'avant / arrière ou un 3ou 5vers la gauche / droite. Cela signifie que la rotation du haut ou du bas d'un quart de tour inverse les quatre bords mais la rotation des autres faces laisse le statut de retournement inchangé.

L'entrée contient des informations explicites pour tous sauf le premier bord et le dernier coin. Les 11 bits les moins significatifs h%2048sont additionnés et le module utilisé pour déterminer l'orientation du premier bord. hest multiplié par 2 en l'ajoutant à lui-même et la valeur de l'orientation du premier bord est ajoutée en tant que bit le moins significatif. L'orientation du dernier coin est trouvée en soustrayant progressivement l'orientation des autres coins de j. Pour le tout dernier coin (où i/19= 1) la valeur de j%3est ajoutée à h(qui aura été réduite à zéro) et cela détermine l'orientation du dernier coin.

La chaîne best préinitialisée avec le texte pour les centres des visages. hest divisé par 2douze fois puis par 3huit fois, les modules étant utilisés pour déterminer l'orientation des pièces. Dans chaque cas, le nombre en zest converti en une chaîne avec le nombre approprié de chiffres (2 ou 3) et la chaîne est ensuite dupliquée. Cela permet à la rotation correcte des chiffres trouvée par le modulo d'être extraite de la chaîne par indexation et ajoutée àb

Afficher

Enfin, les autocollants bruts sont copiés bdans un format plus lisible par l'homme en sutilisant les nombres magiques dans la table d'index.

Level River St
la source