Wyzwanie

W przypadku tego wyzwania górzysty sznurek jest zgodny z regułą gramatyczną, w M: x(Mx)*której przy każdej produkcji wszystkie x mają ten sam charakter. Po wcięciu górski ciąg może wyglądać mniej więcej tak:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

Jak widać, z boku wygląda trochę jak góra.

Definicja formalna

• Każda pojedyncza postać ajest górzysta.
• Jeśli Sjest górzystym ciągiem i ajest postacią, to aSajest górzysty, gdzie zestawienie reprezentuje konkatenację struny.
• Jeśli aSai aTasą strunami górzystymi, to aSaTajest to struna górzysta. Zauważ, że ta reguła oznacza, że ​​ten wzór obowiązuje dla dowolnej liczby powtórzeń. (czyli aSaTaUa, aSaTaUaVa, aSaTaUaVaWa... są górzyste).

Przykłady

Wszystkie palindromy o nieparzystej długości są górzyste, na przykład:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq jest mniej trywialnym przykładem:

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

Przykładowe wyniki

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

Zasady

• Jest to problem decyzyjny, więc każda reprezentacja prawdy lub fałszu jest prawidłowym wyjściem, o ile jest poprawna, spójna, jednoznaczna, a program kończy się w określonym czasie. Pamiętaj, aby podać konwencję wyjściową ze swoim rozwiązaniem.
  • Ustalenie, czy dane wyjściowe wskazują prawda, czy fałsz, nie musi być trywialne, bez konieczności znajomości łańcucha wejściowego. Zauważ, że nie oznacza to, że dane wyjściowe zgodne z prawdą lub fałszem muszą być stałe, jednak konwencja „drukuj górzysty sznurek, jeśli sznur jest górzysty, a nie-górzysty sznur, jeśli nie jest górzysty”, jest z oczywistych powodów zabroniona.
  • Z drugiej strony, konwencja typu „zgłasza wyjątek dla fałszu i kończy cicho dla prawdy”, a także „drukuje pojedynczy znak dla prawdy, a wszystko inne dla fałszu”
• To jest golf golfowy, więc wygrywa najkrótszy program.
• Standardowe luki są zabronione.

Japt v2 , 14 13 bajtów

e/.).\1/_g
¥g

Przetestuj online!

Czysty , 94 89 87 80 bajtów

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

Wypróbuj online!

Perl, 22 bajty

Obejmuje +dlap

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

Drukuje 1 za prawdę, nic za fałsz

Brain-Flak , 78 bajtów

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

Wypróbuj online!

Drukuje 1 dla prawdy, nic dla fałszu.

Aby zweryfikować słowo górzyste, wystarczy założyć, że słowo „schodzi” z góry, gdy tylko jest to możliwe.

Python 2 , 89 83 bajtów

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

Wypróbuj online!

Dzięki ovs za 6 bajtów.

Prolog (SWI) , 29 bajtów

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

Wypróbuj online!

Ten program definiuje regułę DCG, a//0która pasuje do dowolnego łańcucha (listy znaków), który jest łańcuchem górzystym.

Wyjaśnienie

W tym programie używam nieco innej, ale równoważnej definicji łańcuchów górskich niż ta opisana w wyzwaniu: Górzysty łańcuch znaków jest postacią, cpo której następuje liczba (może być zero) łańcuchów górskich cprzyczepiona do ich końców. W bardziej zwięzłej notacji pochodnej wyrażenia regularnego, łańcuch górski musi pasować do wzoru, w c(Mc)*którym Młańcuch górski, i *oznacza, że ​​wyrażenie w nawiasach jest powtarzane zero lub więcej razy. Zauważ, że chociaż każdy cmusi być tego samego znaku, Mnie musi to być ten sam górzysty sznurek.

Dowód równoważności

Oczywiste jest, że reguły 1 i 2 z wyzwania są równoważne z moją zasadą, w której Mcwystępuje odpowiednio zero i jeden raz.

W przypadku, gdy górzysty sznurek Mcwystępował w nczasach, w których n > 1sznurek można przepisać, tak jak cMcScgdzie Ssą te ostatnie n - 1czasy, z Mcwyjątkiem ostatniego c(należy pamiętać, że Mjest to dowolny sznurek górzysty i niekoniecznie taki sam jak inny M). Ponieważ Mjest to górzysty sznur, zgodnie z regułą 2, cMcmusi być górzystym sznurkiem. Albo Sjest to górzysty sznurek, w którym cScto przypadku jest to górzysty sznurek, albo Smożna go przepisać, tak jak cMcTctam, gdzie Twystępują te ostatnie n - 2czasy, z Mcwyłączeniem ostatniego c. Ta linia rozumowania może być stosowana, dopóki sznurek nie ma gwarancji, że zawiera górzysteMckiedyś, co oznaczałoby, że musiałoby to być również górzyste. Skoro więc cMcjest górzysty, a jeśli cMci cM'cgórzysty, to cMcM'cmusi być górzysty, cały sznurek musi być górzysty.

Z drugiej strony, dla sznurka, w cScTcktórym cSci cTcsą górzyste, to albo cScjest sznurkiem górzystym zgodnie z regułą 2, albo regułą 3. Jeśli jest sznurkiem górzystym zgodnie z regułą 2, Smusi być również sznurkiem górzystym. Jeśli jest to górzysty sznurek zgodnie z regułą 3, cScmusi on mieć formę cUcVcgdzie cUci cVcsą sznurkami górzystymi. Ponieważ dłuższy cUci cVcmusi być co najmniej o dwa znaki krótszy niż, cSca reguła 3 wymaga zastosowania co najmniej 5 znaków, to po skończonej liczbie zastosowań reguły 3 każdy ciąg znaków między literami cwybranymi przez zastosowanie reguły 3 musi być górzysty strunowy. Można zastosować tę samą linię rozumowaniacTc dlatego według mojej definicji sznurek jest górzysty.

Ponieważ dowolny ciąg pasujący do mojej definicji jest górzysty, a moja definicja pasuje do wszystkich łańcuchów górskich, jest on równoważny z podanym w pytaniu.

Objaśnienie kodu

Ogólnie a//0reguła DCG, zdefiniowana w pierwszym wierszu, pasuje do każdego górzystego łańcucha. +//1Reguła DCG (jak orzeczników, zasady DCG można nadać nazwy operatora ), określone na drugiej linii, pasuje dowolny ciąg znaków, który składa się z sekwencji zero lub więcej górskich ciągów z charakterem przekazywane jako argumenty Xdołączona na końcach nich . Lub pożyczyć notację regularną, której użyłem powyżej, a//0dopasowuje, c(Mc)*ale zleca zadanie dopasowania (Mc)*do tego, +//1co przyjmuje cza swój argument X.

Kody po linii kody zachowują się w następujący sposób:

a-->[X],+X.

Ta linia określa regułę DCG a. Stwierdza [X], że pierwszy znak musi być równy aktualnie niezdefiniowanej zmiennej X. Powoduje to, Xże jest ustawiony jako pierwszy znak. +XNastępnie stwierdza, że reszta łańcucha musi zgadzać się z reguły DCG +//1ze znaku, który Xjest ustawiony jako argument.

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

Ta linia określa +//1regułę DCG. ;Oznacza grupę lub w Prologu co oznacza, że łańcuch może pasujących albo []albo a,[X],+X. []Reprezentuje ciąg pusty, więc +//1zawsze jest w stanie dopasowania pusty łańcuch. Jeśli struna nie jest pusta, początek musi się zgadzać, a//0a więc musi być struną górską. Następnie musi następować dowolna Xustawiona postać . Wreszcie reszta ciągu musi się zgadzać +X.

Łuska , 15 bajtów

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

Wypróbuj online! Wnioskowanie typu zajmuje około 40 sekund, więc bądź cierpliwy.

Wyjaśnienie

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

Chodzi o to, aby wielokrotnie zastąpić podciąg formularza abaze adopóki nie jest to już możliwe. Dane wejściowe są górzyste wtedy i tylko wtedy, gdy skutkuje to ciągiem jednego znaku (co εtestuje). Jedyną niebezpieczną sytuacją jest sytuacja, gdy mamy taki ciąg znaków, abaktóry nie wydaje się szczytem:

a
 b
  a
   c
  a
   d
  a
 b
a

Na szczęście zawsze możemy go przekształcić w jedno:

a
 b
a
 c
a
 d
a
 b
a

Retina 0.8.2 , 15 bajtów

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

Wypróbuj online! Trywialny port odpowiedzi JET @ETHproductions.

JavaScript (Node.js) , 53 bajty

Przypuszczam, że jest to prawie najprostsza metoda, aby to zrobić?

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

Wypróbuj online!

JavaScript (Node.js) , 72 bajty

Mniej banalny, ale o wiele dłuższy.

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

Wypróbuj online!