Perbedaan persegi panjang

20

Dalam tantangan ini, Anda diberi dua persegi panjang yang tumpang tindih, dan Anda perlu menghitung persegi panjang yang dibuat dengan menghapus satu dari yang lain.

Misalnya, jika Anda menghapus persegi panjang merah dari yang hitam:

persegi panjang

Anda berakhir dengan salah satu dari dua set persegi panjang berikut:

terbelah satu perpecahan dua

Anda juga harus menangani hal-hal berikut:

Semua uji kasus

Untuk lebih eksplisit:

  • Anda akan memasukkan koordinat dua persegi panjang, A dan B.
  • Anda perlu menampilkan persegi panjang non-tumpang tindih paling sedikit yang mencakup semua area A tanpa B. Penutup yang memungkinkan diizinkan
  • Koordinat persegi panjang dilewatkan sebagai 4 bilangan bulat. Anda dapat mengirimkannya dalam dua pasangan (mewakili dua titik sudut), atau sebagai tuple / daftar 4 bilangan bulat. Input dan output Anda harus konsisten.
  • A dan B belum tentu tumpang tindih atau menyentuh, dan masing-masing akan memiliki area minimal 1

Kasus uji:

[(0 0) (5 5)] [(3 4) (8 7)]   -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)]  -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)]    #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)]   ->    #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)]   -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)]  #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)]   -> [(1 5) (7 8)]  #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)]   -> [(4 1) (10 5)] [(4 7) (10 9)]  #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)]     -> [(1 1) (8 6)]   #Only possible output

Ini adalah , jadi buat kode Anda sesingkat mungkin!

Nathan Merrill
sumber
3
Terkait
Martin Ender
1
dapatkah kita berasumsi bahwa input yang diberikan {(x1, y1), (x2, y2)}berlaku x1 < x2dan y1 < y2?
tsh
Ya. Persegi panjang akan memiliki luas 1, dan Anda dapat memesan koordinat dalam urutan apa pun yang Anda suka.
Nathan Merrill
Apakah tepiannya tebal? Kapan persegi panjang didefinisikan termasuk tepi?
Евгений Новиков
Tepi memiliki 0 ketebalan.
Nathan Merrill

Jawaban:

3

Python 2 , 375 360 345 343 byte

from itertools import*;P=product
def f(S,M):(l,t),(r,b)=S;(L,T),(R,B)=M;u,v,x,y=(L>=r)+(l<L),(T>=b)+(t<T),(R>=r)+(l<R),(B>=b)+(t<B);return[S]if v==y!=1or u==x!=1else[list(p(p(*zip(*(S+M))),repeat=2))[[43,197,6,199,9,231,142,229,53,189,134,181][int(i,36)]]for i in '38,491,258,2058,8,4B,28,208,7,41,27,461,,4,2,4A'.split(',')[u+2*v+4*x+8*y-12]]

Cobalah online!

EDIT: -15 dari saran dari @notjagan; lain -15 dengan pengkodean ulang array solusi persegi panjang ke format int36 dan tabel pencarian pendek; lain -2 dengan mengganti produk dengan p sesuai @musicman.

Fungsi yang mengambil dua persegi panjang, masing-masing persegi menjadi tupel ((kiri, atas), (kanan, bawah)); mengembalikan daftar persegi panjang yang dihasilkan.

Strategi dasar:

     |     |
 0,0 | 1,0 | 2,0
-----A-----+-----
     |     |
 0,1 | 1,1 | 2,1
-----+-----B-----
     |     |
 0,2 | 1,2 | 2,2
     |     |

Dalam diagram di atas, masing-masing titik A dan B adalah kiri atas dan kanan bawah, dari persegi panjang 'Sumber' (persegi pertama).

Kami menemukan penempatan masing-masing kiri atas (u,v)dan kanan bawah (x,y)persegi panjang 'Topeng' di kotak itu.

Jika kedua titik ini ada di kolom pertama atau terakhir; atau baris pertama atau terakhir; maka tidak ada tumpang tindih; dan kita bisa mengembalikan hanya Sumber rect.

Kalau tidak, ada 16 kasus yang tersisa; misalnya, contoh pertama OP adalah kasus yang dapat kita beri label (1,1),(2,2). Setiap kasus dapat dipetakan ke seperangkat persegi panjang yang dihasilkan yang sudutnya selalu berkoordinasi dengan nilai horizontal di salah satu persegi panjang Sumber kiri, kanan, atau persegi panjang Mask kiri, kanan; dan juga untuk nilai-nilai vertikal, bagian atas, bawah, atau topeng Sumber.

Sebagai contoh, untuk (1,1),(2,2)kasus ini, persegi panjang akan ((l,t),(T,r))dan ((l,T),(R,b)), di mana l,t,r,bdan L,T,R,Badalah kiri, atas, kanan dan bawah dari persegi panjang Sumber dan Mask, masing-masing.

Jadi kita dapat membuat tabel pencarian yang memetakan koordinat ke himpunan semua kombinasi yang mungkin (yaitu tentang apa product(product(*zip(*)))bit itu) ke himpunan persegi panjang yang harus disediakan untuk masing-masing kasus (yang, setelah beberapa dekompresi golf) , adalah isi dari daftar sisanya adalah tentang).

Chas Brown
sumber
-15 byte dengan membuat berbagai peningkatan golf, atau -18 byte menggunakan string dalam Python 3.
notjagan
Anda dapat memotong dua byte lagi dengan melakukan p=productdan mengganti product(productdenganp(p
musicman523
3

JavaScript, 115 byte

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=a[i]=n,p)).filter(x=>x)

versi yang tumpang tindih:

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=n,p)).filter(x=>x)

Masukan dalam format berikut: f([1,1,8,8])([0,6,9,9])


Nyatakan input sebagai ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))

Jika salah satu dari kondisi berikut ini terpenuhi, kembalikan persegi panjang pertama seperti:

  • x3> x2
  • x4 <x1
  • y3> y2
  • y4 <y1

jika tidak

  • Jika x1 <x3 <x2 maka kita menghasilkan sebuah persegi panjang ((x1, y1), (x3, y2)); dan atur x1: = x3
  • Jika x1 <x4 <x2 maka kita menghasilkan sebuah persegi panjang ((x4, y1), (x2, y2)); dan atur x2: = x4
  • Jika y1 <y3 <y2 maka kita menghasilkan sebuah persegi panjang ((x1, y1), (x2, y3)); dan atur y1: = y3
  • Jika y1 <y4 <y2 maka kita menghasilkan persegi panjang ((x1, y4), (x2, y2)); dan atur y2: = y4
tsh
sumber
Ini adalah pendekatan yang menjanjikan; tetapi kadang-kadang gagal, misalnya, ketika persegi panjang Mask tidak tumpang tindih dengan persegi panjang Sumber; mis. f([0, 30, 10, 40])([5, 1, 6, 2])harus kembali [[0, 30, 10, 40]]tetapi sebaliknya kembali[[0,30,5,40],[6,30,10,40]]
Chas Brown
@NathanMerrill ok, diedit.
tsh
@ tsh terlihat bagus!
Nathan Merrill
1

Java, 268 byte

class W{public static void main(String[]z) {int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};for(i=0;i<4;i+=1){for(j=0;j<4;j+=1){a[j]=Integer.parseInt(z[y[i*4+j]]);}if(a[0]<a[2] && a[1]<a[3]){for(j=0;j<4;j+=1){System.out.println(String.valueOf(a[j]));}}}}}

Tidak disatukan

class W{
    public static void main(String[]z) {
        int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};

        for(i=0;i<4;i+=1){
            for(j=0;j<4;j+=1){
                a[j]=Integer.parseInt(z[y[i*4+j]]);
            }
            if(a[0]<a[2] && a[1]<a[3]){
                for(j=0;j<4;j+=1){
                    System.out.println(String.valueOf(a[j]));
                }
            }
        }
    }
}

Masukan input sebagai argumen. Contoh

java -jar W.jar 0 0 5 5 3 4 8 7
Евгений Новиков
sumber
0

Python 2 , 272 byte

lambda((a,b),(c,d)),((e,f),(g,h)):[([([[(a,b),(e,min(h,d))]]+[[(g,max(b,f)),(c,d)]]*2+[[(max(a,e),b),(c,f)]]*4+[[(a,h),(min(c,g),d)]])[m-1]for m in M&{1,2,4,8}]if M&{0}else[(a,b),(c,d)])for M in[{(x<e)*1+(x>g)*2+(y<f)*4+(y>h)*8 for x in range(a,c)for y in range(b,d)}]][0]

Cobalah online!

Ini bekerja dengan menguji setiap sel di dalam persegi panjang pertama untuk kiri = 1, aboveness = 4, rightness = 2, dan belowness = 8 w / r ke yang lain, dan ORing hasilnya. Jika yang lain tidak berpotongan = 0 dengan yang pertama, maka yang asli dikembalikan, jika tidak, kombinasi dari irisan kiri, irisan kanan, irisan atas dan irisan bawah dikembalikan, dengan akomodasi untuk tumpang tindih.

SmileAndNod
sumber