22
\$\begingroup\$

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 , so the shortest code wins. Answers in all languages are encouraged.

\$\endgroup\$
  • \$\begingroup\$ Does the input list always contain at least one element? \$\endgroup\$ – nimi Mar 25 '17 at 12:35
  • 2
    \$\begingroup\$ @nimi otherwise it wouldn't represent an infinite periodic sequence. \$\endgroup\$ – Martin Ender Mar 25 '17 at 13:47
  • 1
    \$\begingroup\$ If you take the thue-morse sequence and add any fixed positive integer greater than 1 to each term, you'll have an aperiodic infinite sequence with this property. \$\endgroup\$ – SuperJedi224 Mar 27 '17 at 15:03

14 Answers 14

7
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Using takeWhile instead of span you can avoid pattern-matching and save three bytes Nice solution, by the way! :) \$\endgroup\$ – Leo Mar 25 '17 at 10:58
  • \$\begingroup\$ @Leo: Nice catch! Usually using span is shorter than using takeWhile, so I didn't look at it at all. \$\endgroup\$ – nimi Mar 25 '17 at 11:27
  • \$\begingroup\$ takeWhile can pretty much always be shortened to fst$span or fst.span, which saves another byte. \$\endgroup\$ – Laikoni Mar 25 '17 at 12:11
  • \$\begingroup\$ @Laikoni: yes of course! Thanks! \$\endgroup\$ – nimi Mar 25 '17 at 12:16
  • \$\begingroup\$ Love haskell ;) \$\endgroup\$ – theonlygusti Mar 25 '17 at 18:15
6
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ That inspired an 8-byte Jelly answer. :) You can save a byte like this. \$\endgroup\$ – Dennis Mar 25 '17 at 20:00
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Very nice, that's exactly what I came up with as well :-) You can create the doubled array once at the start and use .shift() to save on the slice: a=>!a.some(b=>z.indexOf(z.shift())>b,z=a.concat(a)) \$\endgroup\$ – ETHproductions Mar 25 '17 at 16:22
  • \$\begingroup\$ Hehe, great golfers think alike ;-). I thought of using shift as well, but I didn't use it, since it turned out to be longer. Creating the double array once and shifting every time is really clever. Thanks! \$\endgroup\$ – Luke Mar 25 '17 at 17:35
  • \$\begingroup\$ Would a=>!a.some((n,i)=>a.concat(a).indexOf(n,++i)>n+i) work? \$\endgroup\$ – Arnauld Mar 25 '17 at 22:34
  • \$\begingroup\$ Yes, it does. Thanks! \$\endgroup\$ – Luke Mar 25 '17 at 22:43
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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]).
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Crazy your variable names are invalid but I like it. \$\endgroup\$ – Jörg Hülsermann Mar 25 '17 at 18:22
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice work! :) There's no need for the \b. Removing it will cause stray matches but they'll fail to remove the entire number, so you won't end up with an empty string anyway. \$\endgroup\$ – Martin Ender Mar 28 '17 at 14:23
  • \$\begingroup\$ @MartinEnder You're right of course, thank you :) \$\endgroup\$ – Leo Mar 28 '17 at 14:29
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ How exactly does _1 work? \$\endgroup\$ – Kritixi Lithos Mar 25 '17 at 20:13
  • \$\begingroup\$ @KritixiLithos It's like _, but refers to the first pulled value. If I had used multiple _s, each would have pulled a separate value. For example, [1, 2, 3] | print(_, _, _) prints 123, but [1,2,3] | print(_, _1, _1) prints 111 222 333 (on separate lines). \$\endgroup\$ – fergusq Mar 25 '17 at 20:40
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.