Twój cel: Biorąc pod uwagę ciąg nawiasów, przekaż minimalną odległość Damerau-Levenshtein wymaganą do przekształcenia ciągu wejściowego w ciąg, w którym nawiasy są zrównoważone.
Wkład
Łańcuch wejściowy będzie zawierał tylko nawiasy kwadratowe i żadnych innych znaków. Oznacza to, że jest to kombinacja dowolnych znaków w (){}[]<>
. Możesz wziąć dane wejściowe jako ciąg znaków lub tablicę znaków. Nie możesz przyjmować żadnych innych założeń dotyczących ciągu wejściowego; może być dowolnie długi (do maksymalnego rozmiaru obsługiwanego przez Twój język), może być pusty, nawiasy mogą być już zrównoważone itp.
Odległość Damerau-Levenshtein
Odległość Damerau-Levenshtein między dwoma łańcuchami to minimalna liczba wstawek, usunięć, podstawień pojedynczych znaków i transpozycji (zamiany) dwóch sąsiednich znaków.
Wydajność
Dane wyjściowe powinny być minimalną odległością Damerau-Levenshtein między łańcuchem wejściowym a łańcuchem, w którym pasują nawiasy. Wyjście powinno być liczbą , a nie wynikowym zbalansowanym łańcuchem.
Para nawiasów jest uważana za „dopasowaną”, jeśli nawiasy otwierające i zamykające są w odpowiedniej kolejności i nie zawierają w sobie znaków, takich jak
()
[]{}
Lub jeśli każdy podelement wewnątrz jest również dopasowany.
[()()()()]
{<[]>}
(()())
Podelementy można również zagnieżdżać na kilku warstwach.
[(){<><>[()]}<>()]
<[{((()))}]>
(Podziękowania dla @DJMcMayhem za definicję)
Przypadki testowe
Input Possible Balanced Output
Empty Empty 0
[](){}<> [](){}<> 0
[(){}<> [(){}<>] 1
[(]) []() 1
[[[[[[[[ [][][][] 4
(](<>}[>(}>><(>(({}] ()(<>)[(<><>){}] 7
>]{])< []{()} 3
([)}}>[ (){}<> 4
{<((<<][{{}>[<) <>(<<[]>{}>[]) 5
{><({((})>}}}{(}} {<><({()})>}{}{()} 4
(](<)>}[>(}>>{]<<(]] (<()<><<>()>>[])<()> 9
}})( {}() 2
(Dzięki @WheatWizard za rozwiązanie połowy przypadków testowych)
To jest golf golfowy , wygrywa najmniej bajtów!
Twoje zgłoszenia powinny być możliwe do przetestowania, co oznacza, że powinny dać wynik dla każdego przypadku testowego w nie więcej niż godzinę.
[<>]
czy[]<>
też<>
Odpowiedzi:
Siatkówka,
254252264248240232267 bajtówDziękuję @AnthonyPham, @officialaimm i @MistahFiggins za wskazanie błędów
Wypróbuj online!
Rozwiązanie nie brutalnej siły! Działa dla wszystkich przypadków testowych, a nawet znalazł błąd w jednym.
-2 bajty dzięki @MartinEnder (
${4}
do$+
)+12 bajtów, aby uwzględnić dodatkowe przypadki zamiany
-16 bajtów dzięki lepszemu wykorzystaniu klas znaków
-8 bajtów poprzez usunięcie niepotrzebnego ograniczenia wymiany. To także naprawiło błąd :)
-10 bajtów poprzez połączenie logiki wymiany w jeden regex
+2 bajty, aby uwzględnić kolejne swapy
+ wiele dla różnych poprawek błędów **
Wyjaśnienie:
T`[]()`:;'"
służy do wymiany specjalnych typów wsporników dla wygody. Po pierwsze, rekurencyjnie zamieniamy wszystkie dopasowane nawiasy klamrowe na-
,AB
lub w69
zależności od tego, czy są sąsiednie czy nie.Następnie przydatne jest „zamiana” poprzez usunięcie nowo dopasowanych nawiasów i dodanie a
1
na początku łańcucha. Zastępujemy również-
pusty ciąg, ponieważ był on właśnie używany do powyższej zamiany.Następnie próbujemy „zamieniać”, usuwając pary niedopasowanych nawiasów, które nie pokrywają się z już dopasowanymi nawiasami i dodając a
1
do łańcucha.Na koniec
\W|6B|1
zlicza wszelkie pozostałe pojedyncze nawiasy i liczbę1
s.** Obecnie pracuję nad krótszą wersją, która korzysta z funkcji podziału linii Retiny, chociaż napotkałem poważny problem, więc może to potrwać dość długo.
źródło
${4}
może być skrócony do$+
. Jestem bardzo ciekawy, dlaczego jest to gwarantowane.[{][}] [] [[][][][][][]] [][][][][][][][][][][][]
, możesz po prostu zamienić}
wewnątrz pierwszą parę nawiasów i ustawić ją w równowadze. Odstępy są używane, aby dane wejściowe były nieco bardziej czytelne. Wyprowadziłeś 3, ale tak naprawdę powinien być jeden.[{]}
zwraca 1, ale[{][]}
zwraca 2.Brain-Flak , 1350 bajtów
Wypróbuj online!
W przypadku porównań o stałej prędkości i dereferencji wskaźnika, algorytm ten to O (n 3 ). Niestety Brain-Flak nie ma żadnego z nich, więc program działa zamiast tego w czasie O (n 5 ). Najdłuższy przypadek testowy zajmuje około 15 minut.
Uproszczenie wyników
Aby zobaczyć, że mój algorytm działa, musimy pokazać wyniki, które znacznie zmniejszają przestrzeń wyszukiwania. Wyniki te opierają się na fakcie, że celem jest cały język zamiast tylko jednego określonego ciągu.
Nie są wymagane żadne wstawki. Zamiast tego możesz po prostu usunąć nawias, do którego wstawiony znak by ostatecznie pasował.
Nigdy nie będziesz musiał usuwać wspornika, a następnie zamieniać jego dwóch sąsiadów. Aby to zobaczyć, załóżmy wlog, że usunięto nawias
(
, więc przekształcamya(c
sięca
w dwa etapy. Zmieniającc
i wstawiając kopię, możemy sięgaćca()
w dwóch krokach bez wymiany. (To wstawienie można następnie usunąć zgodnie z powyższą regułą).Ten sam wspornik nigdy nie będzie wymagał dwukrotnej zamiany. Jest to standardowy fakt dotyczący odległości Damerau-Levenshtein w ogóle.
Kolejny wynik uproszczenia, którego nie użyłem, ponieważ rozliczenie ich kosztowałoby bajty:
Algorytm
Gdy dowolny ciąg zostanie zredukowany do zbalansowanego, spełniony będzie jeden z następujących warunków:
k
(być może po zmianie jednego lub obu z nich).k
.W drugim przypadku wspornik w położeniu
k
mógł zamienić się z jednym z sąsiadów. W każdym z dwóch ostatnich przypadków ciąg między (ewentualnie nowym) pierwszym nawiasiem i wspornikiem, który zaczął się w pozycji,k
musi być edytowany do łańcucha zrównoważonego, podobnie jak łańcuch składający się ze wszystkiego po nimk
.Oznacza to, że można zastosować podejście programowania dynamicznego. Ponieważ zamieniony nawias nie musi być zamieniany ponownie, musimy jedynie wziąć pod uwagę ciągłe podciągi, a także podsekwencje utworzone przez usunięcie drugiego znaku i / lub przedostatniego znaku z takiego podłańcucha. Dlatego są tylko O (n 2 ) podsekwencje, na które musimy spojrzeć. Każdy z nich ma O (n) możliwe sposoby dopasowania (lub usunięcia) pierwszego nawiasu, więc algorytm będzie O (n 3 ) w powyższych warunkach.
Struktura danych
Właściwy stos zawiera nawiasy z oryginalnego łańcucha, z dwoma bajtami na nawias. Pierwszy wpis określa cały nawias i jest wybierany w taki sposób, że dopasowane nawiasy mają różnicę dokładnie 1. Drugi wpis określa tylko, czy jest to nawias otwierający czy zamykający: określa to, ile zmian potrzeba, aby dopasować dwa nawiasy wzajemnie. Żadne ukryte zera poniżej tego nigdy nie są jawne, dzięki czemu możemy użyć,
[]
aby uzyskać całkowitą długość tego ciągu.Każdy rozpatrywany podciąg jest reprezentowany przez dwie liczby z zakresu od 0 do 2n: jeden dla pozycji początkowej i jeden dla końca. Interpretacja jest następująca:
2k
zaczyna się w pozycjik
(indeksowany 0), a drugi znak nie jest usuwany.2k+1
zaczyna się od pozycjik
, a drugi znak jest usuwany z powodu zamiany w lewo.2k
kończy się tuż przed pozycjąk
(tzn. Zakres obejmuje lewy i prawy wyłączny).2k-1
kończy się tuż przed pozycjąk
, a przedostatni znak jest usuwany z powodu zamiany w prawo.Niektóre zakresy (
k
dok+1
,2k+1
do2k+1
,2k+1
do2k+3
i2k+1
do2k+5
) nie mają fizycznego sensu. Niektóre z nich i tak pokazują się jako wartości pośrednie, ponieważ jest to łatwiejsze niż dodanie dodatkowych kontroli, aby ich uniknąć.Lewy stos przechowuje liczbę zmian potrzebnych do przekształcenia każdego podłańcucha w zrównoważony ciąg. Odległość edycji interwału
(x,y)
jest zapisywana na głębokościx + y(y-1)/2
.Podczas pętli wewnętrznej wpisy są dodawane powyżej lewego stosu, aby wskazać, które ruchy są możliwe. Te wpisy mają długość 5 bajtów. Licząc od góry, numery są
d+1
,y1
,x1
,y2
,x2
, gdzie ruch kosztujed
edytować kroki i dzieli podciąg do(x1,y1)
i(x2,y2)
.Kod
Opis, który ma nadejść. Na razie oto moja robocza kopia kodu. Niektóre komentarze mogą być niezgodne z terminologią.
źródło
Haskell , 797 bajtów
Wypróbuj online!
źródło