Платные строки

28

Строка является платной, если ее можно разбить на подстроки, каждая из которых представляет собой строку, повторяемую дважды подряд. Например, aabaaababbbabaможно изменить как:

aaba aaba
b b
ba ba

Если задана непустая строка a's' и b's', выведите значение Truthy, если оно допустимо, и значение Falsey, если это не так.

спариваемая:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Не платный:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Я призываю вас предлагать решения, не основанные на регулярных выражениях, даже если на вашем языке уже есть более короткий ответ. Вы можете пометить их как "без регулярных выражений". Под регулярным выражением я подразумеваю встроенную подсистему сопоставления с образцом строки.

Leaderboard:

Показать фрагмент кода

code-golf string subsequence XNOR
источник
Можем ли мы использовать что-нибудь кроме ab?
Эрик Outgolfer
Если bbababbb платный, то почему нет baab и aaaaabbaaaaa?
rnso
@ rnso Насколько я понимаю, bbababbb можно разделить на 3 пары: bb, abab и bb, которые объединяются в том порядке, чтобы сформировать исходную строку, тогда как две другие не могут.
Солнечный Пан
На вопрос «каждая из которых (подстрока) является строкой, повторяемой дважды ПОСТОЯННО», и это не устраивает bbababbb. В противном случае baab также можно разделить на baab, а aaaaabbaaaaa на aaaaa bb aaaaa.
rnso
@ rnso Не уверен, что ты имеешь в виду. Под последовательно я имею в виду два повторения рядом друг с другом. В «baa b» два b разделены a, так что это не работает.
xnor

Ответы:

11

Python 2, 68 63 байта

f=lambda s,n=1:s==2*s[:n]or''<s[n:]>-f(s,n+1)<f(s[n:])*f(s[:n])

Возвращает True или False . Проверьте это на Ideone .

Деннис
источник
4
Это действительно чистая рекурсия, использующая индекс как для центра двойного, так и для центра разбиения. Забавно, что правдивость проверяется как нечто меньшее, чем что-либо. Я вижу некоторые улучшения ...
xnor
8

Сетчатка , 11 байт

^((.+)\2)+$

Попробуйте все тестовые случаи. Первые два байта делают его многострочным.

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

FryAmTheEggman
источник
2
Дангит, я ждал 3 недели, чтобы опубликовать это ...
ETHproductions
2
Мартин тоже ждал .
xnor
5
Упс! Я тоже бью его только на 10 секунд ... Ну, я уверен, что если я напишу ответ в Гексагонии, он меня простит!
FryAmTheEggman
5
@FryAmTheEggman Я с нетерпением жду этого. :)
Мартин Эндер
2
То же самое с Perl:perl -pE '$_=/^((.+)\2)+$/'
Дада
8

Желе , 10 байт

ẆŒPẋ€€2F€ċ

Не совсем эффективно ... Попробуйте онлайн!

Как это работает

ẆŒPẋ€€2F€ċ  Main link. Argument: s (string)

Ẇ           Window, generate the array of all substrings of s.
 ŒP         Powerset; generate all subarrays of substrings of s.
   ẋ€€2     Repeat each substring in each subarray twice.
            For example, ["ab", "a", "b"] becomes ["abab", "aa", "bb"].
       F€   Flatten the subarrays by concatenating their strings.
         ċ  Count how many times s appears in the generated strings.
Деннис
источник
Это ... кажется неэффективным. Как долго эти данные могут обрабатываться в разумные сроки?
Джон Дворжак
1
Это крайне неэффективно ( O (2 ^ n ^ 2) , я думаю). Я должен проверить на месте. TIO не хватает памяти для строк длиной 6 .
Деннис
8
Строка длиной 6 занимает 3:20 минут на моей машине и требует 6 ГБ памяти.
Деннис
1
@Dennis Давайте не будем делать ввод длины 100 , потому что все рухнет. Да, даже TIO.
Эрик Outgolfer
@EriktheGolfer Это хорошая идея, поскольку она излишне замедлит работу TIO для других целей, но не приведет к сбою. Как только система исчерпывает память, OOM просто убивает процесс.
Деннис
5

Haskell, 72 69 байтов (без регулярных выражений)

g(a:b:c)|a==b=g c
g x=x==[]
any(g.words.concat).mapM(\c->[[c],c:" "])

Метод грубой силы. Попробуйте это на Ideone .

Спасибо BlackCap за -3 байта.

объяснение

Вспомогательная функция gберет список строк и проверяет, что она состоит из пар идентичных строк, например ["aa","aa","bba","bba","ab","ab"]. Функция (анонимная) main разбивает строку всеми возможными способами и проверяет, что хотя бы одно разбиение приводит к получению списка g.

g(a:b:c)                                  g on list with elements a, b and tail c,
        |a==b                              in the case that a==b,
             =g c                          recurses to the tail c.
g x=                                      g on any other list x
    x==[]                                  checks that x is empty.
                                           This includes the case where a is not equal
                                           to b, resulting in False.
any(g.words.concat).mapM(\c->[[c],c:" "]) The main function:
                    mapM(\c->[[c],c:" "])  Replace each letter c with either "c" or "c "
                                           in all possible ways, return list of results.
any(              ).                       Check that at least one result satisfies this:
            concat                          Concatenate the 1- or 2-letter strings,
      words.                                split again at each space,
    g.                                      apply g.
Zgarb
источник
Вы можете заменить or.mapнаany
BlackCap
@ BlackCap Конечно, спасибо! Я изначально был any g.map(words.concat)и подумал : «Эй, я могу Гольф anyв or» ...
Zgarb
5

Python 2, 60 байт

f=lambda s,t='':''<s>f(s[1:],t+s[0])|f(t and s)*f(t)>-(s==t)

Я надеюсь, что это правильно. Он работает довольно медленно и andне выглядит оптимальным.

xsot
источник
1
Я пытался использовать строки, но я не мог приблизиться к своему показателю на основе индекса. Это один умный у andвас там.
Денис
Congrats! Повторение в разделе было уловкой, которую я имел в виду.
xnor
4

Желе , 12 байт

ŒṖµœs€2ZEµ€S

На два байта длиннее моего другого ответа , но этот подход намного более эффективен и обрабатывает все тесты, кроме одного.

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

Как это работает

ŒṖµœs€2ZEµ€S  Main link. Argument: s (string)

ŒṖ            Generate all partitions of s.
  µ      µ€   Map the monadic chain between the µ's over the partitions.
   œs€2         Split each string in the partition into two chunks of equal length.
       Z        Zip/transpose, collecting the first halves in one array and the
                second halves in another.
        E       Test the arrays of halves for equality.
           S  Return the sum of the results, counting the number of different
              ways s can be paired.
Деннис
источник
3

Pyth - без регулярных выражений - 13 12 байт

Проверяет, состоит ли какой-либо из разделов из всех строк, которые равны друг другу при разделении на две части.

sm.AqMcL2d./

Тестовый пакет .

Maltysen
источник
3

Брахилог , 14 байтов (без регулярных выражений)

lye~l:1j@2zcc?

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

Это слишком медленно для некоторых тестовых случаев

объяснение

ly                  The list [0, …, length(Input)]
  e~l               A list whose length is an element of the previous list
     :1j            Append itself to this list
        @2zc        Split in half, zip and concatenate so that the list contains pairs of
                      consecutive identical elements
            c?      The concatenation of that list must result in the Input
Фатализировать
источник
3

JavaScript (ES6), без регулярных выражений, 75 74 байта

f=s=>!s|[...s].some((_,i)=>i&&s[e='slice'](0,i)==s[e](i,i+=i)&&f(s[e](i)))

1В противном случае возвращается за деньги 0. Редактировать: 1 байт сохранен благодаря @ edc65.

Нил
источник
Ницца! То же количество, используя substrбез изменения i. Но с sliceповторением 3 раза вы можете сохранить 1 байт для псевдонима
edc65
@ edc65 Как получить тот же счет без изменения i? Я понимаю, что s.substr(i,i+i)возвращает то же самое, s.slice(i,i+=i)но затем я использую измененное значение iпозже ...
Нейл
это на s.substr(i,i)2 байта меньше, чем на s.slice(i+i)2 байта больше
edc65
@ edc65 Да, конечно, мне нужно больше кофе ...
Нил
3

Python, 58 байт

f=lambda s,p='':s>''and(f(p)>-(s==p)<f(s))|f(s[1:],p+s[0])

Это основано на рекурсивном методе Денниса . Трюк с булевым отрицанием также взят оттуда.

Новая идея состоит в том, чтобы проходить по разделам (p,s)исходной строки, начиная с ('',s)многократного перемещения первого символа sв качестве последнего символа p. Это позволяет ссылаться на части напрямую, без нарезки строк. Но, поскольку раздел начинается с pпустого, мы должны быть осторожны, чтобы избежать бесконечных циклов f(s)вызовов f(s).

XNOR
источник
2

JavaScript (ES6), 24 байта

x=>/^((.+)\2)+$/.test(x)

Вероятно, не становится короче этого.

ETHproductions
источник
Не должно ли это быть \2?
Нейл
@Neil Почему-то я думал, что это сработало \1, но aabвозвращает true... спасибо за исправление.
ETHproductions
2

PHP, 40 байт

печатает 0 для ложного и 1 для истинного

<?=preg_match("#^((.+)\\2)+$#",$argv[1]);
Йорг Хюльсерманн
источник
2

Python, 66 64 байта

Спасибо @Zgarb за -1 байт!

f=lambda x,s=1:x>x[:s]and(x==2*x[:s])|f(x[:s])&f(x[s:])|f(x,s+1)

Возвращает Trueили False.

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

Любая помощь в гольф это будет оценено.

Оливер Ни
источник
1

Ракетка 230 байтов

(let((sl string-length)(ss substring))(if(odd?(sl s))(printf ".~n")(begin(let p((s s))(if(equal? s "")(printf "!")
(for((i(range 1(add1(/(sl s)2)))))(when(equal?(ss s 0 i)(ss s i(* 2 i)))(p(ss s(* 2 i)(sl s)))))))(printf ".~n"))))

Печатает '!' для каждого способа, которым строка является платной. Печатает '.' в конце.

Ungolfed:

(define (f s)
  (let ((sl string-length)                              ; create short names of built-in fns
        (ss substring))
    (if (odd? (sl s))  (printf ".~n")                   ; odd length strings cannot be pairable; end here.
        (begin
          (let loop ((s s))                             ; start testing here
            (if (equal? s "") (printf "!")              ; if no remaining string, it must be pairable
                (for ((i (range 1 (add1 (/(sl s)2)))))  ; ch lengths varying from 1 to half of string length
                  (when (equal? (ss s 0 i)              ; ch if substrings are same
                                (ss s i (* 2 i)))
                    (loop (ss s (* 2 i) (sl s) ))))))   ; if yes, loop to check remaining string.
          (printf ".~n")))))                            ; End of testing.

Тестирование: 

(println "Following should be pairable")
(f "bbaabbaa")            ; should produce 2 '!' since 2 ways are possible.
(f "aa")
(f "abaaba")
(f "bbababbb")
(f "aabaaababbbaba")
(f "babababa")                    ; should be pairable in 2 ways.
(f "bbbbbbbbbbbb")                ; should be pairable in many ways.
(f "aaababbabbabbbababbaabaabaababaaba")
(f "aaaabaab")
(println "Following should be unpairable")
; (f "a")
(f "ba")
(f "baab")
(f "abaabaaba")
(f "bbbbbbbbbbbbbbb")
(f "baababbabaaaab")
(f "aaaaabbaaaaa")

Выход: 

"Following should be pairable"
!!.
!.
!.
!.
!.
!!.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.
!.
!.
"Following should be unpairable"
.
.
.
.
.
.
rnso
источник
1

Perl, 16 +2 = 18 байт (с регулярным выражением)

Беги с -nlфлагами. -Eэто бесплатно.

say/^((.+)\2)+$/

Беги как:

perl -nlE 'say/^((.+)\2)+$/'

Возвращает список групп захвата (правдивых), если это допустимо, и нулевой строки, если это не так.

объяснение

Эти -nlфлаги будут выполнять код в цикле ( -n), помещая вход (с задней новой строкой удалена из -l) в переменную $_каждый раз, а затем оценить код каждый раз , когда вход вводится, пока программа не будет вручную прекращена. -EФлаг позволяет оценивать код в командной строке, и позволяет sayкоманду.

say/^((.+)\2)+$/

   /^((.+)\2)+$/  #The regex engine
      (.+)\2      #Find any set of at least one character, followed by itself
     (      )+    #Do this at least one time
   /^         $/  #Make sure that this matches the entire string from start to end
say               #Output the result of the regex

Если совпадение найдено (например, если строка является допустимой), то регулярное выражение возвращает список групп захвата, который оценивается как истинный, который затем передается sayи выводится. Если совпадений не найдено, то регулярное выражение возвращает пустую строку, которая оценивается как ложное значение, которое затем передается sayи выводится.

Образец:

$ perl -nlE 'say/^((.+)\2)+$/'
aaababbabbabbbababbaabaabaababaaba
baababaababaaba                      #Truthy
baababbabaaaab
                                     #Falsy
bbababbb
bbb                                  #Truthy
aabaaababbbaba
bababa                               #Truthy
abaabaaba
                                     #Falsy
Габриэль Бенами
источник
1

GNU Пролог, 49 46 байтов

Вероятно, работает и в других вариантах, хотя они не все представляют строки одинаково; Представление GNU Prolog является полезным для этой проблемы.

Неясно, считается ли это использованием регулярных выражений или нет. Он не использует никаких функций, подобных регулярному выражению, но вся семантика языка похожа на семантику регулярного выражения.

Новая версия (использует трюк рекурсии, замеченный в некоторых других ответах):

s(X):-append(A,B,X),(A=B;A\=X,B\=X,s(A),s(B)).

Старая версия:

s(X):-X=[];append(A,B,X),B\=X,append(C,C,A),s(B).

Это предикат (эквивалент функции Пролога) s, а не полная программа. Используйте это так:

| ?- s("aa").
true ?
yes
| ?- s("aaababbabbabbbababbaabaabaababaaba").
true ?
yes
| ?- s("baababbabaaaab").
no
| ?- s("bbbbbbbbbbbbbbb").
no

Интересная особенность старого решения заключается в том, что если вы спросите переводчика: «Есть ли еще решения?» с помощью использования ;в true ?приглашении (вместо того, чтобы спрашивать «есть ли какое-либо решение» путем нажатия возврата в приглашении, как я делал выше), он возвращает «true» количество раз, равное количеству различных способов выражения строки в заданной форме (например, он возвращает «true» дважды с помощью s("aaaa")., поскольку это может быть проанализировано как (a a)(a a)или как(aa aa) ).

Программы Prolog часто обратима ( что позволяет , sчтобы сформировать список строк с заданным свойством). Более старый не (это входит в бесконечный цикл), но это из-за метода игры в гольф, который я использовал, чтобы гарантировать, что C не пуст; если вы переписываете программу для явного указания C как непустого, она генерирует строки вида «aa», «aabb», «aabbcc» и т. д. (Prolog, будучи Prolog, не определяет тождества для символов, которые их делают вверх, просто спецификация, какие символы одинаковы). Более новый генерирует строки вида «aa», «abab», «abcabc» и т. Д .; это бесконечный цикл сам по себе, и, таким образом, он никогда не достигнет точки, в которой он застрянет из-за невозможности обнаружить строку нулевой длины.


источник
1

Brainfuck, 177 байтов

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

отформатирован:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Ожидается ввод без завершающей строки. Отпечатки \x00за ложь и \x01за правду.

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

Это реализует поиск в глубину. В частности: проверьте наличие повторяющихся префиксов увеличивающейся длины, начиная с текущего суффикса, затем перейдите к следующему суффиксу, если совпадение найдено, в противном случае вернитесь назад.

В начале строка переворачивается, и \x01в конце помещается страж .

Лента разделена на 4-ячеечные узлы. Расположение памяти узла:

c h x 0

где c- символ, hэто флаг, обозначающий, находится ли символ в первой половине повторяющегося префикса, и xфлаг, который отслеживает текущую пару сравниваемых символов. Эти hфлаги остаются на месте в то время какx флаги образуют окно движущегося.

Если строка является платной, указатель попадает рядом с часовым в конце основного цикла; в противном случае указатель падает с левой стороны строки при возврате.

Митч Шварц
источник
1

Брахилог , 5 байт

~c~jᵐ

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

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

объяснение

~c     Reversed concatenate: find a list that, when concatenated, results in the input string
       This examines all partitions of the input
  ~jᵐ  Map reversed juxtapose: for each string in that list, is it the result of concatenating
       a string to itself?

Для входной строки, подобной "ababcc", ~cпробует разные разделы до тех пор, пока не дойдёт до этого ["abab", "cc"], и в этот момент ~jоба элемента списка будут ᵐуспешны ["ab", "c"], выходные данные и предикат завершатся успешно.

DLosc
источник
1

R , 31 байт

grepl("^((.+)\\2)+$",scan(,""))

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

На основании ответа Retina.

р , 129 байт

А вот оригинальный ответ без регулярных выражений:

o=(y=utf8ToInt(scan(,"")))<0;for(i in 2*1:(sum(y>0)/2))for(j in 1:(i/2)){w=i:(i-j+1);v=w-j;if(all(y[w]==y[v]))o[c(v,w)]=T};all(o)

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

Ник Кеннеди
источник
0

Lithp , 57 символов

#S::((? (!= (null) (match S "^((.+)\\2)+$")) true false))

Пример использования:

% pairable_strings.lithp
(
    (def f #S::((? (!= (null) (match S "^((.+)\\2)+$")) true false)))
    (print (f "aa"))
    (print (f "aabaaababbbaba"))
    (print (f "aaababbabbabbbababbaabaabaababaaba"))
    (print (f "ba"))
)

# ./run.js pairable_strings.lithp
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 3, type: 'Atom', name: 'false' }
Andrakis
источник