A Turtle Find a Portal

30

Kura-kura ingin bergerak di sepanjang grid untuk mendapatkan makanannya. Dia ingin tahu berapa banyak gerakan yang diperlukan baginya untuk sampai ke sana.

Selain itu karena dia lambat dia memiliki teleporter yang didirikan di sekitar domainnya yang akan dia gunakan jika jalurnya lebih pendek. Atau hindari jika itu memperpanjang jalannya.

Temui kura-kura

🐢

Kura-kura hidup di atas kisi Kura-kura dapat pindah ke sembarang kotak ...

XXXXXXXXXXXX🐢XXXXXXXXXXXX
XXXXXXXX🐢XXXXXXXX

Namun, kura-kura tidak dapat bergerak ke bujur sangkar dengan gunung

X🌄XXXXXX🌄🐢XX🌄XX🌄XXX

Kura-kura ingin memakan Strawberry-nya, dan ingin tahu berapa lama untuk mencapai Strawberry-nya

X🌄🍓🐢🌄XX🌄XXXX
Contoh ini akan mengambil kura-kura 5 putaran
X🌄🍓🌄🌄XX
Untungnya, Kura-kura menemukan teleporter! Ada dua teleport di grid yang saling memetakan. Menginjak teleporter segera memindahkan kura-kura ke teleporter yang sesuai. Teleporter sangat tidak stabil dan setelah menggunakannya sekali, mereka menghilang dan tidak lagi bisa digunakan.
🔵🌄🍓🐢🌄🔴X🌄XXXX
Sekarang lebih cepat bagi kura-kura untuk naik dua kali. Sekarang jalur kura-kura tersingkat adalah 2
🔵🌄🐢🌄🔴X🌄XXXX

Tantangan

Mengingat output konfigurasi grid awal jumlah gerakan itu akan mengambil kura-kura untuk mencapai strawberry-nya.

Aturan

  • Anda dapat berasumsi bahwa kisi input memiliki solusi

  • Setiap kotak hanya akan memiliki satu strawberrydan dua portalsdan satuturtle

  • Kotak input dapat dimasukkan dalam format apa pun yang nyaman

  • Anda harus memperlakukan teleportersitem sekali pakai

  • Giliran penyu yang bergerak ke teleporterkotak dia sudah di sesuai teleporter. Dia tidak pernah pindah ke teleporterdan tinggal di sana untuk bergerak

  • Jalur terpendek tidak perlu menggunakan portal

  • Kura-kura tidak bisa melewati ubin gunung

  • Anda dapat menggunakan karakter ASCII atau integer untuk mewakili mountains, turtle, empty grid square,strawberry

  • Anda dapat menggunakan karakter yang sama atau dua karakter ASCII yang berbeda atau bilangan bulat untuk mewakili teleporterpasangan

  • Grid dapat memiliki lebih dari satu jalur dengan panjang jalur terpendek yang sama

  • Ini adalah

Klarifikasi terhadap Aturan

  • Anda harus memperlakukan teleportersitem sekali pakai.

Alasan : bahwa kasus:

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

Bisa hanya dipecahkan dengan memasukkan dan keluar portal dua kali. Pada saat membuat klarifikasi ini, kedua solusi bertindak dengan mengasumsikan bahwa keduanya adalah penggunaan tunggal, atau tidak ada alasan untuk mencoba kotak yang sebelumnya digunakan. Untuk menghindari pemecahan solusi kerja keras mereka, ini sepertinya cara terbaik untuk pengaturan ini. Oleh karena itu, ini akan dianggap sebagai grid yang tidak valid.

Kasus Uji diformat sebagai daftar

[ ['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 Case diformat untuk manusia

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

Kredit

Desain dan struktur melalui: Mouse lapar oleh Arnauld

Usulan Tantangan Sunting Saran: Kamil-drakari , beefster

Saran Pengeditan Umum: okx nedla2004 mbomb007

akozi
sumber
2
Saya pikir itu akan menjadi ide yang bagus untuk menambahkan test case di mana menggunakan teleporter akan membuatnya lebih lama.
Okx
@Okx Membuat dan menambah sekarang.
akozi
Diedit, terima kasih.
akozi
1
@ xnor Saya merasa ini mungkin abstrak dari aturan asli saya. Jadi mungkin lebih baik untuk portal item yang digunakan?
akozi
1
Terkait (saya pikir).
Charlie

Jawaban:

13

JavaScript (ES7),  140 139  138 byte

Mengambil input sebagai matriks bilangan bulat dengan pemetaan berikut:

  • 1 = 🔵 (portal apa saja)
  • 0 = (kosong)X
  • 1 = 🌄 (gunung)
  • 2 = 🐢 (kura-kura)
  • 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

Cobalah online!

Bagaimana?

Fungsi pencarian rekursif utama dapat mencari ubin tertentu di papan (jika itu disebut dengan ) atau untuk ubin apa pun di yang dapat dicapai dari posisi saat ini .gtt0(x,y)(X,Y)

Ini melacak panjang jalur saat ini di dan memperbarui hasil terbaik to setiap kali kura-kura menemukan strawberry.iRmin(R,i)

Ini pertama kali disebut dengan untuk menemukan posisi awal kura-kura.t=2

Ia menyebut dirinya sendiri dengan jika suatu portal tercapai, sehingga kura-kura tersebut diteleportasikan ke portal lainnya. Kami tidak menambah selama iterasi seperti itu.t=1i

Setiap ubin yang dikunjungi sementara diatur ke gunung untuk mencegah kura-kura bergerak dua kali pada ubin yang sama di jalur yang sama. Jika kita terjebak dalam buntu, rekursi hanya berhenti tanpa memperbarui .R

Berkomentar

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
sumber
1
"Setiap ubin yang dikunjungi sementara diatur ke gunung untuk mencegah kura-kura dari bergerak dua kali di ubin yang sama" Sungguh trik yang bagus. Jawaban yang bagus, dan seperti biasa saya menghargai jawaban dengan penjelasan :)
akozi
5

Python 2 , 441 431 341 byte

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)

Cobalah online!

Masukkan sebagai daftar, tetapi gunakan angka sebagai ganti karakter (terima kasih kepada Quintec) dan nilai terpisah untuk tujuan teleporter. Lekukan besar itu harus berupa karakter tab jika Stack Exchange menghapusnya. Setiap tips atau ide sangat disambut, karena saya merasa ini bisa menjadi jauh lebih pendek.

Tabel untuk karakter yang digunakan dalam tantangan angka yang digunakan untuk program saya ada di bawah, tetapi Anda juga dapat menggunakan program ini .

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

-10 byte terima kasih kepada Quintec dengan mengubah input dari menggunakan karakter menjadi angka.

-Banyak byte berkat Jonathan Frech, ElPedro, dan Jonathan Allan.

nedla2004
sumber
2
Anda mungkin dapat mencukur beberapa karakter dengan mengambil daftar di mana setiap objek diwakili oleh angka, bukan karakter string.
Quintec
@ Quintec Ditambahkan, terima kasih. Saya ingin melakukan hal yang sama untuk arah, tetapi kemudian diagonal harus dilakukan secara terpisah. Meskipun demikian, masih dimungkinkan untuk memindahkannya ke angka.
nedla2004
1
@ ElPedro Ahha Saya dapat mencukur 4 seperti ini
Jonathan Allan
1
... dan 10 lainnya untuk 356
Jonathan Allan
2
@Jonathan Allan dan ElPedro dan Jonathan French. Kiat-kiat hebat dari Anda semua, dan saya telah menambahkannya bersama beberapa hal yang saya buat. (Setelah banyak penundaan)
nedla2004
2

Python 2 , 391 397 403 422 byte

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

Cobalah online!

Masalahnya diterjemahkan ke dalam grafik dan solusinya adalah menemukan jalur terpendek dari kura-kura ke stroberi.

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