Longest path in a rotating maze

Question

This maze was inspired by the Deusovi Honeypot .

The rules of this maze are simple. The solid colored triangles inside the bigger triangles are shrunken replicas of the bigger triangles of there same color. and don't forget to rotate them 30 degrees clockwise for each level in you go.

The yellow triangles are portals, portals only work when both of them are exactly the same, by both size, and angle.

So the question is, assuming that you don't make any mistakes which two entrances (A,B,C,D,E,F) are the hardest to move between?

To rate which two entrances are correct, use this system.

Moving in a level costs 1 move.

Teleportation costs 1 move.

P.S.(for the colorblind; red inside of blue on top, blue inside red on bottom).

For anyone really fascinated with this type of maze. try getting rid of the portal in "F" or bottom left. the solutions will get so much deeper! :).

Answer 1

Answer:

B and E, which take 8 steps to move between.

Solution:

As was done in the Deusovi Honeypot, I'll name the outermost exits we see $A_1$, $B_1$, etc., and each subsequent smaller copy with increasing subscripts. I'll denote by $X \Leftrightarrow Y$ that $X$ and $Y$ are connected by a teleport, and $X \leftrightarrow Y$ that they're connected by walking between fractal levels. Then we have for all positive $n$:

$A_n \Leftrightarrow E_n$, $D_n \Leftrightarrow F_n$

$A_n \leftrightarrow E_{n+1}$, $B_n \leftrightarrow F_{n+1}$, $C_n \leftrightarrow D_{n+1}$, $D_n \leftrightarrow A_{n+1}$, $E_n \leftrightarrow B_{n+1}$, $F_n \leftrightarrow C_{n+1}$

At this point we have a graph so we can brute force an answer with a few dozen lines of code and a shortest-paths library. It's not too hard to do by hand either - we can get quick upper bounds for most of them by reaching the nearest A or E and then changing fractal levels "in place": $E_1 \Leftrightarrow A_1 \leftrightarrow E_2 \Leftrightarrow A_2$ etc. Once B-E starts looking like the longest path, you can exhaustively search that tree of possibilities; it never gets too big because nothing branches more than two directions and since you can quickly get an upper bound of 8, you never have to travel to the 4th level or beyond (since any travel to the 4th level will take at least 8 steps - 4 inward and 4 outward). Here is one such path of length 8: $B_1 \leftrightarrow F_2 \Leftrightarrow D_2 \leftrightarrow A_3 \Leftrightarrow E_3 \leftrightarrow A_2 \Leftrightarrow E_2 \leftrightarrow A_1 \Leftrightarrow E_1$. This is the only tree you have to search that thoroughly, since once we have B-E at 8, we do not need to find shortest paths for all the other pairs; merely paths shorter than 8.