An Ant on a Cube

Question

An ant walks along the edges (not faces) of a wireframe cube. Each vertex it encounters presents it with a fork from which two new edges branch off. The ant chooses which way to turn -- left or right. These direction are relative to the ant, who is facing the vertex and is outside the cube. Your goal is to determine, from the sequence of left/right choices the ant took, whether it ends at the same position that it started.

For example, if the ant turns left four times (left left left left), it will have traversed a square counterclockwise and ended at the same place it started. But, if it goes left left left left right, it will end on a different spot on the cube. Also, if it goes left right right right left, it ends on its starting edge but facing the opposite vertex, which does not count as the same position.

The ant's path might repeat edges, including the edge it started at, but what matters is where it ends after the whole sequence.

Write a named function that takes in the ant's sequence of turns and outputs whether the ant is back at its start position after the sequence. Assigning an unnamed function to a variable is enough to make it a named function.

(Edit: If your language can't make a named function, it can instead implement the function with inputs and outputs through STDIN/printing or the stack. If that's not possible, make it a snippet in which the input and output are saved in variables.)

Input

A sequence of left/right decisions of length 0 to 31 inclusive, represented in a format of your choice. This might be a string of letters R/L, a list of numbers 1/-1, or an array of Booleans. Nothing cheesy like having them be method names or strings useful for your code.

Please post the test cases in your format if it's different from the test cases below.

Output

True/False, 0/1, or the analogues in your language.

Winning criteria

Fewest bytes wins. Remember, you need to give a named function. You can have code outside the function, but those bytes count too. Your function should behave correctly if called multiple times.

Test cases

True cases (one per line, second one is empty list):

1 1 1 1

-1 -1 -1 -1
1 -1 1 -1 1 -1
1 1 -1 -1 1 1 -1 -1
-1 1 1 -1 -1 1 1 -1
1 1 1 -1 -1 -1 -1 1
1 -1 -1 1 -1 -1
1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1
-1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

False cases (one per line):

1
1 1
1 1 1
-1 1
1 -1 -1 -1 1
1 -1 -1 1 1
-1 1 -1 1
1 1 1 1 -1
-1 -1 1 -1 1 -1 -1 1
1 -1 1 1 1 1 -1 -1 -1 1 1 -1 -1 -1

Here's the same test cases with L's and R's.

True cases:

RRRR

LLLL
RLRLRL
RRLLRRLL
LRRLLRRL
RRRLLLLR
RLLRLL
RRRRLLLLRLLRLL
LLLRLLRRLRLRRRRRRRRRRRRRRRRR

False cases:

R
RR
RRR
LR
RLLLR
RLLRR
LRLR
RRRRL
LLRLRLLR
RLRRRRLLLRRLLL

Extra credit challenge

Same thing, but with a dodecahedron rather than a cube. See Hunt the Wumpus for ideas.

Answer 1

GolfScript, 24 chars (19 for function body only)

Math FTW!

{3,.@{[+~@\{@}*~]}/=}:f;

Test this solution online.

This function takes as input a binary array (0 for left, 1 for right) and returns 1 for true and 0 for false.

Conceptually, it works by rotating the cube so that the ant always maintains the same position and orientation, and checking whether the cube finally ends up in the same orientation as it began in.

In particular, we can represent the left and right turns as two linear maps in three dimensions, where a left turn corresponds to a 90° rotation around the x axis, i.e. the map (x, y, z) → (x, z, −y), and a right turn corresponds to a 90° rotation around the y axis, i.e. the map (x, y, z) → (z, y, −x).

At the beginning of the function, we simply set up a three-element vector containing the distinct positive values (1, 2, 3), apply the sequence of rotation maps to it, and check whether the resulting vector equals the initial one.

(In fact, to save a few chars, I actually transform the coordinates so that the initial vector is (0, 1, 2) and the maps are (x, y, z) → (x, z, −1−y) and (x, y, z) → (z, y, −1−x), but the end result is the same.)

Ps. Thanks to proud haskeller for spotting the bug in the original version of this solution.

---

Perl, 58 chars

As requested in the comments, here's the same solution ported to Perl. (This version actually uses the untransformed coordinates, since the transformation saves no chars in Perl.)

sub f{@a=@b=1..3;@a[$_,2]=($a[2],-$a[$_])for@_;"@a"eq"@b"}

Test this solution online.

---

Bonus: Ant on a Dodecahedron (GolfScript, 26 chars)

{5,.@{{2*2%[~\]}*(+}/=}:f;

Test this solution online.

Like the ant-on-a-cube function above, this function takes as input a binary array (0 for left, 1 for right) and returns 1 if the ant ends up at the same position and orientation as it started in, or 0 otherwise.

This solution uses a slightly more abstract representation than the cube solution above. Specifically, it makes use of the fact that the rotational symmetry group of the dodecahedron is isomorphic to the alternating group A₅, i.e. the group of even permutations of five elements. Thus, each possible rotation of the dodecahedron (that maps edges to edges and vertices to vertices) can be uniquely represented as a permutation of a five-element array, with consecutive rotations corresponding to applying the corresponding permutations in sequence.

Thus, all we need to do is find two permutations L and R that can represent the left and right rotations. Specifically, these permutations need to be 5-cycles (so that applying them five times returns to the original state), they must not be powers of each other (i.e. R ≠ Lⁿ for any n), and they need to satisfy the relation (LR)⁵ = (1), where (1) denotes the identity permutation. (In effect, this criterion states that the path LRLRLRLRLR must return to the original position.)

Fixing the L permutation to be a simple barrel shift to the left, i.e. mapping (a, b, c, d, e) → (b, c, d, e, a), since it can be implemented in GolfScript in just two chars ((+), we find that there are five possible choices for the R permutation. Out of those, I chose the mapping (a, b, c, d, e) → (c, e, d, b, a), since it also has a relatively compact GolfScript implementation. (In fact, I implement it by first interleaving the elements with 2*2% to obtain (a, c, e, b, d), then swapping the last two elements with [~\], and finally applying the L permutation unconditionally to move a to the end.)

The online demo link above includes some test cases of valid paths on a Dodecahedron that return to the origin, such as:

           # empty path
1 1 1 1 1  # clockwise loop
0 0 0 0 0  # counterclockwise loop
1 0 0 0 0 1 1 0 0 0 0 1  # figure of 8
1 0 1 0 1 0 1 0 1 0      # grand circle
1 0 0 0 1 0 0 0          # loop around two faces 
1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 0  # Hamilton cycle

Answer 2

Python, 68

Takes a list of 1 and -1. Based on 3D rotations: checks if the point (3,2,1) ends up at the same position after applying a series of rotations. There are two possible rotations, corresponding to 1 and -1. Each one is done by permuting two coordinates and changing the sign of one of them. The exact coordinates to change and which sign to permute is not important.

def f(l):
 p=[3,2,1]
 for d in l:p[d],p[0]=-p[0],p[d]
 return[3,2]<p

EDIT: this is actually mostly the same solution as "Perl, 58".

Answer 3

C (gcc), 118 116 107 105 bytes

-2 bytes thanks to ceilingcat

f(char*s){char*p,n[]="@ABCDEFG",y;for(;*s;s++)for(p=n;*p;*p++^=*s^82?y%2+1:4-(y&2))y=*p/2^*p;y=n[2]==66;}

Try it online!

Suppose we gave the cube the following coordinates:

            (1,1,1)       (1,1,0)
          G +--------------+ C
           /|             /|
          / |            / |
         /  |    (0,1,0)/  |
(0,1,1) +--------------+ D |
      H |   |          |   |
        |   |          |   |
        | F +----------|---+ (1,0,0)
        |  /(1,0,1)    |  / B           x
        | /            | /           y / 
        |/             |/            |/  
      E +--------------+ A      z ---*   
        (0,0,1)       (0,0,0)

If we start on corner D, then moving to C or H can be thought of as rotating the cube around us instead. Moving right would mean rotating counter-clockwise around the Z axis, and moving left would mean rotating clockwise around the X axis. These are the only two rotations we need to care about. Since each rotation is exactly 90 degrees, we can imagine the corners "sliding" along the edges. For moving right, this means A -> B, B -> C, C -> D, D -> A with the other side doing E -> F etc. For moving left, we instead get A -> E, E -> H etc.

Since each corner only slides along an edge, that means only one of the dimensions of each point changes for each rotation. When B moves to C, only its y component changes, and when H moves to D, only its z component changes, and so on. Furthermore, since the coordinates are restricted to 0 and 1, we can think of each point as a binary number, with the appropriate bit flipped upon movement.

We can see that for a movement to the right, A and C flip their x's, while D and B flip their y's. If we change perspective to look on that side of the cube head on, and ignore the z component (which does not change for this rotation anyway) we get:

D (0,1)         C (1,1)
 +-------------+
 |             |
 |             |
 |             |
 |             |
 |             |
 |             |
 +-------------+
A (0,0)         B (1,0)

A pattern emerges: For the points that flip their x, x == y, while the opposite is true for the points flipping their y's. This holds for the other type of rotation, but with z instead of x.

In other words:

Right
    if (x == y) x = !x
    if (x != y) y = !y

Left
    if (z == y) z = !z
    if (z != y) y = !y

Now we can easily go through all the rotations, and at the end see if the final D matches our initial D.

Storing each point as a single number is a given, but in C, assigning a char array is that much more compact than an int array. We take care to choose characters whose lower three bits match 000..111, making it possible to just ignore the rest of the bits. Flipping the coordinates is simply a matter of XOR'ing with the appropriate bitmask.

Answer 4

Mathematica

Inspired by Ilmari Karonen's solution. The rotational symmetry group of a cube is isomorphic to S₄.

Cube, 51 bytes

Fold[Part,r=Range@4,{{2,3,4,1},{3,4,2,1}}[[#]]]==r&

Takes a list of 1s and -1s as input.

Try it online!

Dodecahedron, 55 bytes

Fold[Part,r=Range@5,{{2,3,4,5,1},{3,5,4,2,1}}[[#]]]==r&

Takes a list of 1s and -1s as input.

Try it online!

Answer 5

Python 2, 57 bytes

f=lambda l:reduce(lambda n,x:n%4*64+n/4*16**x%63,l,27)<28

Try it online!

This uses the permutation representation

0: abcd -> dabc
1: abcd -> dcab

where left and right (0 and 1) correspond to length-4 cycles on 4 elements. We iterate over the input applying the indicated permutation, and check if the outcome equals the initial value.

We start a,b,c,d as the four-element list 0,1,2,3. We compact them into a single base-4 number n=abcd, with initial value n=27 corresponding to 0123 in base 4. We instantiate each the permutation arithmetically on n.

Since both results start with d, we can do n%4 to extract d, then n%4*64 to move it into the right position d___. The other digits are abc, extracted as n/4. We need to insert them into the lower three place values.

For direction x=0, we insert abc as is, and for x=1, we rotate them as cab. The rotation can be achieved as *16%63, which takes abc to abc00 to cab. (The %63 would go wrong on a==b==c==3, but these value aren't possible.) Since just doing %63 is a no-op, the direction-dependent expression *16**x%63 gives abc or cab as required.

---

Python 2, 55 bytes

f=lambda l:reduce(lambda n,x:n^(n*8%63|7*8**x),l,10)<11

Try it online!

Answer 6

Python - 110, 150

Takes in a list of integers with -1 for turn left, 1 for turn right.

Cube, 110:

def f(l):
    c,p='07'
    for d in l:a="100134462634671073525275"[int(c)::8];c,p=a[(a.index(p)+d)%3],c
    return'1'>c

Test:

l=map(int,'1 1 1 1'.split())
print f(l)

Dodecahedron, 150:

def f(l):
    c,p='0J'
    for d in l:a="I5H76E8BBA8F76543100JI0J21D3A5C7E9CJI2132H4GF94C6D98AHGBEDGF"[int(c,36)::20];c,p=a[(a.index(p)+d)%3],c
    return'1'>c

Answer 7

Marbelous 188

Shameless theft of Ilmari Karonen's algorithm for the purpose of showing off a new language.

This script expects a string of 0x00 for left and 0x01 for right on stdin, followed by a 0x0A (newline). It outputs "0" for a failed case and "1" for a success.

......@5@3FF
@0@1@2\\]]@5
010203@4=A@4
&0&0&0&0/\
MVMVMVMV..
@0@1@2@3..!!
:MV
}2}2}1}0}1}0}3
&0&1&0&1~~~~<A@P
{0{1{1{0&1&0=0&1
}0}1}2@P{2{2&030
=1=2=3&2FF}3..//
&2&2&231&2{3
\/\/\/&2!!..//

example run:

# echo -e "\x0\x0\x0\x1\x0\x0\x1\x1\x0\x1\x0\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1\x1" | marbelous.py ant-on-a-cube.mbl
1

Answer 8

APL (Dyalog Unicode), 22 bytes (Adám's SBCS)

f←{x∊(-@3∘⌽⌽)/⍵,x←⊂⍳3}

Try it online!

H.PWiz suggested that reversing the steps doesn't make a difference, and that resulted in -2 bytes.

Well, this is embarrassing, since it was intended to be way shorter than GolfScript. At least I tried to.

The function is named f, and, in the test cases, 1 represents a left turn (boolean true) and 0 represents a right turn (boolean false). ⍬ represents the empty list.

Answer 9

Haskell, 53 bytes

f=(<28).foldl(\n x->mod n 4*64+mod(div n 4*16^x)63)27

Try it online!

Same logic as my Python answer, even thought mod and div are longer to write.

---

Haskell, 58 bytes

r=[1..3]
f=(==r).foldl(\[x,y,z]->(!!)[[x,-z,y],[-z,y,x]])r

Try it online!

Answer 10

APL (Dyalog), 21 bytes

f←{x≡(↓∪⊢∘⌽)/⍵,x←⊂⍳4}

Try it online! (Using the testing environment from Erik the Outgolfer's answer)

I take left and right as 1 and 2. This uses the following permutations of abcd:

1 : bcda
2 : cdba

I apply the permutations corresponding to 1 and 2 to ⍳4 : 1 2 3 4, and check if it is unchanged

Answer 11

Bash, 71 65 bytes

f()(a=1234;for i;{ a=`tr 1-4 4$[$i?123:312]<<<$a`;};((a==1234));)

Try it online!

Like many previous answers, uses a representation of the group of rotations of the cube generated by 1234->4123 and 1234->4312. Uses numbers instead of letters so that I can use a ternary operator with an arithmetic expansion. Expects its input as 0's and 1's separated by spaces, and outputs via exit code.

6 bytes saved thanks to @manatwork's comment!

Answer 12

brainfuck, 119 bytes, 137 bytes

Uses the fact that the rotation group of the cube is isomorphic to \$S_4\$. Brainfuck has no functions at all, named or otherwise, so this is a full program that takes input through STDIN and outputs to STDOUT. (If you insist on a variable, pretend the value of the cell the program ends on is a variable.)

Cube, 119 bytes

++++>+++>++>+>,[+++[->+++<]<<<<[->>>>+<<<<]>[>]<+[[-]<[->+<]<<<[->>>+<<<]>[>]],]<[[<]>[->]<[>>]<]<[>>-<]-[----->+<]>--.

Try it online!

++++>+++>++>+    Initialize tape as 4 3 2 1

>,[              For each input byte:

  +++[->+++<]       Add 3 and multiply by 3; if input is R, this will be 255

  <<<<[->>>>+<<<<]  Move first number to end (BCDA)

  >[>]<+[           If input wasn't R:

    [-]                Zero input cell (which is now negative 18)

    <[->+<]            Move previously moved number one slot further (BCD_A)

    <<<[->>>+<<<]      Move first number into vacated slot (CDBA)

  >[>]]

,]

<[[<]>[->]<[>>]<]     Determine whether tape is still 4 3 2 1

<[>>-<]               If not: subtract 1 from output cell

-[----->+<]>--.       Create "1" in output cell and output

Dodecahedron, 137 bytes

+++++>++++>+++>++>+>,[+++[->+++<]<<<<<[>>>>>+[<]>-]>[>]<+[[-]<<[[->>+<<]<<]>[>>>>>>+[<]<-]>>[>]],]<[[<]>[->]<[>>]<]<[>>-<]-[----->+<]>--.

Try it online!

The only differences between the two programs are the setup and permutations. The left permutation used here is DCAEB, which seemed to be the golfiest conjugate available.

Answer 13

Haskell, 104 103 99 97 96 / 67 64 chars

I feel the equivalent of right/left would be a datatype Direction like so:

Direction = R | L

so I assumed in my answer that they were available.
edit: actually realized that booleans would lead to shorter code. True represents a left turn, and False represents a right turn (although, technically, the code would work the same if it was flipped; it's symmetric)

96 characters:

m[p,l,r]b|b=[p%l,7-r-l,r]|0<1=[p%r,l,7-r-l]
p%x|odd$div p x=p-x|0<1=p+x
g l=foldl m[0..2]l<[0,2]

g is a function that given a list of Direction would return weather of not the ant got back to its place.

explanation of representation of position: the position of the ant is coded as a three tuple of integers. the first integer represents the vertex that the ant is heading to. the first bit represents if the vertex is at the up/down half, the second is the left/right half, and the third is the back/front half. this is done so that moving from a vertex to a neighbor vertex can be done by flipping one bit.

the second integer is the amount that the ant's vertex would change if it would go left. for example, if the ant was at vertex 3, and the second integer was 4, than after turning left the vertex would be 7. note this would always be a power of 2, because exactly one bit is flipped by moving one vertex.

the third integer is the same, but for going right; i know this is can be calculated by the first two, but i don't know how to. if you got an idea, please tell me.

something to note is that when turning left, the third integer would stay the same, and the second would become the one between 1 2 and 4 that wasn't either the second integer or the third, which happens to be the same as 7 - second integer - third integer.

i chose this way of representing position because (as was just stated in the previous paragraph) it was trivial to compute the next position.

explanation of functions:

the (%) function is the function that takes the current vertex and the amount to change it, and changes it. it gets to the bit that is going to change and flips it (in a very numeric way).

the m function is a function that takes the position of the ant, and the direction, and returns the new position by using the note we noted earlier.

then the m function is combined using foldl (which is sort of like reduce in javascript, but a bit more expressive) to create the function g, the answer to this question.

---

Haskell, 64 characters

inspired by @alphaalpha's answer, here is it's version ported to haskell:

m[a,b,c,d]p|p=[b,c,d,a]|0<1=[b,d,a,c]
g l=foldl m[0..3]l<[0,1,3]

---

edit: I now feel incredibly stupid because of lmari Karonen's answer. maybe i'll port his answer to haskell. another edit: not feeling as stupid as his answer is was wrong
edit: switched from actually using tuples to using lists as their Ord instance and the [ ... ] syntactic sugar makes it shorter

Answer 14

Jelly, 14 bytes

3RðW;ṙN1¦ṚƊ/⁼⁸

Try it online!

1 = left turn, 0 = right turn. Based on my Dyalog solution.

Unfortunately, Jelly doesn't have named functions. If I can't use an implicit input and need to assume it's in a variable, this same-length version will do:

3RµW;®ṙN1¦ṚƊ/⁼

It assumes the input is in the register (©/®).

Answer 15

Perl - 120, 214

Takes an array (list) of booleans.

Cube (120):

sub e{$a=$b=0;for$c(@_){$_=(13,62,53,40,57,26,17,'04')[$b];$d=s/$a/($b-1)%8/e;($a,$b)=($b,substr($_,$c^$d,1))}return!$b}

Dodecahedron (214):

sub e{$a=$b='00';for$c(@_){$_=('01041102090307040500061807160308091502101114121019131714151016081706131819051200'=~/\d{4}/g)[$b];$d=s/$a/sprintf'%02d',($b-1)%20/e;($a,$b)=($b,substr($_,($c^$d)*2,2));}return!($b+0)}