Definieren wir eine nicht leere, unsortierte und endliche Matrix mit eindeutigen Zahlen wie folgt:
Definieren wir 4 Matrixbewegungen als:
- ↑ * (nach oben): Verschiebt eine Spalte nach oben
- ↓ * (nach unten): Verschiebt eine Spalte nach unten
- → * (rechts): Verschiebt eine Reihe nach rechts
- ← * (links): Verschiebt eine Zeile nach links
Das Sternchen (*) stellt die Spalte / Zeile dar, die von der Verschiebung betroffen ist. (Es kann 0-indiziert oder 1-indiziert sein. Bitte geben Sie in Ihrer Antwort an, welche).
Die Herausforderung besteht darin, die Matrix mithilfe der obigen Schritte in aufsteigender Reihenfolge zu sortieren (wobei die obere linke Ecke die niedrigste und die untere rechte Ecke die höchste ist).
Beispiel
Eingabe:
↑0
oder ↓0
. (Beachten Sie, dass jede dieser Bewegungen die Matrix sortieren kann, sodass beide Antworten korrekt sind.)
Eingabe:
Mögliche Ausgabe:→0
Eingabe (Beispiel Testfall):
Mögliche Ausgabe:↑0↑1←1↑2
Eingabe:
Mögliche Ausgabe:
↑0↑2→0→2↑0→2↑1↑2←1
Eingabe:
↑2↑1←3→0←3↓0←0←2→3↑3↑4
Anmerkungen
- Es kann verschiedene korrekte Ausgaben geben (es müssen nicht unbedingt die gleichen wie die Testfälle oder die kürzesten sein)
- Sie können davon ausgehen, dass es immer eine Möglichkeit sein wird, die Matrix zu bestellen
- Kanten verbindet (wie Pacman: v)
- Es wird keine Matrix mit mehr als 9 Spalten oder / und Zeilen geben
- Angenommen, die Matrix enthält nur positive eindeutige Ganzzahlen ungleich Null
- Sie können 4 verschiedene Werte als Zahlen verwenden, um die Bewegungen darzustellen (in diesem Fall geben Sie dies bitte in Ihrer Antwort an).
- Spalte / Zeile kann mit 0 oder 1 indiziert werden
- Gewinnkriterien Code-Golf
Zusätzliche Testfälle sind immer willkommen
←0←0
eine gültige Lösung für das zweite Beispiel, in dem Sie eine Lösung als angegeben haben→0
. Wenn dies der Fall ist, wird wahrscheinlich die Hälfte der Verschiebeoptionen nicht verwendet.Antworten:
JavaScript (ES6),
226.219ByteBrute-Force-Methode, mit rechts (
"R"
) und nach unten ("D"
) bewegt.Gibt entweder eine Zeichenfolge zurück, die die Bewegungen beschreibt, oder ein leeres Array, wenn die Eingabematrix bereits sortiert ist. Spalten und Zeilen in der Ausgabe sind 0-indiziert.
Probieren Sie es online!
Kommentiert
quelle
Python 2 , 296 277 245Python 3 ,200194 BytesProbieren Sie es online!
-19: Unicode-Pfeile wurden nicht benötigt ...
-32: leicht überarbeitet, aber im Durchschnitt viel langsamer.
-45: Hat sich von @ Arnauld inspirieren lassen. Für
f''
(-4 Byte)-6 auf Python 3 umgestellt:
range( )
→r_[: ]
,diff(ravel( ))
→ediff1d( )
Vollständige Suche nach Kombinationen aller möglichen
↓
Züge und→0
. Zeitüberschreitung beim dritten Testfall.Da
→n
ist gleichbedeutend mitWo
r
undc
wie viele Zeilen und Spalten vorhanden sind, reichen diese Bewegungen aus, um jede Lösung zu finden.>v
entsprechen jeweils→↓
. (andere undefiniert)quelle
Gelee , 35 Bytes
Probieren Sie es online!
Volles Programm. Die Ausgänge werden mit L für links und R für rechts nach STDOUT verschoben. Versucht weiterhin zufällige Bewegungen, bis die Matrix sortiert ist, was die Geschwindigkeit oder die algorithmische Komplexität betrifft.
quelle