Skip to main content
added 495 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652

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.

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.

added 661 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652

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.

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.

Bitwise shenanigans

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.

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.

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.

added 661 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652

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.

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.

deleted 2 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
added 453 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
added 453 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
added 132 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
deleted 4 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
added 755 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
added 321 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
added 590 characters in body
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading
Source Link
xnor
  • 146.6k
  • 26
  • 279
  • 652
Loading