Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

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

share|improve this question
    
Does this preclude the use of languages without named functions? –  Mike Precup Aug 9 at 18:34
    
@MikePrecup Can you give me some examples of such languages? I'll look into alternatives. –  xnor Aug 9 at 18:36
    
I do all my code golf submissions in ><>, which is why I ask. It has a stack that you can load the args onto the top of, and then leave the result on the stack, but it's not exactly a named function. –  Mike Precup Aug 9 at 19:00
    
@MikePrecup OK, I put in an allowance for that. If there still an issue for some language, please tell me, I don't want to exclude any languages. –  xnor Aug 9 at 19:07
    
I can think of befunge and ><> and this kind of languages –  proud haskeller Aug 9 at 19:24

7 Answers 7

up vote 18 down vote accepted

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 A5, 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. RLn for any n), and they need to satisfy the relation (LR)5 = (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
share|improve this answer
    
Nice solution! Does this exclude the case though where the ant returns to the same vertex from another direction? –  xnor Aug 9 at 23:33
    
I don't understand - basically what you're doing here is representing the position of the ant using 3 bits, but there are 24 possible positions. How? –  proud haskeller Aug 10 at 0:08
1  
@proudhaskeller: Thanks for spotting the bug. I've fixed it, and added your counterexample to my test suite. –  Ilmari Karonen Aug 10 at 0:53
1  
@xnor: Added a solution for the dodecahedron too. –  Ilmari Karonen Aug 11 at 0:13
1  
Nice pair of permutations for the dodecahedron. The ones I used for Hunt the Wumpus would be one char longer: {[~@]-1%}*[~@] or ){[~@]-1%}*-1% replacing your {2*2%[~\]}*(+ –  Peter Taylor Aug 11 at 9:11

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

share|improve this answer
    
You're right, It is indeed. –  proud haskeller Aug 10 at 12:14
    
+1, it's still shorter than my attempt at a Python solution. Looking at what I have, though, I think you could save a few more chars by taking the input as 0s and 1s and splitting the last element of p into a separate variable. –  Ilmari Karonen Aug 10 at 12:31
1  
Wow, I wrote the exact same solution, character for character except for variable names, when test-solving this problem! –  xnor Aug 10 at 15:00

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
share|improve this answer
1  
It's rather impressive how you wrote this in three minutes :-P –  xnor Aug 9 at 18:15
5  
Have been waiting quite some time for this boss question to spawn. ;-) –  bitpwner Aug 9 at 18:30
    
I'm getting "TypeError: expected an object with the buffer interface" when I run this in Python 3.2. –  xnor Aug 9 at 19:31
    
@xnor Edited, now in python 2. Hope it works. –  bitpwner Aug 9 at 20:16

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
share|improve this answer
1  
I didn't realize how crazy this answer is until I read the language description. That's a really cool concept for a golf language! –  xnor Aug 13 at 15:24
    
@xnor it's unlikely to ever be a serious competitor in the golf arena, but it's still somewhat fun :) –  Sparr Aug 13 at 16:07

Mathematica

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

Cube, 60 chars

c=Fold[Permute,r=Range@4,Cycles/@{{r},{{1,3,2,4}}}[[#]]]==r&

Usage:

c[{1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1, -1, -1}]

True

Dodecahedron, 62 chars

d=Fold[Permute,r=Range@5,Cycles/@{{r},{{1,3,4,2,5}}}[[#]]]==r&

Usage:

d[{1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1}]

True

share|improve this answer
    
I was searching the how can it be found that it's isomorphic to S3? –  proud haskeller Aug 26 at 12:42
    
Oops i meant "how can it be found/proved that it's isomorphic to S4? –  proud haskeller Aug 26 at 14:30
    
@proudhaskeller You can find it here: en.wikipedia.org/wiki/Octahedral_symmetry –  alephalpha Aug 26 at 15: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

share|improve this answer
1  
This looks so elegant, especially the fold. Might it save yet more chars to assign [0,1,2,3] to a variable and use it both as input to the expression and the check for the result? –  xnor Aug 26 at 23:01
    
@xnor because your comment my mind decided to come up with golfng it to [0..3] ... I don't know why i didn't notice that earlier. thanks. but now your trick doesn't work. oh well. –  proud haskeller Aug 26 at 23:07

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)}
share|improve this answer
1  
What are the magic numbers encoding? –  xnor Aug 10 at 15:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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