Tantangan ini didasarkan pada tantangan lain yang serupa. Karena menemukan pengemasan persegi panjang yang paling efisien adalah NP-hard (yaitu, solusinya mudah diperiksa tetapi sulit ditemukan), tantangan ini jauh lebih mudah daripada yang ini di sini
Tantangan ini
Diberikan banyak persegi panjang, cari tahu apakah mereka mengisi ruang persegi panjang tanpa celah atau tumpang tindih.
Memasukkan
Input bisa dalam dua bentuk, salah satunya membawa penalti mencetak gol.
Yang pertama: berisi daftar sub daftar, masing-masing dengan panjang 4. Daftar ini berisi 4 bilangan bulat yang merupakan koordinat dari vertex yang berlawanan. Karena semua persegi panjang akan horisontal / vertikal, tidak ada ambiguitas di mana persegi panjang berada. Setiap sublist akan berisi empat bilangan bulat, yang, secara berurutan, adalah koordinat-x dari simpul pertama, koordinat-y dari simpul pertama, koordinat-x dari simpul kedua, dan koordinat-y dari simpul kedua.
Yang kedua: berisi empat daftar bilangan bulat dengan panjang yang sama. Keempat daftar mewakili koordinat yang berbeda. Jika Anda membayangkan opsi input 1 sebagai matriks, input di sini hanyalah transpose dari matriks. Input ini membawa +20%
penalti byte.
Keluaran
Keluaran kebenaran / kepalsuan sederhana.
Spesifikasi
Jika ada kotak dengan area 0 (yaitu, x1 == x2 || y1 == y2
), abaikan kotak ini (jadi [0 0 1 1], [2 2 3 2]
valid). Spesifikasi ini tersedia untuk mempersulit orang untuk hanya mendapatkan nilai min / maks x / y.
x1 <= x2
dan y1 <= y2
tidak selalu benar. Jika x1 > x2 || y1 > y2
, persegi panjang bukan persegi panjang nol-daerah; melainkan, ia menempati ruang persegi panjang antara (x1, y1)
dan (x2, y2)
.
Koordinat bisa negatif, dalam hal ini mereka masih menempati ruang antara koordinat.
Rectangle paling kiri atas tidak selalu di (0, 0)
; dengan demikian, ruang persegi panjang yang diisi tidak harus memiliki sudut kiri atas (0, 0)
.
(Terima kasih kepada @xnor karena telah menunjukkan ambiguitas ini)
Silakan tentukan bagaimana Anda ingin input Anda dan bagaimana output Anda akan diwakili.
Mencetak gol
Skor adalah ukuran kode dalam byte, ditambah penalti byte jika berlaku. Skor terendah pada 15 Desember menang.
Uji Kasus
0 0 1 2
1 0 3 1 ==> true
1 1 3 2
0 0 2 2
0 0 1 1 ==> false
0 0 0 0
0 0 1 1
2 2 2 2 ==> true
0 1 2 1
Semoga berhasil, senang bermain golf!
sumber
x1 <= x2
dany1 <= y2
? Apakah area 0 berbentuk persegi panjang denganx1 == x2
dany1 <= y2
mungkin?x1 > x2
dany1 > y2
, apakah ini persegi panjang area-nol karena koordinatnya diaktifkan?Jawaban:
JavaScript (ES6), 249 byte
Catatan: Untuk menggunakan ini, lakukan evaluasi sebagai string dan tetapkan hasilnya ke variabel, atau masukkan tugas setelah
with(Math)
. Penjelasan:with(Math)a=>!(
Bawamin
danmax
masuk ke ruang lingkup.a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b])
Menormalkan koordinat.filter(g=([l,t,r,b])=>(r-l)*(b-t)))
Hapus persegi panjang kosong, juga mendefinisikan fungsi untuk menghitung area.reduce((s,b)=>s-g(b),
Kurangi area semua persegi panjangg([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))
dari area kotak pembatas>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))
dan periksa bahwa tidak ada persegi panjang yang tumpang tindih.sumber
with(Math)f=a=>
dll - menempatkanf=
di awal tidak akan berhasil.Mathematica, 194 byte
Versi ungolfed:
Baris 1 mendefinisikan
r
sebagai himpunan empat persegi panjang dari input yang diberikan. (Ada banyak hal yang& @@
terjadi dalam kode ini; itu hanya supaya kita dapat menggunakan#1,#2,#3,#4
untuk empat elemen dari daftar sebagai ganti#[[1]],#[[2]],#[[3]],#[[4]]
.) Kemudian baris 2 mendefinisikanm
sebagai koordinat dari persegi panjang terkecil yang mengikat semua yang terdaftar dalamr
; jadi jika input persegi panjang ubin persegi panjang besar, persegi panjang besar itu harusm
.Baris 3 mendefinisikan fungsi
b
yang, ketika diterapkan pada quadruple yang mewakili persegi panjang, menghasilkan fungsi dua variabelx
dany
itu sama dengan 1 jika titik(x,y)
berada di dalam persegi panjang dan 0 jika tidak. Baris 5 menghasilkan banyak fungsi-fungsi ini, satu untuk setiap persegi panjang dir
(semua ditambahkan bersama-sama) dan satu terakhir untuk persegi panjang besarm
(dikurangi); fungsi dua variabel yang rumit ini kemudian dikuadratkan.Kuncinya, pada titik ini, adalah bahwa fungsi dua variabel identik 0 jika persegi panjang kecil ubin persegi panjang besar, tetapi akan memiliki beberapa nilai positif jika dua persegi panjang kecil tumpang tindih, atau beberapa nilai negatif (sebelum kuadrat) jika beberapa bagian dari persegi panjang besar tidak tercakup. Kami mendeteksi ini dengan benar-benar mengintegrasikan (!) Fungsi dua variabel di atas persegi panjang besar (batas-batas integrasi diberikan dalam baris 6-7): jika kita memperoleh 0, maka ubinnya sempurna, dan jika kita memperoleh nilai positif , lalu ada masalah di suatu tempat. Karena semuanya yang terlihat adalah bilangan bulat, kami menyimpan satu byte terakhir dengan menggunakan
< 1
alih-alih== 0
di baris 8.(Saya pikir cukup menyenangkan bahwa kita dapat memanfaatkan kemampuan Mathematica untuk melakukan kalkulus untuk menyelesaikan masalah kombinatorial ini.)
sumber