43 quintillones de permutaciones

16

Podemos representar un cubo de Rubik como una red de la siguiente manera (cuando se resuelve):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Cada letra representa el color correspondiente ( Wes blanco, Gverde , etc.)

Se ha demostrado que hay exactamente 43,252,003,274,489,856,000 (~ 43 quintillones) diferentes permutaciones en las que puede estar un cubo de Rubik.

Su tarea es tomar un número entero entre 1 y y generar la permutación correspondiente, de la manera que se muestra arriba. Puede elegir cómo se ordenan las permutaciones, pero se debe mostrar el algoritmo que utiliza para generar una permutación única y correcta para cada entrada posible.43,252,003,274,489,856,000

Reglas de permutación no válidas

Tomado de esta página

Para empezar, el centro de cada cara de 3x3 debe permanecer igual, ya que el cuadrado central en un Cubo de Rubik no se puede girar. Se puede rotar todo el cubo, cambiando donde parece estar una cara, pero esto no afecta la red del cubo.

Si decimos que cada permutación tiene una paridad, basada en la paridad del número de permutas para alcanzar esa permutación, podemos decir

  • Cada pieza de esquina tiene tres orientaciones posibles. Se puede orientar correctamente (0), en sentido horario (1) o en sentido antihorario (2). La suma de las orientaciones de las esquinas siempre es divisible por 3.

  • Cada rotación legal en el Cubo de Rubik siempre voltea un número par de aristas, por lo que no puede haber una sola pieza orientada incorrectamente.

  • Teniendo en cuenta la permutación de todas las esquinas y bordes, la paridad general debe ser uniforme, lo que significa que cada movimiento legal siempre realiza el equivalente de un número par de intercambios (ignorando la orientación)

Por ejemplo, las siguientes tres redes son salidas no válidas:

   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)

Reglas

  • Debes demostrar, como quieras, que el algoritmo es válido. No tiene que enumerar cada permutación, siempre que demuestre la validez de su algoritmo.
  • 143,252,003,274,489,856,000
    • 253-1253-1
    • 27,946,105,037,114,827,095
  • Usted debe incluir algún tipo de prueba de la validez de su respuesta. Esta prueba puede probar la validez en cualquier método de prueba aceptado, excepto para enumerar todas las posibilidades.
  • Puede optar por utilizar un método de entrada alternativo si lo desea, siempre que:
    • La entrada está limitada
    • Cada entrada corresponde a una salida única
    • Explica claramente el formato de entrada y cómo corresponde a cada salida
  • Puede cambiar los caracteres utilizados para usar 6 caracteres ASCII diferentes, entre 33 ( !) y 126 ( ~), en lugar deWGRBOY
  • Puede imprimir de la forma que desee, siempre que forme una representación clara de un cubo en el que se puedan mostrar las 6 caras, incluida una red de cubos válida, una sola cadena forrada o una representación 3D. Si no está seguro acerca de un formato específico, no dude en preguntar en los comentarios.

Este es un por lo que gana el código más corto, en bytes, en cada idioma.

Ejemplo de salidas válidas

   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)
caird coinheringaahing
fuente
En el tercer ejemplo inválido, no es solo que la esquina está en una configuración inválida, la esquina r / y / o es una esquina imposible debido a que r y o están opuestos entre sí
fəˈnɛtɪk
Se corrigió el tercer ejemplo no válido (CC @ fəˈnɛtɪk)
Jonathan Allan, el
El mismo problema también estaba en el segundo ejemplo no válido, pero no lo había notado. Importa menos allí porque los colores están desordenados de todos modos
fəˈnɛtɪk
(un1,un2,un3,un4 4)un18!un237 7un312!/ /2un4 4211
1
@ Shaggy Sí, una cadena de una sola línea está bien
caird coinheringaahing

Respuestas:

13

Carbón , 334 297 bytes

Nθ≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θF⪪”B"↷:μêKO″KW#})”³«J⌕α§ι⁰I§ι¹§ι²»≔⁰ω≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δF²«Fδ«≔§υ⎇⁼Lυ⊗ιωζδ≧÷Lυζ≧⁺⌕υδω≔Φυ¬⁼λδυFLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»≧÷Lκε»≔⪪”A‽}R›K<≡^μ≡⟦σD⎚+πη±t¿e∧L⸿~↑�w”⁴υ≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ≔θζ≔ηε

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Nθ

Ingrese el entero en la variable q.

≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ

Divide qpor 3⁷, poniendo el resto adentro e. Luego, considerándolo ecomo un número en la base 3, sufije un dígito para eque sus dígitos (en la base 3) sumen un múltiplo de 3. Esto permite edefinir las rotaciones de las esquinas.

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

Divide qpor 8 !, poniendo el resto adentro z. (8! Se almacena temporalmente dpara guardar un byte). Esto permite zdefinir las posiciones de las esquinas.

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

Divide qpor 2¹¹, poniendo el resto adentro h. Luego, considerando hcomo un número en la base 2, sufije un dígito para hque sus dígitos (en la base 2) sumen un múltiplo de 2. Esto permite hdefinir los volteos de los bordes.

F⪪”B"↷:μêKO″KW#})”³

Pase sobre una representación de cadena de los centros.

«J⌕α§ι⁰I§ι¹§ι²»

Salte a la posición de cada centro e imprímalo.

≔⁰ω

Mantenga un registro de la paridad de las posiciones de las esquinas en variable w.

≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ

Crea una variedad de posiciones de esquina.

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

Crea una variedad de colores de esquina.

F²«

Haga un bucle dos veces, una vez para las esquinas, una vez para los bordes, en lo sucesivo denominados "cubos".

Fδ«

Pase sobre la matriz de colores del cubo.

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

Extraiga la siguiente posición del cubo z, actualizando la paridad en w. Use esta paridad para el último pero un borde. Esto asegura que la suma de paridad de los bordes y esquinas sea uniforme.

FLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»

Imprima el cubo en esa posición, ajustado para la siguiente rotación o voltee según corresponda.

≧÷Lκε»

Retire la rotación o voltee de e.

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

Crea una variedad de posiciones de borde. Esto se usará la segunda vez a través del ciclo.

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

Crea una variedad de colores de borde.

≔θζ≔ηε

Sobrescribir las variables de esquina zy econ las variables de borde correspondiente qy hpara que los bordes se permutan y se volcó durante la segunda pasada del bucle.

Neil
fuente
Aconsejarme a mí mismo: si algo golf en Charcoal tiene 330 bytes, ¡no lo intente en PHP!
Noche2
@ Night2 Tristemente 334 ahora, debido a una corrección de errores (cálculo de paridad incorrecto).
Neil
8

Rubí , 570 408 bytes

->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}

Pruébalo en línea!

Versión original, con matrices de números mágicos en lugar de cuerdas mágicas

->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}

Pruébalo en línea!

Una función anónima que en su forma actual toma una entrada de dos enteros, que parece estar permitida: "puede elegir un método de entrada alternativo". La primera es la permutación en el rango de 0 a 12!*8!/2 - 1y la segunda es la orientación de las piezas en el rango de 0 a 2**11 * 3*7 - 1. La salida en el estado resuelto es la siguiente cadena:

000
000
000
222333444555
222333444555
222333444555
111
111
111

Golf adicional

Hay aproximadamente 10 caracteres más para guardar ajustando el formato de salida a la siguiente forma. Pero esto reduciría la legibilidad, por lo que no lo haré en este momento

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

Explicación

Permutación

Internamente, el estado resuelto está representado por la serie de números octales en la matriz a. La entrada gse divide por los números 12..1con el módulo que se utiliza para seleccionar y eliminar un borde ay colocarlo z. Una vez hecho esto, solo quedan las esquinas a, por lo que gse divide por los números 8..1con el módulo que se utiliza para quitar una esquina ay colocarla z.

Como no hay información suficiente para determinar el orden de las dos últimas esquinas, el valor de gse habrá dividido a cero en el momento en que las alcance, por lo que siempre se agregarán zen el orden original. Luego se realiza una verificación para determinar si la permutación general es par o impar, y si es necesario, se intercambian las dos últimas esquinas para hacer que la permutación sea pareja.

Orientación

Hay varias formas diferentes de decidir si una esquina o borde está en la orientación correcta si no está en su ubicación resuelta. Para el propósito de esta respuesta, una esquina se considera en su orientación correcta si se muestra 0o 1en la cara superior o inferior. Por lo tanto, girar la cara superior o inferior no cambia la orientación de la esquina. Girar las otras caras cambia la orientación, pero de tal manera que la suma de paridad general permanece sin cambios. Los bordes se consideran en la orientación correcta si muestran a 2o 4al frente / atrás o a 3o 5hacia la izquierda / derecha. Esto significa que la rotación de la parte superior o inferior en un cuarto de vuelta voltea los cuatro bordes, pero la rotación de las otras caras deja el estado de cambio sin cambios.

La entrada contiene información explícita para todos menos el primer borde y la última esquina. Se h%2048suman los 11 bits menos significativos y se usa el módulo para determinar la orientación del primer borde. hse multiplica por 2 agregándolo a sí mismo y el valor para la orientación del primer borde se agrega como el bit menos significativo. La orientación de la última esquina se encuentra restando progresivamente la orientación de las otras esquinas j. Para la última esquina (donde i/19= 1) j%3se agrega el valor de h(que se habrá reducido a cero) y esto determina la orientación de la última esquina.

La cadena bviene preinicializada con el texto para los centros de las caras. hse divide por 2doce veces y luego por 3ocho veces, y los módulos se utilizan para determinar la orientación de las piezas. En cada caso, el número zse convierte en una cadena con el número apropiado de dígitos (2 o 3) y la cadena se duplica. Esto permite que la rotación correcta de los dígitos que encuentra el módulo se extraiga de la cadena mediante indexación y se agregue ab

Monitor

Finalmente, las etiquetas en bruto se copian ben un formato más legible para los humanos al susar los números mágicos en la tabla de índice.

Level River St
fuente