17
\$\begingroup\$

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.

Task

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]
\$\endgroup\$
6
  • \$\begingroup\$ Related OEIS sequence \$\endgroup\$ – Arnauld Feb 24 '20 at 9:53
  • \$\begingroup\$ I'd find it more circular if also \$b_n\$ was defined in the obvious way. \$\endgroup\$ – Christian Sievers Feb 24 '20 at 11:42
  • \$\begingroup\$ Do the permutations 135642, 135624, 135462, 135426, 153462, 153426, 153264 and 153246 all have the same step sequence 22122? \$\endgroup\$ – Neil Feb 24 '20 at 16:33
  • 2
    \$\begingroup\$ 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\$. \$\endgroup\$ – Lynn Feb 24 '20 at 22:49
  • 1
    \$\begingroup\$ 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\$. \$\endgroup\$ – xnor Feb 27 '20 at 3:07

18 Answers 18

8
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Really cool solution... \$\endgroup\$ – RGS Feb 24 '20 at 15:06
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Indeed I do not, thanks! \$\endgroup\$ – Jonathan Allan Feb 27 '20 at 21:11
2
\$\begingroup\$

Japt, 11 bytes

õ á d_äa eV

Try it

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

Wolfram Language (Mathematica), 84 bytes

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

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ What does the @@@ do? \$\endgroup\$ – RGS Feb 24 '20 at 22:37
  • \$\begingroup\$ @RGS f@@@expr or Apply[f,expr,{1}] replaces heads at level 1 of expr by f. \$\endgroup\$ – ZaMoC Feb 25 '20 at 9:16
2
\$\begingroup\$

05AB1E, 13 bytes

Lœ€üαD¹αÅLJIå

Try it online!

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ 94 bytes \$\endgroup\$ – RGS Feb 25 '20 at 9:04
2
\$\begingroup\$

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!

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ Very nice. You are missing the f= for a recursive function though. \$\endgroup\$ – Jonathan Allan Feb 27 '20 at 21:14
2
+150
\$\begingroup\$

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?
\$\endgroup\$
2
+50
\$\begingroup\$

Scala, 88 82 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!
\$\endgroup\$
2
  • \$\begingroup\$ 70 bytes by using underscore and toSet. (Btw, there's something wrong with your current TIO link) \$\endgroup\$ – user Nov 25 '20 at 16:55
  • \$\begingroup\$ 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. \$\endgroup\$ – user Nov 25 '20 at 17:02
1
\$\begingroup\$

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.

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

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!

\$\endgroup\$
1
  • \$\begingroup\$ Really cool way of defining r to be the range! \$\endgroup\$ – RGS Feb 24 '20 at 23:47
1
\$\begingroup\$

Python 3, 120 115 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!

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

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?

\$\endgroup\$
2
  • \$\begingroup\$ 17 bytes. You don't need 1+ since it doesn't affect the adjacent differences, and you can refactor the duplicated i. using &. \$\endgroup\$ – Bubbler Feb 25 '20 at 0:53
  • \$\begingroup\$ Excellent edits. Thank you very much! \$\endgroup\$ – Jonah Feb 25 '20 at 1:25
0
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ You can use lambda and any to lower the byte count to 118. Try it online! \$\endgroup\$ – Surculose Sputum Feb 24 '20 at 17:52
  • \$\begingroup\$ @SurculoseSputum Snap, was just posting a 119 byte version of that \$\endgroup\$ – Noodle9 Feb 24 '20 at 17:58
  • \$\begingroup\$ @SurculoseSputum Clever rejig of the equality/for loop - thanks! :-) \$\endgroup\$ – Noodle9 Feb 24 '20 at 18:02
0
\$\begingroup\$

Charcoal, 41 bytes

⬤EX²LθE⊕Lθ﹪∨ΣE…◧⍘ι²Lθλ×∨Σλ±¹§θμ⁰⊕Lθ⊙ι⊖№ιλ

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

EX²Lθ

Outer loop to 2ⁿ⁻¹ (exclusive).

E⊕Lθ

Inner loop to n (exclusive)

…◧⍘ι²Lθλ

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

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

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

﹪∨Σ...⁰⊕Lθ

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.

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

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

Try it online!

See all possible permutations: Try it online!

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