Detect round trips on a hyperbolic grid

Question

You're driving a car in an infinite city whose blocks are pentagons arranged in the order-4 pentagonal tiling. At each step, you proceed to the next intersection and choose whether to continue left, right, or straight. A sequence of choices that returns you to your initial state (street segment and direction) is called a round trip.

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

Examples:

LLLLL -> yes (this is a drive around one pentagonal block)
LLLLSRRRRS -> yes
SRRSRRSRRSRR -> yes
(empty sequence) -> yes
R -> no
LLLLLL -> no (starts with a round trip but leaves initial state)
SLLLLR -> no (returns to initial street but opposite direction)

(Note that L and R are not in-place rotations; every move includes entering and exiting the next intersection.)

Cool! I'm trying to teach myself some math related to isometries of hyperbolic space, and I'm surprised none of the solutions to that challenge use an algebraic representation of the tiling's symmetry group (e.g. a set of matrices in PSL(2,R) that can be easily multiplied and checked for equality). Does that not work for some reason? — Karl, Mar 10 at 21:57
In the hyperbolic plane, floating-point errors accumulate exponentially with distance, so you need a more symbolic representation if you want to take more than a few dozen steps. — Anders Kaseorg, Mar 10 at 22:57
Sure, you can represent the moves exactly in \$\mathrm{PSL}{\left(2, \mathbb Q{\left[\sqrt{φ + \sqrt φ}\right]}\right)}\$ by \$S = \left[\begin{smallmatrix}\sqrt{φ + \sqrt φ} & 0 \\ 0 & \sqrt{φ - \sqrt φ}\end{smallmatrix}\right]\$, \$L = S\frac1{\sqrt 2}\left[\begin{smallmatrix}1 & -1 \\ 1 & 1\end{smallmatrix}\right]\$, \$R = S\frac1{\sqrt 2}\left[\begin{smallmatrix}1 & 1 \\ -1 & 1\end{smallmatrix}\right]\$ using 16×16 big integer matrices. It’s probably not going to be the golfiest solution though. — Anders Kaseorg, Mar 11 at 3:11

Anders Kaseorg · Accepted Answer · 2023-04-27 21:14:22Z

Python, 259 bytes

from numpy import*
k=kron
u=lambda x:fromiter(base_repr(x,3),int).reshape(4,4)-1
s=k(u(25952008),u(27752297))+k(u(21543856),u(18501071))
t=k(u(21169798),i:=eye(4,4,0,object))
a=b=2*k(i,i)
for c in input():b=[s@t,s,s@t@t@t][-ord(c)%4]@b//2
print(all(a*a==b*b))

Attempt This Online!

How it works

Uses only big integer linear algebra. This is probably not the golfiest solution method, but OP said they’re interested in this approach.

The rigid motions of the hyperbolic plane are isomorphic to \$\mathrm{PSL}(2, \mathbb R)\$, which can be represented by 2×2 matrices acting on \$\mathbb R^2\$.

\begin{gather*} S = \begin{bmatrix} \frac1{\sqrt 2}(-\sqrt φ + φ + \sqrt φ^3) & 0 \\ 0 & \frac1{\sqrt 2}(\sqrt φ + φ - \sqrt φ^3) \end{bmatrix}, \\ T = \begin{bmatrix} \frac1{\sqrt2} & -\frac1{\sqrt2} \\ \frac1{\sqrt2} & \frac1{\sqrt2} \end{bmatrix}, \quad L = ST, \quad R = ST^3. \end{gather*}

However, in the hyperbolic plane, floating-point errors accumulate exponentially with distance, so we need a way to do the same calculation exactly. For our purposes, we only need to work in the 16-dimensional sublattice \$M\mathbb Z^{16} ⊂ \mathbb R^2\$ generated by the columns of

$$M = \left[\begin{smallmatrix} 1 & \sqrt φ & φ & \sqrt φ^3 & \frac{1}{\sqrt 2} & \frac{\sqrt φ}{\sqrt 2} & \frac{φ}{\sqrt 2} & \frac{\sqrt φ^3}{\sqrt 2} & 0 & 0 & 0 & 0 & -\frac{1}{\sqrt 2} & -\frac{\sqrt φ}{\sqrt 2} & -\frac{φ}{\sqrt 2} & -\frac{\sqrt φ^3}{\sqrt 2} \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt 2} & \frac{\sqrt φ}{\sqrt 2} & \frac{φ}{\sqrt 2} & \frac{\sqrt φ^3}{\sqrt 2} & 1 & \sqrt φ & φ & \sqrt φ^3 & \frac{1}{\sqrt 2} & \frac{\sqrt φ}{\sqrt 2} & \frac{φ}{\sqrt 2} & \frac{\sqrt φ^3}{\sqrt 2} \end{smallmatrix}\right].$$

In order for \$L, S, R\$ to act on this lattice, we need it to be closed under multiplication by \$\sqrt2\$ and \$\sqrt φ\$, which it is; for example:

$$ \sqrt2 \begin{bmatrix}1 \\ 0\end{bmatrix} = \begin{bmatrix}\frac1{\sqrt 2} \\ \frac1{\sqrt 2}\end{bmatrix} - \begin{bmatrix}-\frac1{\sqrt 2} \\ \frac1{\sqrt 2}\end{bmatrix}, \quad \sqrt φ\begin{bmatrix}\sqrt φ^3 \\ 0\end{bmatrix} = \begin{bmatrix}1 \\ 0\end{bmatrix} + \begin{bmatrix}φ \\ 0\end{bmatrix}. $$

We also need to multiply some points by \$\frac12\$, but it turns out that as long as we use \$2I\$ as the initial matrix rather than \$I\$, those points always have even coefficients. The resulting actions are given by

\begin{gather*} SM = \frac12 M\left[\begin{smallmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0 \\ 0 & 0 & 0 & 0 & -1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & -1 & 0 & -1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 \\ 0 & -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & -1 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ -1 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \end{smallmatrix}\right], \\ TM = M\left[\begin{smallmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{smallmatrix}\right], \end{gather*}

which we compress slightly using the Kronecker product.

\$\begingroup\$ Thanks, this is very illuminating! \$\endgroup\$
– Karl
Mar 12 at 19:25 — Karl, Mar 12 at 19:25

Neil · Accepted Answer · 2023-03-11 22:06:16Z

Retina 0.8.2, 55 bytes

\d
$*RF
FRRRFRRRF
RFRFR
FRFRF
RRRFRRRFRRR
}`FF|RRRR

^$

Try it online! Takes input as 123 but test suite converts from LSR for convenience. Explanation: Similar approach to @AndrovT's Vyxal answer, but reduces the problem further to two movements, R (rotate on the spot without moving) and F (flip around and move to the next intersection).

\d
$*RF

Convert digits to the appropriate R and F movements.

FRRRFRRRF
RFRFR
FRFRF
RRRFRRRFRRR

Simplify moving along three sides of the same pentagon to moving along the other two sides.

FF|RRRR

Remove redundant multiples of F and R movements.

}`

Repeat until the path cannot be simplified further.

^$

Check whether the path is now empty.

AndrovT · Accepted Answer · 2023-03-11 22:55:21Z

Vyxal, 26 bytes

fC‹\1꘍›ṅ»¬½ẆZ¶ẋḞ≥P»3R2€yøV

Try it Online!

Port of @Neil's Retina answer. Returns a falsey value if the path is closed and truthy otherwise.

fC                   # covert to a list of charcodes
  ‹                  # decrement
   \1꘍               # prepend that many spaces to "1"
      ›              # replace spaces with zeros
       ṅ             # join by nothing
        »...»        # push the compressed integer 36932780194571550874
             3R      # convert to base 3 "100010001201010210101200010001000200002211"
               2€    # split on 2 ["100010001", "01010", "10101", "00010001000", "0000", "", "11"]
                 y   # uninterleave ["100010001", "10101", "0000", "11"], ["01010", "00010001000", ""]
                  øV # replace strings from the first list with corresponding strings from the second list while it's possible

Old:

Vyxal, 44 bytes

‹‹C‹λ2Ẏk₁⁼[ḢḢǔk₁-3Y]₌ǔh¬[3₌ȯẎ∑J]:hċßN4%;İṪta

Try it Online!

Returns 0 for closed paths and 1 otherwise.

First it represents the turns right, straight, left and backwards with numbers 1, 2, 3 and 0 respectively.

If the path is closed with length greater than 1, then it can be reduced to path 0, 0 with the following transformations:

Rotating the path (e. g. 0, 1, 2, 1, 3 -> 3, 0, 1, 2, 1)
Changing right turns to left turns and vice versa (e. g. 0, 1, 2, 1, 3 -> 0, 3, 2, 3, 1)
If the path contains the pattern a, 0, b replacing it with a+b mod 4 (e. g. 2, 0, 1, 3 -> 3, 3)
If the path contains the pattern a, 1, 1, b replacing it with (a-1 mod 4), 3, (b-1 mod 4) (e. g. 1, 1, 1, 2 -> 0, 3, 1)

This is because a closed path has at least one of 0, [1, 1] and [3, 3] so we can always use the transformations to shorten it.

Code explanation

Append "--" representing two backwards turns to avoid cases where the path is too short.

‹‹

Replace L, R, S and - with the corresponding numbers.

C    # get the ascii value
 ‹   # decrement
     # eventually when mod 4 gets applied it will transform into the correct numbers

Apply the a function repeatedly and collect unique results

λ ... ;İ

where the function is:

Use the fourth transformation

  2Ẏk₁⁼           # are the first two items equal to 1?
       [        ] # if they are:
        ḢḢ        #   remove first two items
          ǔ       #   rotate right
           k₁-    #   subtract 1 from the first two items
              3Y  #   insert 3 into the second position

Use the third transformation and rotate

  ₌ǔh          # push the list rotated to the right and then the first item of the original list
     ¬[      ] # if it's equal to 0:
       3₌ȯẎ    #   push a[3:] and a[:3]
           ∑   #   sum
            J  #   join

Mirror the turns such that the first turn is not 3

  :hċß    # if the first item is not 1:
      N   #   negate each
       4% # mod 4

Finally check if the second to last item in the list is [0, 0].

Ṫ   # remove last item
 t  # last item
  a # is any truthy

Save another 3 bytes by porting my Charcoal answer instead: fC‹↵ṅ»¬½ẆZ¶ẋḞ≥P»3R2€yøV — Neil, Mar 12 at 8:22

Neil · Accepted Answer · 2023-03-12 00:12:15Z

4

Charcoal, 52 bytes

≔⭆ＳＸχ⊕⌕LSRιθＷ⌊ΦＥ⪪”←“tU≧*h？λêQ✳x”¶⪪κ №θ⌈κ≔⪫⪪θ⌈ι⌊ιθ¬θ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a round trip, nothing if not. Explanation: Based on my Retina 0.8.2 answer, but using 1 instead of F and 0 instead of R because it's golfier in Charcoal.

≔⭆ＳＸχ⊕⌕LSRιθ

Change L to 10, S to 100 and R to 1000 in the input. (These are actually reversed from my Retina answer but it doesn't matter because round trips are reversible.)

Ｗ⌊ΦＥ⪪”...”¶⪪κ №θ⌈κ

While the string contains one of the patterns 100010001, 10101, 11 or 0000...

≔⪫⪪θ⌈ι⌊ιθ

... replace all matches with the 01010, 00010001000 or the empty string respectively.

¬θ

Test whether the string is now empty.

answered Mar 12 at 0:12

Neil

158k12 gold badges69 silver badges268 bronze badges

\$\begingroup\$ Amazing! I'm curious how you establish the correctness of these path-rewriting solutions. Is there a general argument that works for arbitrary regular hyperbolic tilings, I wonder? \$\endgroup\$
– Karl
Mar 12 at 19:35
1

\$\begingroup\$ @Karl In theory I believe you can always come up with a canonical form to describe your destination and orientation and "simplify" the input into that form, but obviously here we're only interested in a form with a partial simplification that will always work for a closed path. (Here for instance the odd number of sides makes things much easier.) \$\endgroup\$
– Neil
Mar 12 at 20:12
\$\begingroup\$ Yeah - it's conceivable that a path like (LS)^n, which uses only two sides of each pentagon, could be a closed loop, but in this case we can see from looking at the picture that this doesn't turn sharply enough, so it seems that your rule is sufficient. \$\endgroup\$
– Karl
Mar 12 at 22:45
\$\begingroup\$ @Karl Strictly speaking that's really AndrovT's rule (point 4). \$\endgroup\$
– Neil
Mar 13 at 0:15

Add a comment |

Kevin Cruijssen · Accepted Answer · 2023-03-13 07:59:54Z

05AB1E, 27 26 (or 23) bytes

Ç<°JΔ•6o₁EAÛr£ð•3B2¡ι`:}õQ

Port of AndrovT's top Vyxal answer, which in turn is a port of @Neil's Retina answer, which in turn is inspired by AndrovT's bottom Vyxal answer. 😅
-1 byte thanks to @Neil.

Outputs 1/0 for truthy/falsey respectively. If outputting an empty string for truthy and a bunch of 0s and/or 1s as falsey is acceptable, the last three bytes could be removed.

Try it online or verify all test cases.
Try it online or verify all test cases with the last three bytes removed.

Explanation:

Ç                      # Convert the (implicit) input-string to a list of codepoint integers
 <                     # Decrease each by 1
  °                    # Take 10 to the power each
   J                   # Join them together
Δ                 :}   # Keep doing the following replacements as long as it's possible:
 •6o₁EAÛr£ð•           #  Push compressed integer 110798340583714652624
            3B         #  Convert it to base-3: 1000100012010102101012000100010002000022112
              2¡       #  Split it on 2s: [100010001,"01010",10101,"00010001000","0000","",11,""]
                ι      #  Uninterleave it into 2 parts: [[100010001,10101,"0000",11],["01010","00010001000","",""]]
                 `     #  Pop and push both lists separately to the stack
                   }   # After the changes loop:
                    õQ # Check if what remains is an empty string
                       # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •6o₁EAÛr£ð• is 110798340583714652624.

As per my Charcoal answer, you don't need the í; my Retina answer only has the fixed F after the variable Rs because it's golfier that way (e.g. 2$&$* is a byte longer than $*RF). You can put subtly different meanings on them to map more directly to the input but closed paths are cyclic and reversible anyway. — Neil, Mar 12 at 20:02

138 Aspen · Accepted Answer · 2023-05-20 00:03:41Z

Octave, 381 309 286 284 282 266 264 259 253 247 bytes

(381 -> 247) Saved 134 bytes thanks to the comment of @ceilingcat

Golfed version. Try it online!

pkg load symbolic;function R=f(S),u=@(x)reshape(str2num(dec2base(x,3)(:)),4,4)-1;a=b=eye(16);for c=S;b=(kron(u(25952008),u(27752297))+kron(u(21543856),u(18501071)))*kron(u(21169798),eye(4))^{1,0,3}{mod(-toascii(c),4)+1}*b/2;end;R=all(a*a==b*b);end

Ungolfed version, modified from @Anders Kaseorg's answer. Try it online!

pkg load symbolic

function mat = u(x)
  base3_repr = dec2base(x, 3);
  mat = reshape(str2num(base3_repr(:)), 4, 4) - 1;
endfunction

function result = check_input(input_str)
  s = kron(u(25952008), u(27752297)) + kron(u(21543856), u(18501071));
  t = kron(u(21169798), eye(4, 4));
  a = b = 2 * kron(eye(4, 4), eye(4, 4));

  for c = input_str
    idx = mod(-toascii(c), 4) + 1;
    b = {s * t, s, s * t^3}{idx} * b / 2;
  endfor

  result = all(all(a == b)) || all(all(a == -b));
endfunction

test_cases = {
  "LLLLL",
  "LLLLSRRRRS",
  "SRRSRRSRRSRR",
  "",
  "R",
  "LLLLLL",
  "SLLLLR"
};

expected_results = [
  true,
  true,
  true,
  true,
  false,
  false,
  false
];

for i = 1:length(test_cases)
  input_str = test_cases{i};
  result = check_input(input_str);
  assert(result == expected_results(i), sprintf("Test case %d failed: input = %s, expected = %d, actual = %d", i, input_str, expected_results(i), result));
  fprintf("Test case %d passed: input = %s\n", i, input_str);
end

Stack Exchange Network

Detect round trips on a hyperbolic grid

6 Answers 6

Python, 259 bytes

How it works

Retina 0.8.2, 55 bytes

Vyxal, 26 bytes

Old:

Vyxal, 44 bytes

Code explanation

Charcoal, 52 bytes

05AB1E, 27 26 (or 23) bytes

Octave, 381 309 286 284 282 266 264 259 253 247 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
decision-problem
geometry
abstract-algebra
or ask your own question.

Linked

Hot Network Questions

Detect round trips on a hyperbolic grid

6 Answers 6

Python, 259 bytes

How it works

Retina 0.8.2, 55 bytes

Vyxal, 26 bytes

Old:

Vyxal, 44 bytes

Code explanation

Charcoal, 52 bytes

05AB1E, 27 26 (or 23) bytes

Octave, 381 309 286 284 282 266 264 259 253 247 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmathdecision-problemgeometryabstract-algebra or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
math
decision-problem
geometry
abstract-algebra
or ask your own question.