Die Schildkröte möchte sich entlang des Gitters bewegen, um zu seinem Futter zu gelangen. Er möchte wissen, wie viele Züge er braucht, um dorthin zu gelangen.

Da er langsam ist, hat er Teleporter um seine Domain eingerichtet, die er nutzen wird, wenn sich sein Weg verkürzt. Oder meide sie, wenn es seinen Weg verlängert.

Treffen Sie die Schildkröte

🐢

Die Schildkröte lebt auf einem Gitter Die Schildkröte kann sich zu jedem benachbarten Quadrat bewegen ...

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

Die Schildkröte kann sich jedoch nicht auf ein Feld mit einem Berg bewegen.

$$\begin{matrix} X&🌄&X&X&X\\ X&\nwarrow&\uparrow&\nearrow&X\\ X&🌄&🐢&\rightarrow&X\\ X&🌄&\downarrow&\searrow&X\\ X&🌄&X&X&X\\ \end{matrix}$$

Die Schildkröte möchte seine Erdbeere essen und möchte wissen, wie lange es dauern wird, bis sie zu ihrer Erdbeere Dieses Beispiel würde die Schildkröte Umdrehungen Zum Glück Die Schildkröte hat einen Teleporter gefunden! Es gibt zwei Teleports auf dem Gitter, die sich gegenseitig zuordnen. Wenn Sie auf den Teleporter treten, bewegt sich die Schildkröte sofort zum entsprechenden Teleporter. Teleporter sind sehr instabil und nach einmaliger Verwendung verschwinden sie und sind nicht mehr verwendbar.

$$\begin{matrix} X&🌄&🍓\\ 🐢&🌄&X\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ $5$ $$\begin{matrix} X&🌄&🍓\\ \downarrow&🌄&\uparrow\\ \searrow&🌄&\uparrow\\ X&\nearrow&X\\ \end{matrix}$$ $$\begin{matrix} 🔵&🌄&🍓\\ 🐢&🌄&🔴\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ Es ist jetzt schneller für die Schildkröte, sich zweimal zu bewegen. Jetzt ist der kürzeste Weg der Schildkröte$2$ $$\begin{matrix} 🔵&🌄&🐢\\ \uparrow&🌄&🔴\uparrow\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$

Die Herausforderung

Wenn eine anfängliche Gitterkonfiguration die Anzahl der Bewegungen ausgibt, benötigt die Schildkröte, um ihre Erdbeere zu erreichen.

Regeln

• Sie können davon ausgehen, dass das Eingaberaster eine Lösung hat

• Jedes Gitter hat nur eins strawberryund zwei portalsund einsturtle

• Das Eingaberaster kann in jedem geeigneten Format eingegeben werden

• Sie sollten behandeln, teleporterssind Einwegartikel

• In dem Zug, in dem sich die Schildkröte auf ein teleporterFeld bewegt, befindet er sich bereits auf dem entsprechenden teleporter. Er zieht nie auf ein teleporterund bleibt dort für einen Zug

• Der kürzeste Weg muss das Portal nicht nutzen

• Die Schildkröte kann nicht in Bergkacheln übergehen

• Sie können eine beliebige ASCII - Zeichen oder ganze Zahl verwenden , um darzustellen mountains, turtle, empty grid square,strawberry

• Sie können entweder dasselbe Zeichen oder zwei verschiedene ASCII-Zeichen oder ganze Zahlen verwenden, um die teleporterPaare darzustellen

• Ein Gitter kann mehr als einen Pfad mit derselben kürzesten Pfadlänge haben

• Das ist Code-Golf

Klarstellungen zu Regeln

• Sie sollten behandeln, teleporterssind Einwegartikel.

Begründung : Es wurde darauf hingewiesen, dass der Fall von:

$$\begin{matrix} 🐢&X&🔵&X&🍓\\ 🌄&🌄&🌄&🌄&🌄&\\ 🔴&X&X&X&X \end{matrix}$$

Könnte nur durch zweimaliges Betreten und Verlassen der Portale gelöst werden. Zum Zeitpunkt dieser Klarstellung gingen beide Lösungen davon aus, dass sie entweder zur einmaligen Verwendung bestimmt waren, oder es gab keinen Grund, zuvor verwendete Quadrate zu testen. Um zu vermeiden, dass ihre hart erarbeiteten Lösungen kaputt gehen, schien dies der beste Weg zu sein, diesen Aufbau zu erklären. Daher würde dies als ungültiges Raster angesehen.

Testfälle, die als Listen formatiert sind

[ ['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

Für Menschen formatierte Testfälle

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 und Struktur über: Hungry mouse von Arnauld

Vorgeschlagene Herausforderungen Edit Advice: Kamil-drakari , Beefster

Allgemeine Bearbeitungshinweise: okx nedla2004 mbomb007

JavaScript (ES7),  140 139  138 Bytes

Übernimmt die Eingabe als Ganzzahlmatrix mit der folgenden Zuordnung:

• $-1$ = 🔵 (beliebiges Portal)
• $0$ = (leer)$X$
• $1$ = 🌄 (Berg)
• $2$ = 🐢 (Schildkröte)
• $3$ = 🍓 (Erdbeere)

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

Probieren Sie es online!

Wie?

Die rekursive Hauptsuchfunktion kann entweder nach einem bestimmten Plättchen auf der Tafel suchen (wenn es mit aufgerufen wird ) oder nach einem beliebigen Plättchen bei , das von der aktuellen Position .$g$$t$$t\ne 0$$(x,y)$$(X,Y)$

Es verfolgt die Länge des aktuellen Pfades in und aktualisiert das beste Ergebnis auf wenn die Schildkröte die Erdbeere findet.$i$$R$$\min(R,i)$

Es wird zuerst mit aufgerufen , um die Startposition der Schildkröte zu finden.$t=2$

Es ruft sich mit wenn ein Portal erreicht ist, so dass die Schildkröte zum anderen Portal teleportiert wird. Wir erhöhen während einer solchen Iteration nicht.$t=-1$$i$

Jedes besuchte Plättchen wird vorübergehend auf einen Berg gesetzt, um zu verhindern, dass sich die Schildkröte zweimal auf demselben Plättchen auf demselben Weg bewegt. Wenn wir in einer Sackgasse gefangen sind, stoppt die Rekursion einfach, ohne zu aktualisieren .$R$

Kommentiert

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)

Probieren Sie es online!

Eingabe als Listen, aber mit Zahlen anstelle von Zeichen (dank Quintec) und einem separaten Wert für das Ziel des Teleporters. Diese großen Einrückungen sollten Tabulatorzeichen sein, wenn sie von Stack Exchange entfernt werden. Alle Tipps oder Ideen sind besonders willkommen, da ich der Meinung bin, dass dies viel etwas kürzer werden könnte.

Die Tabelle für die Zeichen, die in der Herausforderung für die für mein Programm verwendeten Zahlen verwendet wurden, ist unten aufgeführt. Sie können dieses Programm jedoch auch verwenden .

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

-10 Byte dank Quintec durch Änderung der Eingabe von Zeichen in Zahlen.

- Vielen Dank an Jonathan Frech, ElPedro und 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

Probieren Sie es online!

Das Problem wird in eine Grafik übersetzt und die Lösung besteht darin, den kürzesten Weg von der Schildkröte zur Erdbeere zu finden.

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