Periksa apakah persegi panjang mengisi ruang persegi panjang tanpa celah atau tumpang tindih

8

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 <= x2dan y1 <= y2tidak 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!

HyperNeutrino
sumber
Haruskah persegi panjang memiliki sudut di (0,0)? Bisakah koordinatnya negatif?
xnor
Apakah kami dijamin bahwa setiap kotak memiliki x1 <= x2dan y1 <= y2? Apakah area 0 berbentuk persegi panjang dengan x1 == x2dan y1 <= y2mungkin?
xnor
@ xnor Ini semua hal kecil yang saya gagal pertimbangkan. Terima kasih telah menunjukkannya, saya akan menjelaskan dalam edit. Jawaban saya untuk pertanyaan-pertanyaan itu adalah tidak, ya, tidak, ya.
HyperNeutrino
Saya akan merekomendasikan Sandbox untuk menuntaskan detail seperti ini sebelumnya. Kasing uji Anda harus mencakup sebanyak mungkin kasing sudut ini. Saya masih belum jelas pada "Jadi, daftar akan terlihat seperti [x1, y1, x2, y2], di mana (x1, y1) dan (x2, y2) mewakili verteks atas-kiri dan kanan bawah". Jika x1 > x2dan y1 > y2, apakah ini persegi panjang area-nol karena koordinatnya diaktifkan?
xnor
2
Seseorang menyaksikan numberphile?
orlp

Jawaban:

0

JavaScript (ES6), 249 byte

with(Math)a=>!(a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b]).filter(g=([l,t,r,b])=>(r-l)*(b-t))).reduce((s,b)=>s-g(b),g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))

Catatan: Untuk menggunakan ini, lakukan evaluasi sebagai string dan tetapkan hasilnya ke variabel, atau masukkan tugas setelah with(Math). Penjelasan:

with(Math)a=>!(Bawa mindan maxmasuk 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 panjang
g([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.

Neil
sumber
Saya kesulitan menguji ini. Bisakah Anda mengklarifikasi apa yang Anda maksud dengan "memasukkan tugas"? (Saya tidak punya pengalaman ES6 sama sekali). Atau jika mungkin, dapatkah Anda memberikan tautan ke beberapa kasus uji? Terima kasih.
HyperNeutrino
@AlexL. Maksud saya Anda harus menulis misalnya with(Math)f=a=>dll - menempatkan f=di awal tidak akan berhasil.
Neil
Baik. Saya mengerti maksud Anda, tetapi kompiler online yang saya coba semuanya memberi saya berbagai kesalahan. Bisakah Anda memberikan kompiler yang benar-benar berfungsi (kompiler lain sedang aneh)?
HyperNeutrino
@AlexL. Ah, saya pikir saya salah ketik salah satu suntingan saya; Saya sudah memeriksa ulang dan Anda harusnya OK sekarang.
Neil
Saya menandai ini sebagai diterima sekarang. Saya akan mempercayai Anda dengan hasil tes, dan saya akan terus berusaha memverifikasinya.
HyperNeutrino
0

Mathematica, 194 byte

(r=Select[#,(#-#3)(#2-#4)&@@#>0&];m={#~Min~#3,#2~Min~#4,#~Max~#3,#2~Max~#4}&@@Transpose@r;b=Boole[(x-#)(x-#3)<0&&(y-#2)(y-#4)<0]&;Integrate[(Plus@@(b@@@r)-b@@m)^2,{x,#,#3}&@@m,{y,#2,#4}&@@m]<1)&

Versi ungolfed:

1  (r = Select[#1, (#1 - #3) (#2 - #4) & @@ #1 > 0 &]; 
2   m = {Min[#1, #3], Min[#2, #4], Max[#1, #3], Max[#2, #4]} & @@ Transpose[r]; 
3   b = Boole[(x - #1) (x - #3) < 0 && (y - #2) (y - #4) < 0] &;
4   Integrate[
5     (Plus @@ (b @@@ r) - b @@ m)^2 ,
6     {x, #1, #3} & @@ m ,
7     {y, #2, #4} & @@ m
8   ] < 1
9  ) &

Baris 1 mendefinisikan rsebagai 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,#4untuk empat elemen dari daftar sebagai ganti #[[1]],#[[2]],#[[3]],#[[4]].) Kemudian baris 2 mendefinisikan msebagai koordinat dari persegi panjang terkecil yang mengikat semua yang terdaftar dalam r; jadi jika input persegi panjang ubin persegi panjang besar, persegi panjang besar itu harus m.

Baris 3 mendefinisikan fungsi byang, ketika diterapkan pada quadruple yang mewakili persegi panjang, menghasilkan fungsi dua variabel xdan yitu 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 di r(semua ditambahkan bersama-sama) dan satu terakhir untuk persegi panjang besar m(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 < 1alih-alih == 0di baris 8.

(Saya pikir cukup menyenangkan bahwa kita dapat memanfaatkan kemampuan Mathematica untuk melakukan kalkulus untuk menyelesaikan masalah kombinatorial ini.)

Greg Martin
sumber