Ihr Ziel: Ausgeben des minimalen Damerau-Levenshtein-Abstands für eine Reihe von Klammern, damit aus der Eingabe-Zeichenfolge eine Zeichenfolge mit ausgeglichenen Klammern wird.
Eingang
Die Eingabezeichenfolge enthält nur Klammern und keine anderen Zeichen. Das heißt, es ist eine Kombination aller Zeichen in (){}[]<>
. Sie können Eingaben entweder als Zeichenfolge oder als Array von Zeichen annehmen. Sie dürfen keine anderen Annahmen über die Eingabezeichenfolge treffen. Es kann beliebig lang sein (bis zu der von Ihrer Sprache unterstützten Maximalgröße), leer sein, die Klammern bereits ausgeglichen sein usw.
Damerau-Levenshtein Entfernung
Der Damerau-Levenshtein-Abstand zwischen zwei Zeichenfolgen ist die minimale Anzahl von Einfügungen, Löschungen, Ersetzungen einzelner Zeichen und Transpositionen (Vertauschen) zweier benachbarter Zeichen.
Ausgabe
Die Ausgabe sollte der minimale Damerau-Levenshtein-Abstand zwischen der Eingabezeichenfolge und einer Zeichenfolge sein, in der die Klammern übereinstimmen. Die Ausgabe sollte eine Zahl sein , nicht die resultierende ausgeglichene Zeichenfolge.
Ein Klammerpaar wird als "übereinstimmend" betrachtet, wenn die öffnende und schließende Klammer in der richtigen Reihenfolge sind und keine Zeichen enthalten, z
()
[]{}
Oder wenn jedes Unterelement in ihm auch übereinstimmt.
[()()()()]
{<[]>}
(()())
Unterelemente können auch mehrere Ebenen tief verschachtelt werden.
[(){<><>[()]}<>()]
<[{((()))}]>
(Danke an @DJMcMayhem für die Definition)
Testfälle
Input Possible Balanced Output
Empty Empty 0
[](){}<> [](){}<> 0
[(){}<> [(){}<>] 1
[(]) []() 1
[[[[[[[[ [][][][] 4
(](<>}[>(}>><(>(({}] ()(<>)[(<><>){}] 7
>]{])< []{()} 3
([)}}>[ (){}<> 4
{<((<<][{{}>[<) <>(<<[]>{}>[]) 5
{><({((})>}}}{(}} {<><({()})>}{}{()} 4
(](<)>}[>(}>>{]<<(]] (<()<><<>()>>[])<()> 9
}})( {}() 2
(Danke an @WheatWizard für die Lösung der Hälfte der Testfälle)
Das ist Code-Golf , die wenigsten Bytes gewinnen!
Ihre Einsendungen sollten testbar sein, das heißt, sie sollten in nicht mehr als einer Stunde ein Ergebnis für jeden Testfall ausgeben.
[<>]
oder[]<>
oder<>
Antworten:
Retina,
254252264248240232267 BytesVielen Dank an @AnthonyPham, @officialaimm und @MistahFiggins für den Hinweis auf Fehler
Probieren Sie es online!
Brute-Force-Lösung! Es funktioniert für alle Testfälle und hat sogar einen Fehler gefunden.
-2 Bytes dank @MartinEnder (
${4}
to$+
)+12 Bytes, um zusätzliche Auslagerungsfälle zu berücksichtigen
-16 Bytes durch bessere Nutzung von Zeichenklassen
-8 Bytes durch Entfernen einer unnötigen Einschränkung beim Auslagern. Dies hat auch einen Fehler behoben :)
-10 Bytes durch Kombinieren der Auslagerungslogik in einem einzigen regulären Ausdruck
+2 Bytes, um aufeinanderfolgende Auslagerungen zu berücksichtigen
+ viele für verschiedene Bugfixes **
Erläuterung:
T`[]()`:;'"
wird verwendet, um spezielle Halterungsarten zu ersetzen. Erstens haben wir alle abgestimmt Klammern rekursiv ersetzen-
,AB
oder69
je nachdem , ob sie benachbart sind oder nicht.Dann wird ein nützlicher "Austausch" durchgeführt, indem neu passende Klammern entfernt und ein
1
an den Anfang der Zeichenkette angefügt werden. Wir ersetzen sie auch durch-
die leere Zeichenfolge, da sie nur für den obigen Austausch verwendet wurde.Als Nächstes versuchen wir "Ersetzungen", indem wir Paare nicht übereinstimmender Klammern entfernen, die sich nicht mit bereits übereinstimmenden Klammern überschneiden, und
1
der Zeichenfolge ein a hinzufügen .Schließlich
\W|6B|1
zählt alle verbleibenden Einzel Klammern plus die Anzahl der1
s.** Ich arbeite derzeit an einer kürzeren Version, die die Funktion zum Aufteilen von Leitungen von Retina verwendet, obwohl ich auf ein beträchtliches Problem gestoßen bin, das eine Weile dauern kann.
quelle
${4}
kann man auf verkürzen$+
. Ich bin sehr gespannt, warum das garantiert funktioniert.[{][}] [] [[][][][][][]] [][][][][][][][][][][][]
, Sie können einfach das}
Innere des ersten Klammerpaares vertauschen und es ausbalancieren lassen. Der Abstand wird verwendet, um die Eingabe ein wenig lesbarer zu machen. Sie haben 3 ausgegeben, aber es sollte wirklich eine sein.[{]}
1, aber 2[{][]}
zurückgibt.Brain-Flak , 1350 Bytes
Probieren Sie es online!
Bei Vergleichen mit konstanter Geschwindigkeit und Zeiger-Dereferenzierung ist dieser Algorithmus O (n 3 ). Leider hat Brain-Flak beides nicht, so dass dieses Programm stattdessen in O (n 5 ) -Zeit ausgeführt wird. Der längste Testfall dauert ca. 15 Minuten.
Ergebnisse vereinfachen
Um zu sehen, dass mein Algorithmus funktioniert, müssen wir einige Ergebnisse anzeigen, die den Suchraum erheblich reduzieren. Diese Ergebnisse beruhen auf der Tatsache, dass das Ziel eine ganze Sprache ist und nicht nur eine bestimmte Zeichenfolge.
Es sind keine Einfügungen erforderlich. Stattdessen können Sie einfach die Klammer entfernen, mit der das eingefügte Zeichen möglicherweise übereinstimmt.
Sie müssen niemals eine Halterung entfernen und dann die beiden Nachbarn austauschen. Um dies zu sehen, gehen davon aus, dass oBdA die entfernte Konsole ist
(
, so dass wir wandelna(c
aufca
in zwei Schritten. Durch Ändernc
und Einfügen einer Kopie können wirca()
in zwei Schritten ohne einen Tausch erreichen. (Diese Einfügung kann dann durch die obige Regel entfernt werden.)Dieselbe Halterung muss niemals zweimal ausgetauscht werden. Dies ist eine Standardtatsache über die Damerau-Levenshtein-Distanz im Allgemeinen.
Ein weiteres vereinfachtes Ergebnis, das ich nicht verwendet habe, weil die Berücksichtigung dieser Daten Byte kosten würde:
Der Algorithmus
Wenn eine Zeichenfolge auf eine ausgeglichene Zeichenfolge reduziert wird, ist eine der folgenden Bedingungen erfüllt:
k
(möglicherweise nachdem eine oder beide geändert wurden).k
.Im zweiten Fall hat die Halterung an der Position
k
möglicherweise mit einem ihrer Nachbarn getauscht. In beiden letzteren Fällen muss die Zeichenfolge zwischen der (möglicherweise neuen) ersten Klammer und der in Position beginnenden Klammerk
zu einer ausgeglichenen Zeichenfolge bearbeitet werden, ebenso wie die Zeichenfolge, die aus allen nachfolgenden Elementen bestehtk
.Dies bedeutet, dass ein dynamischer Programmieransatz verwendet werden kann. Da eine ausgetauschte Klammer nicht erneut ausgetauscht werden muss, müssen nur zusammenhängende Teilzeichenfolgen sowie Teilfolgen berücksichtigt werden, die durch Entfernen des zweiten Zeichens und / oder des vorletzten Zeichens aus einer solchen Teilzeichenfolge gebildet werden. Daher gibt es nur O (n 2 ) Untersequenzen, die wir betrachten müssen. Jedes von diesen hat O (n) mögliche Möglichkeiten, die erste Klammer abzugleichen (oder zu löschen), so dass der Algorithmus unter den obigen Bedingungen O (n 3 ) wäre .
Die Datenstruktur
Der rechte Stapel enthält die Klammern der ursprünglichen Zeichenfolge mit zwei Bytes pro Klammer. Der erste Eintrag bestimmt die gesamte Klammer und wird so ausgewählt, dass übereinstimmende Klammern einen Unterschied von genau 1 aufweisen. Der zweite Eintrag bestimmt nur, ob es sich um eine öffnende Klammer oder eine schließende Klammer handelt: Dies bestimmt, wie viele Änderungen erforderlich sind, damit zwei Klammern übereinstimmen gegenseitig. Darunter werden keine impliziten Nullen explizit angegeben, sodass wir
[]
die Gesamtlänge dieser Zeichenfolge ermitteln können.Jeder betrachtete Teilstring wird durch zwei Zahlen im Bereich von 0 bis 2n dargestellt: eine für die Anfangsposition und eine für das Ende. Die Interpretation ist wie folgt:
2k
, beginnt an der Positionk
(0-indiziert), und das zweite Zeichen wird nicht entfernt.2k+1
, beginnt an der Positionk
, und das zweite Zeichen wird entfernt, da es nach links ausgetauscht wurde.2k
, endet kurz vor der Positionk
(dh der Bereich ist von links nach rechts inklusive und von rechts exklusiv).2k-1
, endet kurz vor der Positionk
, und das vorletzte Zeichen wird entfernt, da es nach rechts vertauscht wurde.Einige Bereiche (
k
zuk+1
,2k+1
zu2k+1
,2k+1
zu2k+3
und2k+1
zu2k+5
) ergeben keinen physischen Sinn. Einige davon werden ohnehin als Zwischenwerte angezeigt, da es einfacher ist, zusätzliche Überprüfungen hinzuzufügen, um sie zu vermeiden.Der linke Stapel speichert die Anzahl der Bearbeitungen, die erforderlich sind, um jede Teilzeichenfolge in eine ausgeglichene Zeichenfolge zu konvertieren. Die Bearbeitungsentfernung für das Intervall
(x,y)
wird in der Tiefe gespeichertx + y(y-1)/2
.Während der inneren Schleife werden Einträge über dem linken Stapel hinzugefügt, um anzuzeigen, welche Bewegungen möglich sind. Diese Einträge sind 5 Byte lang. Zählen von oben, die Zahlen sind
d+1
,y1
,x1
,y2
,x2
, wobei die Bewegung kostetd
Bearbeitungsschritte und unterteilt den Teilstring in(x1,y1)
und(x2,y2)
.Der Code
Beschreibung zu kommen. Im Moment ist hier meine Arbeitskopie des Codes. Einige Kommentare stimmen möglicherweise nicht mit der Terminologie überein.
quelle
Haskell , 797 Bytes
Probieren Sie es online!
quelle