Deine Aufgabe
.. soll das tun, was Brian Fantana anscheinend nicht konnte, und den 2x2x2 Rubik's Cube lösen.
Das Layout
- - A B - - - -
- - C D - - - -
E F G H I J K L
M N O P Q R S T
- - U V - - - -
- - W X - - - -
Und wird Ihnen über stdin oder die Kommandozeile (Ihre Wahl - bitte in Ihrer Antwort angeben) in folgendem Format mitgeteilt:
ABCDEFGHIJKLMNOPQRSTUVWX
Beachten Sie, dass AD die U-Seite (up), EFMN die L-Seite (left), GHOP die F-Seite (front), IJQR die R-Seite (right) und KLST die B-Gesicht (Rückseite) und UX bilden das D-Gesicht (nach unten).
Es gibt sechs eindeutige Zeichen für jede Farbe, die jedoch variieren können. Bereiten Sie sich also auf eine beliebige Kombination von 6 ASCII-Zeichen vor, die für jede Farbe verwendet werden sollen.
Spezifikationen
- Ihr Code sollte eine Lösung nur mit der rechten (R), oberen (U) und vorderen (F) Seite ausgeben und die Standardnotation verwenden: R, R ', R2, U, U', U2, F, F ', F2. Weitere Infos finden Sie hier . Die Beschränkung auf die RUF-Teilmenge ist Standard für den 2x2-Würfel (Hinweis: Behandeln Sie die linke untere Ecke als feste Basis, von der aus Sie arbeiten können).
- Ihr Code muss in der Lage sein, alle möglichen Permutationen des Taschenwürfels zu lösen.
- Jede Lösung sollte weniger als 30 Sekunden dauern.
- Jede Lösung sollte weniger als 30 Züge umfassen.
- Ein Bonus von -20% wird für Lösungen gewährt, die Antworten mit weniger als 20 Zügen enthalten. (Bitte geben Sie dies in Ihrer Antwort an, damit ich eine gründliche Überprüfung durchführen kann.)
- Für Code, der immer eine optimale Lösung bietet, wird ein Bonus von -50% gewährt. - Bitte bewerben Sie sich erneut in Ihrer Antwort
- Die Lösungen dürfen nicht zwei aufeinanderfolgende Züge auf derselben Seite enthalten, da sie leicht zu einem Zug kombiniert werden können.
- Lösungen können optional ein einzelnes - und nur ein einziges - Leerzeichen zwischen den einzelnen Zügen enthalten.
- Bei Bedarf kann die gesamte Lösungssequenz in Klammern, Anführungszeichen, geschweiften Klammern, Klammern oder Carets angegeben werden. Es ist jedoch keine andere externe Ausgabe zulässig.
- Bitte geben Sie entweder eine kurz kommentierte Version Ihres Codes oder eine ausführliche Erklärung Ihres Codes an.
- Keine Verwendung von externen Dateien. Dies schließt Internet, Datentabellen und Bibliotheken / Pakete ein, die für diese Art von Problem erstellt wurden.
- Die kürzeste Anzahl von Codes pro Byte gewinnt.
- Der Gewinner wurde am Mittwoch (30. Juli 2014) ausgewählt.
code-golf
puzzle-solver
permutations
rubiks-cube
Kyle McCormick
quelle
quelle
Antworten:
Python 2.7: 544 Bytes -50% = 272 Bytes **
Stackexchange ersetzt Tabs durch mehrere Leerzeichen. Also technisch hat diese Version 549 Bytes. Ersetzen Sie einfach die ersten beiden Leerzeichen in den Zeilen 6-10 durch einen Tabulator.
Idee hinter meinem Programm: Meine erste Idee war eine erste Suche. Aber das hat zu lange gedauert. Etwa 2 Minuten für ein hartes (11 Züge optimales) Scramble. Deshalb habe ich mich entschlossen, das Problem von beiden Seiten anzusprechen. Ich benutze zwei Sätze. Ich generiere nacheinander alle Zustände mit Abstand 1,2,3, ... zum Scramble und speichere sie in set1, und gleichzeitig alle Zustände mit Abstand 1,2,3, ... zum gelösten Zustand und speichere sie in set2. Wenn sich ein Zustand zum ersten Mal in beiden Mengen befindet, haben wir die Lösung gefunden.
Dafür brauche ich die Farben des gelösten Würfels, die nicht bekannt sind. Die Zeichen 13, 20 und 23 definieren die linke, hintere und untere Farbe. Diese 3 Farben reichen jedoch aus, um den Würfel darzustellen. Ich ersetze einfach die anderen 3 Farben durch Leerzeichen und kann meinen gelösten Zustand als '____ll____bbll____dddd' darstellen.
Oh, und zum Verkürzen der Permutationen habe ich eine Idee von /codegolf//a/34651/29577 verwendet
Ungolfed-Version:
Ich bin ziemlich zufrieden mit dem Ergebnis, weil ich Python noch nicht kenne. Dies ist eines meiner ersten Python-Programme.
Bearbeiten: Ein halbes Jahr später: 427 - 50% = 213,5
Habe ein bisschen mehr Erfahrung in Python und im Golfen. Also habe ich meinen ursprünglichen Code überarbeitet und konnte mehr als 100 Zeichen speichern.
Ich gehe grundsätzlich genauso vor. Die größte Änderung ist, dass ich keine Funktion mehr definiere. Anstatt von
ich kann
Auch ich habe den Umzug lamda ein wenig geändert. Zuerst verkürzen und dann den Code direkt einbinden, da der Funktionsaufruf nur einmal erscheint.
Ich behalte für jeden Zustand eine Liste von Zahlen zwischen 0 und 11, um die Züge darzustellen, anstelle einer Zeichenkette, die die Züge enthält. Die Zahlen werden ganz am Ende umgerechnet.
Außerdem habe ich die beiden for-Schleifen
'for k in r(3):for j in r(3):
zu einer kombiniertfor y in r(12)
. Deshalb muss ich auch die Umzüge machenU4, R4, F4
. Natürlich erscheint ein solcher Zug nicht in der kürzesten Lösung," 2'"[x%4]
funktioniert also. (Wennx % 4 == 3
es eine Ausnahme außerhalb des Bereichs für den Index geben würde)Es ist auch ein bisschen schneller, da ich den Eintrag im zweiten Satz früher suche. Etwa 0,5 Sekunden für eine Lösung mit 11 Zügen.
quelle
C, 366 - 50% optimaler Bonus = 183
Unter Verwendung der Rekursion durchsucht das Programm einen Baum mit einer Tiefe von bis zu 11 Zügen (die maximale Länge einer optimalen Lösung gemäß http://en.wikipedia.org/wiki/Pocket_Cube und der unten genannten Seite) und findet eine Lösung Es wird gedruckt (bis zu 22 Zeichen lang, nach Funktionsargument verfolgt
m
). Die verwendete Reihenfolge ist eine Art Wörterbuchreihenfolge, bei der alle Routen, die mit U, U2, U 'beginnen, durchsucht werden, bevor Routen durchsucht werden, die mit R oder F beginnen. Es muss also nicht unbedingt zuerst die optimale Lösung gefunden werden.Wenn eine Lösung gedruckt wird,
r
wird gleich gemachtm
wodurch sichergestellt wird, dass anschließend nur gleiche oder kürzere Lösungen gedruckt werden. Das Einfügenr=m-2
kostet 2 zusätzliche Zeichen, stellt jedoch sicher, dass nur eine Lösung jeder gefundenen Länge (bis auf das Optimum) gedruckt wird. Wenn NUR die optimale Lösung angezeigt werden soll, muss die beste bisher gefundene Lösung in einer Variablen gespeichert und die optimale Lösung am Ende des Programms ausgedruckt werden (dies würde ca. 15 zusätzliche Zeichen kosten).Die Eingabe wird
c[]
ab Index 64 in das Array eingelesen . Dies ist erforderlich, um Buchstaben in der Tabelle zu verwenden. Die Symbole@
bisW
werden in der Frage anstelle von A bis X verwendet, da es erforderlich ist, mit einer geraden Zahl zu beginnen, damit der Test für Lösungen funktioniert.c['Z']
wird auch für die vorübergehende Speicherung verwendet, da für eine 4-fache Drehung insgesamt 5 Zuordnungen erforderlich sind. Weil der erste Teil vonc[]
nicht verwendet wird, kann die Lösung gespeichert werden (die wie alle C-Zeichenfolgen mit einem Null-Byte abgeschlossen wird).for(i..)
durchläuft eine Folge von 4 viertel Umdrehungen des durch angegebenen Gesichtsn
.Der erste
for(j..)
führt den eigentlichen Austausch gemäß Tabelle durcht[]
.Um zu testen, ob der Würfel gelöst ist, müssen nur die vier Seitenflächen überprüft werden.Die Teile URF und DFR können auch bei entfernten Aufklebern U und D voneinander unterschieden werden, da bei einem Teil RFA im Uhrzeigersinn und bei dem anderen Teil RFA angezeigt wird. Wenn die beiden Teile so vertauscht sind, dass U auf der Unterseite und umgekehrt angezeigt wird, wird die Farbe F auf der rechten Seite und umgekehrt angezeigt.
Die Sekunde
for(j..)
zählt die Anzahl der Fehlpaarungen auf den vier Seitenflächen. Zum Beispiel vergleicht es für die Vorderseite G & O, H & P und G & H (zweimal). Wenne
== 0, wird der Würfel gelöst. Wenne
<9 odere
<13, kann der Würfel möglicherweise im nächsten Zug oder in zwei Zügen gelöst werden. Andernfalls ist es definitiv nicht möglich, den Würfel in dieser Anzahl von Zügen zu lösen. Um Zeit zu sparen, wird diese Heuristik verwendet, um den Suchbaum zu beschneiden und Zeitverschwendung bei vielen Zweigen der Tiefe 10 oder 11 zu vermeiden, die nicht erfolgreich sind. Ausgedrückt als Formel wird diese<45-m*2
.Ungolfed Code
Performance
Das Programm wurde mit den Mustern 1 bis 13 unter http://www.jaapsch.net/puzzles/cube2.htm getestet
Die folgenden Ergebnisse geben das Timing auf meiner Maschine an, um ALLE optimalen Lösungen zu finden (für Neugierige). Auch für die komplexeren Positionen wird das Timing für die oben erwähnte 2-Byte-Modifikation angegeben, die nur eine optimale Lösung findet. Hierfür werden sowohl Zeitangaben gemacht, um die erste Lösung zu finden, als auch um das Programm zu beenden. Die angegebenen Lösungen (die sich im Allgemeinen von den Lösungen unterscheiden, die durch Umkehren der Generatoren auf der verknüpften Seite erhalten wurden) wurden mit einem Online-Würfelsimulator überprüft.
quelle