30
\$\begingroup\$

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

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

\$\endgroup\$
8
  • 2
    \$\begingroup\$ I think it would be a good idea to add a test case where using the teleporter would make it take longer. \$\endgroup\$
    – Okx
    Feb 3, 2019 at 17:13
  • \$\begingroup\$ @Okx Creating and adding now. \$\endgroup\$
    – akozi
    Feb 3, 2019 at 17:14
  • \$\begingroup\$ What happens when an unwanted teleporter is in the way, like TXOXS,MMMMM,OXXXX? Does the turtle have to move off the other end of the teleporter and go back onto it? What if that's not possible like TXOXS,MMMMM,OMXXX? \$\endgroup\$
    – xnor
    Feb 3, 2019 at 19:44
  • 1
    \$\begingroup\$ @xnor I feel that this may be to abstract from my original rules. So perhaps it's better to portals a one use item? \$\endgroup\$
    – akozi
    Feb 3, 2019 at 21:31
  • 1
    \$\begingroup\$ Related (I think). \$\endgroup\$
    – Charlie
    Feb 4, 2019 at 10:46

3 Answers 3

13
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ "Each visited tile is temporarily set to a mountain to prevent the turtle from moving twice on the same tile" What a lovely trick. Great answer, and as always I appreciate answers with explanations :) \$\endgroup\$
    – akozi
    Feb 4, 2019 at 3:05
5
\$\begingroup\$

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.

\$\endgroup\$
13
  • 2
    \$\begingroup\$ You can probably shave a few characters off by taking in a list where each object is represented by a number instead of a string character. \$\endgroup\$
    – Quintec
    Feb 3, 2019 at 19:51
  • \$\begingroup\$ @Quintec Added, thanks. I would like to do the same for the directions, but then the diagonals would have to be done separately. It still may be possible to move them to numbers though. \$\endgroup\$
    – nedla2004
    Feb 3, 2019 at 20:10
  • 1
    \$\begingroup\$ @ElPedro Ahha I can shave 4 off like this \$\endgroup\$ Feb 4, 2019 at 22:21
  • 2
    \$\begingroup\$ ...and another 10 for 356 \$\endgroup\$ Feb 4, 2019 at 22:31
  • 3
    \$\begingroup\$ @JonathanAllan and ElPedro and Jonathan French. Great tips from all of you, and I have added them together with I couple things I came up with. (After much delay) \$\endgroup\$
    – nedla2004
    Feb 5, 2019 at 15:01
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.