Einführung:
Ein 3x3x3 Rubik's Cube hat mögliche Permutationen, was ungefähr 43 Trillionen entspricht . Sie haben vielleicht schon einmal von dieser Zahl gehört, aber wie wird sie tatsächlich berechnet?
Ein 3x3x3 Rubik's Cube hat sechs Seiten mit jeweils neun Aufklebern. Betrachtet man jedoch die (äußeren) Teile anstelle von Aufklebern, so hat man sechs Mittelteile; acht Eckstücke; und zwölf Randstücke. Da die Zentren nicht verschoben werden können, können wir diese in den Berechnungen ignorieren. Wie für die Ecken und Kanten:
- Es gibt( ) Möglichkeiten zum Anordnen der acht Ecken. Jede Ecke hat drei mögliche Ausrichtungen, obwohl nur sieben (von den acht) unabhängig voneinander ausgerichtet werden können. Die Ausrichtung der achten / letzten Ecke hängt von den vorhergehenden sieben ab, wenn ( ) Möglichkeiten gegeben sind.
- Es gibt ( ) Möglichkeiten, die zwölf Kanten anzuordnen. Die Hälfte vonDas liegt daran, dass Kanten immer in einer gleichmäßigen Permutation sein müssen, genau dann, wenn die Ecken sind. Elf Kanten können unabhängig voneinander gespiegelt werden, wobei das Spiegeln der zwölften / letzten Kante von den vorhergehenden elf abhängt, wenn ( ) Möglichkeiten gegeben sind.
Zusammen haben wir die folgende Formel:
Quelle: Wikipedia - Rubiks Würfel-Permutationen
Obwohl dies bereits recht komplex aussieht, ist es für einen 3x3x3-Würfel immer noch recht unkompliziert. Für gerade Würfel ist die Formel etwas anders; Dies ist die Formel für einen 4x4x4-Würfel, zum Beispiel:
Welches ist etwa 7,40 Quattuordecillion auf der kurzen Skala .
Und für größere NxNxN-Würfel (dh den aktuellen Weltrekord 33x33x33) wird die Formel erheblich erweitert. Um diese Einführung nicht zu lang zu machen, habe ich stattdessen diese Links hier eingefügt, wo die Permutationen des 4x4x4-Würfels und einiger NxNxN-Würfel anderer Größe mit der folgenden Formel erklärt werden:
Sie wundern sich jetzt vielleicht: Gibt es eine allgemeine Formel, die auf für einen beliebigen x x Würfel basiert ? Das gibt es sicherlich. Hier sind drei völlig unterschiedliche Algorithmen, die alle auf der Basis von exakt dieselben Ergebnisse liefern :
1: Chris Hardwicks Formel:
Probieren Sie es auf WolframAlpha.
2: Christopher Mowlas Trigger Formel:
Probieren Sie es auf WolframAlpha.
3: Christopher Mowlas Primzahlen Formel:
wo ist .
Probieren Sie es auf WolframAlpha.
Herausforderung:
Wählen und implementieren Sie eine dieser drei Formeln (oder Ihre eigene Ableitung), die bei einer Eingabe-Ganzzahl im Bereich das richtige Ergebnis liefert.
Herausforderungsregeln:
- Es steht Ihnen frei, eine andere Formel als diese drei zu verwenden. Beachten Sie jedoch, dass diese drei nachweislich korrekt sind. Wenn Sie eine andere Formel verwenden, fügen Sie bitte einen Link hinzu, über den Sie die Formel erhalten haben (oder wenn Sie selbst darauf gekommen sind, fügen Sie eine ausführliche Erläuterung hinzu). Und ich werde nach allen ganzen Zahlen im Bereich suchen, ob die Ausgabe korrekt ist. Vielleicht könnte Inspiration in der Oeis für diese Sequenz gefunden werden: A075152 .
- Wenn Ihre Sprache automatisch eine wissenschaftliche Ausgabe ausgibt (dh anstelle der Zahl nach der 4x4x4-Formel), ist dies zulässig. Fügen Sie Ihrer Antwort jedoch zusätzlichen Code hinzu, um diese wissenschaftliche Rundung in eine exakte Ausgabe umzuwandeln, damit die Ergebnisse überprüft werden können, da Rundungsfehler aufgrund der Gleitkommapräzision während der Ausführung der Formel in Ihrem Code nicht zulässig sind - das tatsächliche Ergebnis sollte es sein genau.
- Ihr Programm / Ihre Funktion sollte für mindestens die Eingaben im Bereich korrekt sein (obwohl, da bereits eine Riesen-Arsch-Zahl ergibt, wird jedes größere wahrscheinlich auch funktionieren, wenn Sie dies ausgeben können eine richtig).
- Sie dürfen nicht alle möglichen Permutationen mit einem Zähler durchlaufen, da dies in einem angemessenen Zeitraum zu keiner Ausgabe führen würde. Nur die Implementierung einer Formel (entweder eine der drei bereitgestellten, eine Ableitung einer dieser Formeln oder eine völlig neue Formel) oder eine andere Methode, die in angemessener Zeit die richtigen Ergebnisse liefert (natürlich ohne harte Kodierung) ) ist erlaubt. Ich habe darüber nachgedacht, eine eingeschränkte Zeit hinzuzufügen , um dies durchzusetzen, aber ich persönlich bin gegen eine zeitliche Beschränkung in Kombination mit Code-Golf , also werde ich das nicht tun. Vergewissern Sie sich dennoch, dass Ihr Programm die Antworten gibt. Wenn es aus irgendeinem Grund für TIO zu langsam ist, fügen Sie zur Überprüfung einige Screenshots mit der Ausgabe von Ihrem lokalen Computer hinzu.
Allgemeine Regeln:
- Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.
Lassen Sie sich von Code-Golf-Sprachen nicht davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, für jede Programmiersprache eine möglichst kurze Antwort zu finden. - Für Ihre Antwort gelten Standardregeln mit Standard-E / A-Regeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp, verwenden. Ihr Anruf.
- Standardlücken sind verboten.
- Fügen Sie nach Möglichkeit einen Link mit einem Test für Ihren Code hinzu (z. B. TIO ).
- Außerdem wird dringend empfohlen, eine Erklärung für Ihre Antwort hinzuzufügen.
Testfälle:
Hier die Testfälle für im Bereich (für größere Testfälle können Sie die obigen WolframAlpha-Links verwenden):
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
ANMERKUNG: Da dies eine Code-Golf- Herausforderung ist, läuft es im Wesentlichen darauf hinaus, eine dieser drei Formeln (oder eine Ableitung / Ihre eigene Methode, die immer noch die richtigen Ergebnisse liefert) so kurz wie möglich zu implementieren.
quelle
floor
Antworten:
Wolfram Language (Mathematica) , 59 Bytes
Probieren Sie es online!
verwendet Herbert Kociembas Algorithmus, der auf der OEIS-Seite zu finden ist
Hier ist die rekursive Formel:
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 von @Peter Taylor gespeichert
Ein weiteres Byte, das von @Expired Data gespeichert wurde
quelle
f@1
, daher können Sie 6 Bytes sparen. Natürlich möchten Sie auch Ihr Testframework für die Verwendung anpassenRange[2,10]
.x86-Maschinencode, 119 Byte
Hexdump:
Die Funktion nimmt die Anzahl
n
inecx
, und einen Zeiger auf eine Zeichenkette auf Aufhellblitzedx
(dhfastcall
convention).Bevor ich den Quellcode zeige, einige Erklärungen, wie es die Sache macht. Es wird die rekursive Formel verwendet, die ich folgendermaßen geschrieben habe:
Alles, was der Code tun sollte, ist die Multiplikation mit kleinen Zahlen. Die Zahlen liegen im Bereich von 6 bis 36, was klein genug ist, um in einer 32-Bit-Bitmap dargestellt zu werden. Ich speichere eigentlich nicht das Bit, das die Multiplikation mit 6 darstellt - so kann ich den Code in einer
do-while
Schleife anordnen , beginnend mit der bedingungslosen Multiplikation mit 6.Die großen Zahlen werden in Dezimalform dargestellt - jedes Byte ist ein Wert im Bereich von 0 bis 9, beginnend mit dem MSB.
Die Multiplikation wird von LSB zu MSB durchgeführt; Es wird davon ausgegangen, dass die Anzahl der Stellen bei jeder Multiplikation um 2 zunimmt. Nach der Multiplikation mit einem kleinen Faktor wie 6 wächst die Anzahl der Stellen möglicherweise nur um 1. Wenn also MSB = 0 ist, wird das gesamte Zwischenergebnis nach links verschoben. Es kann tatsächlich vorkommen, dass die Anzahl der Stellen überhaupt nicht wächst und das MSB dann immer noch 0 ist. Dieses Problem wird jedoch behoben, wenn der Code mit größeren Faktoren fortfährt.
Da der Multiplikationscode groß ist, möchte ich ihn nicht zweimal ausdrücken. Ich möchte es auch nicht in eine Funktion verschieben, da der Maschinencode zum Aufrufen einer Funktion groß ist. Also habe ich die äußeren Schleifen so umgestellt, dass der Multiplikationscode nur einmal benötigt wird.
C-Code:
Demontage:
Die Laufzeit für n = 100 beträgt ungefähr 4 Sekunden und das Ergebnis ist eine Zahl mit 38416 Ziffern:
23491019577617 (viele Ziffern hier) ... (viele Nullen hier) 0000000000000000
quelle
05AB1E , 38 Bytes
Erster Versuch.
Verwendet Chris Hardwicks Formel .
Werde versuchen weiter zu golfen und erklären wann ich Zeit habe.
Probieren Sie es online!
quelle
Julia 1.0 ,
8376 BytesProbieren Sie es online!
Verwendet Chris Hardwicks Formel. Übernimmt die Eingabe als Big Integer.
Vielen Dank an H.PWiz für -7 Bytes
quelle
~=n->factorial(big(n))
->~n=prod(big,1:n)
und(24576*~12)^(n%2)
->^(24576*~12,n%2)
~=n->
statt~n=
?Python 2 , 72 Bytes
Probieren Sie es online!
4 Bytes durch Kopieren
n*(n-2)/4
von Neil gespeichert .quelle
Wolfram Language (Mathematica) , 67 Byte
Mit Chris Hardwicks Formel.
Probieren Sie es online!
quelle
JavaScript (Node.js) , 81 Bytes
Herbert Kociembas rekursive Formel. Nimmt ein BigInt als Eingabe.
Probieren Sie es online!
JavaScript (Node.js) ,
102 9896 ByteChris Hardwicks Formel. Nimmt ein BigInt als Eingabe.
Probieren Sie es online!
quelle
JavaScript (Node.js) ,
777573 ByteProbieren Sie es online! Basierend auf Christopher Mowlas Formel. Nimmt ein BigInt als Eingabe. Testgeschirr schamlos von @Arnauld gestohlen.
0xb88d4641131f0n
ist3246670537110000n
in Dezimalzahl. Erläuterung: Ich habe mit dem letzten Prim-Exponenten begonnen und ihn auf vereinfachtn*(n-2n)/4n
(dies ist eine Ganzzahldivision, daher brauche ich keine Anpassung für ungerade Zahlen). Ich untersuchte dann die anderen Primzahlen, um festzustellen, ob ihre Exponenten mit diesem Wert in Beziehung standen (den ich als bezeichnen werdeo
), und stellte fest, dass sie auf eine Art und Weise waren, wenn ich die Verwendung der Parität vonn
(den ich als bezeichnen werde) erlaubtep
). Die Formeln für die Exponenten lauten wie folgt:Die Potenzen können dann nach Exponenten gruppiert werden, beispielsweise
p
ist dies der Exponent von11*7*5**2*3**3*2**14
.quelle
Schläger ,
151141 Bytes-7 bytes dank fede s.!
Probieren Sie es online!
Die längste Antwort mit Chris Hardwicks Formel :)
quelle
expt
Anrufen:(λ(n[e expt])...(e ...)...)
.Python 2 , 122 Bytes
Probieren Sie es online!
Verwendet die rekursive Methode von Herbert Kociemba.
-2 Bytes dank Herman L
quelle
3**6
durch 729 und2**10
durch1024
TIOJelly ,
3938 BytesIch habe das Gefühl, ein paar Golfplätze verpasst zu haben, aber ...
Ein monadischer Link, der Chris Hardwicks Formel implementiert.
Probieren Sie es online! Oder schauen Sie in die Testsuite (
n=[1..33]
).quelle
CJam (47 Bytes)
Online-Demo
j
quelle
Jelly , 43 Bytes
Probieren Sie es online!
quelle
Symbol ,
125 bis110 BytesProbieren Sie es online!
quelle
C (gcc) -lgmp, 279 Bytes
Probieren Sie es online!
quelle
N--*--N/4
statt(N*N-2*N)/4
und entfernen SieN-=2
und#define s mpz_init_set_str
Perl 6 , 85 Bytes
Probieren Sie es online!
quelle
Haskell ,
868574 Bytes-1 Byte gespeichert dank H.PWiz
-11 Byte gespeichert dank Max Yekhlakov
Probieren Sie es online!
quelle
24576
ist kürzer als2^13*3
Python 2 , 92 Bytes
Probieren Sie es online!
quelle
Schale ,
514844 Bytes-4 Bytes dank H.PWiz
Probieren Sie es online!
Dies ist die Formel von Chris Hardwick. Dies ist auch mein erstes Schalenprogramm, daher wären alle Tipps sehr willkommen.
quelle
÷^*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 (es gab einen Fehler) 193175 Bytes (mit Hilfe von Ceiling Cat)Hierfür werden der GMP C ++ - Wrapper (GNU Multi-Precision Library) und die von @ J42161217 ( https://codegolf.stackexchange.com/a/183381/55953 ) verwendete Formel verwendet .
Verwenden Sie
g++ -g rubix.cpp -lgmp -lgmpxx
zum Kompilieren und Linkungolfed, mit testcode
https://tio.run/##PZAxb4MwEIV3foWVDrETqBpARMImWZqha7t0iFQZ4xC3xrg2tJERf73UIVXfcE937zvpdEzrqGZsmu6EYrKvOKkbfbncn3dBb4WqgSsa7d6YpNZiBzR0gIYOlGhwgBUb/H0WksMyihBbFRQb3vVGAYZHB4xnFRr@Rqoo4n2SbdNN9pD7Jtk7uNCvafVEn7fvjx@LMItRbqCKYrTSME7D7OoeOpivl4Mp@eeMhFcAj//3AiJa2xlOm13QUKEgCoYAeJ1aA4XqgChiDARJUl/XazRnXrar8py1fUeIIGR57JaE@AUECLllXFUSB2Mw/bCTpLWdIjm/5ua/
quelle
n=10
Testfalls hinzufügen , damit ich überprüfen kann, ob er funktioniert? Ich vermute, es gibt keine Möglichkeit, diese Arbeit auf dem C ++ (Clang) oder C ++ (GCC) TIO aufgrund der verwendeten Bibliothek zu machen?TI-BASIC,
6362 Bytes (nicht konkurrierend)Ausdruck, der die Eingabe als Ganzzahl annimmt
Ans
. Implementierung der Chris Hardwick Formel. Nicht konkurrierend, da die Hardware, auf der es ausgeführt wird, nur bis zu 16 Dezimalstellen speichert, sodass die Antwort niemals 100% genau ist.Erläuterung:
quelle