Вызов

Для этой задачи гористая строка - это строка, которая соответствует правилу грамматики, M: x(Mx)*где в каждом произведении все x имеют одинаковый символ. При отступе горная строка может выглядеть примерно так:

A
 B
  C
   D
  C
   E
    F
   E
  C
 B
A

Как вы можете видеть, это выглядит как гора со стороны.

Формальное определение

Любой персонаж a- гористый.
Если Sэто горная строка и aсимвол, то aSaона гористая, где сопоставление представляет собой конкатенацию строк.
Если aSaи aTaесть горные нити, то aSaTaэто гористая нить. Обратите внимание, что это правило подразумевает, что этот шаблон выполняется для любого количества повторений. (то есть aSaTaUa, aSaTaUaVa, aSaTaUaVaWa... все горы.)

Примеры

Все палиндромы нечетной длины горные, например:

t
 a
  c
   o
  c
 a
t

qwertytrasdfdgdsarewqjklkjq это менее тривиальный пример:

Пример выходов

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

правила

Это проблема решения, поэтому любое представление true или false является допустимым выводом, если оно является правильным, непротиворечивым, однозначным и программа завершается за конечное время. Обязательно укажите соглашение о выходе с вашим решением.
- Должно быть тривиально определять, указывает ли выход истину или ложь, не зная, что является входной строкой. Обратите внимание, что это не означает, что истинные или ложные результаты должны быть постоянными, однако соглашение «печатать гористую строку, если строка гористая, и не горная строка, если не гористая», является запрещенной лазейкой по очевидным причинам.
- С другой стороны, соглашение вроде «выдает исключение для ложного и беззвучно завершает работу для истины» было бы хорошо, а также «печатает один символ для истины и все остальное для ложного»
Это код гольф, поэтому выигрывает самая короткая программа.
Стандартные лазейки запрещены.

code-golf string decision-problem Beefster
источник

4

Было aaaбы неплохо создать тестовый пример , где один и тот же символ должен использоваться на нескольких уровнях.

Мартин Эндер

Вы уверены wasitacaroraratisaw? Это кажется мне горным

Тон Хоспел

wasitacaroraratisawдействительно гористый AFAICT

ETHproductions

Так что, это. Думаю, я просто пытался найти «почти палиндром», но случайно нашел гористую нить.

Beefster

2

Я думал, что это будет легко решить, разделив строку по первому символу, но такие случаи, как aaaзаставляют это не работать.

xnor

8

Japt v2 , 14 13 байт

e/.).\1/_g
¥g

Проверьте это онлайн!

ETHproductions
источник

7

Чистый , 94 89 87 80 байт

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

Попробуйте онлайн!

Οurous
источник

6

Perl, 22 байта

Включает +в себя дляp

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

Отпечатки 1 за правду, ничего за ложь

Тон Хоспел
источник

5

Brain-Flak , 78 байт

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

Попробуйте онлайн!

Печатает 1 за правду, ничего за ложь.

Чтобы проверить гористое слово, достаточно предположить, что слово спускается с горы, когда это возможно.

Nitrodon
источник

3

Python 2 , 89 83 байта

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

Попробуйте онлайн!

Спасибо ovs за 6 байтов.

Час Браун
источник

3

Пролог (SWI) , 29 байт

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

Попробуйте онлайн!

Эта программа определяет правило DCG, a//0которое соответствует любой строке (списку символов), которая является горной строкой.

объяснение

Для этой программы я использую немного другое, но эквивалентное определение для горных нитей, чем то, что описано в задании: горная строка - это символ, cза которым следует число (может быть ноль) горных нитей с cприкрепленными на концах. В более кратких обозначениях, полученных из регулярных выражений, горная строка должна соответствовать шаблону, c(Mc)*где Mесть горная строка, и *означает, что выражение в скобках повторяется ноль или более раз. Обратите внимание, что хотя каждый из них cдолжен быть одного и того же символа, каждый Mне обязательно должен быть одной и той же горной строкой.

Доказательство эквивалентности

Ясно, что правила 1 и 2 из соревнования эквивалентны моему правилу, где Mcпроисходит ноль и один раз соответственно.

В случае, когда гористая строка Mcвстречается, nкогда n > 1строка может быть переписана так, как cMcScесли бы Sэто было последнее n - 1время, Mcза исключением последнего c(обратите внимание, что Mэто любая горная строка и не обязательно такая же, как и другие M). Поскольку Mгорная нить, по правилу 2, cMcдолжна быть гористая нить. Либо Sявляется горной строкой, в этом случае cScявляется горной строкой, либо Sее можно переписать так, как cMcTcесли бы Tэто было последнее n - 2время, Mcза исключением последнего c. Эта линия рассуждений может продолжаться до тех пор, пока не будет гарантированно быть горной строкой.Mcоднажды, что означало бы, что это также должно быть гористым. Таким образом, поскольку cMcон гористый, а если cMcи cM'cгористый, то cMcM'cдолжен быть гористым, вся цепочка должна быть горной.

Для обратного, для строки, cScTcгде cScи cTcявляются гористыми, то либо cScявляется горной строкой по правилу 2, либо по правилу 3. Если это горная строка по правилу 2, то Sтакже должна быть горная строка. Если по правилу 3 это гористая нить, то она cScдолжна иметь форму, в cUcVcкоторой cUcи cVcесть гористая нить. Поскольку длиннее cUcи cVcдолжно быть не менее чем на два символа короче, чем для cScправила 3, требуется применение не менее 5 символов, то после конечного числа применений правила 3 каждая строка между cs, выбранными применениями правила 3, должна быть горной строка. Та же самая линия рассуждения может быть применена кcTc таким образом, строка по моему определению гористая.

Поскольку любая строка, которая соответствует моему определению, является горной, а мое определение соответствует всем горным строкам, она эквивалентна той, которая приведена в вопросе.

Объяснение кода

В целом a//0правило DCG, определенное в первой строке, соответствует любой горной строке. +//1Правило DCG (как предикаты, правила DCG могут дать имена операторов ), определенное на вторую линии, соответствует любой строке , которая состоит из последовательности нуля или более гористых строк с характером , переданным в качестве ее аргументов Xпришитых концов их , Или заимствовать-как регулярные выражения обозначения , которые я использовал выше, a//0спички , c(Mc)*но аутсорсинг работы фактически соответствует силе (Mc)*в +//1который принимает в cкачестве аргумента X.

Строки за строкой коды ведут себя следующим образом:

a-->[X],+X.

Эта строка определяет правило DCG a. В [X]гласит , что первый символ должен быть равен в настоящее время неопределенной переменной X. Это приводит к тому, Xчто устанавливается равным первому символу. Затем +Xоператор утверждает, что остальная часть строки должна соответствовать правилу DCG +//1с символом, Xустановленным в качестве аргумента.

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

Эта строка определяет +//1правило DCG. ;Представляет собой или в Прологе , который означает , что строка может соответствовать либо []или a,[X],+X. []Представляет собой пустую строку , так +//1всегда способен согласовать пустую строку. Если строка не пуста, то ее начало должно совпадать, a//0и поэтому она должна быть горной. После этого должен следовать любой установленный символ X. Наконец, остальная часть строки должна совпадать +X.

0 '
источник

2

Шелуха , 15 байт

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

Попробуйте онлайн! Вывод типа занимает около 40 секунд, так что наберитесь терпения.

объяснение

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

Идея заключается в том , чтобы повторно заменить подстроку формы abaс aпока это уже не возможно. Ввод является горным, если и только если это приводит к односимвольной строке (что и εпроверяет). Единственная опасная ситуация - когда у нас есть строка, подобная этой, где aba, кажется, нет пика:

a
 b
  a
   c
  a
   d
  a
 b
a

К счастью, мы всегда можем превратить его в один:

a
 b
a
 c
a
 d
a
 b
a

Zgarb
источник

Я считаю, что возвращение одного символа для trueслучаев и не было бы "последовательным".

Джонатан Аллан

На самом деле это может подтолкнуть его, поскольку нет четкой линии между этим и бездействующим («возвращает гористую нить, когда она гористая, а не иначе»), которая явно была бы лазейкой.

Джонатан Аллан

@JonathanAllan Отдельные символы и другие строки кажутся мне слишком нечеткими, тем более, что они мало связаны с правдивостью (в Husk ложная только пустая строка).

Згарб

Да, «любое представление» явно слишком либерально - я прокомментировал УН :)

Джонатан Аллан

Я на самом деле хочу, чтобы определение было либеральным, потому что оно допускает более креативные решения. Я изменил формулировку с «последовательный» на «однозначный», хотя мог бы также добавить, что он должен быть однозначным без контекста. Например, должно быть ясно, не зная, какой была входная строка, является ли результат истинным или ложным. Так что один символ для истины и ничего для ложного не подойдет.

Beefster

2

Сетчатка 0.8.2 , 15 байт

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

Попробуйте онлайн! Тривиальный порт ответа @ETHproductions 'Japt.

Нил
источник

1

JavaScript (Node.js) , 53 байта

Я полагаю, это почти самый простой способ сделать это?

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

Попробуйте онлайн!

JavaScript (Node.js) , 72 байта

Менее тривиально, но гораздо дольше.

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

Попробуйте онлайн!

Сиеру Асакото
источник

Это гористый?

Вызов

Формальное определение

Примеры

Пример выходов

правила

Ответы:

Japt v2 , 14 13 байт

Чистый , 94 89 87 80 байт

Perl, 22 байта

Brain-Flak , 78 байт

Python 2 , 89 83 байта

Пролог (SWI) , 29 байт

объяснение

Доказательство эквивалентности

Объяснение кода

Шелуха , 15 байт

объяснение

Сетчатка 0.8.2 , 15 байт

JavaScript (Node.js) , 53 байта

JavaScript (Node.js) , 72 байта