15
\$\begingroup\$

An ant starts on an edge of a dodecahedron, facing parallel to it. At each step, it walks forward to the next vertex and turns either left or right to continue onto one of the other two edges that meet there. A sequence of left/right choices that returns the ant to its initial state (edge and direction) is called a round trip.

Write a function (or program) that takes a string of Ls and Rs and returns (or outputs) one of two values, indicating whether the input represents a round trip.

Examples:

LLLLL -> yes
LRLRLRLRLR -> yes
RRLRRLRRL -> yes
(empty sequence) -> yes
R -> no
LLLLLL -> no (starts with a round trip but leaves initial state)
RLLLLR -> no (returns to initial edge but opposite direction)
\$\endgroup\$
8
  • 2
    \$\begingroup\$ Welcome to CGCC. This question looks good except that it's missing an objective winning criterion. You probably want code-golf? \$\endgroup\$
    – pxeger
    Sep 1 at 18:49
  • \$\begingroup\$ Thanks! That's right. Is it sufficient to just add the tag? \$\endgroup\$
    – Karl
    Sep 1 at 18:51
  • 2
    \$\begingroup\$ Ooh, I just found this old near-duplicate which asks essentially this question as bonus task. \$\endgroup\$
    – Karl
    Sep 1 at 19:21
  • 5
    \$\begingroup\$ I wouldn't worry about the old question listing this as a bonus task, given that answers to that challenge don't have to complete the bonus task, and so are less likely to be able to answer this one (plus, it's 8 years old, so we could do with a new version) \$\endgroup\$ Sep 1 at 19:47
  • 3
    \$\begingroup\$ Wow, that challenge from 2014 was the second one I ever posted! \$\endgroup\$
    – xnor
    Sep 1 at 20:21

5 Answers 5

13
\$\begingroup\$

Python 2, 79 bytes

lambda s:all(n==reduce(lambda n,c:-~[n,n%3+n%4][c>'L']%5,s,n)for n in range(5))

Try it online!

This uses the group-theoretic approach from Ilmari Karonen's GolfScript answer to my 2014 challenge, in particular to the bonus question.

Instead of the ant crawling around the dodecahedron, we imagine it stays in place while the dodecahedron turns under its feet. We must determine whether the sequence of rotations returns the dodecahedron to the initial position.

There are 60 rotation of the dodecahedron -- 12 faces times 5 positions per face. These rotations can be expressed as permutations of 5 elements. Specifically, they permute 5 colored tetrahedra shown below that partition the 20 vertices of the dodecahedron.

Five tetrahedra inside dodecahedron

We could take each rotation and write down which color tetrahedron moves onto which color's position to obtain a permutation of the five colors. Specifically, these are the even permutations, which are half of the 5!=120 permutations of five elements, or 60, forming the alternating group \$A_5\$ on five elements. The other 60 odd permutations would involve reflecting the dodecahedron and well as rotating it, so they do not figure in this problem.

We want to choose two even permutations that represent the rotations from the ant turning left and right. As noted by Ilmari Karonen, the two permutations must have order 5, corresponding to five left or five right turns brining the ant back to the same place. Moreover, their product must have order 5 as well, and neither can be a power of the other.

There are many choices for the two permutations. If we think of them as permuting the values 0 to 4, the pair our code uses is 12340 and 13042. The first one simply adds one modulo 5. From here, there's 5 choices for the other one: 13042, 14302, 24310, 32041, 32410. The code uses 13042 because it happens to have a short expression in Python 1+(n%3+n%4)%5, or just n%3+n%4 if we "share" the +1 and %5 for the other case`. I found this via some brute-forcing.

Now let's take another look at the code:

lambda s:all(n==reduce(lambda n,c:-~[n,n%3+n%4][c>'L']%5,s,n)for n in range(5))

Try it online!

To check that the sequence of permutations combines to the identity, we test each starting value n from range(5), apply the sequence of permutations to it using reduce, and check that all of them end up at the initial value. The -~ is a shortcut to add one.


74 bytes

lambda s:0in[n==reduce(lambda n,c:-~[n,48/~n][c>'L']%5,s,n)for n in 0,1,2]

Try it online!

Outputs True/False swapped.

I found 48/~n as a shorter alternative for the second permutation when it is incremented and taken mod 5.

Also, instead of checking that the permutation maps each of 0,1,2,3,4 to themselves, this only checks 0,1,2. This suffices because the map is bijective, so once 0,1,2 are fixed, 3 and 4 have to either map to themselves or swap, and because the permutation is even they can't swap.

65 bytes

S=s=`321.`
for c in input():s=(s+s[ord(c)%9:3]+s)[3:8]
print s==S

Try it online!

This uses a different mapping pair: 34012, 34120. These are nice to implement as operations on lists, moving the last two elements to the front in both cases, and for the latter cycling the last 3. To start, we just need any sequence of 5 distinct elements, so we use `321.` which equals '321.0'.

61 bytes

n=27
for c in input():n=n%16*64|n/16*4**(c>'L')%63
print n<28

Try it online!

This uses bitwise shenanigans, much like my 2018 answer with cubes. It implements the permutations 34012, 34120.

The number n encode 5 fields of bits 2 each, say abcde. Each step permutes these bits to either deabc or debca using bitwise operations. n%16*64 moves de into the first two positions, while n/16*4**(c>'L')%63 makes abc in the last 3 positions and then conditionally transforms it to bca if an R is read.

Initial, these five fields are 00123, which translates into n=27 in base 4. It's fine that the first 2 of them are the same, as no sequence of permutations can solely swap them because all the permutations are even. Because n=27 is the smallest possible permutation of the fields, we can use n<28 to check that the final state is the same as the initial one.

60 bytes

L=1;R=1j
for c in input():exec c+"=(L+R)%5%5j"
print L*1j==R

Try it online!

A new method based on alephalpha's finding that \$A_5 \cong PSL(2,5)\$. A cute trick here is using L and R for variables so we can plug the character we read and exec.

We interpret the L's and R's as instructions to set either L=L+R or R=L+R. If this always results in either getting back the original values mod 5 or getting back their negations mod 5, then the instructions give a closed loop.

It suffices to test that this works for both the initial "basis vectors" L=1, R=0 and L=0, R=1. Instead of testing twice, we run both tests in parallel using complex numbers, with one case in the real part and the other in the imaginary part, so L=1, R=1j. Python 2 has a wacky complex modulus that lets us %5 to reduce the real part and %5j to reduce the imaginary part.

In the end, we can if we're in one of the success cases of the original L=1,R=1j or its negation mod 5 of L=4,R=4j. It turns out it suffices to check L*1j==R as shown by this code testing for false positives.

59 bytes

L=1;R=1j
exec"=(L+R)%5%5j;".join(input()+' ')
print L*1j==R

Try it online!

Saves one byte from above using .join to create the string to execute.

\$\endgroup\$
7
\$\begingroup\$

PARI/GP, 51 bytes

s->t=x;[t=Mod(t+p=c>"O",5)/(t*!p+1)|c<-Vec(s)];t==x

Attempt This Online!

Using the isomorphism \$A_5 \cong PSL(2,5)\$. See this question on Mathematics SE: https://math.stackexchange.com/q/93762/99103

In this isomorphism, the permutations represented by L and R are mapped to the rational functions \$\frac{x}{x+1}\$ and \$x+1\$ respectively.


PARI/GP, 58 bytes

s->m=matid(2);[m=m*[1,p=c>"O";!p,1]%5|c<-Vec(s)];m==m[1,1]

Attempt This Online!

This uses the same isomorphism as above, but uses matrices (\$\bigl(\begin{smallmatrix}1&0\\1&1\end{smallmatrix}\big)\$ and \$\bigl(\begin{smallmatrix}1&1\\0&1\end{smallmatrix}\big)\$ for L and R) instead of rational functions to represent elements of \$PSL(2,5)\$.


PARI/GP, 63 bytes

s->prod(n=0,4,m=n;[m=[m+1,33%m+=9][c%5]%5|c<-Vecsmall(s)];m==n)

Attempt This Online!

A port of @xnor's answer, but uses 33%(n+9)%5 instead of (1+n%3+n%4)%5.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 15 13 bytes (thanks @Jonathan Allan!)

OH+53œ?@ƒ5FṢƑ

Try it online!

OH+53œ?@ƒ5FṢƑ
O                ord() the input list (vectorizes)
 H               Divide by 2 (vectorizes)
  +              Add...
   53            ...53 (all these steps vectorize)
        ƒ        Reduce the input list with:
       @             The preceding dyadic link, with its arguments swapped:
     œ?                  The nth permutation of the right argument
                 ...using the following as the starting value for the reduce:
         5           5 (which gets implicitly converted to [1,2,3,4,5] by œ?)
          F      Flatten (wraps 5 into [5] in case the input list is empty)
            Ƒ    Check if the output of the previous link is equal to its left argument:
           Ṣ         Sort the output list
(The last two bytes effectively check if the list is already in sorted order.)

Uses essentially the same logic as @xnor's answer. The two permutations I used were 45231 and 45123, since their indices (94 and 91, respectively) can be easily computed from the ord values of 'R' and 'L' (82 and 76, respectively): divide by 2 and add 53. I wrote a Python script to check all valid pairs of permutations to find the optimal ones (in terms of how many bytes are needed to calculate their indices from 82 and 76), and no other permutations were better than these.

\$\endgroup\$
1
  • \$\begingroup\$ You can save a couple of bytes - one by using the invariance quick, Ƒ to do away with the need for µ and another by noting that [5] is also invariant under sorting so all we need is to keep everything the same but turn 5 into [5] which we can do with F and now we don't need to do the :) - TIO - 13 bytes. Side note: the "preceding dyadic link" is really only œ?, the result of evaluating OH+53 is the left argument of @. \$\endgroup\$ Sep 2 at 18:13
4
\$\begingroup\$

Charcoal, 33 32 bytes

≔E⁵ιθFSUMθ⎇›ιL﹪⁺³κ⁵÷↔⁻⁹×⁴κ²⬤θ⁼ικ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a round trip, nothing if not. Explanation: I too read the linked post with the dodecahedral bonus but I decided to pick [4, 2, 0, 1, 3] and [3, 4, 0, 1, 2] as my permutations for which the formulas are max(n*2,9-n*2)%5 abs(9-4*n)//2 and (n+3)%5. (Porting @xnor's formulas would probably be shorter but that would have been boring.)

≔E⁵ιθ

Start with a list [0, 1, 2, 3, 4].

FS

Loop over the input string.

UMθ

Update the list elements in-place.

﹪⎇›ιL⁺³κ⌈⟦⊗κ⁻⁹⊗κ⟧⁵

Apply one of the two permutations as appropriate.

⬤θ⁼ικ

Check that each list element is equal to its index.

\$\endgroup\$
3
\$\begingroup\$

Python+, 49 bytes

n=27
£c:§()
 n=n%16*64|n/16*4**(c>'L')%63
$(n<28)

Basically just xnor's Python answer, converted to Python+

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Sep 2 at 16:34

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.