Mit einem Fenster ähnlich dem unten abgebildeten erhalten Sie eine Liste von Zeichenfolgen, die Sie in alphabetischer Reihenfolge einfügen möchten.
Wie gezeigt, haben Sie fünf Operationen:
- Nach oben bewegen [U] - Verschiebt die ausgewählte Zeichenfolge um eine Stelle nach oben
- Nach unten bewegen [D] - Verschiebt die ausgewählte Zeichenfolge um eine Stelle nach unten
- Zuerst verschieben [F] - Verschiebt die ausgewählte Zeichenfolge an den Anfang der Liste
- Letzte verschieben [L] - Verschiebt die ausgewählte Zeichenfolge an den unteren Rand der Liste
- Umkehren [R] - Kehrt die Reihenfolge der Liste um
Akzeptieren Sie mit STDIN eine Zahl (wie viele Zeichenfolgen), gefolgt von der ungeordneten Liste der Zeichenfolgen. Jede Zeichenfolge besteht aus 2-99 englischen Kleinbuchstaben. (Das obige Beispiel wäre keine gültige Eingabe.)
Drucken Sie mit STDOUT die Reihenfolge der Liste. Erwähnen Sie zuerst ein Element, das Sie auswählen möchten, und dann die Operationen, die Sie ausführen müssen, um die Liste in alphabetischer Reihenfolge zu platzieren.
Zum Beispiel: February U December F May D D June D R D...
Erläuterung: Klicken Sie auf Februar und verschieben Sie es nach oben. 1. Wählen Sie Dezember und verschieben Sie es nach oben. Mai, bewege es zweimal nach unten. Juni, einmal nach unten gehen, die Liste umkehren, wieder nach unten gehen ...
Da es offensichtlich viele gültige Lösungen gibt, müssen Sie die kürzestmögliche auswählen. Wählen Sie also die Methode mit der geringsten Anzahl von Operationen (7 im obigen Beispiel).
Wenn die korrekten Ausgaben mit der Eingabe verknüpft sind, lösen Sie sie in der folgenden Reihenfolge.
Wählen Sie diejenige mit der geringsten Auswahl an Zeichenfolgen (4 im obigen Beispiel).
Wählen Sie die Operation mit den wenigsten Operationen aus und zählen Sie aufeinanderfolgende identische Operationen (an einer Zeichenfolge) als eine (6 im obigen Beispiel).
Wählen Sie die mit der kürzesten Ausgabe (geringste Anzahl von Zeichen insgesamt, Leerzeichen zählen).
Wählen Sie die mit der Ausgabe, die zuerst alphabetisch angezeigt wird.
Das ist Code-Golf; Die kürzeste Einreichung, die immer die richtige Ausgabe liefert, gewinnt.
Beispiele
- IM
2 zz abc
- AUS
zz D
- AUS
- IM
3 cc bb aa
- AUS
aa R
- AUS
- IM
4 abc def cd ccc
- AUS
abc L R
- AUS
- IM
6 rr mm nn oo qq pp
- AUS
pp U rr L
- AUS
Zusätzliche Beispiele (bereitgestellt von Scott Leadley, alle Fehler sind meine und nicht die von ypnypn)
Einige schwierige Fälle:
- IN => OUT
6 xx aa dd bb ee cc
=>dd L ee L xx L
7 aa bb ee cc dd ff gg
=>ee D D
8 dd ww aa bb cc xx yy zz
=>ww D D D dd D D D
- ( nicht die minimale Anzahl von Zügen, die wäre
cc F bb F aa F
)
- ( nicht die minimale Anzahl von Zügen, die wäre
Permutationen von 4 Elementen aa bb cc dd
mit Sortierpfaden der Länge> 1:
- IN => OUT
4 aa cc dd bb
=>bb F D
4 aa dd cc bb
=>aa L R
4 bb aa dd cc
=>aa F cc U
4 bb dd aa cc
=>aa F cc U
4 bb dd cc aa
=>bb D D R
4 cc aa bb dd
=>cc D D
4 cc aa dd bb
=>bb F aa F
4 cc bb aa dd
=>dd F R
4 cc bb dd aa
=>dd F R
4 cc dd aa bb
=>bb F aa F
4 cc dd bb aa
=>cc D R
4 dd aa cc bb
=>aa L R
4 dd bb aa cc
=>cc F D R
4 dd bb cc aa
=>bb D R
4 dd cc aa bb
=>aa D R
Variationen über ein Thema, 4 Elemente, bei aaaaa bbbb ccc dd
denen die Länge der Zeichenfolge einen Unterschied macht:
- IN => OUT
4 ccc dd aaaaa bbbb
=>ccc L dd L
4 bbbb aaaaa dd ccc
=>bbbb D dd D
4 bbbb dd aaaaa ccc
=>dd L bbbb D
4 ccc aaaaa dd bbbb
=>ccc L dd L
4 ccc dd bbbb aaaaa
=>dd F R
4 dd bbbb ccc aaaaa
=>ccc R D
4 dd ccc aaaaa bbbb
=>bbbb R D
A
der nicht vorhanden ist.ddkP
, D =ddp
, F =ddggP
, L =ddGp
, R =:g/^/m0
. : PAntworten:
Python 2 -
593521Es ist sehr brutal mit einigen Effizienzen, so dass es tatsächlich zu Ende geht. Die Liste mit 6 Elementen, mit der ich teste, dauert auf meinem Laptop ungefähr 5 Sekunden.
Beachten Sie, dass ich die Nummer in der Eingabe ignoriere. Ich finde es nutzlos.
Ugh, ich habe gerade festgestellt, dass ich nicht mehrere Operationen mit demselben Wert richtig verarbeite. Ich werde versuchen, das zu beheben.
quelle
Ruby 2.0
Wenn der Operator [U, D, F, L] eingestellt ist, ist die Anzahl der Elemente in der Liste abzüglich der längsten gemeinsamen Teilsequenz die geringste Anzahl von Zeichenfolgen, die zum Sortieren der Liste ausgewählt werden. Um den R-Operator hinzuzufügen, kehren Sie einfach die Zeichenfolge um und wenden dieselbe Regel an. Leider ist das Minimieren der Auswahl von Zeichenfolgen nicht dasselbe wie das Minimieren der Anzahl von Operationen. Für eine Eingabe von
8 dd ww aa bb cc xx yy zz
lautet beispielsweise die richtige Antwortww D D D dd D D D
, aber die geringste Anzahl von Operationen (die die anderen Kriterien in der Frage erfüllen) wärecc F bb F aa F
. Dies bedeutet, dass ein viel größerer Teil des Satzes möglicher Sortierpfade untersucht werden muss.Diese Lösung verwendet eine Tiefensuchstrategie und Alpha-Beta-Bereinigung. Es ist wichtig, den Alpha-Wert schnell zu senken, um die Suchtiefe zu minimieren. Andernfalls explodiert der Suchbaum exponentiell. Das Bestimmen des Sortierpfads mit der Mindestpunktzahl für das Einführungsbeispiel von OP, das Sortieren von Monaten in Kalenderreihenfolge nach lexikalischer Reihenfolge, wird mit der aktuellen Bewertungsmethode dieses Programms wahrscheinlich einige Jahrzehnte dauern. Das Programm findet sehr schnell die minimale Anzahl von String-Auswahlen (8). Leider bleibt immer noch ein riesiger Baum übrig, durch den man laufen kann.
Ich verwende die Gnomensortierung als Bewertungsfunktion, weil:
Nummer 4 wäre ausreichend. Alles andere ist ein Bonus.
Bei einer Tiefensuche hat die Reihenfolge, in der Operationen untersucht werden, einen erheblichen Einfluss auf die Suchzeit. Da jeder nicht leere Satz von N Elementen mit ≤ N-1 F (erste) oder L (ast) Operationen sortiert werden kann, werden diese Operationen zuerst versucht.
Es besteht diese Perl-TAP -Testsuite:
quelle