43 Trillionen Permutationen

16

Wir können einen Zauberwürfel wie folgt als Netz darstellen (wenn gelöst):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Jeder Buchstabe stellt die entsprechende Farbe dar ( Wist weiß, Ggrün usw.)

Es hat sich gezeigt, dass es genau 43,252,003,274,489,856,000 (~ 43 Billionen) verschiedene Permutationen gibt, in denen sich ein Zauberwürfel befinden kann.

Ihre Aufgabe ist es, eine ganze Zahl zwischen 1 und 43,252,003,274,489,856,000 und die entsprechende Permutation wie oben gezeigt auszugeben. Sie können wählen, wie die Permutationen sortiert werden sollen, aber der von Ihnen verwendete Algorithmus muss angezeigt werden, um eine eindeutige und korrekte Permutation für jede mögliche Eingabe zu generieren.

Ungültige Permutationsregeln

Entnommen von dieser Seite

Zunächst muss die Mitte jeder 3x3-Fläche gleich bleiben, da das mittlere Quadrat auf einem Zauberwürfel nicht gedreht werden kann. Der gesamte Würfel kann gedreht werden, wobei sich die Position einer Fläche ändert. Dies wirkt sich jedoch nicht auf das Würfelnetz aus.

Wenn wir sagen, dass jede Permutation eine Parität hat, basierend auf der Parität der Anzahl von Swaps, um diese Permutation zu erreichen, können wir sagen

  • Jedes Eckstück hat drei mögliche Ausrichtungen. Es kann richtig ausgerichtet sein (0), im Uhrzeigersinn (1) oder gegen den Uhrzeigersinn (2). Die Summe der Eckorientierungen bleibt immer durch 3 teilbar

  • Bei jeder legalen Drehung auf dem Rubik's Cube wird immer eine gerade Anzahl von Kanten umgedreht, sodass nicht nur ein Teil falsch ausgerichtet sein kann.

  • Unter Berücksichtigung der Permutation aller Ecken und Kanten muss die Gesamtparität gerade sein, was bedeutet, dass jeder legale Zug immer eine gerade Anzahl von Swaps ausführt (ohne Berücksichtigung der Ausrichtung).

Die folgenden drei Netze sind beispielsweise ungültige Ausgaben:

   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)

Regeln

  • Sie müssen nachweisen, wie Sie möchten, dass der Algorithmus gültig ist. Sie müssen nicht jede einzelne Permutation aufzählen, solange Sie die Gültigkeit Ihres Algorithmus nachweisen.
  • 143,252,003,274,489,856,000
    • 253-1253-1
    • 27,946,105,037,114,827,095
  • Sie müssen Ihrer Antwort eine Art Gültigkeitsnachweis beifügen. Dieser Beweis kann die Gültigkeit in jeder akzeptierten Beweismethode beweisen, mit Ausnahme der Aufzählung aller Möglichkeiten.
  • Sie können auf Wunsch auch eine andere Eingabemethode verwenden, sofern:
    • Die Eingabe ist begrenzt
    • Jeder Eingang entspricht einem eindeutigen Ausgang
    • Sie erläutern deutlich das Eingabeformat und wie es den einzelnen Ausgaben entspricht
  • Sie können die Zeichen verwenden 6 verschiedene ASCII - Zeichen verwendet , ändern, zwischen 33 ( !) und 126 ( ~), stattWGRBOY
  • Sie können beliebig ausgeben, sofern es sich um eine übersichtliche Darstellung eines Würfels handelt, in der alle 6 Flächen angezeigt werden können, einschließlich eines gültigen Würfelnetzes, einer einzelnen Zeichenfolge oder eines 3D-Renderings. Wenn Sie sich über ein bestimmtes Format nicht sicher sind, zögern Sie nicht, in den Kommentaren nachzufragen.

Dies ist ein so dass der kürzeste Code in Bytes in jeder Sprache gewinnt.

Beispiel für gültige Ausgaben

   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
quelle
In dem dritten Beispiel ungültig ist es nicht nur , dass die Ecke in einer ungültigen Konfiguration ist, die r / y / o Ecke ist eine unmögliche Ecke aufgrund R und O , das sie gegenüberliegend
fənɛtɪk
Das dritte ungültige Beispiel (CC @ fəˈnəˈtɛk)
Jonathan Allan,
Das gleiche Problem war auch im zweiten ungültigen Beispiel, aber ich hatte es nicht bemerkt. Es kommt weniger dort , weil die Farben sowieso verwirrt sind
fənɛtɪk
(ein1,ein2,ein3,ein4)ein18!ein237ein312!/2ein4211
1
@ Shaggy Ja, eine einzeilige Zeichenfolge ist in Ordnung
Caird Coinheringaahing

Antworten:

13

Holzkohle , 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'→↑Þ³№¹”²δ≔θζ≔ηε

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

Nθ

Geben Sie die Ganzzahl in die Variable ein q.

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

Teilen Sie qdurch 3⁷, und geben Sie den Rest ein e. Betrachtet eman dann eine Zahl in der Basis 3, so setzt man eine Ziffer eso, dass sich ihre Ziffern (in der Basis 3) zu einem Vielfachen von 3 addieren. Auf diese Weise können edie Rotationen der Ecken definiert werden.

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

Teilen Sie qdurch 8!, Und geben Sie den Rest ein z. (8! Wird vorübergehend gespeichert d, um ein Byte zu speichern.) Auf diese Weise können zdie Positionen der Ecken definiert werden.

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

Teilen Sie qdurch 2¹ und geben Sie den Rest ein h. Betrachtet hman dann eine Zahl in der Basis 2, so setzt man eine Ziffer hso, dass sich ihre Ziffern (in der Basis 2) zu einem Vielfachen von 2 addieren. Auf diese Weise können hdie Umkehrungen der Kanten definiert werden.

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

Schleife über eine Zeichenfolgendarstellung der Zentren.

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

Springe zu der Position jedes Zentrums und drucke es aus.

≔⁰ω

Verfolgen Sie die Parität der Eckpositionen in Variable w.

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

Erstellen Sie eine Reihe von Eckpositionen.

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

Erstellen Sie eine Reihe von Eckfarben.

F²«

Schleife zweimal, einmal für Ecken, einmal für Kanten, im Folgenden als "Würfel" bezeichnet.

Fδ«

Durchlaufen Sie die Anordnung der Würfelfarben.

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

Extrahieren Sie die nächste Cube-Position aus zund aktualisieren Sie die Parität in w. Verwenden Sie diese Parität für die vorletzte Kante. Dies stellt sicher, dass die Summe der Paritäten der Kanten und Ecken gleichmäßig ist.

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

Drucken Sie den Würfel an dieser Position aus und passen Sie ihn für die nächste Drehung an oder drehen Sie ihn entsprechend.

≧÷Lκε»

Entfernen Sie die Drehung oder Klappe von e.

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

Erstellen Sie ein Array von Kantenpositionen. Dies wird das zweite Mal in der Schleife verwendet.

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

Erstellen Sie eine Reihe von Kantenfarben.

≔θζ≔ηε

Überschreiben der Ecke Variablen zund emit den entsprechenden Kantenvariablen qund hso , dass die Kanten permutieren und während des zweiten Durchlaufs der Schleife umgedreht.

Neil
quelle
Hinweis für mich: Wenn etwas in Charcoal 330 Bytes hat, probieren Sie es nicht in PHP aus!
Night2
@ Night2 Leider jetzt 334, aufgrund eines Bugfixes (falsche Paritätsberechnung).
Neil
8

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

Probieren Sie es online!

Originalversion mit Arrays von magischen Zahlen anstelle von magischen Strings

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

Probieren Sie es online!

Eine anonyme Funktion, die in ihrer aktuellen Form eine Eingabe von zwei Ganzzahlen akzeptiert, was zulässig zu sein scheint: "Sie können eine alternative Eingabemethode auswählen." Das erste ist die Permutation im Bereich von 0 bis 12!*8!/2 - 1und das zweite ist die Ausrichtung der Teile im Bereich von 0 bis 2**11 * 3*7 - 1. Die Ausgabe im gelösten Zustand ist die folgende Zeichenfolge:

000
000
000
222333444555
222333444555
222333444555
111
111
111

Weiteres Golfen

Es müssen ungefähr 10 weitere Zeichen gespeichert werden, indem das Ausgabeformat auf die folgende Form eingestellt wird. Dies würde jedoch die Lesbarkeit beeinträchtigen, so dass ich dies derzeit nicht tun werde

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

Erläuterung

Permutation

Intern wird der gelöste Zustand durch die Reihe der Oktalzahlen im Array dargestellt a. Die Eingabe gwird durch die Zahlen geteilt, 12..1wobei der Modul verwendet wird, um eine Kante auszuwählen und zu entfernen aund in diese zu platzieren z. Sobald dies erledigt ist, bleiben nur die Ecken in a, wird also gdurch die Zahlen geteilt, 8..1wobei der Modul verwendet wird, um eine Ecke zu entfernen aund darin zu platzieren z.

Da es nicht genügend Informationen gibt, um die Reihenfolge der letzten beiden Ecken zu bestimmen, wurde der Wert gvon zum Zeitpunkt ihres Eintreffens auf Null heruntergeteilt, sodass sie immer zin der ursprünglichen Reihenfolge hinzugefügt werden. Anschließend wird geprüft, ob die Gesamtpermutation gerade oder ungerade ist. Falls erforderlich, werden die letzten beiden Ecken vertauscht, um die Permutation gerade zu machen.

Orientierung

Es gibt verschiedene Möglichkeiten zu entscheiden, ob eine Ecke oder Kante in der richtigen Ausrichtung ist, wenn sie sich nicht an der gelösten Stelle befindet. Für die Zwecke dieser Antwort wird eine Ecke in der richtigen Orientierung in Betracht gezogen , wenn es zeigt , 0oder 1auf der Ober- oder Unterseite. Daher ändert das Drehen der Ober- oder Unterseite nicht die Ausrichtung der Ecken. Durch Drehen der anderen Flächen wird zwar die Ausrichtung geändert, die Gesamtparitätssumme bleibt jedoch unverändert. Die Kanten werden in der richtigen Ausrichtung berücksichtigt, wenn sie ein 2oder 4nach vorne / hinten oder ein 3oder 5nach links / rechts zeigen. Dies bedeutet, dass die Drehung von oben oder unten um eine Vierteldrehung die vier Kanten kippt, die Drehung der anderen Flächen jedoch den Kippstatus unverändert lässt.

Die Eingabe enthält explizite Informationen für alle außer der ersten Kante und der letzten Ecke. Die 11 niedrigstwertigen Bits h%2048werden summiert und der Modul wird verwendet, um die Ausrichtung der ersten Kante zu bestimmen. hwird mit 2 multipliziert, indem es zu sich selbst addiert wird, und der Wert für die Ausrichtung der ersten Kante wird als niedrigstwertiges Bit addiert. Die Ausrichtung der letzten Ecke wird durch fortschreitendes Subtrahieren der Ausrichtung der anderen Ecken von ermittelt j. Für die allerletzte Ecke (wobei i/19= 1) wird der Wert von j%3zu h(der auf Null reduziert wurde) addiert und dies bestimmt die Ausrichtung der letzten Ecke.

Die Zeichenfolge bwird mit dem Text für die Gesichtsmitten vorinitialisiert. hwird durch das 2Zwölffache und dann durch das 3Achtfache geteilt, wobei die Modulos verwendet werden, um die Ausrichtung der Stücke zu bestimmen. In jedem Fall wird die Zahl in zin eine Zeichenfolge mit der entsprechenden Anzahl von Ziffern (2 oder 3) umgewandelt und die Zeichenfolge dann dupliziert. Dadurch kann die korrekte Drehung der vom Modulo gefundenen Ziffern durch Indizieren und Anhängen aus der Zeichenfolge extrahiert werdenb

Anzeige

Schließlich werden die Roh-Aufkleber unter Verwendung der magischen Zahlen in der Indextabelle von bin ein besser lesbares Format kopiert s.

Level River St
quelle