Introducción:
Un cubo de Rubik 3x3x3 tiene permutaciones posibles, que es aproximadamente 43 quintillones . Es posible que haya escuchado sobre este número antes, pero ¿cómo se calcula realmente?
Un cubo de Rubik 3x3x3 tiene seis lados, cada uno con nueve pegatinas. Sin embargo, al mirar las piezas (externas) en lugar de las pegatinas, tenemos seis piezas centrales; piezas de ocho esquinas; y doce piezas de borde. Como los centros no se pueden mover, podemos ignorarlos en los cálculos. En cuanto a las esquinas y bordes:
- Hay( ) formas de organizar las ocho esquinas. Cada esquina tiene tres orientaciones posibles, aunque solo siete (de las ocho) pueden orientarse independientemente; la orientación de la esquina octava / final depende de las siete anteriores, dadas ( ) posibilidades.
- Hay ( ) formas de organizar los doce bordes. La mitad de lases porque los bordes siempre deben estar en una permutación pareja exactamente cuando las esquinas están Once aristas se pueden voltear de forma independiente, con la inversión de la doceava / última arista dependiendo de las once anteriores, dadas ( ) posibilidades.
Al poner esto juntos, tenemos la siguiente fórmula:
Fuente: Wikipedia - Permutaciones del cubo de Rubik
Aunque esto puede parecer bastante complejo, sigue siendo bastante sencillo para un Cubo de 3x3x3. Para cubos pares, la fórmula es ligeramente diferente; Esta es la fórmula para un cubo 4x4x4, por ejemplo:
Que es aproximadamente 7.40 quattuordecillion en la escala corta .
Y para cubos NxNxN más grandes (es decir, el récord mundial actual 33x33x33), la fórmula se ampliará bastante. Sin embargo, para no hacer esta introducción demasiado larga, pongo estos enlaces aquí, donde las permutaciones del Cubo 4x4x4 y algunos Cubos NxNxN de otro tamaño se explican con una fórmula resultante:
Quizás ya se esté preguntando: ¿existe una fórmula general basada en para cualquier cubo x x ? Ciertamente lo hay. Aquí hay tres algoritmos completamente diferentes, todos dando exactamente los mismos resultados basados en N :
1: Fórmula de Chris Hardwick:
2: Fórmula trigonométrica de Christopher Mowla:
3: Fórmula de los primos de Christopher Mowla:
donde es .
Fuente: Cubers-reddit - Fórmulas de conteo matemático de número de posiciones, número de Dios, etc.
Reto:
Elija e implemente una de estas tres fórmulas (o su propia derivada), que dado un entero de entrada en el rango , genera el resultado correcto.
Reglas de desafío:
- Puede usar otra fórmula además de estas tres, pero tenga en cuenta que se ha demostrado que estas tres son correctas. Si usa otra fórmula, agregue un enlace de donde la obtuvo (o si se le ocurre, agregue una explicación detallada). Y comprobaré todos los enteros en el rango si la salida es correcta. Quizás se pueda encontrar inspiración en los oeis para esta secuencia: A075152 .
- Si su idioma genera automáticamente un resultado científico (es decir, lugar del número después de la fórmula 4x4x4), esto está permitido. Pero agregue un código adicional a su respuesta para convertir este redondeo científico en un resultado exacto para que se puedan verificar los resultados, ya que los errores de redondeo debido a la precisión de coma flotante durante la ejecución de la fórmula en su código no están permitidos; exacto.
- Su programa / función debe ser correcto para al menos las entradas en el rango (aunque, dado que ya da como resultado un número enorme, cualquier mayor probablemente funcionará también si puede generar esto uno correctamente).
- No está permitido recorrer todas las permutaciones posibles con un contador, ya que eso nunca generaría nada en un período de tiempo razonable. Solo la implementación de una fórmula (ya sea una de las tres proporcionadas, una derivada de una de ellas o una fórmula completamente nueva) u otro método que brinde los resultados correctos en un período de tiempo razonable (sin codificación, por supuesto) ) esta permitido. Pensé en agregar un tiempo restringido para hacer cumplir esto, pero personalmente estoy en contra del tiempo restringido en combinación con el código de golf , por lo que no lo haré. Aún así, asegúrese de que su programa dé las respuestas, y si por algún motivo es demasiado lento para TIO, agregue algunas capturas de pantalla con la salida de su máquina local como verificación.
Reglas generales:
- Este es el código de golf , por lo que la respuesta más corta en bytes gana.
No permita que los lenguajes de código de golf lo desalienten de publicar respuestas con idiomas que no sean de codegolf. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación. - Las reglas estándar se aplican a su respuesta con las reglas de E / S predeterminadas , por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
- Las lagunas predeterminadas están prohibidas.
- Si es posible, agregue un enlace con una prueba para su código (es decir, TIO ).
- Además, se recomienda agregar una explicación para su respuesta.
Casos de prueba:
Aquí los casos de prueba para en el rango (siéntase libre de usar los enlaces WolframAlpha anteriores para casos de prueba más grandes):
n=2
3674160
n=3
43252003274489856000
n=4
7401196841564901869874093974498574336000000000
n=5
282870942277741856536180333107150328293127731985672134721536000000000000000
n=6
157152858401024063281013959519483771508510790313968742344694684829502629887168573442107637760000000000000000000000000
n=7
19500551183731307835329126754019748794904992692043434567152132912323232706135469180065278712755853360682328551719137311299993600000000000000000000000000000000000
n=8
35173780923109452777509592367006557398539936328978098352427605879843998663990903628634874024098344287402504043608416113016679717941937308041012307368528117622006727311360000000000000000000000000000000000000000000000000
n=9
14170392390542612915246393916889970752732946384514830589276833655387444667609821068034079045039617216635075219765012566330942990302517903971787699783519265329288048603083134861573075573092224082416866010882486829056000000000000000000000000000000000000000000000000000000000000000
n=10
82983598512782362708769381780036344745129162094677382883567691311764021348095163778336143207042993152056079271030423741110902768732457008486832096777758106509177169197894747758859723340177608764906985646389382047319811227549112086753524742719830990076805422479380054016000000000000000000000000000000000000000000000000000000000000000000000000000000000
NOTA: Dado que este es un desafío de código de golf , básicamente se reduce a: implementar una de estas tres fórmulas (o una derivada / su propio método que aún produce los resultados correctos) lo más breve posible.
fuente
floor
Respuestas:
Wolfram Language (Mathematica) , 59 bytes
Pruébalo en línea!
utiliza el algoritmo de Herbert Kociemba que se encuentra en la página OEIS
Aquí está la fórmula recursiva:
a(1)=1; a(2)=7!*3^6; a(3)=8!*3^7*12!*2^10; a(n)=a(n-2)*24^6*(24!/24^6)^(n-2)
6 bytes guardados por @Peter Taylor
un byte más guardado por @Expired Data
fuente
f@1
, por lo que puede guardar 6 bytes. Obviamente, también querrás ajustar el marco de prueba para usarRange[2,10]
.código de máquina x86, 119 bytes
Hexdump:
La función recibe el número
n
enecx
, y un puntero a una cadena de rellenaredx
(es decirfastcall
convención).Antes de mostrar el código fuente, algunas explicaciones sobre cómo funciona. Utiliza la fórmula recursiva, que escribí de la siguiente manera:
Entonces, todo lo que debe hacer el código es la multiplicación por números pequeños. Los números están en el rango 6 ... 36, que es lo suficientemente pequeño como para representarse en un mapa de bits de 32 bits. En realidad, no almaceno el bit que representa la multiplicación por 6; esto me permite organizar el código en un
do-while
bucle, comenzando con la multiplicación incondicional por 6.Los números grandes se representan usando la forma decimal: cada byte es un valor en el rango 0 ... 9, comenzando desde el MSB.
La multiplicación se realiza de LSB a MSB; se supone que el número de dígitos crecerá en 2 por cada multiplicación. Después de multiplicar por un factor pequeño como 6, el número de dígitos puede crecer solo 1. Por lo tanto, si MSB = 0, mueve todo el resultado intermedio a la izquierda. En realidad, puede suceder que el número de dígitos no crezca en absoluto, y luego MSB seguirá siendo 0, pero este problema se solucionará a medida que el código proceda a factores mayores.
Debido a que el código de multiplicación es grande, no quiero ponerlo dos veces. Tampoco quiero moverlo a una función, porque el código de máquina para llamar a una función es grande. Así que reorganicé los bucles externos de tal manera que el código de multiplicación se necesita solo una vez.
Código C:
Desmontaje
El tiempo de ejecución para n = 100 es de aproximadamente 4 segundos, y el resultado es un número con 38416 dígitos:
23491019577617 (muchos dígitos aquí) ... (muchos ceros aquí) 0000000000000000
fuente
05AB1E , 38 bytes
Intento inicial
Utiliza la fórmula de Chris Hardwick .
Intentaré jugar más al golf y explicar cuando tenga tiempo.
Pruébalo en línea!
fuente
Julia 1.0 ,
8376 bytesPruébalo en línea!
Utiliza la fórmula de Chris Hardwick. Toma la entrada como entero grande.
Gracias a H.PWiz por -7 bytes
fuente
~=n->factorial(big(n))
->~n=prod(big,1:n)
y(24576*~12)^(n%2)
->^(24576*~12,n%2)
~=n->
lugar de~n=
?Python 2 , 72 bytes
Pruébalo en línea!
Guardado 4 bytes copiando
n*(n-2)/4
desde Neil .fuente
Wolfram Language (Mathematica) , 67 bytes
Usando la fórmula de Chris Hardwick.
Pruébalo en línea!
fuente
JavaScript (Node.js) , 81 bytes
La fórmula recursiva de Herbert Kociemba. Toma un BigInt como entrada.
Pruébalo en línea!
JavaScript (Node.js) ,
102 9896 bytesLa fórmula de Chris Hardwick. Toma un BigInt como entrada.
Pruébalo en línea!
fuente
JavaScript (Node.js) ,
777573 bytesPruébalo en línea! Basado en la fórmula de Christopher Mowla. Toma un BigInt como entrada. Pruebe el arnés descaradamente robado de @Arnauld.
0xb88d4641131f0n
está3246670537110000n
en decimal. Explicación: Comencé con el último exponente primo y lo simplifiqué an*(n-2n)/4n
(esta es una división entera, por lo que no necesito el ajuste para números impares). Luego examiné los otros números primos para ver si sus exponentes estaban relacionados con este valor (al que me referiré comoo
), y descubrí que eran de una moda, si permitía el uso de la paridad den
(a la que me referiré comop
) Las fórmulas para los exponentes son las siguientes:Las potencias se pueden agrupar por exponente, por ejemplo,
p
es el exponente de11*7*5**2*3**3*2**14
.fuente
Raqueta ,
151141 bytes-7 bytes gracias a fede s.!
Pruébalo en línea!
La respuesta más larga usando la fórmula de Chris Hardwick :)
fuente
expt
llamadas:(λ(n[e expt])...(e ...)...)
.Python 2 , 122 bytes
Pruébalo en línea!
Utiliza el método recursivo Herbert Kociemba.
-2 bytes gracias a Herman L
fuente
3**6
con 729 y2**10
con1024
TIOJalea ,
3938 bytesSiento que me he perdido algunos campos de golf, pero ...
Un enlace monádico que implementa la fórmula de Chris Hardwick.
Pruébalo en línea! O vea el conjunto de pruebas (
n=[1..33]
).fuente
CJam (47 bytes)
Demostración en línea
Esto implementa la recurrencia de Herbert Kociemba de OEIS:a ( n ) = ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪17 ! × 36 6a ( n - 1 ) × 3 × 12 ! × 213a ( n - 2 ) × ( 24 !246 6)n - 2× 246 6 si n∈{0,1} si n=2 si n=3 si n>3
utilizando el operador de recursión memorable de CJam
j
. He ordenado los términos en el bloque MathJax en el mismo orden que en el código para facilitar la verificación de la correspondencia para aquellos que leen CJam: cualquier disección adicional no arrojará más luz.fuente
Jalea , 43 bytes
Pruébalo en línea!
fuente
Icono ,
125110 bytesPruébalo en línea!
fuente
C (gcc) -lgmp, 279 bytes
Pruébalo en línea!
fuente
N--*--N/4
lugar de(N*N-2*N)/4
y eliminarN-=2
y#define s mpz_init_set_str
Perl 6 , 85 bytes
Pruébalo en línea!
fuente
Haskell ,
868574 bytes-1 byte guardado gracias a H.PWiz
-11 bytes guardados gracias a Max Yekhlakov
Pruébalo en línea!
fuente
24576
es más corto que2^13*3
Python 2 , 92 bytes
Pruébalo en línea!
fuente
De cáscara ,
514844 bytes-4 bytes gracias a H.PWiz
Pruébalo en línea!
Esto es Fórmula de Chris Hardwick. Además, este es mi primer programa de cáscara, por lo que cualquier consejo sería muy apreciado.
fuente
÷^*6÷4□-2⁰Π4*^÷4-D⁰□⁰Π24*729*Π7^%2⁰*24*1024Π12
÷^*6÷4□-2⁰Π4*^÷4-D⁰□⁰Π24*729*Π7^%2⁰*24576Π12
C ++,
187 185 180 176 195 (hubo un error) 193175 bytes (con ayuda del techo cat)Utiliza el contenedor GMP C ++ (biblioteca de precisión múltiple GNU) y la fórmula utilizada por @ J42161217 ( https://codegolf.stackexchange.com/a/183381/55953 ).
Úselo
g++ -g rubix.cpp -lgmp -lgmpxx
para compilar y vincularsin golf, con código de prueba
https://tio.run/##PZAxb4MwEIV3foWVDrETqBpARMImWZqha7t0iFQZ4xC3xrg2tJERf73UIVXfcE937zvpdEzrqGZsmu6EYrKvOKkbfbncn3dBb4WqgSsa7d6YpNZiBzR0gIYOlGhwgBUb/H0WksMyihBbFRQb3vVGAYZHB4xnFRr@Rqoo4n2SbdNN9pD7Jtk7uNCvafVEn7fvjx@LMItRbqCKYrTSME7D7OoeOpivl4Mp@eeMhFcAj//3AiJa2xlOm13QUKEgCoYAeJ1aA4XqgChiDARJUl/XazRnXrar8py1fUeIIGR57JaE@AUECLllXFUSB2Mw/bCTpLWdIjm/5ua/
fuente
n=10
caso de prueba para que pueda verificar que funciona? ¿Supongo que no hay forma de hacer que esto funcione en C ++ (clang) o C ++ (gcc) TIO debido a la biblioteca utilizada?TI-BASIC,
6362 bytes , (sin competencia)Expresión que toma la entrada como un entero en
Ans
. Implementación de la fórmula de Chris Hardwick. Sin competencia porque el hardware en el que se ejecuta solo almacenará hasta 16 decimales, por lo que la respuesta nunca será 100% precisa.Explicación:
fuente