An alternative approach might be to implement the permutation composition directly using bit operations as I do in my 2018 answer to my challenge with the cube. The idea here would be store the state as a 15-bit number split into five 3-bit fields, and implement the two permutations of the 5 bit fields using bit operations. At least one of the bit operations would be fairly involved, but it would parallelize the current solution's applying permutations to 5 starting values, so I'm not sure which would win out.
BitwiseThis 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.
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.