AoCG2021 Day 22: Hyperbolic rescueAoCG2021 Day 22: Hyperbolic rescue
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-6, 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
