Tantangan
Diberikan matriks biner dan string biner, tentukan apakah string biner itu dapat ditemukan mulai dari titik mana saja dalam matriks dan bergerak ke segala arah pada titik selanjutnya untuk membentuk string biner. Artinya, dapatkah string ditemukan terlipat di dalam matriks?
Tali hanya dapat dilipat pada 90 derajat atau 180 derajat (koneksi tepi; Manhattan Distance 1) dan tidak dapat tumpang tindih dengan sendirinya di titik mana pun.
Contoh
Mari kita ambil contoh berikut:
Matrix:
010101
111011
011010
011011
Snake: 0111111100101
Ini adalah kasus uji kebenaran. Kita bisa melihat ular terlipat di posisi berikut:
0-1 0 1 0 1
|
1 1 1-0 1 1
| | | |
0 1 1 0-1-0
| |
0 1-1 0 1 1
Aturan
- Celah Standar Berlaku
- Anda dapat mengambil panjang string dan lebar dan tinggi matriks sebagai input jika Anda mau
- Anda dapat menggunakan matriks biner dan string biner sebagai string multiline / array string / string yang tergabung dengan baris baru / string apa pun yang tergabung dan string
- Anda dapat mengambil dimensi sebagai susunan datar alih-alih beberapa argumen
- Program Anda harus menyelesaikan untuk setiap matriks 5 x 5 dengan string hingga panjang 10 dalam waktu kurang dari satu menit
Keterbatasan
- Matriksnya tidak harus persegi
- String tidak akan kosong
- String bisa panjang-1
- String tidak akan mengandung lebih banyak kotak daripada yang tersedia (yaitu,
len(string) <= width(matrix) * height(matrix)
Uji Kasus
Sejujurnya
01010
10101
01010
10101
01010
0101010101010101010101010
01110
01100
10010
10110
01101
011111000110100
0
0
10
01
1010
100
010
001
100010001
Palsu
00000
00000
00000
00000
00000
1
10101
01010
10101
01010
10101
11
100
010
001
111
10001
01010
00100
01010
10001
1000100010001000101010100
code-golf
decision-problem
binary-matrix
HyperNeutrino
sumber
sumber
Jawaban:
Python 2 ,
275271264249 byte-1
denganH
dan menghapus satu operasi mengiris ([:]
).[:]
), menggunakan penugasan multi-target untuk memberikan entri yang dikunjungi nilaiv not in "01"
(S=S[1:];M[y][x]=H;
->S=M[y][x]=S[1:];
) dan beralih dari terner jika / selain ke logika sederhana atau (any(...)if S else 1
->not S or any(...)
).ZeroDivisionError
) ketika ular ditemukan dan mengembalikan daftar kosong ([]
) ketika tidak ada ular yang ditemukan, yang merupakan dua perilaku berbeda.not S or
keS<[1]or
~S==[]or
.Cobalah online!
Penjelasan
Fungsi Lambda yang mengambil dalam matriks sebagai daftar string dua dimensi (salah satu
"0"
atau"1"
), ular sebagai daftar satu dimensi dan dimensi matriks sebagai dua bilangan bulat.Fungsi lambda mencari matriks untuk entri yang cocok dengan elemen pertama ular. Untuk setiap kecocokan yang ditemukan, ia memanggil
H
dengan salinan yang dalam dari matriks, tidak ada salinan dari ular, dimensi matriks dan posisi pertandingan.Ketika
H
dipanggil, ia menghapusS
entri pertama dan mengatur entri matriks posisi yang diberikan ke sesuatu yang lain selain"0", "1"
. JikaS
'panjang adalah nol, itu akan kembaliTrue
; karena ia menyebut dirinya secara rekursif, ular itu ditemukan di suatu tempat dalam matriks.Jika
S
'panjangnya bukan nol, ia akan melewati empat arah mata angin, menguji apakah posisi itu dalam matriks, membandingkan elemen matriks' pada posisi itu dengan elemen pertamaS
dan - jika cocok - menyebut dirinya secara rekursif.H
Nilai kembali disalurkan ke atas bingkai tumpukan, selalu memeriksa apakah setidaknya satu fungsi menemukan kemungkinan ular.Output Terformat
Saya telah menambahkan program saya untuk juga menampilkan jalur slithers ular (jika ada). Ia menggunakan desain keluaran ASCII yang sama dengan pertanyaan. TIO link .
sumber
m[:]for
~>m*1for
? Mungkin bekerjaJavaScript (ES6),
138134Tidak jauh berbeda dengan @ Neil, tapi apa lagi itu?
Input: matriks sebagai string multi baris, string biner, lebar (tidak termasuk baris baru)
NB: logika dalam fungsi rekursif
r
agak terbalik untuk menyimpan beberapa byteKurang golf
Uji
sumber
JavaScript (ES6), 149 byte
Mengambil matriks sebagai string yang dibatasi-baris baru, ular sebagai string dan lebar (sebagai integer). Secara longgar didasarkan pada jawaban @ JonathanFrech.
sumber
Mathematica,
180156141153138136104 byteContoh input
Penjelasan
GridGraph@{##4}
adalahGraph
objek untuk kisi-kisi simpul dengan simpul-simpul yang berdekatan yang dihubungkan oleh tepian, dengan dimensi{##4}
- yaitu,{#4,#5}
atau{width,height}
.x
(dinomori1
ke1##4 = width*height
), semua simpul akhiry
, dan semua jalurp
panjang paling banyak#3
darix
hinggay
.""<>Part[Join@@#,p]
ekstrak karakter yang sesuai dari matriks dan menempatkannya ke dalam string.s
, mencari di semua level karena ini adalah daftar yang sangat multidimensi yang telah kami buat.Catatan: Mengganti
#3
dengan{#3-1}
dalamFindPath
, sehingga kami hanya menemukan jalur dengan panjang yang tepat, merupakan peningkatan besar dalam hal kecepatan - tetapi biaya 4 byte lebih banyak.-24 byte: mengambil dimensi benda sebagai input
-15 byte: menggunakan
StringPart
danStringJoin
benar+12 byte: memperbaiki casing panjang-1
-15 byte: ...
-2 byte: mengambil ukuran dari matriks sebagai input sebagai array
-32 bytes: menggunakan
Table
untuk beralih di jalan memungkinkan kita menghindari menggunakanFunction
, dan menggunakanMemberQ[...,s,All]
memungkinkan kita hanya semacam menempelkan matriks ke atas meja ketika berhadapan dengan ular panjang 1.sumber
C # (.NET Core) ,
346341336302297 byteCobalah online!
5 byte disimpan dengan
p
menambahkan golf5 byte disimpan dengan mengambil panjang ular dan mulai dari ekornya, dan menghilangkan ruang yang tidak perlu
34 byte disimpan dengan membaca tantangan dengan benar dan melihat saya dapat memperhitungkan tinggi dan lebar matriks
5 byte disimpan, kasus uji elemen tunggal gagal, dan perbaikannya bermanfaat
Tidak disatukan
sumber
if(...)return true;
->return ...;
.b[y,x]
perlu diatur ulang di beberapa titik. (Juga maaf karena salah mengeja nama Anda dalam jawaban saya.)if(N(x,y,0)>0)return 0<1;
; penampilan pertamareturn
.Kotlin , 413 byte
Yg diperindahkan
Uji
sumber