Safety in numbers

Question

Write a program to determine if a periodic sequence of positive integers has the property that, for every integer n occurring in the sequence, there are never more than n other integers between two consecutive occurrences of n.

For example, 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ... does have this property: every pair of consecutive occurrences of 2 have at most two integers between them (such as 2, 3, 5, 2 and 2, 3, 6, 2; every pair of consecutive occurrences of 3 have at most three integers between them; and the same for 5 and 6.

However, 2, 3, 5, 2, 3, 4, 2, 3, 5, 2, 3, 4, ... does not have this property: two consecutive occurrences of 4, namely 4, 2, 3, 5, 2, 3, 4, have more than four integers between them.

Input: a reasonable representation of a periodic sequence of positive integers. For example, a finite list such as {2, 3, 5, 2, 3, 6} can represent the first infinite sequence 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ... above. (For that matter, the problem could be stated for finite lists that wrap around instead of for infinite periodic lists.)

Output: a truthy/falsy value.

Truthy examples:

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

Falsy examples:

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

This is codegolf, so the shortest code wins. Answers in all languages are encouraged.

Answer 1

Python, 57 56 bytes

-1 byte thanks to Dennis (replace i+1:i+v+2 with i:i-~v with an i offset of 1 from enumerate)

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

Try it online!

Unnamed function taking a list, a, and testing the condition that each value, v, appears in the relevant slice to its right in a concatenation of a with itself, (a+a)[i:i-~v], where the 1-based index of v in a, i, is provided by enumerate(a,1).

Answer 2

Haskell, 60 57 56 55 bytes

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

Assumes that the input list contains at least one element.

Usage example: g [1] -> True. Try it online!

Let a be the head of the list and b the tail. The result is True if b is empty or the number of elements at the beginning of b that are not equal to a is not greater than a and the recursive call of f b is also True, else False. Start with twice the input list.

Edit: @Leo saved 3 bytes. Thanks!

Edit 2: @Laikoni saved 1 byte. Thanks!

Answer 3

JavaScript (ES6), 67 65 55 54 51 49 bytes

Saved 3B thanks to @ETHproductions and 2B thanks to @Arnauld

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

Explanation

This defines a function that takes an array a as input. Then, the .some method iterates over that array, executing another function for every element.

This inner function takes two arguments, b and c, the current value and its index. The function finds the index of the current value, starting from index c + 1. Then it checks if this index is greater than the current value plus the current index (the difference between two occurrences of the same value is greater than b). Note that this returns the exact opposite of what we want.

If one of these return values is true, the .some function returns true as well. If none of the checks return true, the .some function returns false. Once again the opposite of the value we want to return, so this result is negated and then returned.

Test it

Try all test cases here:

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

Answer 4

Jelly, 11 bytes

ṣZL
;çЀ<‘P

Try it online!

How it works

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

Answer 5

Jelly, 8 bytes

ṙJḣ"‘Œpċ

Insipred by @JonathanAllan's Python answer.

Try it online!

How it works

ṙ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.

Answer 6

SWI-Prolog, 83 bytes

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

The list should be entered twice:

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

If this is not considered acceptable, you may add the predicate

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

which adds an extra 14 bytes.

Try it online

nb: you may test for different false cases at once by separating your queries with ';' (or) and test for different true cases by separating with ',' (and)

ie, using the OP examples :

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

and

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

Answer 7

PHP, 52 bytes

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

takes sequence from command line arguments; exits with code 1 for falsy, 0 for truthy.
Run with -nr.

• loop $n through arguments:
  • if there was no previous occurence or it was recent enough
    then do nothing, else exit with code 1
  • remember previous occurence in $$n (variable variables)
• exit with code 0 (implicit)

Answer 8

Retina, 50 bytes

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

Input as a list of comma-separate unary numbers.

Try it online!

Explanation

$
,$`

Duplicate the input so we can check steps that wrap around the end.

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

Match and return each (shortest) section between two identical values, e.g. 11,111,1,11.

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

Repeatedly remove a digit from the first number, together with an entire number after it. If the gap is small enough this will completely remove the first number. Otherwise, at least one digit will remain.

M`1,

Count how often 1, appears in all the lines. If it appears anywhere, one of the steps was too wide.

^0

Try to match a number starting with 0 (i.e. only 0 itself). This is effectively a logical negation of the output.

Answer 9

JavaScript (ES6), 47 bytes

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

How it works

We re-use the input array a to store the position of the last encountered occurrence of each integer in a. We use the key -n to store this position so that it does not interfere with the original indices of a.

When a[-n] exists, the actual test occurs. When a[-n] doesn't exist, the expression a[-n] - (a[-n] = i) equals undefined - i == NaN and the comparison with ~n is always falsy, which is the expected result.

Test cases

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

Answer 10

Retina,  41 39 bytes

2 bytes golfed thanks to Martin Ender, which by the way introduced me to balancing groups with his fantastic guide on SO

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

^$

Input is a comma-separated list of unary numbers. Output is 0 for false and 1 for true.

Try it online! (Test suite that automatically converts from decimal)

I've recently learned about balancing groups, so I wanted to give them a try. They're not among the easiest tools to use, but sure they are powerful.

Explanation

$
,$`,

As many other submissions do, we duplicate the list to deal with wrapping. We also add a comma at the end, so every number is followed by a comma (this makes things a bit easier later)

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

Here's where things get interesting. This is a replacement stage, we replace everything matched by the first line with the second line, in this case we are looking to remove all numbers n not followed by n+1 other different numbers.

To do so, we first match the number, capturing each 1 in a group (capturing group number 2 in this case). Then with a positive lookahead, in order to have a zero-width assertion, we repeatedly try to match in a balancing group -2, that will succeed no more than the number of captures made by group 2, a number followed by a comma. After this sequence of numbers, we are satisfied if we reach either the first number again or the end of the line.

Note: this expression could match just the final part of a number, if it doesn't manage to find a match with the full number. This is not a problem, because then the first part of the number will remain in the string and we will know that the replacement didn't completely succeed.

^$

Finally, the result should be truthy iff we have completely removed all numbers from the list. We try to match the empty string and return the number of matches found.

Answer 11

Jelly, 11 bytes

ẋ2ĠṢI_2<"QȦ

Try it 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.

Answer 12

Python 3, 101 bytes

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

Try it online!

Answer 13

Röda, 50 bytes

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

Try it online!

Finally! I have been waiting for this challenge...

It's a function that returns a truthy or a falsy value. It takes one argument, the array.

It iterates over a stream of indices and checks for each index _1 that the distance of the current index and the next index of a[_1] is not more than a[_1].

Answer 14

Vyxal, 10 bytes

ƛ?=T¯‹≤A;A

Try it Online!

ƛ       ;A # Does every value have the property that...
       A   # All of...
    ¯      # The differences between...
 ?=T       # Indices of that value in the input
     ‹     # Minus 1
      ≤    # Are at most that value?

Answer 15

05AB1E, 13 bytes

Dì©v®¦©yky›_P

Try it online! or as a Test suite

Explanation

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