Défi

Pour ce défi, une chaîne montagneuse est celle qui est conforme à la règle de grammaire M: x(Mx)*où à chaque production, tous les x sont du même caractère. En retrait, une chaîne montagneuse pourrait ressembler à ceci:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

Comme vous pouvez le voir, cela ressemble un peu à une montagne de côté.

Définition formelle

• Tout personnage aest montagneux.
• Si Sest une chaîne montagneuse et aest un caractère, alors aSaest montagneux, où la juxtaposition représente la concaténation de chaînes.
• Si aSaet aTasont des cordes montagneuses, alors aSaTaest une chaîne montagneuse. Notez que cette règle implique que ce modèle est valable pour un nombre illimité de répétitions. (c.-à aSaTaUa- d . aSaTaUaVa, aSaTaUaVaWa... sont tous montagneux.)

Exemples

Tous les palindromes de longueur impaire sont montagneux, par exemple:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq est un exemple moins 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

Exemples de sorties

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

Règles

• Ceci est un problème de décision, donc toute représentation de vrai ou faux est une sortie valide tant qu'elle est correcte, cohérente, sans ambiguïté et que le programme se termine dans un laps de temps fini. Assurez-vous d'indiquer votre convention de sortie avec votre solution.
  • Il devrait être trivial de déterminer si la sortie indique vrai ou faux sans avoir à connaître la chaîne d'entrée. Notez que cela ne signifie pas que les sorties véridiques ou fausses doivent être constantes, cependant la convention de "imprimer une chaîne montagneuse si la chaîne est montagneuse et une chaîne non montagneuse sinon montagneuse" est une échappatoire interdite pour des raisons évidentes.
  • D'un autre côté, une convention comme «lève une exception pour faux et quitte silencieusement pour vrai» serait bien, ainsi que «imprime un seul caractère pour vrai et rien d'autre pour faux»
• C'est le golf de code, donc le programme le plus court gagne.
• Les failles standard sont interdites.

Japt v2 , 14 13 octets

e/.).\1/_g
¥g

Testez-le en ligne!

Nettoyer , 94 89 87 80 octets

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

Essayez-le en ligne!

Perl, 22 octets

Comprend +pourp

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

Imprime 1 pour vrai, rien pour faux

Brain-Flak , 78 octets

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

Essayez-le en ligne!

Imprime 1 pour vrai, rien pour faux.

Pour vérifier un mot montagneux, il suffit de supposer que le mot descend "la montagne" chaque fois que possible.

Python 2 , 89 83 octets

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

Essayez-le en ligne!

Merci aux ovs pour 6 octets.

Prolog (SWI) , 29 octets

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

Essayez-le en ligne!

Ce programme définit une règle DCG a//0qui correspond à n'importe quelle chaîne (liste de caractères) qui est une chaîne montagneuse.

Explication

Pour ce programme, j'utilise une définition légèrement différente mais équivalente pour les chaînes montagneuses de ce qui est décrit dans le défi: Une chaîne montagneuse est un caractère csuivi d'un nombre (pouvant être zéro) de chaînes montagneuses avec cclouées aux extrémités. Dans une notation dérivée d'expressions plus concises, une chaîne montagneuse doit correspondre au modèle c(Mc)*où se Mtrouve une chaîne montagneuse et *signifie que l'expression entre parenthèses est répétée zéro ou plusieurs fois. Notez que bien que chacun cdoive être le même caractère, chacun Mn'a pas besoin d'être la même chaîne montagneuse.

Preuve d'équivalence

Il est clair que les règles 1 et 2 du défi sont équivalentes à ma règle où Mcse produisent respectivement zéro et une fois.

Dans le cas où la chaîne montagneuse a Mceu des nmoments où n > 1alors la chaîne peut être réécrite comme cMcScoù Ssont les derniers n - 1temps qui Mcse produisent à l'exclusion du dernier c(notez qu'il Ms'agit de n'importe quelle chaîne montagneuse et pas nécessairement la même que les autres M). Puisque Mest une chaîne montagneuse, selon la règle 2, cMcdoit être une chaîne montagneuse. Soit Sest une chaîne montagneuse, auquel cas il cScs'agit d'une chaîne montagneuse, soit Speut être réécrite comme cMcTcoù Tse trouvent les derniers n - 2temps qui Mcse produisent en excluant le dernier c. Ce raisonnement peut continuer à être appliqué jusqu'à ce que la chaîne non garantie soit montagneuse contienneMcune fois ce qui signifierait qu'il devrait être également montagneux. Ainsi, cMcétant montagneux et si cMcet cM'csont montagneux, alors cMcM'cdoit être montagneux, la chaîne entière doit être montagneuse.

Pour l'inverse, pour une chaîne cScTcoù cScet cTcsont montagneuses, alors soit cScune chaîne montagneuse selon la règle 2, soit selon la règle 3. Si c'est une chaîne montagneuse selon la règle 2, alors elle Sdoit également être une chaîne montagneuse. S'il s'agit d'une chaîne montagneuse selon la règle 3, elle cScdoit être de la forme cUcVcoù cUcet cVcsont des chaînes montagneuses. Étant donné que le plus long de cUcet cVcdoit toujours être au moins deux caractères plus court que cScet la règle 3 nécessite au moins 5 caractères à appliquer, puis après un nombre fini d'applications de la règle 3, chaque chaîne entre les cs sélectionnés par les applications de la règle 3 doit être montagneuse. chaîne. Le même raisonnement peut être appliqué àcTc ainsi la corde est montagneuse par ma définition.

Étant donné que toute chaîne qui correspond à ma définition est montagneuse et ma définition correspond à toutes les chaînes montagneuses, elle est équivalente à celle donnée dans la question.

Explication du code

Dans l'ensemble, la a//0règle DCG, définie sur la première ligne, correspond à n'importe quelle chaîne montagneuse. La +//1règle DCG (comme les prédicats, les règles DCG peuvent donner des noms d'opérateur ), définie à la ligne deux, correspond à toute chaîne composée d'une séquence de zéro ou plusieurs chaînes montagneuses avec le caractère transmis lorsque ses arguments sont Xcollés aux extrémités de ceux-ci . Ou d'emprunter la notation semblable à regex j'ai utilisé ci - dessus, les a//0matchs c(Mc)*mais externalise le travail de correspondant en fait le (Mc)*à +//1qui prend ccomme argument X.

Ligne par ligne, les codes se comportent comme suit:

a-->[X],+X.

Cette ligne définit la règle DCG a. Les [X]états que le premier caractère doit être égale à la variable actuellement non défini X. Cela se traduit par Xêtre mis égal au premier caractère. Le +Xindique ensuite que le reste de la chaîne doit correspondre à la règle DCG +//1avec le caractère Xdéfini comme argument.

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

Cette ligne définit la +//1règle DCG. Le ;représente un ou dans Prolog, ce qui signifie que la chaîne peut correspondre à []ou a,[X],+X. Le []représente la chaîne vide et +//1est donc toujours capable de correspondre à la chaîne vide. Si la chaîne n'est pas vide, le début de celle-ci doit correspondre a//0et doit donc être une chaîne montagneuse. Celui-ci doit ensuite être suivi du caractère Xdéfini. Enfin, le reste de la chaîne doit correspondre +X.

Husk , 15 octets

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

Essayez-le en ligne! L'inférence de type prend environ 40 secondes, alors soyez patient.

Explication

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

L'idée est de remplacer à plusieurs reprises une sous-chaîne du formulaire abapar ajusqu'à ce que ce ne soit plus possible. L'entrée est montagneuse si et seulement si cela se traduit par une chaîne à un seul caractère (qui est ce qui εteste). La seule situation dangereuse est lorsque nous avons une chaîne comme celle-ci, où abane semble pas être un pic:

a
 b
  a
   c
  a
   d
  a
 b
a

Heureusement, nous pouvons toujours le transformer en un seul:

a
 b
a
 c
a
 d
a
 b
a

Retina 0.8.2 , 15 octets

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

Essayez-le en ligne! Port trivial de la réponse Japt de @ETHproductions.

JavaScript (Node.js) , 53 octets

Je suppose que c'est presque la méthode la plus simple pour le faire?

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

Essayez-le en ligne!

JavaScript (Node.js) , 72 octets

Moins trivial, mais beaucoup plus long.

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

Essayez-le en ligne!