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:
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 > 0
dan tinggi h > 0
yang 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
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:
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)]
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)]
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)]
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)]
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.
3-h
ke~h
?Python -
272261258251224Saya 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.Saya sedang berupaya menambahkan gambar hasil.Sunting: Berikut adalah hasil dari contoh dan kasus pengujian: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?
sumber
(i[0]+w,i[1]+j)not in c
ke{(i[0]+w,i[1]+j)}-c
dan Anda dapat pindahw=h=1
kec=set(a)-set(b)
saluranb+=[(j+i[0],k+i[1])]
keb+=(j+i[0],k+i[1]),
dan Anda menggunakanrange
tiga kali sehingga lebih pendek untuk menetapkanr=range
x,y=i
menggunakanx
dany
bukannyai[0]
dani[1]
? Itu akan menghemat banyak byte.while not[j for j in r(h)if(x+w,y+j)not in c]:w+=1
digunakanwhile all((x+w,y+j)in c for j in r(h)):w+=1
.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)}
Sering menjengkelkan (tidak hanya di golf) bahwa Python tidak mengizinkan tugas di dalam tes loop. Untuk mengatasi ini, saya menggunakan operasi pemformatan string.
sumber
Mathematica -
315 285267 byteDengan bantuan dari @ MartinBüttner.
Tidak Disatukan:
Pemakaian:
Uji Kasus
Wilayah berbentuk U
Segitiga besar
Kotak dengan lubang
Daerah terputus
sumber
Haskell, 158
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.
sumber
not$all(\x->elem(x,i)s)
denganany(\x->notElem(x,i)s)
.JavaScript (ES6) 148
155 199Sunting2 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.
Ya? Elemen pertama tumbuh, elemen kedua dihapus, mulai lagi di langkah 2
Lain, lanjutkan ke elemen berikutnya
Tes dalam cuplikan
sumber
Mathematica,
153 151 144 136133Contoh:
Memasukkan:
Keluaran:
Memasukkan:
Keluaran:
Algoritma:
Tutupi wilayah dengan kotak unit, lalu gabungkan.
sumber