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

Например, 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ...имеет это свойство: каждая пара последовательных вхождений 2имеет не более двух целых чисел между ними (таких как 2, 3, 5, 2и 2, 3, 6, 2; каждая пара последовательных вхождений 3имеет не более трех целых чисел между ними; и то же самое для 5и 6.

Однако 2, 3, 5, 2, 3, 4, 2, 3, 5, 2, 3, 4, ...не имеет этого свойства: два последовательных вхождения 4, а именно 4, 2, 3, 5, 2, 3, 4, имеют более четырех целых чисел между ними.

Входные данные : разумное представление периодической последовательности натуральных чисел. Например, конечный список, такой как, {2, 3, 5, 2, 3, 6}может представлять первую бесконечную последовательность 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ...выше. (В этом отношении, проблема могла быть заявлена ​​для конечных списков, которые оборачиваются вместо бесконечных периодических списков.)

Вывод : истинное / ложное значение.

Правдивые примеры:

{1}
{8, 9}
{2, 3, 4}
{5, 5, 3, 3, 6}
{2, 3, 5, 2, 3, 6}
{6, 7, 3, 5, 3, 7}
{9, 4, 6, 7, 4, 5}
{1, 1, 1, 1, 1, 100, 1}
{1, 9, 1, 8, 1, 7, 1, 11}

Ложные примеры:

{1, 2, 3}
{2, 3, 9, 5}
{3, 5, 4, 4, 6}
{2, 3, 5, 2, 3, 4}
{3, 5, 7, 5, 9, 3, 7}
{5, 6, 7, 8, 9, 10, 11}
{1, 9, 1, 8, 1, 6, 1, 11}

Это Codegolf , поэтому выигрывает самый короткий код. Ответы на всех языках приветствуются.

Haskell, 60 57 56 55 байтов

f(a:b)=b==[]||length(fst$span(/=a)b)<=a&&f b
g x=f$x++x

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

Пример использования: g [1]-> True. Попробуйте онлайн!

Позвольте aбыть главой списка и bхвостом. Результатом является, Trueесли bпусто или число элементов в начале b, которые не равны, aне больше, чем aи рекурсивный вызов f bтакже True, в противном случае False. Начните с двойного списка ввода.

Редактировать: @Leo сохранил 3 байта. Благодарность!

Редактировать 2: @Laikoni сохранил 1 байт. Благодарность!

Python , 57 56 байт

-1 байт благодаря Деннису (заменить i+1:i+v+2на i:i-~vсо iсмещением 1 от enumerate)

lambda a:all(v in(a+a)[i:i-~v]for i,v in enumerate(a,1))

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

Без имени функция принимает список, aи тестирование условия , что каждое значение, v, появляется inсоответствующий фрагмент в свое право на конкатенации aс самими собой, (a+a)[i:i-~v]где 1 на основе индекс vв a, i, обеспечиваются enumerate(a,1).

JavaScript (ES6), 67 65 55 54 51 49 байт

Сохранено 3B благодаря @ETHproductions и 2B благодаря @Arnauld

a=>!a.some((b,c)=>a.concat(a).indexOf(b,++c)>b+c)

объяснение

Это определяет функцию, которая принимает массив в aкачестве входных данных. Затем .someметод выполняет итерацию по этому массиву, выполняя другую функцию для каждого элемента.

Эта внутренняя функция принимает два аргумента, bи c, текущее значение и его индекс. Функция находит индекс текущего значения, начиная с индекса c + 1. Затем он проверяет, больше ли этот индекс, чем текущее значение плюс текущий индекс (разница между двумя вхождениями одного и того же значения больше, чем b). Обратите внимание, что это возвращает полную противоположность того, что мы хотим.

Если одно из этих возвращаемых значений равно true, .someфункция также возвращается true. Если ни одна из проверок не вернется true, .someфункция вернется false. Еще раз противоположное значение, которое мы хотим вернуть, поэтому этот результат отменяется, а затем возвращается.

Попробуй это

Попробуйте все тестовые случаи здесь:

let f=
a=>!a.some((b,c)=>a.concat(a).indexOf(b,++c)>b+c)

let truthy = [[1], [8, 9], [2, 3, 4], [5, 5, 3, 3, 6], [2, 3, 5, 2, 3, 6], [6, 7, 3, 5, 3, 7], [9, 4, 6, 7, 4, 5], [1, 1, 1, 1, 1, 100, 1], [1, 9, 1, 8, 1, 7, 1, 11]];
let falsy  = [[1, 2, 3], [2, 3, 9, 5], [3, 5, 4, 4, 6], [2, 3, 5, 2, 3, 4], [3, 5, 7, 5, 9, 3, 7], [5, 6, 7, 8, 9, 10, 11], [1, 9, 1, 8, 1, 6, 1, 11]];

console.log("Truthy test cases:");
for (let test of truthy) {
    console.log(`${test}: ${f(test)}`);
}

console.log("Falsy test cases:");
for (let test of falsy) {
    console.log(`${test}: ${f(test)}`);
}

Желе , 11 байт

ṣZL
;çЀ<‘P

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

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

;çЀ<‘P  Main link. Argument: A (array)

;        Concatenate A with itself.
 çD€     For each n in A, call the helper with left arg. A + A and right arg. n.
     ‘   Increment all integers in A.
    <    Perform element-wise comparison of the results to both sides.
      P  Take the product of the resulting Booleans.


ṣZL      Helper link. Left argument: A. Right argument: n

ṣ        Split A at all occurrences of n.
 Z       Zip to transpose rows and columns.
  L      Length; yield the number of rows, which is equal to the number of columns
         of the input to Z.

Желе , 8 байт

ṙJḣ"‘Œpċ

Вдохновленный ответом Python @ JonathanAllan .

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

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

ṙJḣ"‘Œpċ  Main link. Argument: A (array)

 J        Yield the indicies of A, i.e., [1, ..., len(A)].
ṙ         Rotate; yield A, rotated 1, ..., and len(A) units rotated to the left.
    ‘     Increment; add 1 to all elements of A.
  ḣ"      Head zipwith; truncate the n-th rotation to length A[n]+1.
     Œp   Take the Cartesian product of all resulting truncated rotations.
       ċ  Count the number of times A appears in the result.

SWI-Пролог, 83 байта

a(L,[H|R]):-nth0(X,R,H),H>=X,a(L,R);length(R,N),nth0(X,L,H),H>=N+X,a(L,R).
a(_,[]).

Список следует вводить дважды:

a([1,2,3],[1,2,3]).

Если это не считается приемлемым, вы можете добавить предикат

a(L):-a(L,L).

который добавляет дополнительные 14 байтов.

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

nb: вы можете проверять различные ложные случаи сразу, разделяя ваши запросы ';' (или) и проверить для различных истинных случаев, разделяя с помощью ',' (и)

то есть, используя примеры OP:

a([1],[1]),
a([8, 9],[8, 9]),
a([2, 3, 4],[2, 3, 4]),
a([5, 5, 3, 3, 6],[5, 5, 3, 3, 6]),
a([2, 3, 5, 2, 3, 6],[2, 3, 5, 2, 3, 6]),
a([6, 7, 3, 5, 3, 7],[6, 7, 3, 5, 3, 7]),
a([9, 4, 6, 7, 4, 5],[9, 4, 6, 7, 4, 5]),
a([1, 1, 1, 1, 1, 100, 1],[1, 1, 1, 1, 1, 100, 1]),
a([1, 9, 1, 8, 1, 7, 1, 11],[1, 9, 1, 8, 1, 7, 1, 11]).

а также

a([1, 2, 3],[1, 2, 3]);
a([2, 3, 9, 5],[2, 3, 9, 5]);
a([3, 5, 4, 4, 6],[3, 5, 4, 4, 6]);
a([2, 3, 5, 2, 3, 4],[2, 3, 5, 2, 3, 4]);
a([3, 5, 7, 5, 9, 3, 7],[3, 5, 7, 5, 9, 3, 7]);
a([5, 6, 7, 8, 9, 10, 11],[5, 6, 7, 8, 9, 10, 11]);
a([1, 9, 1, 8, 1, 6, 1, 11],[1, 9, 1, 8, 1, 6, 1, 11]).

PHP, 52 байта

for(;$n=$argv[++$i];$$n=$i)!$$n|$i-$$n<$n+2?:die(1);

принимает последовательность из аргументов командной строки; выходит с кодом 1для фальши, 0для правды.
Беги с -nr.

• перебрать $nаргументы:
  • если не было предыдущего события или оно было достаточно недавним,
    то ничего не делайте, иначе выйдите с кодом1
  • помните предыдущий случай в $$n( переменные переменные )
• выход с кодом 0(неявный)

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

$
,$`
M!&`\b(1+),.*?\b\1\b
+%`(^1*)1,1+
$1
M`1,
^0

Ввод в виде списка запятых унарных чисел.

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

объяснение

$
,$`

Дублируйте ввод, чтобы мы могли проверить шаги, которые обертывают вокруг конца.

M!&`\b(1+),.*?\b\1\b

Сопоставьте и верните каждый (самый короткий) раздел между двумя одинаковыми значениями, например 11,111,1,11.

+%`(^1*)1,1+
$1

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

M`1,

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

^0

Попробуйте сопоставить число, начинающееся с 0(т.е. только с 0себя). Это фактически логическое отрицание результата.

JavaScript (ES6), 47 байт

a=>![...a,...a].some((n,i)=>a[-n]-(a[-n]=i)<~n)

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

Мы повторно используем входной массив aдля хранения позиции последнего встреченного вхождения каждого целого числа в a. Мы используем ключ -nдля хранения этой позиции, чтобы она не мешала исходным индексам a.

Когда a[-n]существует, фактический тест происходит. Когда a[-n]не существует, выражение a[-n] - (a[-n] = i)равно undefined - i == NaNи сравнение с ~nвсегда ложным, что является ожидаемым результатом.

Контрольные примеры

f=
a=>![...a,...a].some((n,i)=>a[-n]-(a[-n]=i)<~n)

console.log('Truthy cases:');
console.log(f([1]));
console.log(f([8, 9]));
console.log(f([2, 3, 4]));
console.log(f([5, 5, 3, 3, 6]));
console.log(f([2, 3, 5, 2, 3, 6]));
console.log(f([6, 7, 3, 5, 3, 7]));
console.log(f([9, 4, 6, 7, 4, 5]));
console.log(f([1, 1, 1, 1, 1, 100, 1]));
console.log(f([1, 9, 1, 8, 1, 7, 1, 11]));

console.log('Falsy cases:');
console.log(f([1, 2, 3]));
console.log(f([2, 3, 9, 5]));
console.log(f([3, 5, 4, 4, 6]));
console.log(f([2, 3, 5, 2, 3, 4]));
console.log(f([3, 5, 7, 5, 9, 3, 7]));
console.log(f([5, 6, 7, 8, 9, 10, 11]));
console.log(f([1, 9, 1, 8, 1, 6, 1, 11]));

Сетчатка ,  41 39 байт

2 байта в гольфе благодаря Мартину Эндеру, который, кстати, познакомил меня с балансировкой групп со своим фантастическим гидом по SO

$
,$`,
((1)+,)(?=(?<-2>1+,)*(\1|$))

^$

Ввод - это разделенный запятыми список унарных чисел. Выход 0для ложного и 1истинного.

Попробуйте онлайн! (Набор тестов, который автоматически преобразует из десятичного числа)

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

объяснение

$
,$`,

Как и во многих других материалах, мы дублируем список, чтобы справиться с переносом. Мы также добавляем запятую в конце, так что после каждого числа следует запятая (позже это будет немного проще)

((1)+,)(?=(?<-2>1+,)*(\1|$))

Здесь вещи становятся интересными. Это этап замены, мы заменяем все совпадающие по первой строке второй строкой, в этом случае мы стремимся удалить все числа, nза которыми не следуют n+1другие разные числа.

Чтобы сделать это, мы сначала сопоставляем номер, захватывая каждый 1в группе (захват группы № 2 в этом случае). Затем с положительным прогнозом, чтобы получить утверждение нулевой ширины, мы неоднократно пытаемся найти соответствие в балансирующей группе -2, которая будет успешной не более, чем число захватов, сделанных группой 2, число, за которым следует запятая. После этой последовательности чисел мы удовлетворены, достигнем ли мы либо первого числа снова, либо конца строки.

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

^$

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

Желе , 11 байт

ẋ2ĠṢI_2<"QȦ

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

ẋ2ĠṢI_2<"QȦ  Main link. Argument: A (array)

ẋ2           Repeat A twice to account for wrap-around.
  Ġ          Group all indices of A + A by their respective values, sorting the
             index groups by the associated values.
   Ṣ         Sort the groups lexicographically, i.e., by first appearance in A.
    I        Increments; compute the forward differences of adjacent indices in
             each of the groups.
     _2      Subtract 2 from the differences.
         Q   Unique; yield A, deduplicated.
       <"    Compare all differences in the index group corresponding to the n-th
             unique value in A with the n-th unqiue value in A.
          Ȧ  All; yield 1 if and only if none of the comparisons returned 0.

Python 3 , 101 байт

lambda l:all(v>=(l[i+1:].index(v)if v in l[i+1:]else len(l[i+1:])+l.index(v))for i,v in enumerate(l))

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

Röda , 50 байтов

f a{seq 0,#a-1|[indexOf(a[_],a[_1+1:]..a)<=a[_1]]}

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

В заключение! Я ждал на этот вызов ...

Это функция, которая возвращает истинное или ложное значение. Требуется один аргумент, массив.

Он перебирает поток индексов и проверяет для каждого индекса, _1что расстояние от текущего индекса до следующего индекса a[_1]не больше, чем a[_1].

05AB1E , 13 байтов

Dì©v®¦©yky›_P

Попробуйте онлайн! или как тестовый набор

объяснение

Dì             # duplicate input and prepend the copy to the original
  ©            # store a copy in the register
   v           # for each element in the list
    ®          # push the list from register
     ¦©        # remove the first element and store a copy in the register
       yk      # get the index of the current element in the list
         y›_   # check if it's less than or equal to the current element
            P  # product of stack