Desafio

Para esse desafio, uma cadeia montanhosa é aquela que se ajusta à regra gramatical, M: x(Mx)*onde em cada produção, todos os x são o mesmo caractere. Quando recuado, uma cadeia montanhosa pode se parecer com isso:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

Como você pode ver, parece um pouco com uma montanha do lado.

Definição formal

• Qualquer caractere único aé montanhoso.
• Se Sé uma cadeia montanhosa e aé um caractere, então aSaé montanhosa, onde a justaposição representa concatenação de cadeias.
• Se aSae aTasão cadeias montanhosas, então aSaTaé uma cadeia montanhosa. Observe que esta regra implica que esse padrão é válido para qualquer número de repetições. (ou seja aSaTaUa, aSaTaUaVa, aSaTaUaVaWa... são todos montanhosa.)

Exemplos

Todos os palíndromos de comprimento ímpar são montanhosos, por exemplo:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq é um exemplo 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

Saídas de exemplo

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

Regras

• Esse é um problema de decisão; portanto, qualquer representação de true ou false é válida, desde que seja correta, consistente, inequívoca e o programa seja finalizado em um período finito de tempo. Certifique-se de indicar sua convenção de saída com sua solução.
  • Deve ser trivial determinar se a saída indica verdadeiro ou falso sem precisar saber qual é a sequência de entrada. Observe que isso não significa que as saídas verdadeiras ou falsas devam ser constantes; no entanto, a convenção de "imprimir uma cadeia montanhosa se a cadeia for montanhosa e uma cadeia não montanhosa se não montanhosa" é uma brecha proibida por razões óbvias.
  • Por outro lado, uma convenção como "lança uma exceção para falso e sai silenciosamente para verdadeiro" seria boa, além de "imprime um único caractere para verdadeiro e qualquer outra coisa para falso"
• Isso é código de golfe, então o programa mais curto vence.
• As brechas padrão são proibidas.

Japonês v2 , 14 13 bytes

e/.).\1/_g
¥g

Teste online!

Limpo , 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]

Experimente online!

Perl, 22 bytes

Inclui +parap

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

Imprime 1 para verdadeiro, nada para falso

Brain-Flak , 78 bytes

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

Experimente online!

Imprime 1 para verdadeiro, nada para falso.

Para verificar uma palavra montanhosa, é suficiente assumir que a palavra desce a montanha sempre que possível.

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'

Experimente online!

Graças a ovs por 6 bytes.

Prolog (SWI) , 29 bytes

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

Experimente online!

Este programa define uma regra do DCG a//0que corresponde a qualquer sequência (lista de caracteres) que seja uma sequência montanhosa.

Explicação

Para este programa, utilizo uma definição ligeiramente diferente, mas equivalente, para as cordas montanhosas do que é descrito no desafio: Uma corda montanhosa é um caractere cseguido por um número (poderia ser zero) de cordas montanhosas com ctachinhas nas extremidades delas. Em uma notação derivada de regex mais concisa, uma cadeia montanhosa deve corresponder ao padrão em c(Mc)*que Mé uma cadeia montanhosa e *significa que a expressão entre parênteses é repetida zero ou mais vezes. Observe que, embora cada um cdeva ter o mesmo caractere, cada um Mnão precisa ter a mesma cadeia montanhosa.

Prova de Equivalência

É claro que as regras 1 e 2 do desafio são equivalentes à minha regra, onde Mcocorre zero e uma vez, respectivamente.

No caso de que a cadeia montanhosa tem Mcocorrendo nvezes em que n > 1, em seguida, a corda pode ser reescrita como cMcSconde Sé o último n - 1vezes que Mcocorre com excepção do último c(note que Mé qualquer cadeia montanhosa e não necessariamente o mesmo que outro M). Como Mé uma cadeia montanhosa, pela regra 2, cMcdeve ser uma cadeia montanhosa. Ou Sé uma cadeia montanhosa; nesse caso, cScé uma cadeia montanhosa ou Spode ser reescrita como cMcTconde Tsão as últimas n - 2vezes que Mcocorre excluindo a última c. Essa linha de raciocínio pode continuar sendo aplicada até que a cadeia que não é garantida como montanhosa contenhaMcuma vez que significaria que teria que ser montanhoso também. Assim, como cMcé montanhosa e se cMce cM'cmontanhosa, cMcM'cdeve ser montanhosa, toda a cadeia deve ser montanhosa.

Para o inverso, para uma cadeia cScTconde cSce cTcsão montanhosas, então cScé uma cadeia montanhosa pela regra 2 ou pela regra 3. Se for uma cadeia montanhosa pela regra 2, Stambém deve ser uma cadeia montanhosa. Se for uma cadeia montanhosa pela regra 3, cScdeverá ser da forma cUcVconde cUce cVcsão cadeias montanhosas. Como o maior de cUce cVcainda deve ter pelo menos dois caracteres a menos que a cScregra 3, é necessário aplicar pelo menos 5 caracteres, depois de um número finito de aplicativos da regra 3, cada sequência entre os cs selecionados pelos aplicativos da regra 3 deve ser montanhosa corda. A mesma linha de raciocínio pode ser aplicada acTc assim, a corda é montanhosa pela minha definição.

Como qualquer sequência que corresponda à minha definição é montanhosa e minha definição corresponde a todas as sequências montanhosas, é equivalente à fornecida na pergunta.

Explicação do Código

No geral, a a//0regra do DCG, definida na primeira linha, corresponde a qualquer cadeia montanhosa. A +//1regra do DCG (como predicados, as regras do DCG podem receber nomes de operadores ), definida na linha dois, corresponde a qualquer sequência composta de uma sequência de zero ou mais sequências montanhosas com o caractere passado quando seus argumentos se Xapegam às extremidades deles . Ou, para emprestar a notação do tipo regex que usei acima, a//0corresponde , c(Mc)*mas terceiriza, o trabalho de realmente corresponder (Mc)*ao +//1que leva ccomo argumento X.

Linha por linha, os códigos se comportam da seguinte maneira:

a-->[X],+X.

Esta linha define a regra do DCG a. Os [X]estados que o primeiro caractere deve ser igual à variável indefinida no momento X. Isso resulta em Xser definido igual ao primeiro caractere. O +Xafirma que o restante da sequência deve corresponder à regra DCG +//1com o caractere Xdefinido como argumento.

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

Esta linha define a +//1regra do DCG. O ;representa um ou no Prolog, o que significa que a cadeia pode corresponder a []ou a,[X],+X. O []representa a sequência vazia, portanto, +//1é sempre capaz de corresponder à sequência vazia. Se a sequência não estiver vazia, o início dela deve corresponder a//0e, portanto, deve ser uma sequência montanhosa. Isso deve ser seguido por qualquer caractere Xdefinido. Finalmente, o restante da string deve corresponder +X.

Casca , 15 bytes

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

Experimente online! A inferência de tipo leva cerca de 40 segundos, portanto, seja paciente.

Explicação

εωφΓ§?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.

A idéia é substituir repetidamente uma substring do formulário abapor aaté que isso não seja mais possível. A entrada é montanhosa se, e somente se, resultar em uma cadeia de caracteres únicos (que é o que εtesta). A única situação perigosa é quando temos uma string como esta, onde abanão parece um pico:

a
 b
  a
   c
  a
   d
  a
 b
a

Felizmente, sempre podemos transformá-lo em um:

a
 b
a
 c
a
 d
a
 b
a

Retina 0.8.2 , 15 bytes

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

Experimente online! Porta trivial da resposta japonesa do @ETHproductions.

JavaScript (Node.js) , 53 bytes

Suponho que esse seja o método mais simples de fazer isso?

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

Experimente online!

JavaScript (Node.js) , 72 bytes

Menos trivial, mas muito mais longo.

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

Experimente online!