Su objetivo: dada una cadena de paréntesis, genere la distancia mínima Damerau-Levenshtein requerida para convertir la cadena de entrada en una cadena donde los corchetes estén equilibrados.

Entrada

La cadena de entrada solo contendrá paréntesis y ningún otro carácter. Es decir, es una combinación de cualquiera de los personajes en (){}[]<>. Puede tomar la entrada como una cadena o una matriz de caracteres. No puede hacer otras suposiciones sobre la cadena de entrada; puede ser arbitrariamente largo (hasta el tamaño máximo admitido por su idioma), puede estar vacío, los corchetes ya pueden estar equilibrados, etc.

Damerau-Levenshtein Distancia

La distancia Damerau-Levenshtein entre dos cadenas es el número mínimo de inserciones, eliminaciones, sustituciones de un solo carácter y transposiciones (intercambio) de dos caracteres adyacentes.

Salida

La salida debe ser la distancia mínima de Damerau-Levenshtein entre la cadena de entrada y una cadena en la que coinciden los corchetes. La salida debe ser un número , no la cadena equilibrada resultante.

Un par de paréntesis se considera "coincidente" si los paréntesis de apertura y cierre están en el orden correcto y no tienen caracteres dentro de ellos, como

()
[]{}

O si cada subelemento dentro de él también coincide.

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

Los subelementos también pueden anidarse en varias capas de profundidad.

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

(Gracias a @DJMcMayhem por la definición)

Casos de prueba

Input                   Possible Balanced       Output

Empty                   Empty                   0
[](){}<>                [](){}<>                0           
[(){}<>                 [(){}<>]                1           
[(])                    []()                    1           
[[[[[[[[                [][][][]                4
(](<>}[>(}>><(>(({}]    ()(<>)[(<><>){}]        7
>]{])<                  []{()}                  3
([)}}>[                 (){}<>                  4
{<((<<][{{}>[<)         <>(<<[]>{}>[])          5
{><({((})>}}}{(}}       {<><({()})>}{}{()}      4
(](<)>}[>(}>>{]<<(]]    (<()<><<>()>>[])<()>    9
}})(                    {}()                    2

(Gracias a @WheatWizard por resolver la mitad de los casos de prueba)

Este es el código de golf , ¡la menor cantidad de bytes gana!

Sus envíos deben ser comprobables, lo que significa que debe generar un resultado para cada caso de prueba en no más de una hora.

Retina, 254 252 264 248 240 232 267 bytes

Gracias a @AnthonyPham, @officialaimm y @MistahFiggins por señalar errores

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

Pruébalo en línea!

Solución de fuerza no bruta! Funciona para todos los casos de prueba, e incluso encontró un error en uno.

-2 bytes gracias a @MartinEnder ( ${4}a $+)

+12 bytes para tener en cuenta los casos de intercambio adicionales

-16 bytes haciendo un mejor uso de las clases de caracteres

-8 bytes eliminando una restricción innecesaria en el intercambio. Esto también solucionó un error :)

-10 bytes combinando la lógica de intercambio en una sola expresión regular

+2 bytes para tener en cuenta los intercambios consecutivos

+ muchos para varias correcciones de errores **

Explicación:

T`[]()`:;'"se utiliza para reemplazar tipos de soportes especiales por conveniencia. Primero, reemplazamos recursivamente todos los corchetes coincidentes con -, ABo 69dependiendo de si son adyacentes o no.

Luego, se realiza un "intercambio" útil eliminando los corchetes recién emparejados y agregando un 1al comienzo de la cadena. También reemplazamos -con la cadena vacía, ya que solo se estaba utilizando para el intercambio anterior.

A continuación, intentamos "reemplazos" eliminando pares de corchetes no coincidentes que no se superponen entre corchetes ya emparejados y agregando un 1a la cadena.

Finalmente, \W|6B|1cuenta cualquier paréntesis restante más el número de 1s.

** Actualmente estoy trabajando en una versión más corta que utiliza las funciones de división de línea de Retina, aunque me encontré con un problema considerable, por lo que podría llevar bastante tiempo.

Brain-Flak , 1350 bytes

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

Pruébalo en línea!

Con comparaciones de velocidad constante y desreferencia de puntero, este algoritmo es O (n ³ ). Desafortunadamente, Brain-Flak no tiene ninguno de estos, por lo que este programa se ejecuta en tiempo O (n ⁵ ). El caso de prueba más largo dura unos 15 minutos.

Simplificando resultados

Para ver que mi algoritmo funciona, necesitamos mostrar algunos resultados que reducen considerablemente el espacio de búsqueda. Estos resultados se basan en el hecho de que el objetivo es un idioma completo en lugar de solo una cadena específica.

• No se necesitan inserciones. En cambio, puede eliminar el corchete con el que el carácter insertado eventualmente coincidiría.

• Nunca necesitará quitar un soporte, luego intercambiar sus dos vecinos. Para ver esto, asumir sin pérdida de generalidad que el soporte eliminada es (, por lo estamos transformando a(ca caen dos pasos. Al cambiar ce insertar una copia, podemos llegar ca()en dos pasos sin un intercambio. (Esta inserción se puede eliminar mediante la regla anterior).

• Nunca será necesario cambiar el mismo soporte dos veces. Este es un hecho estándar sobre la distancia Damerau-Levenshtein en general.

Otro resultado simplificador que no utilicé, porque contabilizarlos costaría bytes:

• Si se intercambian dos corchetes, y no coinciden entre sí, la coincidencia eventual con cada uno de esos corchetes nunca se cambiará ni se intercambiará.

El algoritmo

Cuando cualquier cadena se reduce a una cadena equilibrada, una de las siguientes será verdadera:

• El primer paréntesis se elimina.
• El primer paréntesis permanece donde está y coincide con el paréntesis en alguna posición k(posiblemente después de cambiar uno o ambos).
• El primer soporte se intercambia con el segundo, que a su vez coincide con el soporte en la posición k.

En el segundo caso, el soporte en la posición kpuede haber cambiado con uno de sus vecinos. En cualquiera de los dos últimos casos, la cadena entre el primer corchete (posiblemente nuevo) y el corchete que comenzó en posición kdebe editarse en una cadena equilibrada, al igual que la cadena que consiste en todo lo que sigue k.

Esto significa que se puede utilizar un enfoque de programación dinámica. Dado que un paréntesis intercambiado no necesita intercambiarse nuevamente, solo necesitamos considerar subcadenas contiguas, así como subsecuencias formadas al eliminar el segundo carácter y / o el penúltimo carácter de dicha subcadena. Por lo tanto, solo hay O (n ² ) subsecuencias que debemos observar. Cada uno de ellos tiene O (n) formas posibles de unir (o eliminar) el primer paréntesis, por lo que el algoritmo sería O (n ³ ) en las condiciones anteriores.

La estructura de datos

La pila derecha incluye los corchetes de la cadena original, con dos bytes por corchete. La primera entrada determina el corchete completo, y se elige de manera que los corchetes coincidentes tengan una diferencia de exactamente 1. La segunda entrada solo determina si es un corchete de apertura o un corchete de cierre: esto determina cuántos cambios se necesitan para que dos corchetes coincidan El uno al otro. No se hacen explícitos los ceros implícitos debajo de esto, de modo que podamos usar []para obtener la longitud total de esta cadena.

Cada subcadena considerada está representada por dos números en el rango de 0 a 2n: uno para la posición inicial y otro para el final. La interpretación es la siguiente:

• Una subcadena que comienza en 2kcomenzará en la posición k(indexada a 0) y el segundo carácter no se eliminará.
• Una subcadena que comienza en 2k+1comenzará en la posición k, y el segundo carácter se elimina debido a que se ha cambiado a la izquierda.
• Una subcadena que finaliza en 2kterminará justo antes de la posición k(es decir, el rango es inclusivo a la izquierda y exclusivo a la derecha).
• Una subcadena que termina en 2k-1terminará justo antes de la posición k, y el penúltimo carácter se elimina debido a que se ha cambiado a la derecha.

Algunos rangos ( kto k+1, 2k+1to 2k+1, 2k+1to 2k+3y 2k+1to 2k+5) no tienen sentido físico. Algunos de ellos aparecen como valores intermedios de todos modos, porque es más fácil que agregar controles adicionales para evitarlos.

La pila izquierda almacena el número de ediciones necesarias para convertir cada subcadena en una cadena equilibrada. La distancia de edición para el intervalo (x,y)se almacena en profundidad x + y(y-1)/2.

Durante el ciclo interno, las entradas se agregan sobre la pila izquierda para indicar qué movimientos son posibles. Estas entradas tienen 5 bytes de longitud. Contando desde la parte superior, los números son d+1, y1, x1, y2, x2, donde los costos de la mudanza deditar pasos y divide la subcadena en (x1,y1)y (x2,y2).

El código

Descripción por venir. Por ahora, aquí está mi copia de trabajo del código. Algunos comentarios pueden ser inconsistentes con la terminología.

# 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 bytes

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))

Pruébalo en línea!