Das fünfzehn Rätsel ist insofern eigenartig, als nur die Hälfte der möglichen Anordnungszustände lösbar sind. Wenn Sie die Kacheln 14 und 15 umdrehen, können Sie die Blöcke auf keinen Fall so verschieben, dass sie zurückgedreht werden.
Ihre Aufgabe besteht darin, ein Programm zu erstellen, das eine Liste von Ganzzahlen im Format Ihrer Wahl akzeptiert (die genau eine Instanz jeder der Zahlen von 0 bis 15 enthält, wobei 0 das Leerzeichen ist), die den Status einer Anordnung von Kacheln in darstellt ein 4x4-Gitter und gibt einen einzelnen booleschen Wert aus, der bestimmt, ob das Gitter lösbar ist oder nicht.
Der kürzeste Code dafür in einer Sprache gewinnt.
Antworten:
Gelee , 9 Bytes
Ein monadischer Link, der eine Liste der Ganzzahlen akzeptiert, die in Zeilen-Hauptreihenfolge abwechselnd zwischen links-rechts und rechts-links gelesen werden. Dies ergibt,
0
wenn lösbar und1
wenn nicht (um dies zu invertieren¬
, rechts neben dem Code hinzufügen ).Probieren Sie es online aus! (Dieses Beispiel ist eine Tafel, auf der 12 nur einrasten muss.)
Wie?
Ähnlich wie bei John Dvoraks Antwort berechnen wir Paritäten und verwenden eine schlangenartige Eingabereihenfolge, um die Schachbrettparität zu vereinfachen. Statt jedoch die Gleichheit der Parität zu überprüfen, addieren wir die Anzahl der nicht in der Reihenfolge befindlichen Werte mit den Nicht-Null-Indizes und testen, ob dies der Fall ist seltsam:
quelle
J, 28 Zeichen
Die Eingabereihenfolge ist zeilenweise, wobei die Zeilen abwechselnd von links nach rechts und von rechts nach links in einem einzelnen Pfad über die Tabelle gelesen werden. Angenommen, die Null gehört zur oberen linken Ecke.
Verwendung unter Windows:
Erläuterung:
<nul set /p=
wird verwendet, um eine neue Zeile in der Eingabe zu verhindern, dieecho
erzeugt,".
die nicht gefällt. Natürlich unterstützt Unixecho /n
.v&.".&.stdin''
liest "v unter Analyse unter stdin" und bedeutet "Eingabe, dann Analyse der Eingabe, dann v, dann Rückgängig machen der Analyse (= Format), dann Rückgängig machen der Eingabe (= Ausgabe)".1!:1]3
ist ein Zeichen kürzer, hat aber keine definierte Umkehrung.C.!.2
bedeutet "Permutationsparität". Es wird entweder1
(gerade Parität) oder_1
(ungerade Parität) zurückgegeben. Das ist,_1^inversions
_1^i.&0
bedeutet "-1 hoch dem Index von 0".C.!.2=_1^i.&0
bedeutet „funktioniert die Permutation Parität , die Lochposition Parität gleich?“Dies funktioniert für eine 4x4-Karte, aber wenn die gewünschte Endposition von links nach rechts zeilenweise ist, hat die Permutation für die gelöste Position eine ungerade Anzahl von Inversionen und damit eine ungerade Parität. Außerdem wird die Parität umgekehrt (für jede Eingabereihenfolge), wenn sich die gewünschte Lochposition von links oben nach rechts unten bewegt. In beiden Fällen ist das Update ein Zeichen: add
-
nach=
der erwarteten Parität zu umkehren.Korrektheitsnachweis:
Nach jeder Bewegung tauscht die Null eine Position mit einer bestimmten Zahl aus, wodurch die Permutationsparität umgedreht wird. Die Null wechselt auch zwischen weißen und schwarzen Schachbrettpositionen, die durch ungerade und gerade Positionen in der Eingabereihenfolge angezeigt werden. Somit ist diese Bedingung notwendig. Das Zählargument reicht auch aus: Es ist allgemein bekannt, dass genau die Hälfte der Positionen lösbar ist. Dieser Zustand filtert genau die Hälfte der möglichen Positionen heraus.
quelle