A Turtle Finds a Portal

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

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.


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

Tags:

Grid

Path Finding

Code Golf

Recent Posts