Żółw znajduje portal

30

Żół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

XXXXXXXXXXXX🐢XXXXXXXXXXXX
Żółw może przejść do dowolnego sąsiedniego kwadratu ...
XXXXXXXX🐢XXXXXXXX

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

X🌄XXXXXX🌄🐢XX🌄XX🌄XXX

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

X🌄🍓🐢🌄XX🌄XXXX
Ten przykład zabrałby żółwia o 5 obrotów
X🌄🍓🌄🌄XX
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.
🔵🌄🍓🐢🌄🔴X🌄XXXX
Żółw jest teraz szybszy dwukrotnie w górę. Teraz najkrótsza ścieżka żółwi to2)
🔵🌄🐢🌄🔴X🌄XXXX

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

Wyjaśnienia zasad

  • Powinieneś traktować teleportersprzedmioty jednorazowego użytku.

🐢X🔵X🍓🌄🌄🌄🌄🌄🔴XXXX

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

akozi
źródło
2
Myślę, że dobrym pomysłem byłoby dodanie skrzynki testowej, w której użycie teleportera wydłużyłoby czas.
Okx
@Okx Tworzenie i dodawanie teraz.
akozi
Edytowane, dzięki.
akozi
1
@xnor Wydaje mi się, że może to być abstrakcja moich pierwotnych zasad. Więc może lepiej jest portalizować przedmiot jednorazowego użytku?
akozi
1
Powiązane (myślę).
Charlie

Odpowiedzi:

13

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 sol jest w stanie wyszukać konkretny kafelek t na planszy (jeśli jest wywoływane z t0) 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 ja i aktualizuje najlepszy wynik R do min(R,ja) ilekroć żółw znajdzie truskawkę.

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

To się nazywa t=-1po osiągnięciu portalu, aby żółw został teleportowany do innego portalu. Nie zwiększamyja 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 aktualizacjiR.

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
Arnauld
źródło
1
„Każda odwiedzana płytka jest tymczasowo ustawiona na górę, aby żółw nie poruszał się dwukrotnie po tej samej płytce.” Co za cudowna sztuczka. Świetna odpowiedź i jak zawsze doceniam odpowiedzi z wyjaśnieniami :)
akozi
5

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.

nedla2004
źródło
2
Prawdopodobnie możesz ogolić kilka znaków, biorąc listę, na której każdy obiekt jest reprezentowany przez liczbę zamiast znaku ciągu.
Quintec
@Quintec Dodano, dzięki. Chciałbym zrobić to samo dla wskazówek, ale wtedy przekątne musiałyby być wykonane osobno. Nadal jednak możliwe jest przeniesienie ich na liczby.
nedla2004
1
@ElPedro Ahha Mogę ogolić 4 w ten sposób
Jonathan Allan
1
... i kolejne 10 za 356
Jonathan Allan
2
@JonathanAllan i ElPedro i Jonathan French. Świetne wskazówki od was wszystkich i dodałem je razem z kilkoma rzeczami, które wymyśliłem. (Po dużym opóźnieniu)
nedla2004
2

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
mdahmoune
źródło