Diberikan matriks dua dimensi 0 dan 1. Temukan jumlah pulau untuk 1s dan 0s di mana tetangga hanya berada dalam posisi horizontal dan vertikal.
Given input:
1 1 1 0
1 1 1 0
output = 1 1
Number of 1s island = 1
xxx-
xxx-
Number of 0s island = 1
---x
---x
------------------------------
Given input:
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
output = 2 2
Number of 1s island = 2
----
xxxx <-- an island of 1s
----
xxxx <-- another island of 1s
Number of 0s island = 2
xxxx <-- an island
----
xxxx <-- another island
----
------------------------------
Given input:
1 0 0
0 0 0
0 0 1
output = 2 1
Number for 1's island = 2:
x-- <-- an island of 1s
---
--x <-- an island of 1s
Number of 0's island = 1:
-xx \
xxx > 1 big island of 0s
xx- /
------------------------------
Given input:
1 1 0
1 0 0
output = 1 1
Number for 1's island =1 and number of 0's island = 1
------------------------------
Given input:
1 1
1 1
output = 1 0
Number for 1's island =1 and number of 0's island = 0
code-golf
binary-matrix
KB sukacita
sumber
sumber
[[1,0];[0,1]]
memastikan konektivitas diagonal tidak termasuk11111 / 10001 / 10101 / 10001 / 11111
2 1
Jawaban:
APL (Dyalog Unicode) ,
2928 byte SBCS-1 terima kasih kepada @ Adám
Cobalah online!
⊂,~∘⊂
matriks dan negasinya{
}¨
untuk masing-masing dari mereka⍸⍵
daftar pasangan 1s+/↑|∘.-⍨
matriks jarak manhattan2>
matriks tetangga∨.∧⍨⍣≡
penutupan transitif≢∪
jumlah baris uniksumber
^:_
?J , 57 byte
Cobalah online!
Ini adalah salah satu di mana idenya sangat sederhana (dan saya pikir menyenangkan), tetapi mengeksekusinya memiliki panjang mekanik yang menutupi kesederhanaan ... misalnya, menggeser matriks asli ke segala arah dengan 0 fill adalah verbose
((,-)#:i.3) |.!.0
.Kemungkinan panjang mekanik ini dapat di-golf lebih lanjut, dan saya dapat mencoba besok malam, tetapi saya akan memposting inti masalahnya sekarang.
Katakan input kami adalah:
Kita mulai dengan matriks bilangan bulat unik dengan ukuran yang sama:
Kemudian untuk setiap sel kita menemukan maks semua tetangganya, dan dikalikan dengan topeng input:
Kami mengulangi proses ini sampai matriks berhenti berubah:
Dan kemudian hitung jumlah elemen unik, bukan nol. Itu memberitahu kita jumlah 1-pulau.
Kami menerapkan proses yang sama untuk "1 minus input" untuk mendapatkan jumlah 0-pulau.
sumber
JavaScript (ES7),
138 ... 107106 byteMengembalikan array
[ones, zeros]
.Cobalah online!
Bagaimana?
Kami menggunakan fungsi rekursif. Selama panggilan awal, kami mencari0 dan 1 . Setiap kali kami menemukan titik awal seperti itu, kami menambah penghitung pulau yang sesuai ( c [ 0 ] atau c [ 1 ] ) dan memasuki fase rekursif untuk mengisi area sel yang berdekatan yang serupa dengan 2 's.
Untuk menyimpan byte, kode yang sama persis digunakan untuk iterasi root dan iterasi rekursif, tetapi berperilaku sedikit berbeda.
Selama iterasi pertama:
Selama iterasi rekursif:
c[v ^ 1]++
ini valid jikaBerkomentar
sumber
MATL ,
1412 byteCobalah online! Atau verifikasi semua kasus uji .
Penjelasan
sumber
K (ngn / k) ,
60 55 51 5046 byteCobalah online!
~:\
sepasang input dan negasinya (secara harfiah: negate iterate-konvergen){
}'
untuk setiap,/x
ratakan arg&
dimana 1s? - daftar indeks(0,#*x)\
lebar divmod (input) untuk mendapatkan dua daftar terpisah untuk ys dan xsx-\:'x:
jarak per-sumbu ∆x dan ∆yx*x:
persegi mereka+/
tambahkan ∆x² dan ∆y²2>
matriks tetangga{|/'x*\:x}/
penutupan transitif#?
hitung baris uniksumber
Bahasa Wolfram (Mathematica) ,
6462 byteCobalah online!
Berkat attinat : kita bisa menulis
1<0
alih-alihFalse
dan menyimpan dua byte.versi tidak golf:
Ada, tentu saja, sebuah Mathematica builtin
MorphologicalComponents
yang mengambil array (atau gambar) dan mengembalikan yang sama dengan piksel setiap pulau yang terhubung secara morfologis digantikan oleh indeks pulau. MengambilMax
dari hasil ini memberikan jumlah pulau (nol latar belakang dibiarkan nol, dan indeks pulau dimulai pada 1). Kita perlu melakukan ini secara terpisah untuk array (memberikan jumlah 1-pulau) dan satu minus array (memberikan jumlah 0-pulau). Untuk memastikan tetangga diagonal tidak dihitung sebagai tetangga, opsiCornerNeighbors->False
harus diberikan.sumber
Rule
Python 3,
144127 byteSolusi ini menggunakan
cv2
kekuatan pemrosesan gambar yang luar biasa. Meskipun nama metode cv kurang mengagumkan, super panjang dan mudah dibaca, ini mengalahkan kedua jawaban Python lainnya!Golf:
Diperluas:
sumber
4
bukannyaconnectivity=4
dann.uint8
bukannyadtype=n.uint8
mungkin?cv2.connectedComponents
metode, jadi saya bingung dan berpikir mungkin ada alasan berbeda untuk memerlukan nama argumen. Seperti yang saya katakan, saya tidak terlalu terbiasa dengan Python. Yang saya pelajari darinya adalah dari sini di CCGC. ;) Tetapi masuk akal untuk menggunakan nama variabel untuk melewati argumen opsional lainnya.J ,
46 4443 byte-1 byte terima kasih kepada @miles
Cobalah online!
tes dan
,&
-.
bungkusnya dicuri dari jawaban @ jonah,&
-.
untuk input dan negasinya lakukan:4$.$.
(y, x) koordinat 1s sebagai matriks n × 21#.[:|@-"1/~
jarak manhattan: abs (∆x) + abs (∆y)2>
matriks tetangga[:+./ .*~^:_:
penutupan transitif#&~.&(
)
jumlah baris uniksumber
,&#&~.
untuk menghindari tutup[:
Retina 0.8.2 , 155 byte
Cobalah online! Tautan termasuk test case. Penjelasan:
Jika ada
1
, ubah ke;
dan tambahkana
ke akhir input sehingga tidak menghalangi.Banjir mengisi lagi yang berdekatan
1
dengan;
s.Ulangi sampai semua pulau
1
telah berubah menjadi;
.Jika ada
0
, ubah ke:
dan tambahkan ab
ke akhir input sehingga tidak menghalangi.Isi banjir lagi bersebelahan
0
dengan:
s.Ulangi sampai semua pulau
0
telah berubah menjadi:
.Hitung secara terpisah jumlah pulau
1
s dan0
s.sumber
Haskell ,
228227225224 byteCobalah online!
Penjelasan:
Gagasan untuk solusi ini adalah sebagai berikut: Menginisialisasi matriks dengan nilai unik di setiap sel, positif untuk
1
dan negatif untuk0
. Kemudian berulang kali membandingkan setiap sel dengan tetangganya dan, jika tetangganya memiliki tanda yang sama tetapi nomor dengan nilai absolut yang lebih besar, ganti nomor sel dengan nomor tetangga. Setelah ini mencapai titik tetap, hitung jumlah angka positif berbeda untuk jumlah1
wilayah dan angka negatif berbeda untuk jumlah0
wilayah.Dalam kode:
dapat dipisahkan menjadi preprocessing (menetapkan angka ke sel), iterasi, dan postprocessing (menghitung sel)
Preprocessing
Bagian preprocessing adalah fungsinya
Yang digunakan
z
sebagai singkatan untukzipWith
mencukur beberapa byte. Apa yang kita lakukan di sini adalah zip array dua dimensi dengan indeks integer di baris dan indeks integer ganjil di kolom. Kami melakukan ini karena kami dapat membangun bilangan bulat unik dari sepasang bilangan bulat(i,j)
menggunakan rumus(2^i)*(2j+1)
. Jika kami hanya menghasilkan bilangan bulat ganjil untukj
, kami dapat melewati penghitungan2*j+1
, menghemat tiga byte.Dengan nomor unik, kita sekarang hanya perlu mengalikan tanda berdasarkan nilai dalam matriks, yang diperoleh sebagai
2*x-1
Perulangan
Iterasi dilakukan oleh
Karena inputnya dalam bentuk daftar daftar, kami melakukan perbandingan tetangga pada setiap baris, mengubah matriks, melakukan perbandingan pada setiap baris lagi (yang karena transpose adalah apa yang menjadi kolom sebelumnya) dan mentranspos lagi. Kode yang menyelesaikan salah satu dari langkah-langkah ini adalah
((.)>>=id$transpose.map l)
di mana
l
fungsi perbandingan (dirinci di bawah) dantranspose.map l
melakukan setengah dari langkah perbandingan dan transposisi.(.)>>=id
melakukan argumennya dua kali, menjadi bentuk pointfree\f -> f.f
dan lebih pendek satu byte dalam hal ini karena aturan prioritas operator.l
didefinisikan pada baris di atas sebagail x=z(!)(z(!)x(0:x))$tail x++[0]
. Kode ini melakukan operator pembanding(!)
(lihat di bawah) pada setiap sel dengan tetangga sebelah kiri pertama, dan kemudian dengan tetangga kanannya, dengan zip daftarx
dengan daftar bergeser kanan dan bergeser daftar0:x
kiritail x++[0]
pada gilirannya. Kami menggunakan nol untuk membuat daftar bergeser, karena mereka tidak pernah dapat terjadi dalam matriks yang telah diproses.a!b
didefinisikan pada baris di atas ini sebagaia!b=div(max(a*a)(a*b))a
. Yang ingin kami lakukan di sini adalah perbedaan kasus berikut:sgn(a) = -sgn(b)
, kami memiliki dua bidang yang berlawanan dalam matriks dan tidak ingin menyatukannya, jadia
tetaplah tidak berubahsgn(b) = 0
, kami memiliki kasing sudut di manab
bantalan dan oleh karena itua
tetap tidak berubahsgn(a) = sgn(b)
, kami ingin menyatukan dua area dan mengambil satu dengan nilai absolut yang lebih besar (demi kenyamanan).Catatan yang
sgn(a)
tidak pernah bisa0
. Kami mencapai ini dengan formula yang diberikan. Jika tanda-tandaa
danb
berbeda,a*b
kurang atau sama dengan nol, sementaraa*a
selalu lebih besar dari nol, maka kami memilihnya sebagai maksimum dan membaginya dengana
untuk kembalia
. Jika tidak,max(a*a)(a*b)
adalahabs(a)*max(abs(a),(abs(b))
, dan dengan membagi ini dengana
, kita dapatkansgn(a)*max(abs(a),abs(b))
, yang merupakan angka dengan nilai absolut yang lebih besar.Untuk beralih fungsi
((.)>>=id$transpose.map l)
sampai mencapai titik tetap, kami menggunakan(until=<<((==)=<<))
, yang diambil dari jawaban stackoverflow ini .Pengolahan pasca
Untuk postprocessing, kami menggunakan bagian itu
yang hanya kumpulan langkah-langkah.
(>>=id)
remas daftar daftar menjadi satu daftar,nub
singkirkan ganda, pisahkan(\x->length.($x).filter<$>[(>0),(<0)])
daftar menjadi sepasang daftar, satu untuk bilangan positif dan satu untuk bilangan negatif, dan hitung panjangnya.sumber
Java 10,
359355281280261246 byte-74 byte terima kasih kepada @NahuelFouilleul .
Cobalah online.
Penjelasan:
sumber
|=2
: 0 -> 2 dan 1 -> 3, namun>0
diubah menjadi==1
|=2
! Dan saya masih bisa menggunakan<2
bukan==1
untuk -1 byte dengan terlebih dahulu memeriksa0
(dan dengan demikian mereka diubah menjadi2
, dan kemudian menggunakan<2
untuk memeriksa1
(yang diubah menjadi3
)Python 3 , 167 byte
Cobalah online!
Python 2 , 168 byte
Cobalah online!
-2 byte terima kasih kepada Kevin Cruijssen
Perbaikan pemformatan +2 byte
Penjelasan
Penghitung disimpan untuk 0s dan 1s. Untuk setiap entri dalam matriks, tindakan berikut dilakukan:
Ini menghasilkan false positive untuk kasus rata kiri seperti
atau
Jika situasi seperti itu muncul, penghitung berkurang sebesar 1.
Nilai pengembalian adalah
[#1, #0]
sumber
[#1, #0]
. Agak tidak ada gunanya untuk menegakkan ini, tetapi untuk sekarang ini adalah apa adanya. Pokoknya, Anda bisa bermain golf{not c}
untuk{c^1}
, dan memperbaiki masalah yang saya sebutkan dengan mengubahn[c]+=
ken[c^1]+=
dalam masalah yang sama. Jawaban yang bagus, +1 dari saya. :)Perl 5 (
-0777p
), 110 byteMungkin ditingkatkan, menggunakan regex untuk mengganti
1
dengan3
, kemudian0
dengan2
.TIO
sumber
Jelly ,
4436 byteCobalah online!
Tautan monadik yang menerima daftar daftar bilangan bulat sebagai argumennya dan mengembalikan daftar jumlah pulau 1 dan 0 dalam urutan itu.
Penjelasan
Langkah 1
Hasilkan daftar semua indeks matriks masing-masing dengan indeks tetangganya ke kanan (kecuali di sisi kanan) dan ke bawah (kecuali di bagian bawah)
Langkah 2
Pisahkan indeks ini dengan apakah ada 1 atau 0 pada input. Mengembalikan satu daftar indeks dengan tetangga untuk 1 dan yang lain untuk 0.
Langkah 3
Gabungkan daftar dengan anggota dalam jumlah yang sama dan hasil
sumber
T-SQL 2008, 178 byte
Input adalah variabel tabel.
Data uji yang digunakan dalam contoh ini:
Cobalah online
sumber
R ,
194172 byteCobalah online!
Lakukan pencarian kedalaman-pertama yang dimulai pada setiap sel dari matriks yang sama dengan 1 (atau nol).
sumber