Żółw chce poruszać się wzdłuż siatki, aby dostać się do jedzenia. Chce wiedzieć, ile ruchów zajmie mu dotarcie.

Ponieważ jest wolny, teleportery ustawiają się wokół jego domeny, z której będzie korzystać, jeśli skróci to jego ścieżkę. Lub unikaj ich, jeśli wydłuży to jego drogę.

Poznaj żółwia

🐢

Żółw żyje na siatce

$$\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}$$ Żółw może przejść do dowolnego sąsiedniego kwadratu ... $$\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}$$

Żółw nie może jednak przejść na plac z górą

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

Żółw chce zjeść swoją truskawkę i chce wiedzieć, ile czasu zajmie dojście do jego truskawek

$$\begin{matrix} X&🌄&🍓\\ 🐢&🌄&X\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ Ten przykład zabrałby żółwia o $5$ obrotów $$\begin{matrix} X&🌄&🍓\\ \downarrow&🌄&\uparrow\\ \searrow&🌄&\uparrow\\ X&\nearrow&X\\ \end{matrix}$$ Na szczęście Żółw znalazł teleporter! Na planszy znajdują się dwa teleporty, które odwzorowują się nawzajem. Nadepnięcie na teleporter natychmiast przenosi żółwia do odpowiedniego teleportera. Teleportery są bardzo niestabilne i po ich jednorazowym użyciu znikają i nie są już użyteczne. $$\begin{matrix} 🔵&🌄&🍓\\ 🐢&🌄&🔴\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ Żółw jest teraz szybszy dwukrotnie w górę. Teraz najkrótsza ścieżka żółwi to$2$ $$\begin{matrix} 🔵&🌄&🐢\\ \uparrow&🌄&🔴\uparrow\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$

Wyzwanie

Biorąc pod uwagę początkową konfigurację wyjściową siatki, liczbę ruchów zajmie żółwia, aby osiągnąć swoją truskawkę.

Zasady

• Możesz założyć, że siatka wejściowa ma rozwiązanie

• Każda siatka będzie miała tylko jeden, strawberrydwa portalsi jedenturtle

• Siatkę wejściową można wprowadzić w dowolnym dogodnym formacie

• Powinieneś traktować teleportersprzedmioty jednorazowego użytku

• Turn, w którym żółw porusza się na pole teleporter, jest już na odpowiednim teleporter. Nigdy nie przechodzi na teleporteri pozostaje tam, aby wykonać ruch

• Najkrótsza ścieżka nie musi korzystać z portalu

• Żółw nie może przejść do górskich kafelków

• Można użyć dowolnego znaku ASCII lub całkowitą do reprezentacji mountains, turtle, empty grid square,strawberry

• Możesz użyć tego samego znaku lub dwóch różnych znaków ASCII lub liczb całkowitych do przedstawienia teleporterpar

• Siatka może mieć więcej niż jedną ścieżkę o tej samej najkrótszej długości

• To jest golf golfowy

Wyjaśnienia zasad

• Powinieneś traktować teleportersprzedmioty jednorazowego użytku.

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

Można to rozwiązać tylko dwukrotnie wchodząc i wychodząc z portali. W momencie dokonywania tego wyjaśnienia oba rozwiązania działały, zakładając, że były albo jednorazowego użytku, albo nie było powodu, aby wypróbować wcześniej używane kwadraty. Aby uniknąć zerwania z ciężko wypracowanymi rozwiązaniami, wydawało się to najlepszym sposobem na uwzględnienie tego ustawienia. Dlatego byłoby to uważane za nieprawidłową siatkę.

Przypadki testowe sformatowane jako listy

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

Przypadki testowe sformatowane dla ludzi

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

Kredyty

Projekt i struktura: Głodna mysz Arnauld

Proponowane wyzwania Edytuj porady: Kamil-drakari , beefster

Ogólne porady dotyczące edycji: okx nedla2004 mbomb007

JavaScript (ES7),  140 139  138 bajtów

Pobiera dane wejściowe jako macierz liczb całkowitych z następującym odwzorowaniem:

• $-1$ = 🔵 (dowolny portal)
• $0$ = $X$ (pusty)
• $1$ = 🌄 (góra)
• $2$ = 🐢 (żółw)
• $3$ = 🍓 (truskawka)

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

Wypróbuj online!

W jaki sposób?

Główna funkcja wyszukiwania rekurencyjnego $g$ jest w stanie wyszukać konkretny kafelek $t$ na planszy (jeśli jest wywoływane z $t\ne 0$) lub dla dowolnego kafelka pod adresem $(x,y)$ do którego można dotrzeć z bieżącej pozycji $(X,Y)$.

Śledzi długość bieżącej ścieżki w $i$ i aktualizuje najlepszy wynik $R$ do $\min(R,i)$ ilekroć żółw znajdzie truskawkę.

Najpierw jest wywoływany z $t=2$ znaleźć pozycję początkową żółwia.

To się nazywa $t=-1$po osiągnięciu portalu, aby żółw został teleportowany do innego portalu. Nie zwiększamy$i$ podczas takiej iteracji.

Każda odwiedzana płytka jest tymczasowo ustawiona na górę, aby żółw nie poruszał się dwukrotnie po tej samej płytce na tej samej ścieżce. Jeśli zostaniemy uwięzieni w ślepym zaułku, rekursja po prostu zatrzymuje się bez aktualizacji$R$.

Skomentował

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 bajtów

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)

Wypróbuj online!

Wprowadź jako listy, ale używając liczb zamiast znaków (dzięki Quintec) i osobnej wartości dla miejsca docelowego teleportera. Te duże wcięcia powinny być znakami tabulacji, jeśli Stack Exchange je usunie. Wszelkie wskazówki lub pomysły szczególnie mile widziane, ponieważ czuję, że to może dostać znacznie nieco krótszy.

Tabela znaków używanych w wyzwaniu do liczb używanych w moim programie znajduje się poniżej, ale możesz także użyć tego programu .

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

-10 bajtów dzięki Quintec, zmieniając dane wejściowe z używania znaków na liczby.

- Dużo bajtów dzięki Jonathanowi Frechowi, ElPedro i Jonathanowi Allanowi.

Python 2 , 391 397 403 422 bajtów

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

Wypróbuj online!

Problem jest tłumaczony na wykres, a rozwiązaniem jest znalezienie najkrótszej ścieżki od żółwia do truskawki.

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