Eine verehrte Passzeit von Pedanten soll darauf hinweisen, dass Bilder von "Rubik's Cubes" (auf T-Shirts, Postern etc.) eigentlich nicht lösbar sind.
Das erste, was überprüft werden sollte, ist, dass der Würfel aus den richtigen Teilen besteht. Um lösbar zu sein, benötigt ein Würfel sechs Farben mit jeweils neun Quadraten. Der Würfel benötigt auch jede Kanten- und Eckeinheit (dies sind die kleineren Würfel, aus denen der Würfel besteht), um einzigartig zu sein. Sie müssen nicht nur einzigartig sein, sondern wenn zwei Mittelstücke einander gegenüberliegen, kann kein Rand- oder Eckstück beide Farben enthalten.
Sobald Sie einen Würfel haben, der aus allen richtigen Teilen besteht, müssen Sie noch überprüfen, ob er lösbar ist. Es gibt hier ein paar Regeln, also werde ich mich an einen Experten wenden, um sie zu erklären. Der Spoiler unten erklärt, wie wir das machen können. Wenn Sie daran interessiert sind, das Problem selbst zu lösen, müssen Sie die Website nicht besuchen, um diese Herausforderung zu verstehen oder daran teilzunehmen.
Ihre Aufgabe ist es, ein Muster als Eingabe zu verwenden und festzustellen, ob es sich tatsächlich um einen lösbaren Rubik's Cube handelt. Um lösbar zu sein, muss es eine Möglichkeit geben, gültige Züge für einen Würfel auszuführen, sodass der Würfel auf jeder Seite nur eine Farbe hat (und die verschiedenen Seiten unterschiedliche Farben haben). Die meisten Rubik-Würfel haben eine Standardfarbe (Weiß steht für Gelb usw.). Möglicherweise wird nicht davon ausgegangen, dass der Lösungsstatus dieser bestimmten Farbe folgt.
Eine gültige Bewegung ist entweder die Drehung einer einzelnen Fläche des Würfels im oder gegen den Uhrzeigersinn. Mit der Drehung der Fläche des Würfels werden auch alle an die Fläche angrenzenden Quadrate gedreht und bleiben mit der Fläche verbunden, die sie zuvor berührt haben.
IO
Sie können den Würfel auf jede vernünftige Weise nehmen. Wenn Ihre Sprache einen eingebauten "Würfelgesichtstyp" hat, der für Sie gut ist, können Sie auch eine 2D-Matrix des Netzes, des Würfels, 1 3 mal 3 Listen für jedes Gesicht verwenden. Sei einfach vernünftig. Wenn Sie wissen möchten, ob ein bestimmtes Format akzeptabel ist, senden Sie einen Kommentar oder einen Ping-Befehl an mich im Chat.
Ihr Eingabeformat muss nur bis zu 9 mögliche Farben unterstützen.
Für die Ausgabe ist dies ein Entscheidungsproblem, daher sollten Sie einen konstanten Wert für "Ja, dies ist ein gültiger Rubiks-Würfel" und einen anderen konstanten Wert für "Nein, dies ist kein gültiger Rubiks-Würfel" ausgeben.
Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.
Testfälle
Hier sind Testfälle. Sie sind als Würfelnetz formatiert, wobei jedes Quadrat ein Buchstabe ist. Verschiedene Buchstaben stehen für verschiedene Farben. Weitere Testfälle können auf Anfrage hinzugefügt werden.
Lösbar
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YYY
YYY
YYY
GRR
GRR
ORW
WWRBWYBOOGGY
GGRBWGYBBOOO
OOGRWGYWWRBB
WYO
YYB
YYB
Unlösbar
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWYWBBBOOO
YWY
YYY
YYY
RRR
RRR
RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
YWY
YYY
YYY
RRR
RRR
GGG
GGYWYWRBBOBO
GGYWWWROBOOO
GGYWWWRBBOOO
BBB
YWY
YYY
RRW
RRW
GGG
GGYWWYEOBROO
GGYWWYEBBROO
GGOWWYWBBROO
BBB
YYW
YYO
quelle
Antworten:
Kubisch ,
Jahre 1664Jahre 16311089 BytesAusgabe wenn lösbar:
Solved!
Ausgabe wenn nicht lösbar: (leer, keine Ausgabe)
Die Eingabe sollte als Cubically Cube-Dump formatiert werden (siehe
Debug
Abschnitt). Dies wurde vom OP ausdrücklich erlaubt.Erläuterung
Dieses Programm verwendet den Ansatz eines Teufelsalgorithmus , um jeden möglichen Zustand des Würfels in derselben Gruppe wie der gelöste Würfel zu durchlaufen. Wenn der Würfel lösbar ist, wird er irgendwann gelöst, bevor der Algorithmus abgeschlossen ist (vorausgesetzt, der von mir verwendete Algorithmus funktioniert ordnungsgemäß).
Jede Zeile, die mit
⇒
(0x84 in Cubicallys Codepage) beginnt, ist eine Funktionsdefinition. Diese Funktionen bauen aufeinander auf und bilden den eigentlichen Teufelsalgorithmus. Die erste auszuführende Zeile ist die letzte:r
Liest einen Würfel aus stdin und setzt den Speicherwürfel darauf.s
Versetzt den Interpreter in den "Solvemode", was bedeutet, dass er beendet und gedruckt wird,Solved!
wenn der Würfel zu irgendeinem Zeitpunkt aufgelöst wird (nachdem er nicht aufgelöst wurde). Die restlichen Befehle (die einfachf36f71
8 Mal wiederholt werden ) entsprechen dem endgültigen Algorithmus am unteren Rand der verknüpften Seite:Wie kann ich es ausführen?
Sie können es online ausprobieren , aber dieser Link funktioniert nicht. TIO wird fast definitiv eine Zeitüberschreitung aufweisen, bevor dieser Algorithmus abgeschlossen ist (die maximale Laufzeit für einen Interpreter beträgt 60 Sekunden). Wenn der Würfel nicht lösbar ist, dauert es bis zu 11 Millionen Jahre, bis Cubically fertig ist (bei ~ 15,2 Millionen Zügen pro Sekunde, was meine Cloud9-IDE erhält).
Zusätzlich benötigen Sie viel Speicher, um 3 Sextillionen Züge auszuführen. Kubisch kann ungefähr 4 Millionen Bewegungen pro Sekunde ausführen, aber der Vorgang wird höchstwahrscheinlich aufgrund von übermäßigem Speicher abgebrochen . Es stirbt nach 15 Sekunden auf meiner VM mit 512 MB Speicher.Warum sollte die Ausführung von Bewegungen auf einem bereits zugewiesenen Flat-Array-Kostenspeicher erfolgen? Fand ein Speicherleck (oder zwanzig) und reparierte es .Hier ist eine viel besser lesbare Version, die sich genauso verhält.
Aber ich möchte wirklich sehen, dass es funktioniert!
Der erste tatsächliche Zug, der in diesem Teufelsalgorithmus ausgeführt wird
F2
, ist folgenderF2
:Dies wird in der Tat in 0,007 Sekunden auf TIO ausgeführt .
Wie kann das verbessert werden?
Es gibt sicherlich mehr Teufelsalgorithmen; Ich habe einen gefunden, der weniger als ein Dreißigstel der Bewegungen verwendet, die dieser macht. Dies würde jedoch einige tausend Bytes (etwa 100 MB mehr) und einige Dutzend Stunden der Konvertierung einer komplexen Hamilton-Schaltung in kubischen Code kosten.
Es ist auch möglich, einige der Funktionen zu entfernen und sie direkt in die Schleife unten einzufügen. Ich werde jedoch einige Bytes für die Lesbarkeit opfern.
Außerdem erwäge ich eine Änderung des Loop-Verhaltens von Cubically, damit ich die Algorithmen einfacher sieben- oder achtmal wiederholen kann (anstatt sie nur mit den Funktionsaufrufen fest zu codieren, die sieben- oder achtmal in der Quelle wiederholt werden). Oder ich arbeite etwas Magie mit dem Notizblock aus und spiele dies mit mehr Loops.
Beachten Sie, dass ich im Interpreter weiterhin alles Mögliche optimieren werde, damit dies in Zukunft möglicherweise auf einem durchschnittlichen PC funktioniert!
Kubisch 2 Bytes
Die obige Antwort gefällt mir besser, daher füge ich sie als alternative Lösung hinzu. Dies dauert weniger als eine Sekunde als einige Millionen Jahre.
Ausgabe, wenn der Würfel lösbar ist: (nichts)
Ausgabe, wenn der Würfel nicht lösbar ist:
Error: The cube has reached an unsolvable state.
quelle
APL (Dyalog Classic) ,
190 bis174 BytesProbieren Sie es online!
Das Argument ist eine 3x2-Matrix (Reihe0: vorne hinten, Reihe1: links rechts, Reihe2: oben unten) aus 3x3-Zeichenmatrizen. Gibt 1 für einen lösbaren Zauberwürfel zurück, andernfalls 0.
In der TIO-Verknüpfung
t
liest die Funktion , die nicht in der Zeichenanzahl enthalten ist, 9 Eingabezeilen, konvertiert sie vom Standardeingabeformat (ein Netz) in die erforderliche 3x2 x 3x3-Matrix, ruft die Lösung auf und druckt OK, wenn das Ergebnis angezeigt wird ist wie erwartet.Der Algorithmus teilt den gegebenen Würfel in 26 Würfel - Zeichenfolgen der Länge 3 (Ecken), 2 (Kanten) und 1 (Zentren). Es werden auch die 26 Würfel eines gelösten Würfels mit den gleichen 6 zentralen Würfeln erzeugt. Alle folgenden Kriterien müssen erfüllt sein:
Es gibt keine Duplikate unter den 6 Zentren
Die Mengen der gegebenen / gelösten Würfel stimmen bis zur Drehung überein - z. B. betrachten Sie
'WBR'
und'BRW'
der gleiche Würfel, aber nicht'BWR'
Die Paritäten sowohl der Eckpermutation als auch der Kantenpermutation sind gleichmäßig
die Modulo-3 - Summe der Eckendrehindizes (zB den „kleinsten“ Brief nimmt
B
als Bezugspunkt haben wir:'BRW'→0
,'WBR'→1
,'RWB'→2
) Übereinstimmung zwischen den angegebenen und gelösten Würfeln; Gleiches gilt für die Ecken Modulo 2quelle