Tengamos una función que toma una cadena y elimina todos los pares de caracteres idénticos adyacentes. Por ejemplo$f$

$f(a\color{red}{bb}ba\color{red}{cc}) = aba$

Tenga en cuenta que cuando dos pares se superponen, solo eliminamos uno de ellos.

Llamaremos a una cadena perfectamente emparejada si la aplicación repetida finalmente produce la cadena vacía. Por ejemplo, la cadena de arriba de no está perfectamente emparejada porque si aplicamos nuevamente, todavía obtenemos . Sin embargo, una cadena como está perfectamente emparejada porque si aplicamos tres veces obtenemos la cadena vacía$abbbacc$$f$$aba$$eabbccadde$$f$

$f(ea\color{red}{bbcc}a\color{red}{dd}e) = eaae$

$f(e\color{red}{aa}e) = ee$

$f(\color{red}{ee}) =$

Su tarea es escribir un código de computadora perfectamente emparejado que tome una cadena (de ASCII imprimible) y decida si está perfectamente emparejado. La cadena de bytes de su fuente debe ser una cadena perfectamente emparejada , aunque su código no necesariamente tiene que estar restringido a ASCII imprimible.

Puede generar dos valores distintos: uno para el caso en que la entrada está perfectamente emparejada y otro para los casos en que no lo está.

Esta es una pregunta de código de golf , por lo que las respuestas se puntuarán por el tamaño en bytes de su fuente con menos bytes mejor.

Casos de prueba

$abbbacc \rightarrow \mathrm{False}\\ abcba \rightarrow \mathrm{False}\\ abab \rightarrow \mathrm{False}\\ abbbaabacc \rightarrow \mathrm{True}\\ eabbccadde \rightarrow \mathrm{True}\\ bbbb \rightarrow \mathrm{True}$

Haskell, 146124 bytes

((""##))
a===bb=bb==a
((aa:bb))##((cc:dd))|aa===cc=bb##dd|1==1=((cc:aa:bb))##dd
a##""=""===a
""##cc=((cc!!00:cc!!00:""))##cc

Sin comentarios. Devuelve ya sea Trueo False.

Pruébalo en línea!

Editar: -22 bytes gracias a @Cat Wizard

Python 2 , 94 bytes

ss=''

for cc in input():ss=[cc+ss,ss[1:]][cc==ss[:1]]

print''==ss##tnirp[,+[=:)(tupni nirof=

Pruébalo en línea!

Todo el paso de actualización se ss=[cc+ss,ss[1:]][cc==ss[:1]]cancela a solo =[+,[.

05AB1E , 26 24 22 20 18 bytes

-2 bytes gracias a los ovs . Emite 0 si la cadena está perfectamente emparejada, 1 de lo contrario.

ΔγʒgÉ}JJ}ĀqqĀÉgʒγΔ

Pruébalo en línea!

ΔγʒgÉ} JJ} ĀqqĀÉgʒγΔ - Programa completo.
Δ} - Hasta que el resultado ya no cambie:
 γʒ} - Divide la cadena en trozos de caracteres iguales y filtra por:
   gÉ - ¿Es la longitud impar?
      JJ - Y después de filtrar, une las partes nuevamente, pero haz esto
                     dos veces para guardar 2 bytes, como en las versiones anteriores.
         Ā - Comprueba si el resultado está vacío
          q - Terminar (salir) la ejecución. El resto del código se ignora.
           qĀÉgʒγΔ: refleja la parte no coincidente para ayudar con el diseño de origen.

Versión anterior

Éste se basa únicamente en un comportamiento indefinido (por lo que no hay un "código muerto"), y genera [['' 0 ']] para cadenas perfectamente emparejadas y [[' 1 ']] para cadenas no perfectamente combinadas:

ΔγεDgÉ£}JJ}ĀĀ£ÉgDεγΔ 

Y la versión de 22 bytes, explicada, que es solo la anterior pero no abusa de UB, y arroja valores razonables .

ΔγεDgÉ£}JJ}ĀqqĀ£ÉgDεγΔ – Full program.
Δ         }            – Until fixed point is reached (starting from the input value):
 γε    }                 – Group equal adjacent values, and for each chunk,
   DgÉ                     – Duplicate, get its length mod by 2.
      £                    – And get the first ^ characters of it. This yields the
                             first char of the chunk or "" respectively for odd-length
                             and even-length chunks respectively.
         JJ                – Join the result to a string, but do this twice to help
                             us with the source layout, saving 2 bytes.
            Ā           – Check if the result is an empty string.
             q          – Terminate the execution. Any other commands are ignored.
              qĀ£ÉgDεγΔ – Mirror the part of the program that isn't otherwise removed
                          anyways. This part forgoes }JJ} because that substring will
                          always be trimmed by the algorithm anyway.

Cubix , 54 bytes

U#;[email protected]>??>i..??O.@1^^...u--u.u!ww;..#..U..;..;!^^!

No genera nada si la cadena está perfectamente emparejada y de lo 1contrario.
Pruébalo aquí

Cubified

      U # ;
      ! u 1
      @ . O
i > ? ? > i . . ? ? O .
@ 1 ^ ^ . . . u - - u .
u ! w w ; . . # . . U .
      . ; .
      . ; !
      ^ ^ !

Explicación

La mayoría de los caracteres son de relleno necesarios para emparejar perfectamente el código. Reemplazando aquellos con .(no-op), obtenemos

      U # ;
      ! u 1
      @ . O
i . ? . > i . . ? . . .
. . ^ . . . . u - . . .
. . . w ; . . . . . . .
      . ; .
      . ; !
      ^ ^ !

Esto se puede dividir en tres pasos:

• Verifique con la cadena vacía (la izquierda iy la ?).
• Bucle, arrojando personajes a la pila y haciendo estallar duplicados (todo en la parte inferior y derecha).
• Compruebe si la pila está vacía (las cosas en la parte superior).

V , 20 , 18 bytes

òóˆ±òø‚

::‚øò±ˆóò

Pruébalo en línea!

Hexdump:

00000000: f2f3 88b1 f2f8 820a 0a3a 3a82 f8f2 b188  .........::.....
00000010: f3f2                                     ..                   ....

Salidas 0 para verdad, 1 para falsedad. Gracias a nmjcman101 por guardar indirectamente 2 bytes.

ò        ò        " Recursively...
 ó                "   Remove...
  <0x88>          "     Any printable ASCII character
        ±         "     Followed by itself
          ø       " Count...
           <0x82> "   The number of non-empty strings

::<0x82>øò±<0x88>óò      " NOP to ensure that the code is paired

R , 142126 bytes

Una lógica más estricta y algunos bytes de comentarios desarrollados por @Giuseppe

f=function(x,p="(.)\\1")"if"(grepl(p,x),f(sub(p,"",x)),!nchar(x))##x(rahcn!,x,,p(bus(f,)x,p(lperg("fi")"1\\).("=p,x(noitcnuf=f

Pruébalo en línea!

f=function(x,p="(.)\\1")"if"(nchar(x),"if"(grepl(p,x),f(sub(p,"",x)),0),1)##)1,)0,xp(bus(f,)x,p(lperg("fi",)x(rahcn("fi")"1).("=p,x(noitcnuf=f

Original:

Pruébalo en línea!

Función de detector recursivo seguido de comentario con todos los caracteres de la función en orden inverso.

APL (Dyalog) , 38 bytes

''≡{'(.)\1'⎕R''⊢⍵}⍣≡⍝⍝≡⍣}⍵⊢R⎕'1\).('{≡

Pruébalo en línea!

Retina , 28 26 bytes

+`(.)\1

C`^$

$^`C1\).(`+

Pruébalo en línea!

Salidas `C1\).(`+0`C1\).(`+para casos falsos y `C1\).(`+1`C1\).(`+verdaderos.

Brain-Flak , 228 200 bytes

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

Pruébalo en línea!

Esta es una prueba de concepto. Probablemente podría ser más corto. Sin embargo, no utiliza ningún comentario.

Emite 0,0si la entrada está perfectamente emparejada y 0,1si la entrada no lo está.

sed 4.2.2 , 34 bytes

:;:t;ss((..??\??))\1ss1;t;/..??/cc

Pruébalo en línea!

Las cadenas emparejadas dan salida vacía, las no emparejadas dan ct:

La versión palindrómica trivial está en 32 :;ss(.)\1ss;t;/./cc/./;t;1\).(;:. La solución anterior fue :;ss((..??\??))\1ss1;t;;/./cc/./t:(cambiada porque la actual abusó cmenos, editar: sí, ahora solo hay 1 carácter después de c: D)

(tenga en cuenta que ;es el separador de declaraciones)

: declara una etiqueta vacía

:t declara la etiqueta t

ss((..??\??))\1ss1es una sustitución, en sed puedes cambiar el delimitador a una sustitución, y esto es lo que hice al cambiarlo s, por lo que lo que hace es sustituir el primero (como se indica 1al final)

• partido de ((..??\??))\1

  • . cualquier personaje
  • .?? seguido de un carácter opcional opcional
  • \?? y un opcional ?
  • seguido de lo mismo justo al lado

• sin nada

Ahora esta sustitución está emparejada consigo misma, por lo que el ;s antes y después de que se cancele también

t y volver a la etiqueta hasta que no haya más sustituciones exitosas

/..?/if .(comodín) seguido de .?un carácter opcional coincide

• cc cambiar el búfer a c

Brain-Flak , 112 110 108 bytes

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

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

Pruébalo en línea!

Esto se basa en mi respuesta de ¿Se corresponden los corchetes? .

Intenté no usar comentarios, pero me quedé atrapado tratando de hacer que el pop nilads ( {}) se empareje . El problema radica en que la forma más fácil de emparejar un par de corchetes es rodearlo en otro par del mismo tipo. Si bien esto es fácil para otras nilas, la {...}mónada crea bucles. Para salir del bucle, debe presionar un 0, pero una vez que haya salido del bucle, debe hacer estallar el 0, lo que agrava el problema.

La solución preparada de 66 bytes es:

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

Pruébalo en línea!

Salidas 1o 1,0si la entrada es un emparejamiento perfecto, 0,0si no.

Versión sin comentarios, 156 bytes

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

Pruébalo en línea!

Como señaló Cat Wizard, la primera respuesta no funciona para todos los intérpretes, ya que no todos manejan los #comentarios. Esta versión no contiene comentarios.

Japt, 24 22 bytes

Salidas falsepara la verdad y truepara falsey.

&&!!e"(.)%1"PP"1%).("e

Intentalo

Brain-Flak , 96 bytes

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

Pruébalo en línea!

No genera nada si la entrada está perfectamente emparejada, y de lo 0contrario.

Versión no perfectamente emparejada (original):

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

Pruébalo en línea!

Haskell , 66 bytes

null.foldr((%))"";;cc%((r:t))|cc==r=t;;t%s=t:s--s:t=s%=r|t:dlof.un

Pruébalo en línea!

Cat Wizard ahorró 6 bytes.

Agregar ++ , 146 bytes

D,g,@~~,L2_|*;;*|_2L,@,g,D
D,ff,@^^,BG€gBF;;FBg€GB,@D1:?:

xx:?

aa:1
`bb
Bxx;;B
Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy

O;;O:,B,`,|,`,>$,`,*W`

Pruébalo en línea!

Dato curioso: esto fue 272 bytes mucho antes de que se iniciara la explicación, ahora supera a Java.

Salidas Truepara cuerdas perfectamente equilibradas, y de lo Falsecontrario

Para mi gran satisfacción, esto supera la aburrida versión de palindromize en 2 bytes, para evitar que el resultado se imprima dos veces. También he tratado de tener el menor código muerto posible, sin embargo, todavía hay algunas secciones comentadas, y el código sale con un código de error de 1 , después de imprimir el valor correcto.

NB : Se solucionó un error con los BFcomandos mientras esta respuesta estaba en desarrollo.

Cómo funciona

f f$\mathit{F}\mathit{F}$$\mathit{ff}$$g$$\mathit{ff}$$\mathit{ff}$$g$$S$$\mathit{ff}(S)$$S$

$S$$abbbaabacc$$[[a], [bbb], [aa], [b], [a], [cc]]$$g$, y reemplace las sublistas con el resultado de la función.

$g$$2$$x$$[a]$$[bb]$$[ccc]$

$x$$x > 2$$x - 2$$x$*

$g(s)$$s$BF^D,ff,@^^,$g$$r$$r$;;

$\mathit{ff}$$g$$\mathit{ff}$

• $\mathit{xx}$$\mathit{ff}$
• $\mathit{yy}$$\mathit{ff}$
• $\mathit{aa}$
• $\mathit{bb}$$\mathit{yy}$

$g$$\mathit{xyab}$$g$

€$\mathit{abc}${...}$g${...}$\mathit{gg}$$\mathit{ff}$$g$

D,gg,@~~,L2_|*;;*|_2L,@D             (NB: -2 bytes)
D,ff,@^^,BG€{gg}BF;;FB}gg{€GB,@D?:   (NB: +6 bytes)

que es 4 bytes más largo.

$x = 5$$x = 15$

x+10 ; Explicit argument
+10  ; Implicit argument, as x is active

$x$`

$\mathit{ff}$$g$$\mathit{xx}$xx:?$\mathit{xx}$$\mathit{aa}$aa:1$1$$\mathit{xx}$$\mathit{bb}$

`bb
Bxx

$\mathit{bb}$$\mathit{xx}$$\mathit{aa} := 1$$\mathit{bb} := \neg \neg \mathit{xx}$

Luego ingresamos a nuestro ciclo while:

Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy

Un ciclo while es una construcción en Add ++: opera directamente en código, en lugar de variables. Las construcciones toman una serie de sentencias de código, separadas con ,las que operan. Las sentencias while y if también toman una condición directamente anterior a la primera, ,que consiste en una única declaración válida, como un comando infijo con variables. Una cosa a tener en cuenta: la variable activa no se puede omitir de la condición.

aa*bb$\mathit{aa}$$\mathit{bb}$$\mathit{yy}$$\mathit{ff}(x)$

`yy,$ff>xx

$\mathit{aa}$

• 1) El nuevo valor no es igual al valor anterior (bucle mientras único)
• 2) El nuevo valor no es la cadena vacía

Uno de los mayores inconvenientes de Add ++ es la falta de declaraciones compuestas, lo que requiere tener una segunda variable de bucle. Asignamos nuestras dos variables:

Con el código

`aa,xx|yy,`bb,Byy

|B $\mathit{xx}$$\mathit{yy}$xx:yy

$\mathit{ff}$$\mathit{aa}$$\mathit{bb}$

$\mathit{aa}$$\mathit{x} = \mathit{y}$$\mathit{aa}$$\mathit{yy}$$\mathit{bb}$$\mathit{aa}$

Luego llegamos a nuestra declaración final:

O

$\mathit{bb}$

• $\mathit{aa} = 1$$\mathit{bb} = \mathrm{False}$$\mathrm{False}$
• $\mathit{aa} = \mathrm{True}$$\mathit{bb} = \mathrm{False}$$\mathrm{False}$
• $\mathit{aa} = \mathrm{False}$$\mathit{bb} = \mathrm{True}$$\mathrm{True}$

$\mathit{bb}$$\mathit{bb}$$\mathrm{True}$$\mathrm{False}$

JavaScript (ES6), 76 bytes

Devuelve un booleano.

ff=ss=>ss==(ss=ss.replace(/(.)\1/,''))?!ss:ff(ss)//)(:!?,/1\).(/(ecalper.=(>

Pruébalo en línea!

Sugerido por @Shaggy: 58 bytes devolviendo una cadena vacía para emparejar perfectamente o arrojando un error de lo contrario.

Wolfram Language (Mathematica) , 70 64 bytes

{#//.{aa___,bb__,bb_,cc___}:>{aa,cc}}=={{}}(**(,{>:}_,{.#{&)**)&

Pruébalo en línea!

Sin comentarios, 92 bytes

((#//.bb_:>StringReplace[00[ecalpeRgnirtS>aa__:_.#&];bb,{{,}};00>00;00;aa:_~~aa_:>""]))==""&

Pruébalo en línea!

Lua , 178 bytes

p=...S={}for a in p:gmatch"."do E=S[#S]~=a;S[E and#S+1 or#S]=E and a or X end;print(#S==0)--)0S#(tnirp;dne X ro a dna E=]S#ro 1+S#dna E[S;a=~]S#[S=E od"."hctamg:p ni a rof}{=S.=p

Pruébalo en línea!

Si bien es una solución terriblemente larga, esto hace bastante uso de las peculiaridades específicas de Lua. Esto es en realidad un algoritmo de pila de fuerza bruta minimizado. El programa se complica por el hecho de que los patrones de Lua no permiten reemplazar pares y la expresión regular no está integrada.

Explicación:

p=... -- command-line argument
S={} -- the stack
for c in p:gmatch"." do -- shorter than "for i=1,#p do ..."
    E=S[#S]~=c -- check whether we have the right letter on top of stack
    -- could've saved some bytes by doing == instead of ~=
    -- but the double negation is necessary for ternary operator
    -- to work with nil values
    S[E and #S+1 or #S]=E and c or X -- Lua's awesome "ternary operator"
end
-- i'm sure there is a better way to output this (table indexing?)
print(#S==0)

Gol> <> , 30 bytes

1ll1**F:}}:{=Q{~~||lzBBzl{Q={F

Pruébalo en línea!

Todo después del primero Bes un código en exceso y no se ejecuta. Una función que devuelve la parte superior de la pila como 1si la entrada fuera un emparejamiento perfecto, de lo 0contrario.

Explicación:

1       Push 1 as the end string marker
 ll1**  Push n, where n (len+1)*(len+2), 
        This is larger than the amount of steps needed to determine pairing
      F           |  Repeat that many times
       :}}:{=        Compare the first two characters of the string
             Q   |   If they are equal
              {~~    Pop both of them
        String is also rotated by 1
        If the string becomes empty, the 1 is compared to itself and removed.
                   lzB   Return whether the length of the stack is 0
                      Bzl{Q={F  Excess code to match unpaired symbols

Cubix , 30 bytes

1O@;??;@ii??O;>>;;;..1Wcc1??1W

Pruébalo en línea!

Salidas 1si la cadena está perfectamente emparejada y nada más.

Cubified

      1 O @
      ; ? ?
      ; @ i
i ? ? O ; > > ; ; ; . .
1 W c c 1 ? ? 1 W . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Simplificado

      1 O @
      ; ? .
      . @ .
i ? . . . . > ; ; ; . .
. W c . . . ? 1 W . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

La lógica y la estructura general son las mismas que en la respuesta de Mnemonic, pero sin una comprobación explícita de la cadena vacía.

Haskell , 92 bytes

gg""

gg((aa:cc:bb))dd|aa==cc=gg bb dd

gg  aa""=""==aa

gg  aa((bb:c))=gg((bb:aa))c--c:=c:|

Pruébalo en línea!

La respuesta de @ nimi es genial, no utiliza ningún comentario. Este es más corto pero usa un comentario.

La respuesta de @ xnor también es genial, usa comentarios y es más corta que esta.

Python 2 , 114 bytes

import re

e=lambda i,nn=1:e(*re.subn('(.)\\1','',i))if nn else''==i##ieslef'1).('(nbus.er*(e:1=,i adbmal=r tropmi

Pruébalo en línea!

Devoluciones Truepara cadenas perfectamente emparejadas, de lo Falsecontrario.

(¡Realmente no se verifica a sí mismo, porque (.)no coincidirá con las nuevas líneas en el código! Pero @Cat Wizard dijo que está bien, porque las nuevas líneas no son caracteres ASCII imprimibles, por lo que mi programa no necesita manejarlos).

Esta es una versión perfectamente emparejada de:

import re;p=lambda s,n=1:p(*re.subn('(.)\\1','',s))if n else''==i

para lo cual una perfeccionización "más perezosa" code + '##' + f(code[::-1])daría 120 bytes. (Es decir, cambiar el nombre de las variables, etc. para introducir más pares contraídos dentro del comentario, la mitad del código guardó 6 bytes).

re.subnEs una variante poco conocida re.subque devuelve una tupla (new_string, number_of_substitutions_made). ¡Es bastante bueno para encontrar puntos de fijación de sustitución de expresiones regulares!

Jalea , 26 24 22 bytes

ẠƬµF€ḂLḣgŒŒgḣLḂ$$€FµƬẠ

Pruébalo en línea!

Extrañamente parece funcionar sin mover el código hacia atrás a un enlace no utilizado.

Devuelve 0 si la entrada está perfectamente emparejada, 1 de lo contrario.

Codigo activo:

ŒgḣLḂ$$€FµƬẠ
Œg            Group runs 'abbbcc'->['a','bbb','cc']
       €      For each of these strings:
      $       Monad{
     $            Monad{
   L                  Find the length...
    Ḃ                 ...mod 2. 
                      } -> [1, 1, 0] in this example.
  ḣ               Take this many characters from the string.
                  } -> [['a'], ['b'], []]
        F     Flatten -> ['a', 'b']
          Ƭ   Repeat...
         µ    The last monadic chain until a fixed point is reached.
           Ạ  All. If it is not a perfectly paired string, all elements in the 
              result of Ƭ will be nonempty and 1 is returned.
              If it is perfectly paired, the last element is [] which is falsy
              and 0 is returned.

Adjunto , 82 bytes

{0=#Fixpoint[{Replace[_,/"(.)\\1",""]},_]}??}]_,}],"1).("/,_[ecalpeR{[tniopxiF#=0{

Pruébalo en línea!

Nada increible aqui. FixpointUna función que elimina pares consecutivos.

Java 8, 158 156 154 bytes

n->{for(;n.matches(".*(.)\\1.*");n=n.replaceAll("(.)\\1",""));return  n.isEmpty();}//};)(ytpmEsi.ruter;,"1).("(Aecalper.n=n;)"*.1).(*."(sehctam.n;(rof{>-n

Devuelve un booleano ( true/ false).

-2 bytes gracias a @raznagul .

Pruébalo en línea.

Explicación:

n->{                              // Method with String parameter and boolean return-type
  for(;n.matches(".*(.)\\1.*");   //  Loop as long as the String still contains pairs
    n=n.replaceAll("(.)\\1","")); //   Remove all pairs
  return  n.isEmpty();}           //  Return whether the String is empty now
//};)(ytpmEsi.ruter;,"1).("(Aecalper.n=n;)"*.1).(*."(sehctam.n;(rof{>-n
                                  // Comment reversed of the source code,
                                  // minus the pairs: '\\';'ll';'\\';'""))';'n  n';'//'