29
2
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 anda
is a character, thenaSa
is mountainous, where juxtaposition represents string concatenation. - If
aSa
andaTa
are mountainous strings, thenaSaTa
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.
4A test case like
aaa
would be good, where the same character needs to be used on multiple levels. – Martin Ender – 2018-02-03T23:13:29.787Are you sure about
wasitacaroraratisaw
? It seems mountanous to me – Ton Hospel – 2018-02-03T23:50:52.747wasitacaroraratisaw
is indeed mountainous AFAICT – ETHproductions – 2018-02-04T00:14:34.397So it is. I guess I was just trying to find an 'almost palindrome', but I found a mountainous string by accident. – Beefster – 2018-02-04T00:29:07.047
2I thought this would be easy to solve by splitting the string on its first character, but cases like
aaa
make that not work. – xnor – 2018-02-04T01:03:24.427You can solve it with a recursive descent parser. I believe a parser generator would also work. – Beefster – 2018-02-04T04:35:43.900
Can we assume the input only contains lowercase ASCII characters? – Zgarb – 2018-02-04T12:00:24.167
I think something like
abcdedfghgedcba
should be in the falsey test cases (the seconde
would match the height of a precedinge
during construction, but there is built mountain in the way, while if the seconde
were anf
instead the string would be mountainous - or indeed if thef
were ane
). – Jonathan Allan – 2018-02-04T14:19:47.797"any representation of true or false is valid output as long as it is correct, consistent, and the program terminates in a finite amount of time." actually does not clearly define a line before a no-op ("returns a mountainous string when mountainous and not otherwise") which would clearly be a loophole. (note that "consistent" does not imply anything about being constant). I'd recommend requiring at least one of the two output sets to be singular as well as the outputs being consistent. (this is why using "truthy vs falsey" is easiest).
– Jonathan Allan – 2018-02-04T16:48:25.127@Zgarb no. Even though I only use lowercase examples, it should work with all 8-bit strings. A lot of languages will handle unicode just fine, but I would rather hit the least common denominator. Whether it works or not for unicode does not matter. – Beefster – 2018-02-05T05:01:41.573
@JonathanAllan "print the string for true and nothing for false" is fine. I see no reason for it to have to be constant. For instance, you could make it so the program throws an exception for true and does nothing for false. Or you could use return codes where 0 is true and nonzero is false. Or you can send out real missile alerts for true and test alerts for false. Whatever convention you want to use is fine as long as it's unambiguous. – Beefster – 2018-02-05T05:08:17.043
Sure but my point was that at least one of the two outpurs should be required be fixed across runs, "print the string if true and nothing if false" fits that but "prints a mountainous string if true and not otherwise" does not and the latter allows a noop. – Jonathan Allan – 2018-02-05T06:49:02.993
'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.' As long as your convention isn't a copout in that same vein, it's allowed. – Beefster – 2018-02-05T17:32:20.953