A Turtle Finds a Portal

Question

The turtle wants to move along the grid to get to his food. He wants to know how many moves it will take for him to get there.

As well since he is slow he has teleporters set up around his domain that he will utilize if it shortens his path. Or avoid them if it lengthens his path.

Meet the turtle

The turtle lives on a grid $$\begin{matrix} X&X&X&X&X\\ X&X&X&X&X\\ X&X&&X&X\\ X&X&X&X&X\\ X&X&X&X&X\\ \end{matrix}$$ The turtle can move to any adjacent square... $$\begin{matrix} X&X&X&X&X\\ X&\nwarrow&\uparrow&\nearrow&X\\ X&\leftarrow&&\rightarrow&X\\ X&\swarrow&\downarrow&\searrow&X\\ X&X&X&X&X\\ \end{matrix}$$

However, the turtle cannot move to a square with a mountain $$\begin{matrix} X&&X&X&X\\ X&\nwarrow&\uparrow&\nearrow&X\\ X&&&\rightarrow&X\\ X&&\downarrow&\searrow&X\\ X&&X&X&X\\ \end{matrix}$$

The Turtle wants to eat his Strawberry, and would like to know how long it will take to get to his Strawberry $$\begin{matrix} X&&\\ &&X\\ X&&X\\ X&X&X\\ \end{matrix}$$ This example would take the turtle \$5\$ turns $$\begin{matrix} X&&\\ \downarrow&&\uparrow\\ \searrow&&\uparrow\\ X&\nearrow&X\\ \end{matrix}$$ Luckily, the Turtle found a teleporter! There are two teleports on the grid that map to each other. Stepping on the teleporter immediately moves the turtle to the corresponding teleporter. Teleporters are very unstable and after using them once, they disapear and are no longer useable. $$\begin{matrix} &&\\ &&\\ X&&X\\ X&X&X\\ \end{matrix}$$ It is now faster for the turtle to move up twice. Now the turtles shortest path is \$2\$ $$\begin{matrix} &&\\ \uparrow&&\uparrow\\ X&&X\\ X&X&X\\ \end{matrix}$$

The challenge

Given an initial grid configuration output the number of moves it will take the turtle to reach his strawberry.

Rules

• You may assume that the input grid has a solution

• Each grid will only have one strawberry and two portals and one turtle

• The input grid may be entered in any convenient format

• You should treat teleporters are single use items

• The turn that the turtle moves onto a teleporter square he is already on the corresponding teleporter. He never moves onto a teleporter and stays there for a move

• The shortest path does not need to make use of the portal

• The turtle cannot pass into mountain tiles

• You may use any ASCII character or integer to represent mountains, turtle, empty grid square, strawberry

• You may use either the same character or two different ASCII characters or integers to represent the teleporter pairs

• A grid can have more than one path with the same shortest path length

• This is code-golf

Clarifications to Rules

• You should treat teleporters are single use items.

Reasoning: It was pointed out that the case of: $$\begin{matrix} &X&&X&\\ &&&&&\\ &X&X&X&X \end{matrix}$$

Could be only solved by entering and exiting the portals twice. At the time of making this clarification both solutions acted by assuming they were either single use, or there was no reason to try previously used squares. To avoid breaking their hard-worked solutions, this seemed the best way account for this set up. Therefore, this would be considered an invalid grid.

Test Cases formatted as lists

[ ['T', 'X', 'X', 'S', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 3
[ ['T', 'M', 'X', 'S', 'X'], ['X', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'O'] ] --> 4
[ ['T', 'M', 'X', 'S', 'O'], ['O', 'M', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 2
[ ['T', 'M', 'X', 'S', 'X'], ['O', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'X'] ] --> 4
[ ['T', 'M', 'S', 'X', 'O'], ['X', 'M', 'M', 'M', 'M'], ['X', 'X', 'X', 'X', 'O'] ] --> 7
[ ['T', 'X', 'X', 'S', 'X'], ['O', 'M', 'M', 'M', 'X'], ['X', 'X', 'O', 'X', 'X'] ] --> 3

Test Cases formatted for humans

T X X S X
X X X X X
X X X X X --> 3

T M X S X
X M X X X
O X X X O --> 4

T M X S O
O M X X X
X X X X X --> 2

T M X S X
O M X X X
O X X X X --> 4

T M S X O
X M M M M
X X X X O --> 7

T X X S X
O M M M X
X X O X X --> 3

Credits

Design and structure via: Hungry mouse by Arnauld

Proposed Challenges Edit Advice: Kamil-drakari, beefster

General Edit Advice: okx nedla2004 mbomb007

Answer 1

JavaScript (ES7),  140 139  138 bytes

Takes input as a matrix of integers with the following mapping:

• \$-1\$ = (any portal)
• \$0\$ = \$X\$ (empty)
• \$1\$ = (mountain)
• \$2\$ = (turtle)
• \$3\$ = (strawberry)

m=>(R=g=(t,X,Y,i)=>m.map((r,y)=>r.map((v,x)=>r[(u=0,t?v-t:(x-X)**2+(y-Y)**2<3?v-3?~v?v:u--:R=R<i?R:i:1)||g(u,x,y,u-~i,r[x]=1),x]=v)))(2)|R

Try it online!

How?

The main recursive search function \$g\$ is able to either look for a specific tile \$t\$ on the board (if it's called with \$t\ne 0\$) or for any tile at \$(x,y)\$ which can be reached from the current position \$(X,Y)\$.

It keeps track of the length of the current path in \$i\$ and updates the best result \$R\$ to \$\min(R,i)\$ whenever the turtle finds the strawberry.

It is first called with \$t=2\$ to find the starting position of the turtle.

It calls itself with \$t=-1\$ if a portal is reached, so that the turtle is teleported to the other portal. We do not increment \$i\$ during such an iteration.

Each visited tile is temporarily set to a mountain to prevent the turtle from moving twice on the same tile in the same path. If we get trapped in a dead-end, the recursion simply stops without updating \$R\$.

Commented

m => (                        // m[] = input matrix
  R =                         // initialize R to a non-numeric value
  g = (t, X, Y, i) =>         // g = recursive search function taking t = expected tile,
                              //     (X, Y) = current coordinates, i = path length
    m.map((r, y) =>           // for each row r[] at position y in m[]:
      r.map((v, x) =>         //   for each tile v at position x in r[]:
        r[                    //     this statement will eventually restore r[x] to v
          ( u = 0,            //     u = next tile to look for, or 0 if none
            t ?               //     if we're looking for a specific tile:
              v - t           //       test whether we've found it
            :                 //     else:
              (x - X) ** 2 +  //       compute the squared Euclidean distance between
              (y - Y) ** 2    //       (x, y) and (X, Y)
              < 3 ?           //       if it's less than 3 (i.e. reachable from (X, Y)):
                v - 3 ?       //         if v is not equal to 3:
                  ~v ?        //           if v is not equal to -1:
                    v         //             test if v = 0
                  :           //           else (v = -1):
                    u--       //             set u = -1 to find the other portal
                :             //         else (v = 3):
                  R = R < i ? //           we've found the strawberry: set R = min(R, i)
                      R : i   //
              :               //       else (this tile can't be reached):
                1             //         yield 1
          ) ||                //     if the above result is falsy:
          g(                  //       do a recursive call:
            u,                //         t = u
            x, y,             //         move to (x, y)
            u - ~i,           //         unless u is set to -1, increment i
            r[x] = 1          //         set this tile to a mountain
          ),                  //       end of recursive call
          x                   //     restore r[x] ...
        ] = v                 //     ... to v
    ))                        // end of both map() loops
)(2) | R                      // initial call to g with t = 2; return R

Answer 2

Python 2, 441 431 341 bytes

from itertools import*
G=input()
W=len(G[0])
H=len(G)
A=[0]*5
E=enumerate
for y,r in E(G):
 for x,C in E(r):A[C]=[x,y]
for L in count():
 for M in product(*[zip('UDLR'*2,'LRDU    ')]*L):
  x,y=A[0]
  for m in M:
    x+='R'in m;x-='L'in m;y+='D'in m;y-='U'in m
    if(x,y)==A[3]:x,y=A[2]
    if 1-(W>x>-1<y<H)or G[y][x]>3:break
  if[x,y]==A[1]:exit(L)

Try it online!

Input as lists, but using numbers instead of characters (thanks to Quintec) and a seperate value for the destination of the teleporter. Those large indentations should be tab characters if Stack Exchange removes them. Any tips or ideas especially welcome, as I feel that this could get much somewhat shorter.

The table for characters used in the challenge to the numbers used for my program is below, but you can also use this program.

Challenge | My program
T         | 0
S         | 1
E         | 2
O         | 3
M         | 4
X         | -1

-10 bytes thanks to Quintec by changing the input from using characters to numbers.

-A lot of bytes thanks to Jonathan Frech, ElPedro, and Jonathan Allan.

Answer 3

Python 2, 391 397 403 422 bytes

M=input()
from networkx import*
a=b=c=d=0
N,h,w,S=[-1,0,1],len(M),len(M[0]),[]
for i in range(h):
 for j in range(w):
  I,m=(i,j),M[i][j]
  if m>7:c,d=a,b;a,b=I
  if m<0:Z=I
  if m==5:F=I
  S+=[I+I]
S+=[(a,b,c,d),(c,d,a,b)]
print len(shortest_path(from_edgelist([((A+p,B+q),(C,D))for A,B,C,D in S for p,q in[(p,q)for p in N for q in N]if-1<A+p<h and-1<B+q<w and M[C][D]*M[A+p][B+q]]),Z,F))-1

Try it online!

The problem is translated into a graph and the solution is to find the shortest path form the turtle to the strawberry.

Challenge | This code
T         | -1
S         |  5
O         |  8
M         |  0
X         |  1