Czy to górzyste?

29

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.
code-golf string decision-problem Wołowina
źródło
4
Przypadek testowy taki aaabyłby dobry, w którym ta sama postać musi być używana na wielu poziomach.
Martin Ender
Jesteś tego pewien wasitacaroraratisaw? Wydaje mi się, że jest górą
Ton Hospel
wasitacaroraratisawjest rzeczywiście górzysty AFAICT
ETHproductions
Tak jest. Chyba właśnie próbowałem znaleźć „prawie palindrom”, ale przez przypadek znalazłem górzystą strunę.
Beefster
2
Pomyślałem, że to będzie łatwe do rozwiązania, dzieląc ciąg na pierwszy znak, ale przypadki takie aaasprawiają, że to nie działa.
xnor

Odpowiedzi:

7

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!

Obrzydliwe
źródło
6

Perl, 22 bajty

Obejmuje +dlap

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

Drukuje 1 za prawdę, nic za fałsz

Ton Hospel
źródło
5

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.

Nitrodon
źródło
3

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.

Chas Brown
źródło
3

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.

0 '
źródło
2

Ł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
Zgarb
źródło
Uważam, że zwrócenie pojedynczego znaku w trueprzypadku i nie w innym przypadku byłoby „spójne”.
Jonathan Allan
W rzeczywistości może to popychać, ponieważ nie ma wyraźnej linii między tym a brakiem operacji („zwraca górzysty sznur, gdy jest górzysty i nie inaczej”), co z pewnością byłoby luką.
Jonathan Allan
@JonathanAllan Pojedyncze znaki w porównaniu z innymi ciągami również wydają mi się zbyt rozmyte, zwłaszcza, że ​​mają niewielki związek z prawdą (tylko pusty ciąg jest fałszem w Husk).
Zgarb
Tak, „jakakolwiek reprezentacja” jest zdecydowanie zbyt liberalna - skomentowałem PO ”:)
Jonathan Allan
Naprawdę chcę, aby definicja była liberalna, ponieważ pozwala na bardziej kreatywne rozwiązania. Zmieniłem sformułowanie z „spójny” na „jednoznaczny”, choć mogę też dodać, że powinien być jednoznaczny bez kontekstu. Jak w przypadku, powinno być jasne, nie wiedząc, jaki ciąg wejściowy był, czy wynik jest prawdziwy, czy fałszywy. Tak więc pojedynczy znak dla prawdy i nic dla fałszu nie byłoby w porządku.
Beefster