AoCG2021 Day 22: Hyperbolic rescue

Question

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2017 Day 11.

---

Crossing the bridge, you've barely reached the other side of the stream when you are overcome with a sense of deja-vu. "Haven't I done this already?" But before you can finish that thought, someone runs up to you, and cries "My child process has gotten lost in an infinite grid! Can you help me?"

Fortunately for them, you have plenty of experience with infinite grids, even hexagonal ones.

Unfortunately for you, this isn't your typical hex grid.

This is is an order-4 hexagonal tiling. In your typical hexagonal tiling three tiles meet at every vertex:

Image by wikipedia user watchduck

The order-4 hexagonal tiling has 4 tiles around every vertex. In terms of geometry this means it's embedded in hyperbolic space.

Image by Anton Sherwood

In order to traverse this hyperbolic space and rescue the child you receive a list of instructions. Each instruction consists a number from 0-5, with 0 move to the next tile straight ahead and each successive number meaning to take move to the next tile clockwise from the last. So as an example 3 would be the tile right behind you.

Given this path you want to figure out how far the child is from your current position.

So your task in this challenge is to take a path of instructions as input and output the number of steps in the shortest path to the same

Strategies

There are three ways to simplify paths we can use. The first is to remove backtracks. If you ever see a 3 that's just a step back to where you were the step before. So you can remove the 3 and that step. The one hitch is that when you get back you are facing the opposite direction so you need to flip the instruction after.

So if your sequence is:

..., y, 3, z, ...

It can be rewritten as:

..., y+3+z mod 6, ...

There's one special case if your sequence ends in a 3:

..., x, 3] = ...]

The second method you to take alternative paths around corners. For example in the regular square grid these two paths are the same length:

  B--D      B  D
  |     ==     | 
  A  C      A--C

Since both tilings are order 4 we can actually use a version of this rule.

..., x, 2, y ... = ..., x+1 mod 6, 4, y+1 mod 6, ...

And again there's an edge case when the 2 or 4 is the last step.

..., x, 2] = ..., x+1 mod 6, 4]

Note that these equivalences go both ways.

You can always find the shortest path by applying a combination of these two rules.

Worked examples

[0,0,0,0]

The second move can't be applied and the first one can only be applied backwards. This is the shortest possible path to the destination, so the answer is the number of steps 4.

[2,2,2,2]

We can apply the second rule right of the bat to get [2+1,4,2+1,2] = [3,4,3,2]. Now we can use the first rule with the 3 to get [3,3], and the first rule again gives us []. The answer here is 0 this is a loop.

[2,0,2,0,2,0,2,0]

Ok this is just the last one except we take an extra step forward after each turn. This should just make a bigger version of the same thing right? Nope, hyperbolic space is tricky. We can apply rule 2 a bunch but it never really goes anywhere. This is actually the shortest path to the destination. The answer is 8.

[2,1,2,1,2,1,2,1,2,1,2,1]

This one forms a big hexagon.

[2,1,2,1,2,1,2,1,2,1,2,1]
[2,1,2,1,2,1,2,1,2,2,4,2]
[2,1,2,1,2,1,2,1,3,4,5,2]
[2,1,2,1,2,1,2,2,5,2]
[2,1,2,1,2,1,3,4,0,2]
[2,1,2,1,2,2,0,2]
[2,1,2,1,3,4,1,2]
[2,1,2,2,1,2]
[2,1,3,4,2,2]
[2,2,2,2]
[2,3,4,3]
[2,3]
[]

It's a loop so the answer is 0.

[0,2,1,2]

This isn't a loop but it can be reduced.

[0,2,1,2]
[1,4,2,2]
[1,5,4,3]
[1,5]

There's nothing we can apply to [1,5] so the answer is 2.

Testcases

[0,0,0,0] -> 4
[2,2,2,2] -> 0
[2,0,2,0,2,0,2,0] -> 8
[4,0,4,0,4,0,4,0] -> 8
[2,1,2,1,2,1,2,1,2,1] -> 2
[4,5,4,5,4,5,4,5,4,5] -> 2
[2,1,2,1,2,1,2,1,2,1,2,1] -> 0
[4,5,4,5,4,5,4,5,4,5,4,5] -> 0
[0,2,1,2] -> 2

Answer 1

Perl 5 -p, 82 bytes

s/./"bc"x($&+3)."ab"/ge;1while s/(.)\1//+s/(b|cac)a/a$1/+s/(cbcbca?)b/b$1/;$_=y;a;

Try it online!

How it works

Draw right triangle \$ABC\$, where \$A\$ is the center of your initial tile, \$B\$ is the vertex of the edge behind you on your right, and \$C\$ is the center of the edge behind you. The group of symmetries of the tiling are generated by the reflections \$a, b, c\$ over the sides \$BC\$, \$CA\$, \$AB\$ of this triangle, which satisfy the equations

$$a^2 = b^2 = c^2 = (bc)^6 = (ca)^4 = (ab)^2 = ε.$$

We can translate our path to a symmetry by applying \$(bc)^{n + 3}ab\$ for each step \$n\$. Conversely, any symmetry written as an even-length string of \$a, b, c\$ can be translated to a path whose length is the number of \$a\$s.

With the Knuth–Bendix algorithm, we can transform the above equations to a rewriting system that produces a canonical representation for any symmetry:

\begin{align*} aa &→ ε, \\ bb &→ ε, \\ cc &→ ε, \\ ba &→ ab, \\ caca &→ acac, \\ cbcbcb &→ bcbcbc, \\ cbcbcab &→ bcbcbca. \end{align*}

Since these rules never increase the number of \$a\$s, we are guaranteed that the canonical representation has the minimal number of \$a\$s.

Answer 2

Charcoal, 139 bytes

≔⟦Ｅ⁶⊕ι⟧η⊞υ⮌ηＦ⁶⊞ηω≔⁰ζ≔⁰εＦＡ«≔§§ηζ⁺ειδＦ¬§ηδ«≔⟦⟧κＷＥΦ§υ±¹№μ⌕ηω⌕ημ«Ｆ¬›⌈λ⊕⌊λ≔⮌λλ⊞λ⊖ＬηＦ⁻⁶Ｌλ⊞λ⊖Ｌ⊞Ｏηω§≔η⌕ηωλ⊞κ뻧≔§κ⁰¦¹⊖Ｌη⊞υκ»≔⁺³⌕§ηδζε≔δζ»Ｉ⌕Ｅυ№ι§ηζ¹

Try it online! Link is to verbose version of code. Explanation: Works by mapping out the grid. The starting point is 0, then the six adjacent hexagons are numbered 1-6, then the 24 hexagons at a distance of 2 are numbered 7-30, then the 90 hexagons at a distance of 3 are numbered 31-120, and so on.

≔⟦Ｅ⁶⊕ι⟧η

The edges of the starting hexagon take you to hexagons 1-6.

⊞υ⮌η

Save a copy as the list of hexagons at a distance of 0.

Ｆ⁶⊞ηω

Add six placeholders for the hexagons at a distance of 1.

≔⁰ζ≔⁰ε

Start at the origin facing direction 0.

ＦＡ«

Loop through the input steps.

≔§§ηζ⁺ειδ

Take a step in the appropriate direction.

Ｆ¬§ηδ«

If we have hit a placeholder, then...

≔⟦⟧κ

Start collecting the hexagons at the next distance.

ＷＥΦ§υ±¹№μ⌕ηω⌕ημ«

Until all of the placeholders at the next distance have been mapped, get the edge or edges of the next hexagon that step to a mapped hexagon.

Ｆ¬›⌈λ⊕⌊λ≔⮌λλ

Ensure that the edges are listed in clockwise order. This usually needs to be descending, except for the very last hexagon to be mapped, which steps to the first and last hexagon to be mapped in the previous pass. For example, hexagon 10 steps back to hexagons 2 and 1, 20 steps back to hexagon 4 and 30 steps back to hexagons 1 and 6, in that order.

⊞λ⊖Ｌη

The next edge from this hexagon goes to the same hexagon as the last edge from the previous hexagon.

Ｆ⁻⁶Ｌλ⊞λ⊖Ｌ⊞Ｏηω

The remaining edges go to new unmapped hexagons that are further away.

§≔η⌕ηωλ

Update the map with the edges of this hexagon.

⊞κλ

Collect this hexagon in the list of hexagons at this distance.

»§≔§κ⁰¦¹⊖Ｌη

Fix the second edge of the first hexagon, which needs to wrap around to the last unmapped hexagon.

⊞υκ

Collect this list of hexagons in the list of hexagons for each distance.

»≔⁺³⌕§ηδζε

Work out the direction we arrived at this hexagon from, and add 3 so that we're facing away from there.

≔δζ

Actually move to this hexagon.

»Ｉ⌕Ｅυ№ι§ηζ¹

Find out which list of hexagons we ended up in, which is our final distance.

Answer 3

Pari/GP, 160 bytes

a->for(i=1,2*#p=Mod(Polrev(a)+y*x^#a,6),p=-if([[t=p%x^l+(3-s)*x^l--+(p\x^j+3)*x^j-=2|j<-[i..#p],x^(k=j-i)+1+x^k++\(x-1)==s=p%x^j\x^l=i-1]|i<-[2..#p]],t,p));#p-1

Try it online!

Based on my Mathematica answer.

Answer 4

TypeScript Types, 568 bytes

//@ts-ignore
type a<N,P=[],A=[[0,1,2,3,4,5],[1,2,3,4,5,0],[2,3,4,5,0,1],[3,4,5,0,1,2],[4,5,0,1,2,3],[5,0,1,2,3,4]],I=A[1],D=A[5]>=N extends[infer X,infer Y,infer Z,...infer R]?Y extends 3?a<[A[3][A[X][Z]],...R],P>:|a<[Y,Z,...R],[...P,X]>|(Y extends 2?a<R,[...P,I[X],4,I[Z]]>:Y extends 4?a<R,[...P,D[X],2,D[Z]]>:never):N extends[infer X,infer Y]?Y extends 3?P:Y extends 2?[...P,I[X],4]|[...P,X,Y]:Y extends 4?[...P,D[X],2]|[...P,X,Y]:[...P,X,Y]:[...P,...N];type b<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type M<C,P=0>=[C]extends[P]?b<C>["length"]:M<a<C>,C>

Try It Online!

Ungolfed / Explanation

// Iterate over an array, applying equivalence rules where possible
type ApplyRules<
  Next,
  Prev=[],
  // Modulo arithmetic addition table
  Add=[[0,1,2,3,4,5],[1,2,3,4,5,0],[2,3,4,5,0,1],[3,4,5,0,1,2],[4,5,0,1,2,3],[5,0,1,2,3,4]],
  Inc=Add[1],
  Dec=Add[5]
> =
  // Get the first three elements of Next
  Next extends [infer X, infer Y, infer Z, ...infer Rest]
    ? Y extends 3
      // Apply the rule for 3
      ? ApplyRules<[Add[3][Add[X][Z]], ...Rest], Prev>
      // Return a union of:
      :
        // Applying no rule and stepping forward one step
        | ApplyRules<[Y, Z, ...Rest], [...Prev, X]>
        // If Y is 2 or 4, applying the 2/4 rule
        | (
          Y extends 2
            ? ApplyRules<Rest, [...Prev, Inc[X], 4, Inc[Z]]>
            : Y extends 4
              ? ApplyRules<Rest, [...Prev, Dec[X], 2, Dec[Z]]>
              : never
        )
    // Next has fewer than 3 elements. If it has exactly 2, store them in X and Y:
    : Next extends [infer X, infer Y]
      ? Y extends 3
        // If Y is 3, remove both X and Y from the end of the array by returning Prev
        ? Prev
        // If Y is 2 or 4, return the union of the current state and the state after applying the end-2/4 rule
        : Y extends 2
          ? [...Prev, Inc[X], 4] | [...Prev, X, Y]
          : Y extends 4
            ? [...Prev, Dec[X], 2] | [...Prev, X, Y]
            // Otherwise, just return the full array array
            : [...Prev, X, Y]
      // Next has fewer than 2 elements; return the full array
      : [...Prev, ...Next]

// Filter a union of tuples for those with the shortest length
type Shortest<T, K=keyof T> = T extends T ? keyof T extends K ? T : never : 0

// Continually apply rules until nothing changes, then return the shortest length in Cur
type Main<Cur, Prev=0> = [Cur] extends [Prev] ? Shortest<Cur>["length"] : Main<ApplyRules<Cur>, Cur>

Answer 5

Wolfram Language (Mathematica), 105 bytes

-7 bytes thanks to @att.

Count[Table[t=b.c,#+3].a.b&/@#/.List->Dot//.{(n:a|b|c).n_:>Dot[],(n:b|c.a.c).a:>a.n,(n:c.t.t).b:>b.n},a]&

Try it online!

A port of Anders Kaseorg's Perl answer.

A proof that the last rule in Anders Kaseorg's answer is not needed

As I said in the comment, the last rule is needed for minimizing the length of the word, but we only need to minimize the number of \$a\$s.

After applying the first 6 rules, there are only 6 possible cases between every two \$a\$s: \$c\$, \$bc\$, \$cbc\$, \$bcbc\$, \$cbcbc\$, \$bcbcbc\$. Since there is no \$ba\$ or \$caca\$, \$aca\$ can only appear at the beginning of the word.

Now let's apply the last rule \$cbcbcab\Rightarrow bcbcbca\$, and see what will happen before and after the \$a\$ in \$cbcbcab\$. Remember that the only way to decrease the number of \$a\$s is applying the first rule: \$aa\Rightarrow \varepsilon\$.

Before the \$a\$

If this is the first \$a\$ in the word, there isn't another \$a\$ for us to apply the first rule.

If it is not the first \$a\$, the only two possible cases between this \$a\$ and the previous \$a\$ are \$cbcbc\$ and \$bcbcbc\$, which will become \$bcbcbc\$ and \$cbcbc\$ respectively. So the number of \$a\$ will not decrease.

After the \$a\$

If this is the last \$a\$ in the word, there isn't another \$a\$ for us to apply the first rule.

If it is not the last \$a\$, there are 3 possible cases between this \$a\$ and the next \$a\$: \$bc\$, \$bcbc\$, \$bcbcbc\$, which will become \$c\$, \$cbc\$, \$cbcbc\$ respectively. In the last two cases, nothing else will change.

But the first case will produce a new \$caca\$: \$cbcbcabca\Rightarrow bcbcbcaca\$. Applying the rule \$caca\Rightarrow acac\$, this substring will become \$bcbcbacac\$, and further become \$bcbcabcac\$ (by applying \$ba\Rightarrow ab\$). Now the \$c\$ at the end of the substring might meet another \$c\$ and get eliminated. But there can't be another \$ca\$ right after the substring, so nothing else will change, and the number of \$a\$ won't decrease.

---

Wolfram Language (Mathematica), 133 bytes

-10 bytes thanks to @att.

Length[##.E.E&@@#//.{a_ . 3 .b_/;a<6>b:>Mod[a+b+3,6],##&@@(a_ .#2.(o:#...).#2.b_/;a<6>b:>Dot@@Mod[-{-a-#,o,-b-#},6]&@@@1?2@*5?4)}]-2&

Try it online!

First appends two dummy variable E's to the list, then repeatedly replaces:

• \$a3b\Rightarrow\operatorname{mod}(a+b+3,6)\$
• \$a2\underbrace{1\cdots 1}_{n\ge0}2b\Rightarrow\operatorname{mod}(a+1,6)\underbrace{5\cdots 5}_{n}\operatorname{mod}(b+1,6)\$
• \$a4\underbrace{5\cdots 5}_{n\ge0}4b\Rightarrow\operatorname{mod}(a-1,6)\underbrace{1\cdots 1}_{n}\operatorname{mod}(b-1,6)\$

And then takes the length of the result and minus 2.

Answer 6

Retina 0.8.2, 55 53 bytes

\d
$*____ab
_
bc
(.)\1

(b|cac)a
a$1
}`(cbcbc)b
b$1
a

Try it online! Link includes test cases. Explanation: Another port of @AndersKaseorg's Perl answer. Edit: Saved 2 bytes using @alephalpha's observation.

\d
$*____ab
_
bc

First expand each digit into n+3 underscores followed by ab, then replace each underscore with bc.

(.)\1

(b|cac)a
a$1
(cbcbc)b
b$1

Perform the simplifications.

}`

Repeat until no more simplifications can be made.

a

Count the remaining number of as.

Answer 7

Python3, 371 bytes

def f(p):
 q,s=[p],[p]
 for i in q:
  for I,a in enumerate(i):
   t=0
   if I:
    if a==3:t=i[:-2]if I+1==len(i)else i[:I-1]+[(i[I-1]+3+i[I+1])%6]+i[I+2:]
    if a in[2,4]:
     U=[-1,1][a==2]
     t=i[:-2]+[(i[-2]+U)%6,[4,2][a==4]]if I+1==len(i)else i[:I-1]+[(i[I-1]+U)%6,[2,4][a==2],(i[I+1]+U)%6]+i[I+2:]
   if t!=0 and t not in s:q+=[t];s+=[t]
 return min(map(len,s))

Try it online!