Tutupi Wilayah dengan Rectangles

22

Memasukkan

Input Anda dalam tantangan ini adalah daftar pasangan integer. Mereka mewakili sudut barat daya kotak unit di pesawat, dan daftar mewakili penyatuan mereka sebagai bagian dari pesawat. Misalnya, daftarnya

[(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)]

mewakili set berwarna merah dalam gambar ini:

Domain

Keluaran

Output Yor adalah daftar quadruple integer, yang mewakili himpunan bagian persegi panjang dari pesawat. Secara lebih eksplisit, sebuah quadruple (x,y,w,h)menandakan persegi panjang lebar w > 0dan tinggi h > 0yang sudut barat dayanya berada (x,y). Persegi panjang harus membentuk penutup wilayah input yang tepat, dalam arti bahwa masing-masing unit kuadrat adalah subset dari beberapa persegi panjang, masing-masing persegi panjang adalah subset dari wilayah tersebut, dan dua persegi panjang mungkin tumpang tindih hanya pada batasnya. Untuk melarang solusi sepele, penutup harus tidak mengandung dua persegi panjang yang dapat digabung menjadi persegi panjang yang lebih besar.

Misalnya, daftarnya

[(0,0,2,1),(0,1,3,1),(1,2,2,1)]

mewakili perlindungan hukum

Perlindungan hukum

dari wilayah di atas, sedangkan penutup diberikan oleh

[(0,0,2,2),(2,1,1,1),(1,2,1,1),(2,2,1,1)]

adalah ilegal, karena kuadrat 1-by-1 yang berdekatan dapat digabungkan:

Perlindungan ilegal

Aturan

Anda dapat memberikan program atau fungsi lengkap. Pemformatan input dan output yang akurat tidak penting, masuk akal. Hitungan byte terpendek menang, dan celah standar tidak diizinkan. Anda disarankan untuk memberikan penjelasan tentang algoritma Anda, dan beberapa contoh hasil.

Uji Kasus

Wilayah berbentuk U:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5)]

Bentuk-U

Segitiga besar:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(6,0),(6,1),(6,2),(6,3),(7,0),(7,1),(7,2),(8,0),(8,1),(9,0)]

Segi tiga

Kotak dengan lubang:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,7),(5,8),(5,9),(6,1),(6,2),(6,3),(6,5),(6,6),(6,7),(6,8),(6,9),(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9)]

Kotak Holed

Wilayah yang terputus:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(4,0),(4,1),(4,2),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(6,0),(6,1),(6,2),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,7),(9,8),(9,9),(10,0),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9)]

Terputus

Penguji

Gunakan ini program Python 2 untuk memverifikasi solusi Anda. Dibutuhkan dari STDIN daftar tupel (input) dan daftar empat kali lipat (output Anda), dipisahkan oleh koma.

Saya juga menulis ini program Python 2 untuk menghasilkan gambar, dan Anda dapat menggunakannya juga. Dibutuhkan dari STDIN daftar tupel atau empat kali lipat, dan menghasilkan file bernama out.png. Ini membutuhkan perpustakaan PIL. Anda dapat mengubah ukuran sel kisi dan lebar garis sandang juga, jika Anda mau.

Zgarb
sumber

Jawaban:

12

Python: 196 193 182 karakter

def g(r):
 for p in r:
  for q in r:
   for h in 0,1:
    if p[h::2]==q[h::2]and p[1-h]+p[~h]==q[1-h]:p[~h]+=q[~h];r.remove(q);return g(r)
 return r
f=lambda P:g([x+[1,1]for x in P])

Solusi pertama saya menggunakan algoritma yang sama persis seperti KSFT, oleh karena itu saya bereksperimen dengan metode lain.

Pertama saya melakukan beberapa preprocessing, saya mengkonversi semua poin menjadi 1x1 persegi panjang kecil {x+(1,1)for x in P}. Dengan persegi panjang ini, saya memanggil fungsi g. giterates atas setiap kombinasi persegi panjang. Jika ia menemukan 2 persegi panjang, yang dapat digabung menjadi yang lebih besar, itu menghapus keduanya dan menambahkan yang baru. Setelah itu ia menyebut dirinya dengan set persegi panjang baru.

Pemakaian

f([[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]])

Hasil

Berikut visualisasi hasilnya. Perhatikan bahwa mereka mungkin sedikit berbeda dalam versi saat ini. Idenya adalah, bahwa tidak ada pola yang terlihat.

Wilayah berbentuk U:

Segitiga besar

Kotak dengan lubang:

Wilayah yang terputus:

Hanya untuk bersenang-senang: Pyth: 73 69 karakter

D!HFGHFZHV2I&q%2>GN%2>ZNqs%2>G-1N@Z-1N X-3NG@Z-3NR!-H]Z)))RH!m+d*2]1Q

Hanya berfungsi dalam versi offline. Bug dalam versi online sudah diperbaiki sekarang. Coba di sini: Pyth Compiler / Executor . Mengharapkan daftar daftar, bukan daftar tupel.

sunting: Menggunakan ide dari @ edc65: Alih-alih menghapus kedua persegi panjang dan membuat yang baru, saya memanipulasi satu dan hanya menghapus satu. Dalam solusi Python saya bisa mendapatkan set dan tuple-list-tuple gips. -11 karakter dalam Python / -4 karakter dalam Pyth

Jakube
sumber
2
Python3: Wajah smiley sekarang kode yang valid.
flawr
Saya mungkin salah, tapi saya pikir Anda dapat mengubah 3-hke ~h?
Sp3000
Diterima untuk versi Pyth.
Zgarb
14

Python - 272 261 258 251 224

Saya pikir saya bisa bermain golf ini lebih banyak. Saya cukup yakin ini berhasil, tetapi saya belum selesai mengujinya pada semua kasus uji. Saya selesai mengujinya. Ini bekerja untuk semua kasus uji.

a=sorted(input())
b=[]
r=range
for i in a:
 c=set(a)-set(b);w=h=1;x,y=i
 if i in b:continue
 while not{(x,y+h)}-c:h+=1
 while all((x+w,y+j)in c for j in r(h)):w+=1
 for j in r(w):
  for k in r(h):b+=(j+x,k+y),
 print x,y,w,h

Saya sedang berupaya menambahkan gambar hasil. Sunting: Berikut adalah hasil dari contoh dan kasus pengujian:

Contoh output Test case 1 output Test case 2 output Test case 3 output Kasing uji 4 keluaran

Saya mencoba untuk menulis ini di Perl, tetapi saya tidak tahu bagaimana cara mendapatkan array multidimensi dari stdin tanpa sejumlah besar karakter. Adakah yang punya saran?

KSFT
sumber
Dua hal: (i[0]+w,i[1]+j)not in cke {(i[0]+w,i[1]+j)}-cdan Anda dapat pindah w=h=1ke c=set(a)-set(b)saluran
Sp3000
Beberapa lagi: b+=[(j+i[0],k+i[1])]ke b+=(j+i[0],k+i[1]),dan Anda menggunakan rangetiga kali sehingga lebih pendek untuk menetapkanr=range
Sp3000
Saya juga tidak yakin, tetapi apakah mungkin untuk melakukannya x,y=imenggunakan xdan ybukannya i[0]dan i[1]? Itu akan menghemat banyak byte.
Sp3000
Belum menguji ini, tapi saya pikir ini berhasil: Alih-alih while not[j for j in r(h)if(x+w,y+j)not in c]:w+=1digunakan while all((x+w,y+j)in c for j in r(h)):w+=1.
Jakube
@ Sp3000 / Jakube Saya telah menggunakan semua saran Anda.
KSFT
8

Python 2, 139

Program menerima daftar pasangan berurutan yang dikelilingi oleh kurung kurawal pada input standar. Misalnya,{(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)}

s=input()
while s:x,y=min(s);w=h=0;exec"while(x+w,y)in s:w+=1\nwhile%s<=s:s-=%s;h+=1"%(("{(X,y+h)for X in range(x,x+w)}",)*2);print x,y,w,h

Sering menjengkelkan (tidak hanya di golf) bahwa Python tidak mengizinkan tugas di dalam tes loop. Untuk mengatasi ini, saya menggunakan operasi pemformatan string.

feersum
sumber
Itu mengesankan. Algoritma yang sama dengan KSFT, 'hanya' 85 (!!!) karakter lebih pendek.
Jakube
5

Mathematica - 315 285 267 byte

f=(r={};For[m=MemberQ;t=Table;s=Sort@#,s!={},For[{x,y,w,h}=#~Join~{1,1}&@@s;i=j=0,i<1||j<1,If[s~m~{x+w,y+a-1}~t~{a,h}==True~t~{h},w++,i++];If[s~m~{x+a-1,y+h}~t~{a,w}==True~t~{w},h++,j++]];s=s~Cases~_?(!m[Join@@t[{x+a,y+b}-1,{a,w},{b,h}],#]&);r~AppendTo~{x,y,w,h}];r)&

Dengan bantuan dari @ MartinBüttner.

Tidak Disatukan:

f = (
    rectangles = {};
    For[squares = Sort[#], squares != {},
        For[{x, y, w, h} = Join[squares[[1]], {1, 1}]; i = j = 0, i < 1 || j < 1,
            If[Table[MemberQ[squares, {x + w, y + a - 1}], {a, h}] == Table[True, {h}], w++, i++];
            If[Table[MemberQ[squares, {x + a - 1, y + h}], {a, w}] == Table[True, {w}], h++, j++];
        ];
        squares = Cases[squares, _ ? (!MemberQ[Join@@Table[{x + a - 1, y + b - 1}, {a, w}, {b, h}], #] &)];
        AppendTo[rectangles, {x, y, w, h}]
    ];
    rectangles
)&

Pemakaian:

In: f @ {{0,0},{1,0},{0,1},{1,1},{2,1},{1,2},{2,2}}
Out: {{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

masukkan deskripsi gambar di sini

Uji Kasus

Wilayah berbentuk U

masukkan deskripsi gambar di sini

{{0, 0, 6, 2}, {0, 2, 2, 4}, {4, 2, 2, 4}}

Segitiga besar

masukkan deskripsi gambar di sini

{{0, 0, 6, 5}, {0, 5, 3, 3}, {0, 8, 2, 1}, {0, 9, 1, 1}, {3, 5, 2, 1}, {3, 6, 1, 1}, {6, 0, 3, 2}, {6, 2, 2, 1}, {6, 3, 1, 1}, {9, 0, 1, 1}}

Kotak dengan lubang

masukkan deskripsi gambar di sini

{{0, 0, 6, 3}, {0, 3, 3, 6}, {1, 9, 9, 1}, {3, 4, 3, 2}, {3, 6, 2, 3}, {4, 3, 6, 1}, {5, 7, 5, 2}, {6, 1, 4, 2}, {6, 5, 4, 2}, {7, 0, 3, 1}, {7, 4, 3, 1}}

Daerah terputus

masukkan deskripsi gambar di sini

{{0, 0, 2, 5}, {0, 5, 1, 4}, {1, 6, 2, 4}, {2, 1, 1, 5}, {4, 0, 3, 3}, {4, 4, 3, 6}, {5, 3, 1, 1}, {8, 0, 3, 4}, {8, 4, 1, 6}, {9, 7, 2, 3}, {10, 4, 1, 3}}
kukac67
sumber
4

Haskell, 158

f[]=[]
f s@((x,y):_)=(x,y,w-x,h-y):f[r|r@(a,b)<-s,a<x||a>=w||b<y||b>=h]where w=[i|i<-[x..],notElem(i,y)s]!!0;h=[i|i<-[y..],not$all(\x->elem(x,i)s)[x..w-1]]!!0

test case dan gambar akan segera hadir.

Algoritma: Ambil kotak pertama. Jangkau sejauh mungkin tanpa menemukan persegi tidak dalam input. Kemudian raih sejauh mungkin tanpa memiliki kotak tidak pada input. Kami sekarang memiliki persegi panjang tanpa kotak yang hilang. Tambahkan ke output, hapus semua kotak dari input dan panggil secara rekursif.

haskeller bangga
sumber
Anda dapat menyimpan 1 byte dengan menggantinya not$all(\x->elem(x,i)s)dengan any(\x->notElem(x,i)s).
nimi
4

JavaScript (ES6) 148 155 199

Sunting2 Beberapa lagi penyetelan
Edit Golf + menulis ulang menggunakan rekursi. Tidak mengharapkan pengurangan seperti itu. Sekarang agak sulit untuk diikuti, tetapi algoritmanya sama.

Algoritma ini mirip dengan jawaban @jakube.

  1. Setiap titik menjadi kotak 1x1 (preprocessing)
  2. Untuk setiap elemen, periksa apakah itu dapat digabung dengan yang lain
    Ya? Elemen pertama tumbuh, elemen kedua dihapus, mulai lagi di langkah 2
    Lain, lanjutkan ke elemen berikutnya
F=l=>
  (l.map(x=>x.push(1,1)),R=f=>
    l.some(u=>
      (l=l.filter(t=>
        [0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))
      ),f)
    )?R():l
  )()

Tes dalam cuplikan

F=l=>(l.map(x=>x.push(1,1)),R=f=>l.some(u=>(l=l.filter(t=>[0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))),f))?R():l)()

// Test
MyCanvas.width= 600;
MyCanvas.height = 220;
var ctx = MyCanvas.getContext("2d");
ctx.fillStyle="#f23";

Draw=(x,y,f,l)=>l.forEach(p=>ctx.fillRect(x+p[0]*f,y+p[1]*f,p[2]*f-1||f-1,p[3]*f-1||f-1));

test=[
[[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,0],[2,1],[3,0],[3,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[6,0],[6,1],[6,2],[6,3],[7,0],[7,1],[7,2],[8,0],[8,1],[9,0]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[3,0],[3,1],[3,2],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,7],[5,8],[5,9],[6,1],[6,2],[6,3],[6,5],[6,6],[6,7],[6,8],[6,9],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7],[7,8],[7,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8],[9,9]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,6],[1,7],[1,8],[1,9],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[4,0],[4,1],[4,2],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[5,8],[5,9],[6,0],[6,1],[6,2],[6,4],[6,5],[6,6],[6,7],[6,8],[6,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,7],[9,8],[9,9],[10,0],[10,1],[10,2],[10,3],[10,4],[10,5],[10,6],[10,7],[10,8],[10,9]]
]

Draw(0,0,10,test[0]),Draw(0,110,10,F(test[0]))
Draw(50,0,10,test[1]),Draw(50,110,10,F(test[1]))
Draw(130,0,10,test[2]),Draw(130,110,10,F(test[2]))
Draw(250,0,10,test[3]),Draw(250,110,10,F(test[3]))
Draw(370,0,10,test[4]),Draw(370,110,10,F(test[4]))
<canvas id=MyCanvas></canvas>

edc65
sumber
3

Mathematica, 153 151 144 136 133

Sort[{##,1,1}&@@@Input[]]//.{a___,r:{x_,y_,__},b___,{X_,Y_,W_,H_},c___}/;r=={x,Y,X-x,H}||r=={X,y,W,Y-y}:>{a,r+Sign@{0,0,X-x,Y-y},b,c}

Contoh:

Memasukkan:

{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 1}, {1, 2}, {2, 2}}

Keluaran:

{{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

masukkan deskripsi gambar di sini

Memasukkan:

{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}, {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}, {4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {4, 9}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}, {5, 7}, {5, 8}, {5, 9}, {6, 1}, {6, 2}, {6, 3}, {6, 5}, {6, 6}, {6, 7}, {6, 8}, {6, 9}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 6}, {8, 7}, {8, 8}, {8, 9}, {9, 0}, {9, 1}, {9, 2}, {9, 3}, {9, 4}, {9, 5}, {9, 6}, {9, 7}, {9, 8}, {9, 9}}

Keluaran:

{{0, 0, 3, 9}, {1, 9, 9, 1}, {3, 0, 3, 3}, {3, 4, 1, 5}, {4, 3, 1, 6}, {5, 3, 1, 3}, {5, 7, 1, 2}, {6, 1, 1, 3}, {6, 5, 1, 4}, {7, 0, 3, 9}}

masukkan deskripsi gambar di sini

Algoritma:

Tutupi wilayah dengan kotak unit, lalu gabungkan.

masukkan deskripsi gambar di sini

alephalpha
sumber