Is It Mountainous?

Question

Challenge

For this challenge, a mountainous string is one that conforms to the grammar rule M: x(Mx)* where at each production, the all x's are the same character. When indented, a mountainous string might look something like this:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

As you can see, it looks a bit like a mountain from the side.

Formal Definition

• Any single character a is mountainous.
• If S is a mountainous string and a is a character, then aSa is mountainous, where juxtaposition represents string concatenation.
• If aSa and aTa are mountainous strings, then aSaTa is a mountainous string. Note that this rule implies that this pattern holds for any number of repetitions. (i.e. aSaTaUa, aSaTaUaVa, aSaTaUaVaWa... are all mountainous.)

Examples

All odd-length palindromes are mountainous, for instance:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq is a less trivial example:

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

Example Outputs

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

Rules

• This is a decision problem, so any representation of true or false is valid output as long as it is correct, consistent, unambiguous, and the program terminates in a finite amount of time. Be sure to state your output convention with your solution.
  • It should be trivial to determine whether the output indicates true or false without having to know what the input string is. Note that this does not mean the truthy or falsy outputs have to be constant, however the convention of "print a mountainous string if the string is mountainous and a non-mountainous string if not mountainous" is a banned loophole for obvious reasons.
  • On the other hand, a convention like "throws an exception for false and exits silently for true" would be fine, as well as "prints a single character for true and anything else for false"
• This is code golf, so the shortest program wins.
• Standard loopholes are banned.

Answer 1

Japt v2, 14 13 bytes

e/.).\1/_g
¥g

Test it online!

Answer 2

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

Try it online!

Answer 3

Perl, 22 bytes

Includes + for p

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

Prints 1 for true, nothing for false

Answer 4

Brain-Flak, 78 bytes

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

Try it online!

Prints 1 for true, nothing for false.

To verify a mountainous word, it is sufficient to assume the word goes "down" the mountain whenever possible.

Answer 5

Prolog (SWI), 29 bytes

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

Try it online!

This program defines a DCG rule a//0 that matches any string (list of characters) that is a mountainous string.

Explanation

For this program I use a slightly different but equivalent definition for mountainous strings than what is described in the challenge: A mountainous string is a character c followed by a number (could be zero) of mountainous strings with c tacked onto the ends of them. In a more terse regex derived notation, a mountainous string must match the pattern c(Mc)* where M is a mountainous string and * means that the expression in parentheses is repeated zero or more times. Note that while each c must be the same character, each M does not need to be the same mountainous string.

Proof of Equivalence

It is clear that rules 1 and 2 from the challenge are equivalent to my rule where Mc occurs zero and one times respectively.

In the case that the mountainous string has Mc occurring n times where n > 1 then the string can be rewritten as cMcSc where S is the latter n - 1 times that Mc occurs excluding the last c (note that M is any mountainous string and not necessarily the same as other M). Since M is a mountainous string, by rule 2, cMc must be a mountainous string. Either S is a mountainous string in which case cSc is a mountainous string or S can be rewritten as cMcTc where T is the latter n - 2 times that Mc occurs excluding the last c. This line of reasoning can keep on being applied until string not guaranteed to be mountainous contains Mc once which would mean it would have to be mountainous as well. Thus since cMc is mountainous and if cMc and cM'c are mountainous then cMcM'c must be mountainous the whole string must be mountainous.

For the converse, for a string cScTc where cSc and cTc are mountainous then either cSc is a mountainous string by rule 2 or by rule 3. If it is a mountainous string by rule 2 then S must also be a mountainous string. If it is a mountainous string by rule 3 then cSc must be of the form cUcVc where cUc and cVc are mountainous strings. Since the longer of cUc and cVc must still be at least two characters shorter than cSc and rule 3 requires at least 5 character to be applied then after a finite number of applications of rule 3 each string between the cs selected by applications of rule 3 must be a mountainous string. The same line of reasoning can be applied to cTc thus the string is mountainous by my definition.

Since any string that matches my definition is mountainous and my definition matches all mountainous strings, it is equivalent to the one given in the question.

Explanation of Code

Overall the a//0 DCG rule, defined on the first line, matches any mountainous string. The +//1 DCG rule (like predicates, DCG rules can be give operator names), defined on line two, matches any string that is made up of a sequence of zero or more mountainous strings with the character passed as its arguments X tacked onto the ends of them. Or to borrow the regex-like notation I used above, a//0 matches c(Mc)* but outsources the job of actually matching the (Mc)* to +//1 which takes c as its argument X.

Line by line the codes behaves as follows:

a-->[X],+X.

This line defines the DCG rule a. The [X] states that the first character must be equal to the currently undefined variable X. This results in X being set equal to the first character. The +X then states that the rest of the string must match the DCG rule +//1 with the character that X is set to as its argument.

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

This line defines the +//1 DCG rule. The ; represents an or in Prolog which means that the string can match either [] or a,[X],+X. The [] represents the empty string so +//1 is always capable of matching the empty string. If the string is not empty then the start of it must match a//0 and so must be a mountainous string. This must then be followed by whatever character X is set to. Finally the rest of the string must match +X.

Answer 6

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'

Try it online!

Thanks to ovs for 6 bytes.

Answer 7

Husk, 15 bytes

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

Try it online! Type inference takes about 40 seconds, so be patient.

Explanation

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

The idea is to repeatedly replace a substring of the form aba with a until this is no longer possible. The input is mountainous if and only if this results in a single-character string (which is what ε tests). The only dangerous situation is when we have a string like this, where aba doesn't seem to be a peak:

a
 b
  a
   c
  a
   d
  a
 b
a

Fortunately, we can always transform it into one:

a
 b
a
 c
a
 d
a
 b
a

Answer 8

Retina 0.8.2, 15 bytes

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

Try it online! Trivial port of @ETHproductions' Japt answer.

Answer 9

JavaScript (Node.js), 53 bytes

I suppose this is nearly the most straightforward method to do so?

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

Try it online!

JavaScript (Node.js), 72 bytes

Less trivial one, but much longer.

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

Try it online!