Apakah Bergunung-gunung?

29

Tantangan

Untuk tantangan ini, string pegunungan adalah yang sesuai dengan aturan tata bahasa M: x(Mx)*di mana pada setiap produksi, semua x adalah karakter yang sama. Saat menjorok, string pegunungan mungkin terlihat seperti ini:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

Seperti yang Anda lihat, itu terlihat seperti gunung dari samping.

Definisi Resmi

  • Setiap karakter tunggal aadalah pegunungan.
  • Jika Sadalah string pegunungan dan akarakter, maka aSaadalah pegunungan, di mana penjajaran mewakili penggabungan string.
  • Jika aSadan aTaadalah string pegunungan, maka aSaTaadalah string pegunungan. Perhatikan bahwa aturan ini menyiratkan bahwa pola ini berlaku untuk sejumlah pengulangan. (yaitu aSaTaUa, aSaTaUaVa, aSaTaUaVaWa... semua pegunungan.)

Contohnya

Semua palindrom panjang aneh bergunung-gunung, misalnya:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq adalah contoh yang kurang sepele:

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

Contoh Keluaran

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

Aturan

  • Ini adalah masalah keputusan, sehingga setiap representasi benar atau salah adalah output yang valid selama itu benar, konsisten, tidak ambigu, dan program berakhir dalam jumlah waktu yang terbatas. Pastikan untuk menyatakan konvensi keluaran Anda dengan solusi Anda.
    • Itu harus sepele untuk menentukan apakah output menunjukkan benar atau salah tanpa harus tahu apa string input. Perhatikan bahwa ini tidak berarti output yang benar atau salah harus konstan, namun konvensi "cetak string pegunungan jika string adalah pegunungan dan string non-pegunungan jika tidak pegunungan" adalah celah yang dilarang karena alasan yang jelas.
    • Di sisi lain, konvensi seperti "melempar pengecualian untuk false dan keluar secara diam-diam untuk true" akan baik-baik saja, serta "mencetak satu karakter untuk true dan yang lainnya untuk false"
  • Ini kode golf, jadi program tersingkat menang.
  • Celah standar dilarang.
code-golf string decision-problem Beefster
sumber
4
Kasing seperti aaaakan bagus, di mana karakter yang sama perlu digunakan pada beberapa tingkatan.
Martin Ender
Anda yakin tentang itu wasitacaroraratisaw? Bagi saya gunung itu bagaikan gunung berapi
Ton Hospel
wasitacaroraratisawmemang pegunungan AFAICT
ETHproduksi
Begitulah. Saya kira saya hanya mencoba menemukan 'hampir palindrom', tetapi saya menemukan string pegunungan secara tidak sengaja.
Beefster
2
Saya pikir ini akan mudah untuk dipecahkan dengan memisahkan string pada karakter pertamanya, tetapi case seperti aaamembuatnya tidak berfungsi.
xnor

Jawaban:

7

Bersih , 94 89 87 80 byte

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

Cobalah online!

Suram
sumber
6

Perl, 22 byte

Termasuk +untukp

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

Mencetak 1 untuk benar, tidak ada untuk salah

Ton Hospel
sumber
5

Brain-Flak , 78 byte

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

Cobalah online!

Mencetak 1 untuk benar, tidak ada untuk salah.

Untuk memverifikasi kata pegunungan, cukup untuk mengasumsikan kata "turun" gunung bila memungkinkan.

Nitrodon
sumber
3

Python 2 , 89 83 byte

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

Cobalah online!

Berkat ovs untuk 6 byte.

Chas Brown
sumber
3

Prolog (SWI) , 29 byte

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

Cobalah online!

Program ini mendefinisikan aturan DCG a//0 yang cocok dengan string apa pun (daftar karakter) yang merupakan string pegunungan.

Penjelasan

Untuk program ini saya menggunakan definisi yang sedikit berbeda tetapi setara untuk string pegunungan daripada apa yang dijelaskan dalam tantangan: String pegunungan adalah karakter cdiikuti oleh sejumlah (mungkin nol) string gunung dengan cditempelkan ke ujungnya. Dalam notasi turunan regex yang lebih singkat, string pegunungan harus cocok dengan pola di c(Mc)*mana Mstring pegunungan dan *berarti bahwa ekspresi dalam tanda kurung diulangi nol atau lebih kali. Perhatikan bahwa sementara masing c- masing harus karakter yang sama, masing-masingM - tidak perlu menjadi string pegunungan yang sama.

Bukti Kesetaraan

Jelas bahwa aturan 1 dan 2 dari tantangan setara dengan aturan saya di mana Mc terjadi nol dan satu kali masing-masing.

Dalam kasus bahwa string pegunungan telah Mcterjadi di nmana n > 1kemudian string dapat ditulis ulang sebagai di cMcScmana Sadalah saat- n - 1saat terakhir yang Mcterjadi tidak termasuk yang terakhir c(perhatikan bahwa Mada string pegunungan dan tidak harus sama dengan yang lain M). Karena Mstring pegunungan, menurut aturan 2, cMcharus menjadi string pegunungan. Entah itu Sadalah string pegunungan di mana case cScadalah string pegunungan atau Sdapat ditulis ulang sebagai di cMcTcmana Tadalah zaman terakhir n - 2bahwa dulu yang berarti itu harus pegunungan juga. Karena itu pegunungan dan jika danMc terjadi tidak termasuk yang terakhir c. Alur penalaran ini dapat terus diterapkan hingga string yang tidak dijamin mengandung gunungMccMccMccM'c bergunung-gunung cMcM'c harus pegunungan seluruh string harus pegunungan.

Untuk kebalikannya, untuk string di cScTcmana cScdan cTcbergunung-gunung maka baik itu cScadalah string pegunungan oleh aturan 2 atau dengan aturan 3. Jika itu adalah string pegunungan oleh aturan 2 maka Sjuga harus menjadi string pegunungan. Jika itu adalah string pegunungan oleh aturan 3 maka cScharus dari bentuk di cUcVcmana cUcdan cVcadalah string pegunungan. Karena semakin lama cUcdan cVcmasih harus setidaknya dua karakter lebih pendek dari cScdan aturan 3 membutuhkan setidaknya 5 karakter untuk diterapkan maka setelah sejumlah aplikasi aturan 3 setiap string antara sehingga string adalah pegunungan menurut definisi saya.c dipilih oleh aplikasi aturan 3 harus menjadi pegunungan tali. Garis penalaran yang sama dapat diterapkancTc

Karena setiap string yang cocok dengan definisi saya adalah pegunungan dan definisi saya cocok dengan semua string pegunungan, itu sama dengan yang diberikan dalam pertanyaan.

Penjelasan Kode

Secara keseluruhan a//0aturan DCG, didefinisikan pada baris pertama, cocok dengan string pegunungan apa pun. The +//1DCG aturan (seperti predikat, aturan DCG dapat memberikan nama Operator ), didefinisikan pada baris kedua, cocok dengan string yang terdiri dari urutan nol atau lebih pegunungan string dengan karakter lulus sebagai argumen Xditempelkan ke ujung mereka . Atau untuk meminjam notasi seperti regex yang saya gunakan di atas, a//0cocok c(Mc)*tetapi mengalihdayakan pekerjaan yang benar-benar cocok (Mc)*dengan +//1yang diambil csebagai argumennya X.

Baris demi baris kode berperilaku sebagai berikut:

a-->[X],+X.

Baris ini mendefinisikan aturan DCG a. The [X]menyatakan bahwa karakter pertama harus sama dengan variabel saat ini tidak terdefinisi X. Ini menghasilkan Xdiset sama dengan karakter pertama. The +Xkemudian menyatakan bahwa sisa string harus sesuai dengan aturan DCG +//1dengan karakter yang Xdiatur sebagai argumen.

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

Baris ini mendefinisikan +//1aturan DCG. The ;mewakili atau di Prolog yang berarti bahwa string dapat mencocokkan baik []atau a,[X],+X. The []mewakili string kosong sehingga +//1selalu mampu cocok dengan string kosong. Jika senarnya tidak kosong, maka permulaannya harus cocok a//0dan karenanya harus berupa tali pegunungan. Ini kemudian harus diikuti oleh karakter apa pun Xyang diatur. Akhirnya sisa string harus cocok +X.

0 '
sumber
2

Sekam , 15 byte

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

Cobalah online! Ketik inferensi membutuhkan waktu sekitar 40 detik, jadi bersabarlah.

Penjelasan

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

Idenya adalah untuk berulang kali mengganti substring formulir abadengan asampai ini tidak mungkin lagi. Input bergunung-gunung jika dan hanya jika ini menghasilkan string karakter tunggal (yang merupakan εtes apa ). Satu-satunya situasi berbahaya adalah ketika kita memiliki string seperti ini, di mana abasepertinya tidak menjadi puncak:

a
 b
  a
   c
  a
   d
  a
 b
a

Untungnya, kita selalu bisa mengubahnya menjadi satu:

a
 b
a
 c
a
 d
a
 b
a
Zgarb
sumber
Saya percaya mengembalikan satu karakter untuk truekasus dan bukan sebaliknya akan "konsisten".
Jonathan Allan
Sebenarnya itu mungkin mendorongnya, karena tidak ada garis yang jelas antara itu dan no-op ("mengembalikan string pegunungan ketika pegunungan dan bukan sebaliknya") yang jelas akan menjadi celah.
Jonathan Allan
@JonathanAllan Karakter tunggal vs string lain tampaknya agak terlalu kabur bagi saya juga, terutama karena memiliki sedikit hubungan dengan kebenaran (hanya string kosong yang salah dalam Husk).
Zgarb
Yap "representasi apa pun" jelas terlalu liberal - Saya telah berkomentar di bawah OP :)
Jonathan Allan
Saya sebenarnya ingin definisi tersebut menjadi liberal karena memungkinkan solusi yang lebih kreatif. Saya mengubah kata-kata dari 'konsisten' menjadi 'tidak ambigu', meskipun saya mungkin juga menambahkan bahwa itu harus tidak ambigu tanpa konteks. Seperti pada, harus jelas tanpa mengetahui string input apakah hasilnya benar atau salah. Jadi satu karakter untuk benar dan tidak ada yang salah akan baik-baik saja.
Beefster