Reto

Para este desafío, una cadena montañosa es una que se ajusta a la regla gramatical M: x(Mx)*donde en cada producción, todas las x son el mismo carácter. Cuando se sangra, una cadena montañosa podría verse así:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

Como puede ver, se parece un poco a una montaña desde el costado.

Definicion formal

• Cualquier personaje individual aes montañoso.
• Si Ses una cadena montañosa y aes un personaje, entonces aSaes montañosa, donde la yuxtaposición representa la concatenación de cadenas.
• Si aSay aTason cadenas montañosas, entonces aSaTaes una cadena montañosa. Tenga en cuenta que esta regla implica que este patrón se cumple para cualquier número de repeticiones. (es decir aSaTaUa, aSaTaUaVa, aSaTaUaVaWa... son todos montañosa.)

Ejemplos

Todos los palíndromos de longitud impar son montañosos, por ejemplo:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq Es un ejemplo menos trivial:

q
 w
  e
   r
    t
     y
    t
   r
    a
     s
      d
       f
      d
       g
      d
     s
    a
   r
  e
 w
q
 j
  k
   l
  k
 j
q

Salidas de ejemplo

a                           ==> true
aaa                         ==> true
mom                         ==> true
tacocat                     ==> true
qwertytrasdfdgdsarewqjklkjq ==> true
wasitacaroraratisaw         ==> true
abcbcbcbcba                 ==> true
aaaaabcbbba                 ==> true

<empty string>              ==> false
aa                          ==> false
pie                         ==> false
toohottohoot                ==> false
asdfdghgfdsa                ==> false
myhovercraftisfullofeels    ==> false

Reglas

• Este es un problema de decisión, por lo que cualquier representación de verdadero o falso es una salida válida siempre que sea correcta, consistente, inequívoca y el programa finalice en un período de tiempo finito. Asegúrese de indicar su convención de salida con su solución.
  • Debería ser trivial determinar si la salida indica verdadero o falso sin tener que saber cuál es la cadena de entrada. Tenga en cuenta que esto no significa que los resultados verdaderos o falsos tienen que ser constantes, sin embargo, la convención de "imprimir una cadena montañosa si la cadena es montañosa y una cadena no montañosa si no es montañosa" es una laguna prohibida por razones obvias.
  • Por otro lado, una convención como "arroja una excepción para falso y sale silenciosamente para verdadero" estaría bien, así como "imprime un solo carácter para verdadero y cualquier otra cosa para falso"
• Este es el código de golf, por lo que gana el programa más corto.
• Las lagunas estándar están prohibidas.

Japt v2 , 14 13 bytes

e/.).\1/_g
¥g

¡Pruébelo en línea!

Limpio , 94 89 87 80 bytes

import StdEnv
?[a,b,c:s]=[a: ?if(a==c)s[b,c:s]]
?l=l
$s=limit(iterate?s)==[hd s]

Pruébalo en línea!

Perl, 22 bytes

Incluye +parap

perl -pe '$_=/^((.)((?1)\2)*)$/' <<< abcbcbcbcba

Imprime 1 para verdadero, nada para falso

Brain-Flak , 78 bytes

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

Pruébalo en línea!

Imprime 1 para verdadero, nada para falso.

Para verificar una palabra montañosa, es suficiente suponer que la palabra "baja" la montaña siempre que sea posible.

Python 2 , 89 83 bytes

f=lambda s:re.search(M,s)and f(re.sub(M,r'\1',s))or len(s)==1
import re;M=r'(.).\1'

Pruébalo en línea!

Gracias a ovs por 6 bytes.

Prólogo (SWI) , 29 bytes

a-->[X],+X.
+X-->[];a,[X],+X.

Pruébalo en línea!

Este programa define una regla DCG a//0que coincide con cualquier cadena (lista de caracteres) que sea una cadena montañosa.

Explicación

Para este programa, utilizo una definición ligeramente diferente pero equivalente de cadenas montañosas que la que se describe en el desafío: una cadena montañosa es un carácter cseguido de un número (podría ser cero) de cadenas montañosas con ctachuelas en sus extremos. En una notación más breve derivada de expresiones regulares, una cadena montañosa debe coincidir con el patrón c(Mc)*donde Mes una cadena montañosa y *significa que la expresión entre paréntesis se repite cero o más veces. Tenga en cuenta que si bien cada uno cdebe ser el mismo personaje, Mno es necesario que sea la misma cadena montañosa.

Prueba de equivalencia

Está claro que las reglas 1 y 2 del desafío son equivalentes a mi regla donde Mcocurre cero y una vez respectivamente.

En el caso de que la cadena montañosa ha Mcproducen ntiempos donde n > 1entonces la cadena puede ser reescrito como cMcScdonde Ses los últimos n - 1tiempos que Mcse produce excluyendo la última c(nota que Mes cualquier cadena montañosa y no necesariamente el mismo que el otro M). Como Mes una cadena montañosa, según la regla 2, cMcdebe ser una cadena montañosa. O bien Ses una cadena montañosa, en cuyo caso cSces una cadena montañosa o Spuede reescribirse como cMcTcdónde Tes la última n - 2vez que Mcocurre excluyendo la última c. Esta línea de razonamiento puede seguir aplicándose hasta que la cadena no garantizada sea montañosaMcuna vez que significaría que también tendría que ser montañoso. Por lo tanto, ya cMces montañoso y si cMcy cM'cson montañosas entonces cMcM'cdebe ser montañosa toda la cadena debe ser montañoso.

Por el contrario, para una cadena cScTcdonde cScy cTcson montañosas, entonces o bien cSces una cadena montañosa según la regla 2 o por la regla 3. Si es una cadena montañosa según la regla 2, entonces Stambién debe ser una cadena montañosa. Si es una cadena montañosa según la regla 3, entonces cScdebe tener la forma cUcVcdonde están cUcy cVcson cadenas montañosas. Dado que el más largo de cUcy cVcdebe ser al menos dos caracteres más corto que cScy la regla 3 requiere que se apliquen al menos 5 caracteres, luego de un número finito de aplicaciones de la regla 3, cada cadena entre los cs seleccionados por las aplicaciones de la regla 3 debe ser montañosa cuerda. La misma línea de razonamiento se puede aplicar acTc así la cadena es montañosa por mi definición.

Como cualquier cadena que coincida con mi definición es montañosa y mi definición coincide con todas las cadenas montañosas, es equivalente a la que aparece en la pregunta.

Explicación del Código

En general, la a//0regla DCG, definida en la primera línea, coincide con cualquier cadena montañosa. La +//1regla DCG (como los predicados, las reglas DCG pueden dar nombres de operadores ), definida en la línea dos, coincide con cualquier cadena que esté compuesta de una secuencia de cero o más cadenas montañosas con el carácter pasado a medida que sus argumentos se Xclavan en los extremos de ellas. . O para decirlo con las expresiones regulares similar a la notación que he usado anteriormente, a//0partidos c(Mc)*, pero subcontrata el trabajo de realidad que coincide con el (Mc)*de +//1los que toma ccomo argumento X.

Línea por línea, los códigos se comportan de la siguiente manera:

a-->[X],+X.

Esta línea define la regla DCG a. Los [X]estados que el primer carácter debe ser igual a la variable actualmente indefinido X. Esto da como resultado que Xse establezca igual al primer carácter. La +Xcontinuación que el resto de la cadena debe coincidir la regla DCG +//1con el personaje que Xse establece en como su argumento.

+X-->[];a,[X],+X.

Esta línea define la +//1regla DCG. El ;representa un o en Prolog, lo que significa que la cadena puede coincidir con []o a,[X],+X. El []representa la cadena vacía, por +//1lo que siempre es capaz de coincidir con la cadena vacía. Si la cadena no está vacía, el inicio debe coincidir a//0y, por lo tanto, debe ser una cadena montañosa. Esto debe ser seguido por cualquier carácter Xestablecido. Finalmente, el resto de la cadena debe coincidir +X.

Casco , 15 bytes

εωφΓ§?t·:⁰`(=←t

Pruébalo en línea! La inferencia de tipo tarda unos 40 segundos, así que sea paciente.

Explicación

εωφΓ§?t·:⁰`(=←t  Implicit input, say s = "abacdca"
 ω               Apply until fixed point is reached
  φ              this self-referential anonymous function (accessed with ⁰):
                  Argument is a string x.
   Γ              Deconstruct x into head h and tail t.
    §?t·:⁰`(=←t   Call this function on h and t. It is interpreted as §(?t)(·:⁰)(`(=←t)).
                  § feeds h to (·:⁰) and (`(=←t)), and calls (?t) on the results.
                  The semantics of ? cause t to be fed to all three functions.
          `(=←t   First, check whether h equals the first element (←) of the tail of t.
     ?t           If it does (e.g. if h='a' and t="bacdca"), return tail of t ("acdca").
                  Otherwise (e.g. if h='b' and t="acdca"),
       · ⁰        call the anonymous function recursively on t: "aca"
        :         and prepend h to the result: "baca".
                 Final result is "a".
ε                Is it a 1-element string? Implicitly print 0 or 1.

La idea es reemplazar repetidamente una subcadena de la forma abacon ahasta que esto ya no es posible. La entrada es montañosa si y solo si esto da como resultado una cadena de un solo carácter (que es lo que εprueba). La única situación peligrosa es cuando tenemos una cadena como esta, donde abano parece ser un pico:

a
 b
  a
   c
  a
   d
  a
 b
a

Afortunadamente, siempre podemos transformarlo en uno:

a
 b
a
 c
a
 d
a
 b
a

Retina 0.8.2 , 15 bytes

+`(.).\1
$1
^.$

Pruébalo en línea! Puerto trivial de la respuesta Japt de @ETHproductions.

JavaScript (Node.js) , 53 bytes

Supongo que este es casi el método más sencillo para hacerlo.

f=s=>(w=s.replace(/(.).\1/,"$1"))==s?w.length==1:f(w)

Pruébalo en línea!

JavaScript (Node.js) , 72 bytes

Menos trivial, pero mucho más largo.

s=>[...s].reduce((a,x)=>(a[a.length-2]==x?a.pop():a.push(x),a),[])==s[0]

Pruébalo en línea!