Napisz program, aby ustalić, czy okresowa sekwencja dodatnich liczb całkowitych ma właściwość, że dla każdej liczby całkowitej nwystępującej w sekwencji nigdy nie ma więcej niż ninne liczby całkowite między dwoma kolejnymi wystąpieniami n.

Na przykład 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ...ma tę właściwość: każda para kolejnych wystąpień 2ma co najwyżej dwie liczby całkowite (takie jak 2, 3, 5, 2i 2, 3, 6, 2; każda para kolejnych wystąpień 3ma co najwyżej trzy liczby całkowite; i to samo dla 5i 6.

Jednak 2, 3, 5, 2, 3, 4, 2, 3, 5, 2, 3, 4, ...nie ma tej właściwości: dwa kolejne wystąpienia 4, mianowicie 4, 2, 3, 5, 2, 3, 4, mają więcej niż cztery liczby całkowite między nimi.

Dane wejściowe : rozsądne przedstawienie okresowej sekwencji dodatnich liczb całkowitych. Na przykład skończona lista, która {2, 3, 5, 2, 3, 6}może reprezentować pierwszą nieskończoną sekwencję 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ...powyżej. (W tym przypadku problem można określić w przypadku skończonych list, które się zawijają zamiast nieskończonych list okresowych).

Wyjście : a truthy / wartość falsy.

Prawdziwe przykłady:

{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}

Przykłady 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}

To jest codegolf , więc wygrywa najkrótszy kod. Zachęcamy do udzielania odpowiedzi we wszystkich językach.

Haskell, 60 57 56 55 bajtów

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

Zakłada, że ​​lista wejściowa zawiera co najmniej jeden element.

Przykład użycia: g [1]-> True. Wypróbuj online!

Niech abędzie głową listy i bogonem. Wynikiem jest, Truejeśli bjest pusty lub liczba elementów na początku b, które nie są równe, anie jest większa niż, aa wywołanie rekurencyjne f bjest również Trueinne False. Zacznij od dwukrotności listy wprowadzania.

Edycja: @Leo zapisał 3 bajty. Dzięki!

Edycja 2: @Laikoni zapisał 1 bajt. Dzięki!

Python , 57 56 bajtów

-1 bajt dzięki Dennis (zamiast i+1:i+v+2z i:i-~vze związkiem iprzesunięcie 1 z enumerate)

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

Wypróbuj online!

Funkcja nienazwany biorąc listę, ai testowania warunek, że każda wartość, vpojawia się inodpowiedni kawałek do jego prawa w konkatenacji aze sobą, (a+a)[i:i-~v]gdzie indeks 1 opartego na poziomie vw a, ijest dostarczonych przez enumerate(a,1).

JavaScript (ES6), 67 65 55 54 51 49 bajtów

Zaoszczędź 3B dzięki @ETHproductions i 2B dzięki @Arnauld

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

Wyjaśnienie

Definiuje funkcję, która pobiera tablicę ajako dane wejściowe. Następnie .somemetoda iteruje tę tablicę, wykonując inną funkcję dla każdego elementu.

Ta funkcja wewnętrzna przyjmuje dwa argumenty boraz cbieżącą wartość i jej indeks. Funkcja znajduje indeks bieżącej wartości, zaczynając od indeksu c + 1. Następnie sprawdza, czy ten indeks jest większy niż bieżąca wartość plus bieżący indeks (różnica między dwoma wystąpieniami tej samej wartości jest większa niż b). Zauważ, że to zwraca dokładne przeciwieństwo tego, czego chcemy.

Jeśli jedna z tych zwracanych wartości jest true, .somefunkcja zwraca truerównież. Jeśli żadna z kontroli nie powróci true, .somefunkcja zwraca false. Jeszcze raz przeciwieństwo wartości, którą chcemy zwrócić, więc ten wynik jest negowany, a następnie zwracany.

Sprawdź to

Wypróbuj wszystkie przypadki testowe tutaj:

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)}`);
}

Galaretka , 11 bajtów

ṣZL
;çЀ<‘P

Wypróbuj online!

Jak to działa

;çЀ<‘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.

Galaretka , 8 bajtów

ṙJḣ"‘Œpċ

Napisane przez @ JonathanAllan's Python answer .

Wypróbuj online!

Jak to działa

ṙ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-Prolog, 83 bajty

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(_,[]).

Listę należy wprowadzić dwukrotnie:

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

Jeśli nie zostanie to uznane za akceptowalne, możesz dodać predykat

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

co dodaje dodatkowe 14 bajtów.

Wypróbuj online

Uwaga: możesz jednocześnie testować różne fałszywe przypadki, oddzielając swoje zapytania znakiem „;” (lub) i sprawdź różne prawdziwe przypadki, oddzielając je znakami „,” (i)

tj. korzystając z przykładów PO:

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]).

i

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 bajty

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

pobiera sekwencję z argumentów wiersza poleceń; wychodzi z kodem 1dla fałszu, 0dla prawdy.
Uruchom z -nr.

• Pętla $nprzez argumenty:
  • jeśli nie było wcześniejszego zdarzenia lub było ono wystarczająco nowe
    , nie rób nic, w przeciwnym razie wyjdź z kodu1
  • zapamiętaj poprzednie wystąpienie w $$n( zmienne zmienne )
• wyjście z kodem 0(niejawne)

Siatkówka oka , 50 bajtów

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

Wprowadź jako listę oddzielnych przecinków liczb jednoargumentowych.

Wypróbuj online!

Wyjaśnienie

$
,$`

Zduplikuj dane wejściowe, abyśmy mogli sprawdzić kroki owijające się wokół końca.

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

Dopasuj i zwróć każdą (najkrótszą) sekcję między dwiema identycznymi wartościami, np 11,111,1,11.

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

Kilkakrotnie usuwaj cyfrę z pierwszego numeru wraz z całym numerem po nim. Jeśli odstęp jest wystarczająco mały, spowoduje to całkowite usunięcie pierwszej liczby. W przeciwnym razie pozostanie co najmniej jedna cyfra.

M`1,

Policz, jak często 1,pojawia się we wszystkich wierszach. Jeśli pojawia się gdziekolwiek, jeden z kroków był zbyt szeroki.

^0

Spróbuj dopasować liczbę zaczynającą się od 0(tj. Tylko 0siebie). Jest to w rzeczywistości logiczna negacja wyniku.

JavaScript (ES6), 47 bajtów

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

Jak to działa

Ponownie używamy tablicy wejściowej ado przechowywania pozycji ostatniego napotkanego wystąpienia każdej liczby całkowitej a. Używamy klucza -ndo przechowywania tej pozycji, aby nie kolidowała z oryginalnymi indeksami a.

Gdy a[-n]istnieje, następuje rzeczywisty test. Gdy a[-n]nie istnieje, wyrażenie a[-n] - (a[-n] = i)jest równe undefined - i == NaNi porównanie z~n jest zawsze fałszem, co jest oczekiwanym rezultatem.

Przypadki testowe

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]));

Siatkówka ,  41 39 bajtów

2 bajty golfa dzięki Martinowi Enderowi, który, nawiasem mówiąc, wprowadził mnie do balansowania grup z jego fantastycznym przewodnikiem po SO

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

^$

Dane wejściowe to oddzielona przecinkami lista liczb jednoargumentowych. Dane wyjściowe są 0dla false i 1true.

Wypróbuj online!(Zestaw testowy, który automatycznie konwertuje z dziesiętnego)

Niedawno dowiedziałem się o równoważeniu grup, więc chciałem spróbować. Nie należą one do najłatwiejszych w użyciu narzędzi, ale z pewnością są potężne.

Wyjaśnienie

$
,$`,

Podobnie jak wiele innych zgłoszeń, duplikujemy listę, aby zająć się pakowaniem. Na końcu dodajemy przecinek, więc po każdym numerze następuje przecinek (to później trochę łatwiej)

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

Tutaj rzeczy stają się interesujące. To jest etap zastępowania, zastępujemy wszystko pasujące pierwszym wierszem drugim wierszem, w tym przypadku chcemy usunąć wszystkie liczbyn po których nie następują n+1inne różne liczby.

Aby to zrobić, najpierw dopasowujemy liczbę, przechwytując każdą 1w grupie (w tym przypadku przechwytując grupę numer 2). Następnie z pozytywnym spojrzeniem w przyszłość, aby uzyskać asercję o zerowej szerokości, wielokrotnie staramy się dopasować w grupie równoważącej-2 , która odniesie sukces nie więcej niż liczba przechwyceń wykonanych przez grupę 2, liczba po której nastąpi przecinek. Po tej sekwencji liczb jesteśmy usatysfakcjonowani, jeśli osiągniemy albo pierwszą liczbę, albo koniec linii.

Uwaga: to wyrażenie może pasować tylko do końcowej części liczby, jeśli nie uda się znaleźć dopasowania z pełną liczbą. Nie stanowi to problemu, ponieważ wtedy pierwsza część liczby pozostanie w ciągu i będziemy wiedzieć, że zastąpienie nie zakończyło się pełnym powodzeniem.

^$

Ostatecznie wynik powinien być prawdziwy, jeśli całkowicie usunęliśmy wszystkie liczby z listy. Próbujemy dopasować pusty ciąg i zwracamy liczbę znalezionych dopasowań.

Galaretka , 11 bajtów

ẋ2ĠṢI_2<"QȦ

Wypróbuj online!

ẋ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 bajtów

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))

Wypróbuj online!

Röda , 50 bajtów

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

Wypróbuj online!

Wreszcie! I zostały oczekiwanie na to wyzwanie ...

Jest to funkcja, która zwraca wartość prawdy lub fałszu. Wymaga jednego argumentu - tablicy.

Powtarza po strumieniu indeksów i sprawdza dla każdego indeksu _1, czy odległość bieżącego indeksu i następnego indeksu a[_1]nie jest większa niż a[_1].

05AB1E , 13 bajtów

Dì©v®¦©yky›_P

Wypróbuj online! lub jako pakiet testowy

Wyjaśnienie

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