Проверьте слово Линдона

22

Линдон слово является строкой , которая является строго лексикографически меньше , чем любой из его циклических вращений. По заданной двоичной строке определите, является ли это слово Линдона как можно меньшим количеством байтов.

Например, 001011это слово Линдона. Его повороты, перечисленные ниже, получены путем многократного перемещения первого символа в конец.

001011
010110
101100
011001
110010
100101

Из них исходная строка ставится лексикографически первой или, что то же самое, представляет наименьшее двоичное число.

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

Связанная проблема.

Входные данные: непустая двоичная строка или список цифр 0и 1. Вы не можете использовать числа, как 5для представления 101.

Вывод: непротиворечивое значение Truthy или Falsey, которое указывает, является ли строка словом Линдона.

Встроенные модули специально для слов Линдона не допускаются.

Тестовые случаи:

Слова Линдона длиной до 6:

0
1
01
001
011
0001
0011
0111
00001
00011
00101
00111
01011
01111
000001
000011
000101
000111
001011
001101
001111
010111
011111

НеЛиндоновские слова длиной до 4:

00
10
11
000
010
100
101
110
111
0000
0010
0100
0101
0110
1000
1001
1010
1011
1100
1101
1110
1111

Leaderboard:

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

code-golf string XNOR
источник

Ответы:

5

Python 2, 42

Кажется, это достаточно хорошо, чтобы сравнивать с суффиксами вместо того, чтобы беспокоиться о вращении.

f=lambda s,i=1:i/len(s)or s<s[i:]*f(s,i+1)

Настройка рекурсии не кажется очень хорошей; может быть, это можно сделать лучше.

Эта 44-байтовая версия делает более очевидным, что происходит:

lambda s:all(s<=s[i:]for i in range(len(s)))
feersum
источник
4

Haskell, 43 38 байт

f x=all(x<=)$init$scanl(const.tail)x x

scanl(const.tail)x xсоздает список всех суффиксов x, включая пустую строку ""в конце, которая удаляется с помощью init.

Изменить: @feersum обнаружил ошибку в моей первой версии и пришел к мысли, что достаточно сравнения с суффиксами.

Ними
источник
Как он проверяет, что нет никаких вращений x, которые равны x?
Feersum
@feersum: это не так. Это ошибка. Починил это. Спасибо, что узнали!
Ними
2

CJam, 15 14 байтов

r_,,\fm<(f>1-!

Попробуйте эту скрипку в интерпретаторе CJam или проверьте все тестовые случаи одновременно.

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

r              e# Read a token from STDIN.
 _,            e# Push the length of a copy.
   ,           e# Turn length L into [0 ... L-1].
    \fm<       e# Rotate the token 0, ..., and L-1 units to the left.
        (      e# Shift out the first rotation, i.e., the original token.
         f>    e# Compare all other rotations with this one.
           1-  e# Remove 1 from the resulting array of Booleans.
             ! e# Apply logical NOT to turn an empty array into 1, and a
               e# non-empty one into 0.
Деннис
источник
2

J, 11 символов

Выводы 1по словам Линдона и 0прочее.

0=0({/:)<\.

<\.принимает суффиксы, а затем /:говорит нам, как их сортировать лексикографически. {берет запись с 0индексом -th и 0=проверяет, равен ли он нулю: если это так, у нас есть слово Линдона, потому что самый большой суффикс не поменяет место в сортировке; если он ненулевой, это не слово Линдона, потому что какой-то суффикс раньше лексикографически.

   0=0({/:)<\. '001011'
1
   0=0({/:)<\. '001001'
0
algorithmshark
источник
2

TeaScript , 10 байт

xe»x«xS(i©

Очень гольф, очень короткий. Попробуйте онлайн

Объяснение && Ungolfed

xe(#x<=xS(i))

xe(#      // Loop through x
          // Check if all iterations return true
    x <=  // Input is less than or equal to...
    xS(i) // Input chopped at current index
)
Downgoat
источник
Святая корова, ты избиваешь <s> Пита </ s> Дениса ! Как это вообще возможно?!
ETHproductions
2
@ETHproductions В мире, где Деннис может быть вне игры в гольф, все возможно: p
Downgoat
Я буду наслаждаться этим моментом, пока он длится, тогда ответы CJam и Pyth, вероятно, будут более
удачными
Подожди, подожди ... Я вижу, что это правильно обрабатывает такие случаи, как 00, но как он это делает, не ловя себя равным себе (то есть когда i==0)?
ETHproductions
@ETHproductions На самом деле это не очень похоже на ответ feersum , просто сравнение суффиксов функционально эквивалентно
Downgoat
1

Хаскелл, 29

f s=all(s<=)$init$scanr(:)[]s

Проверяет, sявляется ли максимум каждый из его непустых суффиксов, как ответ nimi .

Выражение scanr(:)[]генерирует список суффиксов путем перечисления.

>> scanr(:)[] "abcd"
["abcd","bcd","cd","d",""]

initЗатем избавляется от пустой строки в конце. Наконец, all(s<=)проверяет, xудовлетворяет ли каждый суффикс s<=x. Поскольку первый суффикс sсам по себе, <=он необходим.

XNOR
источник
1

Рубин, 37 байт

->s{(1...s.size).all?{|i|s[i..-1]>s}}

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

lyndon_words = %w(0 1 01 001 011 0001 0011 0111 00001 00011 00101 00111
                  01011 01111 000001 000011 000101 000111 001011 001101
                  001111 010111 011111)

not_lyndon_words = %w(00 10 11 000 010 100 101 110 111 0000 0010 0100 0101
                      0110 1000 1001 1010 1011 1100 1101 1110 1111)

f=->s{(1...s.size).all?{|i|s[i..-1]>s}}

p lyndon_words.all? &f      # => true
p not_lyndon_words.any? &f  # => false
daniero
источник
1

Бурлеск, 15 байт

JiRJU_j<]x/==&&

В основном 8 из этих 7 байтов должны проверить, не связывается ли он. В противном случае вы можете пойти с просто JiR<]==.

Объяснение:

J       -- duplicate word
iR      -- all rotations
J       -- duplicate list of all rotations
U_      -- check if list contains no duplicates
j       -- swap
<]      -- find minimum of the list
x/      -- rotate top
==      -- compare minimum with the original word
&&      -- and results of min == orig and list unique
mroman
источник
0

Javascript (ES6), 129 байт

a=Array;s=prompt();console.log(a.from(a(s.length),(x,i)=>i).map(n=>(s.substring(n)+s.substring(0,n--))).sort().pop().contains(s))
anOKsquirrel
источник
0

Javascript, 91 87 байт

f=x=>(y=(x+x).slice(1,-1),x[0]==x||!(y.indexOf(x)+1)&&!x.indexOf('0')&&x.slice(-1)==1);

Я в основном объединяю слово с собой и проверяю, есть ли оно еще там. Чтобы проверить, является ли это наименьшим возможным числом, я просто проверяю, чтобы оно начиналось с 0 и заканчивалось 1.

тесты

[
['0',1],
['1',1],
['01',1],
['001',1],
['011',1],
['0001',1],
['0011',1],
['0111',1],
['00001',1],
['00011',1],
['00101',1],
['00111',1],
['01011',1],
['01111',1],
['000001',1],
['000011',1],
['000101',1],
['000111',1],
['001011',1],
['001101',1],
['001111',1],
['010111',1],
['011111',1],
['00',0],
['10',0],
['11',0],
['000',0],
['010',0],
['100',0],
['101',0],
['110',0],
['111',0],
['0000',0],
['0010',0],
['0100',0],
['0101',0],
['0110',0],
['1000',0],
['1001',0],
['1010',0],
['1011',0],
['1100',0],
['1101',0],
['1110',0],
['1111',0]
].forEach(t =>{ 
  r=f(t[0])
  x=t[1]
  console.log('Test '+(r==x?'OK':'Fail (Expected: ' + x +')')
  +'\nInput: '+t[0]+'\nResult: ' +r+'\n')                       
})
Naouak
источник
0

Mathematica, 86 байт

(s=Table[#~StringRotateLeft~i,{i,StringLength@#}];Last@s==First@Sort@s&&s~Count~#==1)&

вход

[ "1111"]

J42161217
источник