# Is this a circular step sequence?

## Background

We define a circular step sequence of order $$\n\$$ as follows:

$$a_1, a_2, \dots, a_n = \text{Permutation of } 1 \dots n \\ b_i = \min ( |a_{i+1} - a_i|, n-|a_{i+1} - a_i| ), 1 \le i < n \\ \text{Circular step sequence} \stackrel{\text{def}}{=} b_1, b_2, \dots, b_{n-1}$$

Informally, it is the $$\n-1\$$ distances between $$\n\$$ points evenly spaced on a circle, given a permutation of those points.

For example, if we choose a permutation $$\1, 3, 6, 2, 4, 5 \$$ for $$\n = 6\$$, we get a circular step sequence of $$\2, 3, 2, 2, 1\$$. (Refer to the circular layout below.)

 1 2
6   3
5 4


On the other hand, a circular step sequence of order 6 cannot have a substring of $$\2, 2, 2\$$. Regardless of where you start and in which direction you go first, you'll get stuck at the third 2.

Given the value of $$\n\$$ and a sequence $$\b_1, b_2, \dots, b_{n-1}\$$ of positive integers, determine if the given sequence can be a circular step sequence of order $$\n\$$, i.e. there exists a permutation $$\a_1, \dots, a_n\$$ which leads to the given sequence $$\b\$$.

## Input and output

The elements $$\b_i\$$ of the input sequence are guaranteed to satisfy $$\ 1 \le b_i \le n/2 \$$ and $$\ b_i \in \mathbb{Z}^+ \$$. Also, you can assume $$\n \ge 1\$$. If $$\ n = 1 \$$, the only possible $$\b\$$ is a zero-length sequence. You can omit the number $$\n\$$ from the input.

For output, you can use truthy/falsy values for your language (swapping is allowed). If such a convention is not defined, you can use two distinct values to represent true/false respectively.

## Scoring and winning criterion

Standard rules apply. The shortest code measured in bytes wins.

## Test cases

### True

1, []              # permutation: [1]
2, [1]             # permutation: [1, 2]
3, [1, 1]          # permutation: [1, 2, 3]
4, [1, 1, 1]       # permutation: [1, 2, 3, 4]
4, [1, 2, 1]       # permutation: [1, 2, 4, 3]
4, [2, 1, 2]       # permutation: [1, 3, 2, 4]
5, [1, 2, 2, 1]    # permutation: [1, 2, 5, 3, 4]
6, [2, 3, 2, 2, 1] # permutation: [1, 3, 6, 2, 4, 5]


### False

4, [2, 2, 1]
5, [2, 2, 1, 1]
6, [1, 2, 2, 2, 3]
6, [3, 2, 1, 1, 2]
7, [2, 2, 3, 1, 2, 2]

• Related OEIS sequence Feb 24, 2020 at 9:53
• I'd find it more circular if also $b_n$ was defined in the obvious way. Feb 24, 2020 at 11:42
• Do the permutations 135642, 135624, 135462, 135426, 153462, 153426, 153264 and 153246 all have the same step sequence 22122?
– Neil
Feb 24, 2020 at 16:33
• From the other perspective, $b_1, \dots, b_{n-1}$ is a CSS iff you can choose signs $s_1, \dots, s_{n-1} \in \{-1, 1\}$ such that the $n$ partial sums of $0 + s_1b_1 + s_2b_2 + \dots$ considered modulo $n$ are a permutation of all the members of $\mathbb{Z}_n$.
– Lynn
Feb 24, 2020 at 22:49
• As a consequence of @Lynn's observation, the partial sums are a permutation of $Z_n$ exactly if no two are the same modulo $n$, which means that no infix has $s_i b_i + s_{i+1} b_{i+1} + \cdots + s_{j} b_{j} = 0 \bmod n$.
– xnor
Feb 27, 2020 at 3:07

# JavaScript (ES7),  99 79 74  72 bytes

Takes input as (n)(b). Returns a Boolean value.

n=>g=([d,...b],x=0,m=2**n-2)=>d?[x+d,x-d+n].some(y=>g(b,y%=n,m^1<<y)):!m


Try it online!

### How?

Instead of using an array for $$\a_i\$$, we use a bitmask $$\m\$$ initialized to $$\2^n-2\$$ and a bit pointer $$\x\$$ initialized to $$\0\$$ (i.e. pointing to the least significant bit).

For instance: for $$\n=4\$$, we start with $$\m=4^2-2=14=1110_2\$$. Because the LSB is our starting position, it is cleared right away to mark it as visited.

The main part of the code is a recursive search in a binary tree: for each $$\b_i\$$, we move the bit pointer to either $$\x+b_i\$$ or $$\x-b_i\$$ (wrapping around modulo $$\n\$$) and toggle the bit at the new position in $$\m\$$.

We have $$\m=0\$$ on a leaf node iff all positions have been reached exactly once.

# Jelly, 9 bytes

Œ!Iæ%H{Aċ


Try it online!

A dyadic link taking $$\n\$$ as its left argument and the input sequence $$\b\$$ as its right argument. Returns a truthy value (positive integer) for True and a falsy value (zero) for False.

## Explanation

Œ!        | Permutations of 1..n
I       | Differences (vectorises)
æ%H{   | Symmetric mod half of n (for n=6, [-5,-4,-3,-2,-1,0,1,2,3,4,5] will map to [1,2,3,-2,-1,0,1,2,3,-2,-1])
A  | Absolute
ċ | Count occurrences of b

• Really cool solution...
– RGS
Feb 24, 2020 at 15:06

# APL (Dyalog Unicode), 28 26 bytes

⊣∊⊣{≢∪⍺|+\⍵}¨⊂⍤,×¯1*2⍳⍤⍴⍨⊣


Try it online!

TIO is only on 17.1, so I've implemented the ⍤ operator from 18.0 manually. Takes $$\n\$$ as the left argument, and the sequence as the right.

### Explanation

                 ¯1*2⍳⍤⍴⍨⊣    ⍝ Get all possible combinations of ¯1 1 with length n
⊂⍤,×             ⍝ Multiply it by n concatenated with the array (it doesn't matter what the starting value is)
⊣{       }¨                 ⍝ Map each to
+\⍵                   ⍝ The cumulative sum
⍺|                      ⍝ Modulo n
≢∪                        ⍝ Then get the number of unique values
⊣∊                            ⍝ Is one of these n?


# Python 3,  90  89 bytes

-1 thanks to FryAmTheEggman

f=lambda n,a,v=[0]:a and any(f(n,a[1:],[(v[0]+x*a[0])%n]+v)for x in(-1,1))or len({*v})==n


Try it online!

• Indeed I do not, thanks! Feb 27, 2020 at 21:11

# Japt, 11 bytes

õ á d_äa eV


Try it

# Wolfram Language (Mathematica), 84 bytes

(y=#;!FreeQ[(x=#;Abs[#-#2]&@@@Array[x[[{#,#+1}]]&,y-1])&/@Permutations@Range@y,#2])&


Try it online!

• What does the @@@ do?
– RGS
Feb 24, 2020 at 22:37
• @RGS f@@@expr or Apply[f,expr,{1}] replaces heads at level 1 of expr by f. Feb 25, 2020 at 9:16

# 05AB1E, 13 bytes

Lœ€üαD¹αÅLJIå


Try it online!

# Python 3, 100 bytes

f=lambda n,b,i=[0]:b and(f(n,b[1:],[(i[0]+b[0])%n]+i)+f(n,b[1:],[(i[0]-b[0])%n]+i))or len(set(i))==n


Try it online!

Returns a non-zero integer (n>1) / True (n==1) for True and False for False.

Explanation

i is the list of visited numbers in reverse order. At each step of the recursion, we remove the first entry of b, move either forwards or backwards by the corresponding amount (modulo n) and append the new position at the 0th position of i. Terminates when b=[], for which the function evaluates to True if i has exactly n distinct numbers and False otherwise.

• 94 bytes
– RGS
Feb 25, 2020 at 9:04

# Ruby, 99 81 71 bytes

f=->n,s,w=[0]{w[-n]||(a=s.pop)&&[a,-a].any?{|g|f[n,s,w|[(w[-1]+g)%n]]}}


Try it online!

# Python, 77 bytes

f=lambda n,l,m=1:all(f(n,l[1:],m<<d*l[0]|1)for d in[1,n-1])if l else m%~-2**n


Try it online!

Outputs True/False swapped.

The idea to store visited values as a bitmask is from Arnauld.

But, instead of storing our current position on the tape of bits and updating it after we move, we simply move the whole tape so that we're located at the end. We treat the tape as unrolled, so that every n-th position is the same, and we always move the tape left with << by converting each rightwards move to an equivalent leftwards move modulo n.

In the end, we collapse the tape to its last n positions by taking the numerical value modulo 2**n-1. The only way to get a result of zero is if every position modulo n was hit exactly once.

• Very nice. You are missing the f= for a recursive function though. Feb 27, 2020 at 21:14

# Scala, 8882 80 bytes

n=>d=>1.to(n).permutations.map(l=>(l.zip(l.tail)).map(_-_)map(_.abs))contains(d)


Try it online!

• -6 thanks to user!
• 70 bytes by using underscore and toSet. (Btw, there's something wrong with your current TIO link)
– user
Nov 25, 2020 at 16:55
• I think the problem is l.zip(l.tail), since it returns a list of tuples, and you can't call map(_-_) on that unless you're using Scala 3/Dotty.
– user
Nov 25, 2020 at 17:02

# K (ngn/k), 29 bytes

{|/x=#'?'+x!+\-1 1[!x#2]*x,y}


Try it online!

Takes n as x and b (the sequence) as y. A port of @Jo King's APL answer.

• -1 1[!x#2] generate all combinations of -1 and 1 with length n
• *x,y multiply these by n prepended to the sequence b
• x!+\ take the column-wise cumulative sums, mod'ing them by n
• + transpose the result
• #'?' calculate the number of distinct values in each row
• |/x= are any of those equal to n?

# Python 2, 101 bytes

lambda n,b:n in map(len,map(set,reduce(lambda Q,k:[q+[(q[-1]+v)%n]for q in Q for v in-k,k],b,[[0]])))


Try it online!

Returns True/False if b is/isn't a circular set sequence.

# Python 3, 101 bytes

lambda n,a,r=range:n in(len({sum([a[j]*(k>>j&1or-1)for j in r(i)])%n for i in r(n)})for k in r(1<<n))


Try it online!

• Really cool way of defining r to be the range!
– RGS
Feb 24, 2020 at 23:47

# Python 3, 120115 90 bytes

f=lambda n,l,x=0,m=0:all(f(n,l[1:],y%n,m^1<<y%n)for y in[x+l[0],x-l[0]])if l else m-2**n+2


You can try it online! Outputs False for CSS and True otherwise.

This is a port of Arnauld's answer (who saved me almost 20 bytes!). Go upvote his answer because it looks better than this one!

# J, 21 17 bytes

e.2|@-/\"1!A.&i.]


Try it online!

-4 bytes thanks to Bubbler

Literal translation of the question: Is the given list and element of e. the adjacent differences of every possible perm?

• 17 bytes. You don't need 1+ since it doesn't affect the adjacent differences, and you can refactor the duplicated i. using &. Feb 25, 2020 at 0:53
• Excellent edits. Thank you very much! Feb 25, 2020 at 1:25

# Python 3.8 (pre-release), 137 $$\\cdots\$$ 119 118 bytes

Saved a byte thanks to Surculose Sputum!!!

lambda n,b:any(b==[min(i:=abs(a-b),n-i)for a,b in zip(p,p[1:])]for p in permutations(range(n)))
from itertools import*


Try it online!

• You can use lambda and any to lower the byte count to 118. Try it online! Feb 24, 2020 at 17:52
• @SurculoseSputum Snap, was just posting a 119 byte version of that Feb 24, 2020 at 17:58
• @SurculoseSputum Clever rejig of the equality/for loop - thanks! :-) Feb 24, 2020 at 18:02

# Charcoal, 41 bytes

⬤ＥＸ²ＬθＥ⊕Ｌθ﹪∨ΣＥ…◧⍘ι²Ｌθλ×∨Σλ±¹§θμ⁰⊕Ｌθ⊙ι⊖№ιλ


Try it online! Link is to verbose version of code. Outputs - only if the input is not a circular step sequence. Explanation:

ＥＸ²Ｌθ


Outer loop to 2ⁿ⁻¹ (exclusive).

Ｅ⊕Ｌθ


Inner loop to n (exclusive)

…◧⍘ι²Ｌθλ


Convert the outer loop index to binary with n-1 digits, but only take the first inner loop index bits.

Ｅ...×∨Σλ±¹§θμ


Replace the 1 bits with the values from the input and the 0 bits with the negated values respectively.

﹪∨Σ...⁰⊕Ｌθ


Take the sum modulo n. Because only the first inner loop index bits were used, each result takes one more bit into account, resulting in a list of the partial sums of the possibly negated values.

⬤...⊙ι⊖№ιλ


Check that all resulting lists contain duplicate elements. This will be true if the input is not a circular step sequence.

# Wolfram Language (Mathematica), 54 bytes

Or@@(0!=##&@@@Mod[Accumulate/@Tuples[{#,-#}&/@#2],#])&


Try it online!

See all possible permutations: Try it online!