Rubik's Snakes! (Part 1)

Question

The Rubik's Snake (or Rubik's Twist) is a toy consisting of several triangular prisms strung together in a line in such a way that the pieces can be rotated about one another in 90 degree turns.

Any snake can be described by an ordered sequence of rotations (format described below). Some sequences do not describe physically possible, "valid", snakes because they would cause the pieces to self-intersect. Some sequences describe "cyclic" snakes, which happens when the open square faces of the first and last piece of the snake meet.

Given a sequence of rotations, your task is to output whether the snake is "valid" and output whether the snake is "cyclic".

Input

A sequence of length n-1 describes a snake with n pieces. The index of the sequence describes the state of the interface between two pieces at that index, i.e., how those two pieces are rotated. Any alphabet with 4 letters can be used to describe the possible rotations.

Here we will use:

• 0 - No rotation
• 1 - 90 degree rotation
• 2 - 180 degree rotation
• 3 - 270 degree rotation

Note that this implies some chirality. For the demos below I use a left-hand rule but the choice is arbitrary as long as you are consistent.

Here are some basic examples:

00000000000 - A straight, unfolded Rubik's Mini Snake (12 pieces)

0220 - A simple 5 piece snake

   

11111111111111111111111 - A Rubik's Snake (24 pieces) consisting only of 90 degree clockwise turns

13131 - A "cyclic" snake that mixes clockwise and counterclockwise turns

20220200022020020220002 - A classic Rubik's Snake dog design without symmetry

222 - The shortest "cyclic" snake

13133311131333111313331 - A more elaborate "cyclic" design on the Rubik's Snake

0022200 - Not a "valid" snake because it self-intersects

00031310000 - A more elaborate invalid snake

   

0003131000313 - Snakes which are not "valid" may still be "cyclic"

   

2222222 - Another invalid snake which is still "cyclic" (deceptively similar to 222, which is valid)

The first image is the "Twin Peaks" pattern as found on Wikipedia (the pattern was found there, the images here are my original work). It is described by 10012321211233232123003 and is both "valid" and "cyclic".

Finally, a bonus 240 piece Rubik's Snake (yes, they actually sell these) 01113133131131331311313330020013000000310000003100000013000000130022031000013211001302020031002203100001300001300003121102022011001300130031001300310031001121300003323100000013211000031000031000220000130000003100000031002022022031233213002

Caveats

• By default, the input is a string consisting of 0s, 1s, 2s, and 3s
• Must be able to handle all sequences of length 3 or greater (n >= 4)
• If it is more practical or golf-able to handle a list of characters or a list of integers 0 thru 3, you may do so as long as it is consistent. Just be sure to specify in your answer.

Output

Given a sequence as described above, your program should ouput whether the sequence describes a snake that is:

• "valid" and "cyclic" ([true, true])
• "valid" but not "cyclic" ([true, false])
• not "valid" but "cylcic" ([false, true])
• not "valid" and not "cyclic" ([false, false])

Caveats
The format of your output need not be exactly [bool, bool], as long as:

• There are exactly 4 possible outputs
• Each possible output uniquely corresponds exactly 1-to-1 with [true, true], [true, false], [false, true], [false, false] for [valid, cyclic]
• Your chosen format is consistent for each input
• Standard loopholes. Ask for clarification in comments

For example, if you want your outputs to be "alice", bob, 37, [], you may do so as long as you specify what that means in your answer.

Examples

INPUT=====================+=OUTPUT==========
Sequence                  | Valid  | Cyclic
==========================+========+========
00000000000               | true   | false
0220                      | true   | false
11111111111111111111111   | true   | false
13131                     | true   | true
20220200022020020220002   | true   | false
222                       | true   | true
13133311131333111313331   | true   | true
0022200                   | false  | false
00031310000               | false  | false
0003131000313             | false  | true
2222222                   | false  | true
10012321211233232123003   | true   | true
                          |        |
0111313313113133131131333 |        |
  00200130000003100000031 |        |
  00000013000000130022031 |        |
  00001321100130202003100 |        |
  22031000013000013000031 | true   | true
  21102022011001300130031 |        |
  00130031003100112130000 |        |
  33231000000132110000310 |        |
  00031000220000130000003 |        |
  10000003100202202203123 |        |
  3213002                 |        |
==========================+========+========

---

This is code-golf, so shortest answer wins!

Answer 1

Python 2, 217 212 198 194 bytes

from numpy import*
A=any
d,t,_=eye(3)
p=b=t
v=0
S=[]
for m in input():S+=(p,d,t),;exec"t=cross(t,d);"*m;p,d,t=p+d,t,d;v|=A([all(p==P)*A([d+D,t+T])*A([d-T,t-D])for P,D,T in S])
print v,A([p,d-b])

Try it online! or Verify all test cases!

-6 bytes thanks to @dingledooper!

Input: A list of integers from STDIN
Output: A number and a boolean, printed to STDOUT.
The number is 0 if the snake is valid, 1 otherwise.
The boolean is False if the snake is cyclic, True otherwise.

Big idea:

Each snake piece fits exactly into half of a unit cube in a 3D grid. There are 12 possible orientations of a piece, corresponding to 6 ways of slicing a cube in half diagonally.

Thus, each snake piece can be characterized by the x, y, z coordinates of the cube containing it, and the orientation of the piece within the cube.

Now that we have a way to store each piece's info, we can build the snake, then detect self-intersection and cycle.

If 2 pieces occupy the same cube, they intersect unless the 2 pieces are exactly opposite of each other in the cube:

_{Example orientations that can coexists within the same cube. Image taken from here}

Details

Snake building

A simple way to characterize the orientation of a piece is with 2 directions: the "in" direction \$t\$, and "out" direction \$d\$. \$d\$ and \$t\$ are always axis-aligned (since they are always perpendicular to a face of a cube).

For each piece, we store the cube position \$p\$ and the 2 directions \$d, t\$. This makes it easy to figure out the position and orientation of the next piece. Consider the piece \$(A)\$ in the figure above. If the move is \$0\$ (no turn), then the next piece will be \$(B)\$. If the move is \$(1)\$ (90 degree turn), then the next piece will be \$(C)\$. We can see that if the current piece is \$(p_1, d_1, t_1)\$ and the number of turns is \$m\$, then the next piece is: $$ p_2 = p_1 + d_1 $$ $$ t_2 = d_1 $$ $$ d_2 = t_1 \text{ rotated } m \text{ times around } d_1 $$

Cycle detection

If the snake is cyclic, then the last and first piece must be connected. This means that the "out" direction of the last piece must be the same as the "in" direction of the first piece, and their coordinates must be adjacent in that direction.

If the first piece has the default value: \$p=(0,0,0), t=(0,1,0)\$, then the last piece must have the value: \$p=(0,-1,0), d=(0,1,0)\$.

Self-intersection detection

If 2 pieces intersect each other, then the following must be true:

• They are in the same cube: \$p_1 = p_2\$
• Their orientations are not opposite of each other.

The orientations of 2 pieces are opposite of each other when one of the following happens:

• \$d_1 = -d_2\$ and \$t_1 = -t_2\$
• or \$d_1 = t_2\$ and \$t_1 = d_2\$