Temukan pengantar tidur pembakar

26

Bayangkan seorang pembakar berjalan di sekitar kota dan mengambil korbannya sesuai dengan pola yang sangat spesifik (Atau, sebagai alternatif, Bayangkan seekor lebah terbang di sekitar taman dan memetik bunga-bunganya untuk diserbuki menurut pola yang sangat spesifik ). Katakanlah kota adalah matriks N × N , di mana N adalah bilangan bulat yang lebih tinggi dari atau sama dengan 2 . Pembakar memulai dari sudut kiri atas dan berturut-turut menetapkan titik M rumah di depan mereka (di mana M adalah jumlah rumah tempat mereka berada saat ini), sambil mengubah arahnya bergerak setelah setiap kebakaran, dalam urutan Timur, Selatan, Barat, Utara, Timur, Selatan, dan seterusnya. Lagu pengantar tidur itudari pelaku pembakaran adalah nilai M yang membuat mereka keluar dari kota (yaitu rumah terakhir yang mereka kunjungi sebelum menghentikan kekejian). Ini adalah cara yang lebih mudah untuk dipahami dengan sebuah contoh. Sebagai contoh, ambil matriks berikut:

3 2 3 2 7
3 1 4 1 6
2 5 3 1 1
4 4 3 2 4
1 1 1 1 1
  • Kita mulai di sudut kiri atas, jadi M = 3 ( Xmenandai posisi saat ini dan sebelumnya dari pelaku pembakaran):
    X 2 3 2 7
    3 1 4 1 6
    2 5 3 1 1
    4 4 3 2 4
    1 1 1 1 1
    
  • Menurut urutan yang diketahui, pertama kali menuju ke timur M (3) tempat dan mendarat pada 2 sehingga M berubah sesuai:
    X 2 3 X 7
    3 1 4 1 6
    2 5 3 1 1
    4 4 3 2 4
    1 1 1 1 1
    
  • Lalu pergi ke selatan 2 tempat dan M sekarang 1 :
    X 2 3 X 7
    3 1 4 1 6
    2 5 3 X 1
    4 4 3 2 4
    1 1 1 1 1
    
  • Sekarang bergerak 1 tempat ke Barat dan M menjadi 3 :
    X 2 3 X 7
    3 1 4 1 6
    2 5 XX 1
    4 4 3 2 4
    1 1 1 1 1
    
  • Setelah bergerak 3 titik ke utara, ia keluar kota! Karena itu, 3 adalah lagu pengantar tidur pembakar ini:
        X
    X 2 3 X 7
    3 1 4 1 6
    2 5 XX 1
    4 4 3 2 4
    1 1 1 1 1
    

Diberi matriks N × N (Anda juga dapat mengambil N sebagai input), temukan pengantar tidur sang pelaku pembakaran. Saya telah menulis sebuah program yang dengannya Anda dapat menghasilkan lebih banyak kasus uji dan memvisualisasikan jalur pelaku pembakaran: Cobalah secara online!

  • Anda dapat berasumsi bahwa pelaku pembakaran memang memiliki lagu pengantar tidur (yaitu, ia benar-benar dapat keluar dari matriks).
  • Matriks hanya akan berisi bilangan bulat positif kurang dari atau sama dengan 9 (digit), untuk kesederhanaan. Solusi yang menangani bilangan bulat positif sangat disambut.
  • Perhatikan bahwa pelaku pembakaran dapat mendarat di tempat yang telah mereka bakar, kalau-kalau perasaan mereka berbeda dari yang pertama kali. Dalam skenario seperti itu, ambil saja nilai elemen itu dan bergerak lagi seperti biasa.
  • Anda dapat bersaing dalam bahasa pemrograman apa pun dan dapat mengambil input dan memberikan output melalui metode standar apa pun , sambil memperhatikan bahwa celah ini dilarang secara default. Ini adalah , jadi pengiriman terpendek (dalam byte) untuk setiap bahasa menang.

Uji kasus

-------------
9 2 3
1 7 2
8 7 6

Lagu pengantar tidur: 9
-------------
2 1 2 1
3 1 1 2
1 2 2 1
1 1 1 3

Lagu pengantar tidur: 2
-------------
3 2 3 2 7
3 1 4 1 6
2 5 3 1 1
4 4 3 2 4
1 1 1 1 1

Lagu pengantar tidur: 3
-------------
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2

Lagu pengantar tidur: 2
-------------
3 2 1 2 1 1 1
2 3 2 3 2 1 1
2 1 1 1 3 1 2
3 1 1 1 1 1 1
4 5 2 3 1 1 1
1 2 1 2 1 2 2
1 2 2 3 2 1 2

Lagu pengantar tidur: 3
-------------

Matriks dalam format yang berbeda:

[[9, 2, 3], [1, 7, 2], [8, 7, 6]]
[[2, 1, 2, 1], [3, 1, 1, 2], [1, 2, 2, 1], [1, 1, 1, 3]]
[[3, 2, 3, 2, 7], [3, 1, 4, 1, 6], [2, 5, 3, 1, 1], [4, 4, 3, 2, 4], [ 1, 1, 1, 1, 1]]
[[1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2]]
[[3, 2, 1, 2, 1, 1, 1], [2, 3, 2, 3, 2, 1, 1], [2, 1, 1, 1, 3, 1, 2]], [ 3, 1, 1, 1, 1, 1, 1], [4, 5, 2, 3, 1, 1, 1], [1, 2, 1, 2, 1, 2, 2, 2], [1, 2, 2, 3, 2, 1, 2]]

Kasus uji kelima sangat menarik untuk divisualisasikan .

Tuan Xcoder
sumber
1
Ini seperti generalisasi Lewati seperti Kelinci dalam dua dimensi, dengan tujuan yang sedikit berbeda. Tema dari tantangan ini dan judulnya diilhami oleh lagu oleh Hozier
Mr. Xcoder
apa yang terjadi ketika pelaku pembakaran mendarat di sebuah kotak yang sudah terbakar?
Level River St
2
Bisakah kita berasumsi bahwa pelaku pembakaran sebenarnya bukan pelaku pembakaran dan malah melakukan sesuatu yang baik di setiap lokasi daripada membakarnya? +1 untuk ide yang sangat bagus :)
ElPedro
2
@ ElPedro Tentu, versi alternatif untuk Anda: Bayangkan seekor lebah terbang di sekitar taman dan memetik bunga-bunganya untuk diserbuki menurut pola yang sangat spesifik. : D Selamat bermain golf!
Tn. Xcoder
1
Itu pemikiran yang jauh lebih baik. Jika saya dapat membenarkan lagi saya akan untuk itu.
ElPedro

Jawaban:

11

MATL , 32 byte

JQ6*`G5thYay&Zj3$)wyJ2@-^*+8M]b&

Cobalah online! Atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Matriks input diisi dengan bingkai lima nol, jadi misalnya

3 2 3 2 7
3 1 4 1 6
2 5 3 1 1
4 4 3 2 4
1 1 1 1 1

menjadi

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 2 3 2 7 0 0 0 0 0
0 0 0 0 0 3 1 4 1 6 0 0 0 0 0
0 0 0 0 0 2 5 3 1 1 0 0 0 0 0
0 0 0 0 0 4 4 3 2 4 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Bingkai nol digunakan untuk mendeteksi ketika lebah pembakar telah keluar dari matriks. Perpanjangan dengan lima nol memastikan bahwa perpindahan modular dengan panjang hingga ke 9arah mana pun dari salah satu entri bukan nol akan mendarat dengan benar di nol tanpa membungkus beberapa entri non-nol.

Dalam koordinat matriks, lebah mulai saat masuknya (6,6)matriks yang diperluas. Bunyinya entri itu, dan memperbarui koordinat yang diperlukan, menerapkan perpindahan (modular) dari panjang baca ke arah yang sesuai. Ini diulang dalam satu lingkaran sampai nilai baca adalah 0. Entri yang telah dibaca sebelum itu (yaitu entri bukan nol terakhir) adalah output.

Koordinat sebenarnya disimpan sebagai bilangan kompleks, jadi misalnya (6,6)menjadi 6+6j. Dengan cara ini empat arah siklik dapat direalisasikan sebagai kekuatan unit imajiner. Kekuatan yang sesuai ( j, 1, -jatau -1) dikalikan dengan masuknya membaca untuk mendapatkan perpindahan kompleks yang digunakan untuk memperbarui koordinat.

Nilai yang dibaca berturut-turut disimpan di tumpukan. Ketika loop keluar, tumpukan berisi semua nilai baca non-nol secara berurutan, lalu nilai baca terakhir 0, lalu koordinat kompleks terbaru. Jadi elemen ketiga atas adalah output yang dibutuhkan.

Luis Mendo
sumber
1
+1 untuk pendekatan yang sangat inovatif.
LastStar007
7

JavaScript (ES6), 70 68 byte

m=>(g=d=>(n=(m[y]||0)[x])?g(--d&3,x-=d%2*(y+=--d%2*n,L=n)):L)(x=y=0)

Cobalah online!

Berkomentar

m => (                        // given m = input matrix
  g = d =>                    // g = recursive function taking the direction d
    (n = (m[y] || 0)[x]) ?    // let n be the content of the current cell; if it's defined:
      g(                      //   do a recursive call:
        --d & 3,              //     with the next direction (0 = E, 3 = S, 2 = W, 1 = N)
        x -=                  //     update x by subtracting ...
          d % 2 * (           //       ... ((d - 1) % 2) * n
            y += --d % 2 * n, //       and update y by adding ((d - 2) % 2) * n
            L = n             //       save n into L
          )                   //     end of x update
      )                       //   end of recursive call
    :                         // else:
      L                       //   stop recursion and return L
)(x = y = 0)                  // initial call to g() with x = y = d = 0

Mengingat bahwa tanda modulo di JS adalah dividen, arahnya diperbarui seperti ini:

 d | d' = --d&3 | dx = -(d%2)  | dy = --d%2 | direction
---+------------+--------------+------------+------------------
 0 |     3      | -(-1%2) = +1 | -2%2 =  0  | (+1,  0) = East
 3 |     2      | -( 2%2) =  0 |  1%2 = +1  | ( 0, +1) = South
 2 |     1      | -( 1%2) = -1 |  0%2 =  0  | (-1,  0) = West
 1 |     0      | -( 0%2) =  0 | -1%2 = -1  | ( 0, -1) = North
Arnauld
sumber
4

Arang , 25 18 byte

PS↶WKK«≔ιθ×Iι¶↷»⎚θ

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

PS

Cetak string input, tetapi jangan gerakkan posisi cetak.

Putar pivot ke kiri, sehingga arah cetak sekarang naik.

WKK«

Ulangi saat ada karakter di bawah posisi cetak.

≔ιθ

Simpan karakter dalam sebuah variabel.

×Iι¶

Keluarkan karakter ke angka dan cetak banyak baris baru. Karena arah cetak sekarang naik, ini berakhir dengan mencetak horizontal. Hasilnya adalah bahwa kami telah memindahkan posisi cetak ke arah yang diinginkan dengan jumlah yang diberikan oleh nomor di bawah posisi cetak.

↷»

Putar pivot sehingga baris baru berikutnya memindahkan posisi cetak searah dengan jarum jam untuk lintasan loop berikutnya.

F⟦ωθ⟧¿ιι⎚

Sayangnya kami masih memiliki input yang mengacaukan kanvas kami, dan bahkan lebih sialnya, jika kami membersihkan kanvas kami juga menghapus variabel kami. Jadi, ini sedikit trik: daftar string kosong dan variabel dilingkarkan. Pada pass pertama dari loop, variabel loop kosong, sehingga kanvas dan variabel loop dan variabel hasil semuanya dihapus. Tetapi loop belum selesai! Pada putaran kedua loop, kita masih bisa mengakses variabel kita dengan hati-hati tersimpan dalam daftar loop kita. Tinggal mencetaknya saja.

⎚θ

Bersihkan kanvas dan cetak variabel yang disimpan. (Terima kasih kepada @ ASCII-only untuk perbaikan ke Arang.)

Neil
sumber
2

Python 2 , 85 84 byte

a=input();x=y=e=0;d=1
while-1<y<len(a)>x>=0:v=a[y][x];x+=v*d;y+=e*v;d,e=-e,d
print v

Cobalah online!

Kiat topi untuk Tn. Xcoder selama 1 byte.

Chas Brown
sumber
2

Arang , 50 49 46 34 33 26 byte

NθEθSMθ↑WKK«MIι✳⊗Lυ⊞υι»⎚⊟υ

Cobalah online

Tautan adalah ke versi kode yang verbose

Input harus berupa N pada barisnya sendiri, kemudian baris array pada baris yang terpisah setelah itu.

Segala cara untuk melepaskan byte disambut dan diinginkan, karena saya bukan pegolf yang baik di Charcoal!

-12 byte terima kasih kepada @Neil! -1 byte terima kasih hanya untuk @ ASCII! -7 byte berkat hanya @ ASCII (mengubah bug yang membuat Clearvariabel reset)

Zacharý
sumber
1

Merah , 145 byte

func[b][h:[0 1 0 -1 0]x: y: 1 i: 0
until[y: h/(i: i % 4 + 1) *(t: b/(y)/(x)) + y x: h/(i + 1) * t + x none = b/(y) or(x < 1 or(x > length? b))]t]

Cobalah online!

Lebih mudah dibaca:

f: func[b][
    h: [0 1 0 -1 0]                                ; step lengths (combined for x and y) 
    x: y: 1                                        ; starting coords (1,1)
    i: 0                                           ; step counter 
    until[
        y: h/(i: i % 4 + 1) * (t: b/(y)/(x)) + y   ; next y; t stores the lullaby
        x: h/(i + 1) * t + x                       ; next x
        none = b/(y) or (x < 1 or (x > length? b)) ; until x or y are not valid indices
    ]
    t                                              ; return the lullaby
]
Galen Ivanov
sumber
1

Perl 6 , 62 byte

{$^w;$^m[0,{$_+$m[$_]*(1,$w,-1,-$w)[$++%4]}...{!$m[$_]}][*-2]}

Cobalah online!

Mengambil matriks sebagai daftar datar dan lebar.

nwellnhof
sumber
1

Bersih , 141 byte

import StdEnv
d=[0,1,1,0,0,-1,-1,0:d]
$m[x,y]n[a,b:l]#r=size m
#u=x+a*n
#v=y+b*n
|0>u||0>v||u>=r||v>=r=n= $m[u,v]m.[u,v]l
?m= $m[0,0]m.[0,0]d

Cobalah online!

Menentukan fungsi ? :: {#{#Int}} -> Int, mengambil larik bilangan bulat tanpa kotak dari bilangan bulat dan mengembalikan hasilnya.

Suram
sumber
1

Java 8, 121 byte

m->{int l=m.length,x=0,y=0,f=0,r=0;for(;x*y>=0&x<l&y<l;x+=f<1?r:f==2?-r:0,y+=f==1?r:f>2?-r:0,f=++f%4)r=m[y][x];return r;}

Cobalah online.

Alternatif dengan 121 byte byte-count yang sama:

m->{int l=m.length,x=0,y=0,f=0,r=0;try{for(;;x+=f<1?r:f==2?-r:0,y+=f==1?r:f>2?-r:0,f=++f%4)r=m[y][x];}finally{return r;}}

Menggunakan try-akhirnya alih-alih memeriksa apakah x,y-coordinate masih dalam batas.

Cobalah online.

Penjelasan:

m->{                   // Method with integer-matrix parameter and integer return-type
  int l=m.length,      //  Dimensions of the matrix
      x=0,y=0,         //  x,y coordinate, starting at [0,0]
      f=0,             //  Direction-flag, starting at 0 (east)
      r=0;             //  Result-integer
  for(;x*y>=0&x<l&y<l  //  Loop as long as the x,y coordinates are still within bounds
      ;                //    After every iteration:
       x+=f<1?         //     If the direction is east:
           r           //      Increase the `x` coordinate by `r`
          :f==2?       //     Else-if the direction is west:
           -r          //      Decrease the `x` coordinate by `r`
          :            //     Else (it's north/south):
           0,          //      Leave the `x` coordinate the same
       y+=f==1?        //     If the direction is south:
           r           //      Increase the `y` coordinate by `r`
          :f>2?        //     Else-if the direction is north:
           -r          //      Decrease the `y` coordinate by `r`
          :            //     Else:
           0,          //      Leave the `y` coordinate the same
       f=++f%4)        //     Go to the next direction (0→1→2→3→0)
    r=m[y][x];         //   Set `r` to the value of the current cell
  return r;}           //  Return the last `r` before we went out of bounds
Kevin Cruijssen
sumber
0

Perl 5 , 92 byte

sub b{1while eval join'&&',map{/./;map"(\$$_$&=".'$n=$_[$y][$x])'.$',x,'y'}'+<@_','->=0';$n}

Cobalah online!

Bagaimana?

Set peta bersarang dan gabungan menghasilkan ini:

($x+=$n=$_[$y][$x])<@_&&($y+=$n=$_[$y][$x])<@_&&($x-=$n=$_[$y][$x])>=0&&($y-=$n=$_[$y][$x])>=0

yang kemudian dievaluasi untuk menentukan apakah loop berakhir. Karena Boolean dievaluasi dari kiri ke kanan, nilai $nsebenarnya berubah (hingga) empat kali selama evaluasi. Karena sirkuit pendek logika Boolean dalam Perl, nilai $nadalah pengantar tidur ketika loop keluar.

Xcali
sumber
0

Python 3 , 85 84 byte

xcoder: -1 (Saya tidak pernah ingat + ~ trik)

def f(x):
 r=c=0
 while-1<r:d=x[r][c];r,c=len(x)-c+~d,r;x=[*zip(*x)][::-1]
 return d

Cobalah online!

Alih-alih bergerak ke arah yang berbeda (E, S, W, N), solusi ini selalu bergerak ke timur dan memutar konter searah jarum jam setelah setiap gerakan. Setelah berputar, apa yang menjadi kolom terakhir sekarang adalah baris pertama, jadi jika indeks baris kurang dari nol itu berarti kita lari dari papan.

RootTwo
sumber
84 byte : -d-1=>+~d
Mr. Xcoder
0

Retina , 161 byte

.
 $.%`*_#$&*
(?<=(.+¶)+|^)
A ¶A$#1*
~(K`{`^X\1YZ¶1S$4¶1XYZ¶2$4$2$4$3¶2XYZ¶3S¶3XY\1Z¶S
X
(_$*)(A_$*)
Y
( _$*)
Z
(?=\n\D$*\2\b.$*\3#(_+))
)`S
$$4$$2$$3
L$0`_+
$.0

Cobalah online!

TwiNight
sumber