Herausforderung

Für diese Herausforderung ist eine gebirgige Zeichenfolge eine Zeichenfolge, die der Grammatikregel entspricht, bei der M: x(Mx)*bei jeder Produktion alle x das gleiche Zeichen sind. Wenn eine gebirgige Zeichenfolge eingerückt ist, sieht sie möglicherweise folgendermaßen aus:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

Wie Sie sehen, sieht es von der Seite ein bisschen aus wie ein Berg.

Formale Definition

• Jedes einzelne Zeichen aist bergig.
• Wenn Ses sich um eine bergige Zeichenfolge handelt und wenn es sich aum ein Zeichen handelt, handelt es sich um eine bergige Zeichenfolge aSa, bei der das Nebeneinander die Verkettung der Zeichenfolgen darstellt.
• Wenn aSaund aTasind bergige Saiten, dann aSaTaist eine bergige Saite. Beachten Sie, dass diese Regel impliziert, dass dieses Muster für eine beliebige Anzahl von Wiederholungen gilt. (dh aSaTaUa, aSaTaUaVa, aSaTaUaVaWa... sind alle gebirgig.)

Beispiele

Alle ungeraden Palindrome sind bergig, zum Beispiel:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq ist ein weniger triviales Beispiel:

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

Beispielausgaben

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

Regeln

• Dies ist ein Entscheidungsproblem, daher ist jede Darstellung von wahr oder falsch eine gültige Ausgabe, solange sie korrekt, konsistent und eindeutig ist und das Programm in einer endlichen Zeitspanne endet. Stellen Sie sicher, dass Sie Ihre Ausgabekonvention mit Ihrer Lösung angeben.
  • Es sollte trivial sein zu bestimmen, ob die Ausgabe true oder false anzeigt, ohne dass die Eingabezeichenfolge bekannt sein muss. Beachten Sie, dass dies nicht bedeutet, dass die wahren oder falschen Ausgaben konstant sein müssen. Die Konvention "Drucken einer Gebirgszeichenfolge, wenn die Zeichenfolge bergig ist, und einer nicht bergigen Zeichenfolge, wenn sie nicht bergig ist" ist jedoch aus offensichtlichen Gründen eine verbotene Lücke.
  • Auf der anderen Seite wäre eine Konvention wie "wirft eine Ausnahme für falsch und beendet stillschweigend für wahr" in Ordnung, ebenso wie "druckt ein einzelnes Zeichen für wahr und alles andere für falsch".
• Dies ist Codegolf, also gewinnt das kürzeste Programm.
• Standardlücken sind verboten.

Japt v2 , 14 13 Bytes

e/.).\1/_g
¥g

Online testen!

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

Probieren Sie es online!

Perl, 22 Bytes

Enthält +fürp

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

Gibt 1 für wahr, nichts für falsch aus

Gehirn-Flak , 78 Bytes

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

Probieren Sie es online!

Gibt 1 für wahr, nichts für falsch aus.

Um ein bergiges Wort zu verifizieren, reicht es aus, anzunehmen, dass das Wort, wann immer möglich, den Berg hinuntergeht.

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'

Probieren Sie es online!

Danke an ovs für 6 Bytes.

Prolog (SWI) , 29 Bytes

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

Probieren Sie es online!

Dieses Programm definiert eine DCG-Regel a//0, die mit jeder Zeichenfolge (Liste von Zeichen) übereinstimmt, die eine bergige Zeichenfolge ist.

Erläuterung

Für dieses Programm verwende ich eine etwas andere, aber äquivalente Definition für Gebirgszüge als in der Herausforderung beschrieben: Ein Gebirgszug ist ein Zeichen, cauf das eine Anzahl (möglicherweise Null) von Gebirgszügen folgt, die can den Enden angeheftet sind. In einer knapperen, von Regex abgeleiteten Notation muss eine Gebirgszeichenfolge mit dem Muster übereinstimmen, c(Mc)*in dem Msich eine Gebirgszeichenfolge befindet. Dies *bedeutet, dass der Ausdruck in Klammern null oder mehrmals wiederholt wird. Beachten Sie, dass jedes cZeichen dasselbe Zeichen sein muss, Maber nicht dieselbe Gebirgszeichenfolge.

Äquivalenznachweis

Es ist klar, dass die Regeln 1 und 2 aus der Herausforderung meiner Regel entsprechen, in Mcder sie null bzw. einmal vorkommen.

In dem Fall, dass die Gebirgszeichenfolge Mcvorkommende nZeiten hat, in denen n > 1die Zeichenfolge dann umgeschrieben werden kann, wie cMcScin Sden letzten n - 1Zeiten, Mcdie ausschließlich der letzten auftreten c(beachten Sie, dass Mes sich um eine beliebige Gebirgszeichenfolge handelt, die nicht unbedingt dieselbe wie die andere ist M). Da Mes sich um eine Bergkette handelt, cMcmuss es sich nach Regel 2 um eine Bergkette handeln. Entweder Sist ein bergiger String , in dem Fall cScein bergiger String oder Skann wie folgt umgeschrieben werden , cMcTcwo Tsind die letztere n - 2Zeiten , die Mcdie letzte treten ohne c. Diese Argumentation kann so lange angewendet werden, bis eine Saite enthält, die nicht unbedingt bergig istMceinmal, was bedeuten würde, dass es auch bergig sein müsste. Da cMcalso bergig ist und wenn cMcund cM'cbergig sind, dann cMcM'cmuss der ganze Faden bergig sein.

Für die Umkehrung ist für eine Zeichenfolge, cScTcin der cScund cTcbergig sind, cScnach Regel 2 oder nach Regel 3 entweder eine bergige Zeichenfolge. Wenn es sich nach Regel 2 Sum eine bergige Zeichenfolge handelt, muss es sich auch um eine bergige Zeichenfolge handeln. Wenn es eine bergige Zeichenfolge von Regel 3 dann cScvon der Form sein muss , cUcVcwo cUcund cVcBerg Strings ist. Da das längere von cUcund cVcmindestens zwei Zeichen kürzer sein muss als cScund Regel 3 mindestens 5 Zeichen erfordert, muss nach einer endlichen Anzahl von Anwendungen von Regel 3 jede Zeichenfolge zwischen den cdurch Anwendungen von Regel 3 ausgewählten Zeichenfolgen ein Berg sein Zeichenfolge. Die gleiche Argumentation kann angewendet werdencTc daher ist die Saite meiner Definition nach bergig.

Da jede Zeichenfolge, die meiner Definition entspricht, bergig ist und meine Definition allen bergigen Zeichenfolgen entspricht, entspricht sie der in der Frage angegebenen.

Erklärung des Codes

Insgesamt entspricht die a//0in der ersten Zeile definierte DCG-Regel einer beliebigen Gebirgszeichenfolge. Die in Zeile 2 definierte +//1DCG-Regel (wie Prädikate, DCG-Regeln können mit Operatornamen versehen werden ) stimmt mit jeder Zeichenfolge überein, die aus einer Folge von null oder mehr bergigen Zeichenfolgen besteht, wobei das Zeichen als Argument Xan deren Enden angefügt wird . Oder zu leihen , um die regex-artige Notation ich oben verwendet, a//0Streichhölzer c(Mc)*aber auslagert die Aufgabe tatsächlich passend die (Mc)*zu +//1dem nimmt cals Argument X.

Zeile für Zeile verhalten sich die Codes wie folgt:

a-->[X],+X.

Diese Zeile definiert die DCG-Regel a. Der [X]Status, dass das erste Zeichen gleich der aktuell undefinierten Variablen sein muss X. Dies führt Xdazu, dass der erste Buchstabe gleichgesetzt wird. Das +Xthen gibt an, dass der Rest der Zeichenfolge mit der DCG-Regel +//1mit dem Zeichen übereinstimmen muss, das Xals Argument festgelegt ist.

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

Diese Zeile definiert die +//1DCG-Regel. Das ;stellt ein oder in Prolog dar, was bedeutet, dass die Zeichenfolge entweder mit []oder übereinstimmen kann a,[X],+X. Das []stellt die leere Zeichenfolge dar und kann daher +//1immer mit der leeren Zeichenfolge übereinstimmen. Wenn die Zeichenfolge nicht leer ist, muss der Anfang der Zeichenfolge übereinstimmen a//0und eine bergige Zeichenfolge sein. Darauf muss dann das Zeichen folgen, auf das eingestellt Xist. Schließlich muss der Rest der Zeichenfolge übereinstimmen +X.

Husk , 15 Bytes

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

Probieren Sie es online! Die Eingabe dauert ungefähr 40 Sekunden. Seien Sie also geduldig.

Erläuterung

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

Die Idee ist, wiederholt eine Teil Form zu ersetzen abamit abis dies nicht mehr möglich. Die Eingabe ist genau dann bergig, wenn dies zu einer Zeichenfolge mit nur einem Zeichen führt (was εtestet). Die einzige gefährliche Situation ist, wenn wir eine Saite wie diese haben, in der abaes keinen Peak zu geben scheint:

a
 b
  a
   c
  a
   d
  a
 b
a

Glücklicherweise können wir es immer in eines umwandeln:

a
 b
a
 c
a
 d
a
 b
a

Retina 0.8.2 , 15 Bytes

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

Probieren Sie es online! Triviale Portierung der Japt-Antwort von @ETHproductions.

JavaScript (Node.js) , 53 Byte

Ich nehme an, dies ist fast die einfachste Methode, dies zu tun.

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

Probieren Sie es online!

JavaScript (Node.js) , 72 Byte

Weniger trivial, aber viel länger.

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

Probieren Sie es online!