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ę.

Siatkówka, 254 252 264 248 240 232 267 bajtów

Dziękuję @AnthonyPham, @officialaimm i @MistahFiggins za wskazanie błędów

T`[]()`:;'"
+`'-*"|:-*;|{-*}|<-*>
-
+`'(\W+)"|:(\W+);|{(\W+)}|<(\W+)>
A$1$2$3$+B
+`'(\D+)"|:(\D+);|{(\D+)}|<(\D+)>
6$1$2$3$+9
(.*)(}{|"'|;:|><)
1$1
-

A6B9|6A9B
1
A6+B9+|A6+.B9+.|A+6.B+9
11
T`':{";}`<<<>
(.*)(<\W|\W>)
1$1
+`<(.*A.*B.*)?\W|\W(.*A.*B.*)?>
1$1$2
\W|6B|1

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 -, ABlub w 69zależ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 1na 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 1do łańcucha.

Na koniec \W|6B|1zlicza wszelkie pozostałe pojedyncze nawiasy i liczbę 1s.

** 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.

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 ³ ). Niestety Brain-Flak nie ma żadnego z nich, więc program działa zamiast tego w czasie O (n ⁵ ). 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łcamy a(csię caw dwa etapy. Zmieniając ci 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:

• Jeśli zamieniono dwa nawiasy i nie pasują one do siebie, ostateczne dopasowanie do każdego z tych nawiasów nigdy nie zostanie zmienione ani zamienione.

Algorytm

Gdy dowolny ciąg zostanie zredukowany do zbalansowanego, spełniony będzie jeden z następujących warunków:

• Pierwszy nawias jest usuwany.
• Pierwszy nawias pozostaje na swoim miejscu i dopasowuje nawias w pewnym położeniu k(być może po zmianie jednego lub obu z nich).
• Pierwszy wspornik jest zamieniany z drugim, który z kolei pasuje do wspornika w pozycji k.

W drugim przypadku wspornik w położeniu kmó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, kmusi być edytowany do łańcucha zrównoważonego, podobnie jak łańcuch składający się ze wszystkiego po nim k.

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 ² ) 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 ³ ) 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:

• Podciąg zaczynający się od 2kzaczyna się w pozycji k(indeksowany 0), a drugi znak nie jest usuwany.
• Podciąg zaczynający się od 2k+1zaczyna się od pozycji k, a drugi znak jest usuwany z powodu zamiany w lewo.
• Podciąg kończący się na 2kkończy się tuż przed pozycją k(tzn. Zakres obejmuje lewy i prawy wyłączny).
• Podciąg kończący się na 2k-1kończy się tuż przed pozycją k, a przedostatni znak jest usuwany z powodu zamiany w prawo.

Niektóre zakresy ( kdo k+1, 2k+1do 2k+1, 2k+1do 2k+3i 2k+1do 2k+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ści x + 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 kosztuje dedytować 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ą.

# Determine bracket type for each byte of input
{({}(())(<>))<>({(()()()())<{({}[()])<>}{}>}{}<>({<({}[()])>{()(<{}>)}}{}{}<>))<>}

# For every possible interval length:
<>([[]]){

  # Compute actual length
  ([[]({}()<>)]<>)

  # Note: switching stacks in this loop costs only 2 bytes.
  # For each starting position:
  # Update/save position and length
  <>{(({}())<<>(({})<

    # Get endpoints
    (({}(<()>))<>({}))

    # If length more than 3:
    ([(())()()]){<>({}())}{}{

      # Clean up length-3 left over from comparison
      <>{}<>

      # Initialize counter at 2
      # This counter will be 1 in the loop if we're using a swap at the beginning, 0 otherwise
      ({}())

      # For each counter value:
      {

        # Decrement counter and put on third stack
        (((({}<

          # Do mod 2 for end position
          (({}<>)<{({}()<([(){}])>)}{}>)<>

          # Do mod 2 for start position
          (({}(<>))<{({}()<([(){}])>)}{}<>>)

        # Subtract 1 from counter if swap already happened
        ><>({}))(<

          # Compute start position of substrings to consider
          (((({}({})[()])[()()]<>({}))

            # Compute start position of matches to consider
            <>[({})({}){}]({}<>))<>

            # Compute end position of matches to consider
            [(({}<>)<>({}<>)<>)]

          # Push total distance of matches
          )

        # Push counter as base cost of moves
        # Also push additional copy to deal with length 5 intervals starting with an even number
        <>>)))[()](<()>)<

          # With match distance on stack
          <>(({})<

            # Move to location in input data
            ({}{}()){({}()<({}<>)<>>)}{}

            # Make copy of opening bracket to match
            <>(({})<<>(({}<>))>)

          # Mark as first comparison (swap allowed)
          <>(())>)

          # For each bracket to match with:
          {({}[()()]<

            (<([(

              # If swap is allowed in this position:
              {

                # Subtract 1 from cost
                [{}]

                # Add 1 back if swap doesn't perfectly match
                <(({})()<>[({})]<>)>{()(<{}>)}

              }{}

              # Shift copy of first bracket over, while computing differences
              <(({})<>[()({}<(({}<<>({}<>)<>(({})<>)>)<>[(){}])<>>)]<>)>

              # Add 1 if not perfectly matched
              {()(<{}>)}{}

              # Add 1 if neither bracket faces the other
              # Keep 0 on stack to return here
              (){[()](<{}>)}

              # Return to start of brackets
              <<>{({}<>)<>}{}>

            # Add to base cost and place under base cost
            )]({}{}))>)

            # Return to spot in brackets
            # Zero here means swap not allowed for next bracket
            <>{({}<>)<>}

          >)}

          # Cleanup and move everything to right stack
          {}{}<>{}{}{({}<>)<>}{}

          # Remove one copy of base cost, and move list of costs to right stack
          {}(<>)<>{({}<>)<>}{}

          # If swap at end of substring, remove second-last match
          {(<{}>)<>{({}<>)<>}<>({}<{}>){({}<>)<>}}{}

          # Put end of substring on third stack
          ((({}<({}({})({})<

            # If swap at beginning of substring, remove first match
            {{}<>{}(<>)}{}

            # Move start of substring to other stack for safekeeping
            (((({}<({}<>)>)<>)))

          # Create "deletion" record, excluding cost
          <>>)<>>)<>

          # Move data to left stack
          <({}<({}<<>

            # Add cost to deletion record
            (()())

          >)>)>)

          # Put start position on third stack under end position
          <<>({}<

            # For each matching bracket cost:
            {}{

              # Move cost to left stack
              ({}<>)

              # Make three configurations
              ([()()()]){

                # Increment counter
                ((({}()()<>))[()]<

                  # Increment cost in first and third configurations
                  (({()(<{}>)}{})<>({}<

                    # Keep last position constant
                    (({}<

                      # Beginning of second interval: 1, 2, 1 past end of first
                      <>({}[()()]

                        # End of first interval: -3, -1, 1 plus current position
                        (()[({})({})]

                          # Move current position in first and third configurations
                          ({[()](<{}>)}{}<>{}<

                            (({})<>)

                          >)

                        <>)

                      )

                    >)<>)

                  >)<>)

                  # Move data back to left stack
                  <>({}<({}<({}<({}<>)>)>)>)

                >)

              }{}

            {}<>}

            # Eliminate last entry
            # NOTE: This could remove the deletion record if no possible matches.  This is no loss (probably).
            <>{}{}{}{}{}{}{}{}

        # Restore loop variables
        >)>)>)

      }{}

      # With current endpoints on third stack:
      ({}<({}<

        # For all entries
        {

          # Compute locations and move to right stack
          ({}<(({}){({}())}{}{}<(({}){({}())}{}{}<>)>)>)<>

        }

        # For all entries (now on right stack):
        <>{

          # Cost of match
          ((({}

            # Do twice:
            (()()){([{}](

              # Add cost of resulting substrings
              <({}(<()>)<>){({}<({}<>)>(())<>)}{}>({})<<>{{}({}<>)<>}{}>

            # Evaluate as sum of two runs
            ))([{}()]{})}{}

          )))

          # Find smaller of cost and current minimum
          <>(({}))<>{<>({}[()])}{}

          # Push new minimum in place of old minimum
          ({}<<>{}{}{<>}>)

          <>{}

        }

        # Subtract 1 if nonzero
        <>(({}<>){[()](<{}>)}{})(<>)

      >)>)

      <>(<({}<>)>)<>

    # Otherwise (length 3 or less), use 1 from earlier as cost.
    # Note that length 0-1 is impossible here.
    }<>{}

    # With cost on third stack:
    ({}<

      # Find slot number to store cost of interval
      (({}){({}())}{}{})

      # Move to slot
      {({}<({}<>)>(())<>)}{}

    # Store new cost
    {}>)

    # Move other slots back where they should be
    <>{{}({}<>)<>}{}

  Restore length/position for next iteration
  >)<>>)}

  # Clear length/position from inner loop
  {}<>([[]{}])

}{}

(([]){<{}{}>([])}{}<>){({}[()]<{}>)}{}({}<>)

Haskell , 797 bajtów

import Data.Array;import Data.Function;import Data.List;
e=length;f=fst;o=map;s=listArray;u=minimum;b p=let{m=e p;x=s(1,m)p;
v=s(1,m)(listArray('(','}')[0,0..]:[v!i//[(x!i,i)]|i<-[1..m-1]]);
d q=let{n=e q;y=s(1,n)q;t(a,b)=listArray((a,b),(m,n));
c=t(1,1)[sum[1|x!i/=y!j]|i<-[1..m],j<-[1..n]];
d=t(-1,-1)[if i<0||j<0then m+n else 
if i*j<1then(i+j)else u[1+d!(i-1,j),1+d!(i,j-1),c!(i,j)+d!(i-1,j-1),
let{k=v!i!(y!j)-1;l=w!(i,j-1)-1}in-3+i+j-k-l+d!(k,l)]|i<-[-1..m],j<-[-1..n]];
w=t(1,0)[if j>0&&c!(i,j)>0then w!(i,j-1)else j|i<-[1..m],j<-[0..n]]}in d!(m,n);
a=s(0,div m 2)([(m,"")]:[(concat.take 2.groupBy(on(==)f).sort.o(\q->(d q,q)))(
[b:c++[d]|[b,d]<-words"() <> [] {}",(_,c)<-a!(l-1)]++
concat[[b++d,d++b]|k<-[1..div l 2],(_,b)<-a!k,(_,d)<-a!(l-k)])|l<-[1..div m 2]]);
}in u(o(f.head)(elems a))

Wypróbuj online!