Hapus persegi panjang yang tidak terhalang

20

Gambar ini dibuat dengan melapisi 7 persegi panjang dengan warna berbeda di atas satu sama lain:

gambar utama

Persegi hitam dan merah marun tidak terhalang , yaitu, tidak ada persegi panjang lain di atas mereka.

Tulis sebuah program yang mengambil gambar seperti ini dan menghapus persegi panjang tunggal yang terhalang, menghasilkan gambar yang dihasilkan.

Contoh

Jika Anda menjalankan program Anda pada gambar di atas dan terus menjalankannya kembali pada output, itu mungkin berkembang seperti ini.

Jalankan 1 - Hitam dihilangkan (bisa jadi merah marun):

jalankan 1

Jalankan 2 - Maroon dihapus (satu-satunya pilihan):

jalankan 2

Jalankan 3 - Kuning dihapus (satu-satunya pilihan):

jalankan 3

Jalankan 4 - Biru dihapus (bisa jadi hijau):

jalankan 4

Run 5 - Hijau dihapus (satu-satunya pilihan):

jalankan 5

Run 6 - Brown dihapus (satu-satunya pilihan):

jalankan 6

Jalankan 7 - Merah dihapus (hanya pilihan):

jalankan 7

Setiap proses tambahan harus menghasilkan gambar putih yang sama.

Semoga Stack Exchange tidak dengan salah mengkompres gambar-gambar ini.

Gambar akan selalu memiliki latar belakang putih dan setiap persegi panjang akan menjadi warna RGB unik yang bukan putih.

Anda dapat mengasumsikan bahwa gambar selalu dapat diartikan sebagai satu set persegi panjang yang tumpang tindih. Khususnya, Anda dapat mengasumsikan bahwa, untuk warna tertentu, piksel dengan warna yang paling dekat dengan bagian atas gambar adalah bagian dari tepi atas persegi panjang warna itu. Hal yang sama berlaku untuk tepi bawah, kiri, dan kanan.

Jadi, misalnya, dalam gambar ini, tepi atas dari persegi panjang merah akan tepat di bawah tepi bawah persegi panjang kuning, karena persegi panjang oranye menutupi tepi atas merah tua:

Contoh 1

Pada gambar ini, persegi panjang merah dapat dihapus terlebih dahulu (bersama dengan hitam / merah marun / oranye / abu-abu):

contoh 2

Ketika urutan persegi panjang lebih rendah ambigu, Anda bisa memberi mereka urutan apa pun.

Misalnya, gambar kiri di sini bisa menjadi tengah atau kanan:

contoh 3 contoh 4 contoh 5

Keluaran seharusnya tidak memiliki tumpang tindih paradoks (sehingga membuatnya dengan algoritma pelukis harus dimungkinkan). Jadi dalam gambar ini ( terima kasih user23013 ), itu harus berwarna hijau di bawah persegi panjang oranye:

contoh 6

detil tambahan

  • Gambar dan persegi panjang mungkin memiliki dimensi apa saja.
  • Persegi panjang dapat menyentuh batas gambar.
  • Mungkin ada hingga 256 3 - 1 persegi panjang.
  • Jika input seluruhnya putih, output juga harus.
  • Anda dapat menggunakan perpustakaan gambar.
  • Input harus berupa nama file gambar atau data gambar mentah. Itu bisa berasal dari stdin atau baris perintah.
  • Output dapat ditulis ke file gambar yang sama atau yang lain, memuntahkan mentah ke stdout, atau hanya ditampilkan.
  • Setiap format file gambar truecolor lossless umum diperbolehkan.

Kiriman dengan byte paling sedikit menang.

Hobi Calvin
sumber
4
Kasing uji ( dan versi terbalik ).
jimmy23013
Secara teknis tidak ada dalam persyaratan yang mengatakan bahwa output mungkin tidak memiliki tumpang tindih paradoks. Haruskah ditambahkan, atau keduanya interpretasi dari kasus uji OK?
John Dvorak
Bisakah Anda memperjelas "truecolor"?
FUZxxl
@FUZxxl RGB dengan 8 bit per saluran
Martin Ender
@ JanDvorak Saya berharap itu tersirat tapi, Anda benar, tidak jelas, jadi saya telah menambahkan catatan tentang hal itu.
Calvin Hobbies

Jawaban:

10

CJam, 241 byte

(dengan baris baru dihapus.)

rri:Hri:Vri:Q[q~]3/_Qa3*a+_|$W%:Pf{\a#}:AH/:B0ff*
P,,[AHAW%HBz:+_W%V\V]2/
ff{~@@f=/::|1#}0Ua4*t:R;
P0f<
V{H{BI=J=_2$=
0R{"I>! I+V<J>! J+H<"4/+4/z{~~}%:&1$*\)}%);2$-|t
}fJ}fI
[P,{_La#\1$0t1$f-}*;;]
{:TR=2/~\~V\-,>\f{\_3$=@~H\-,>{Tt}/t}~}/
:~Pf=:~
~]S*N

Ini menggunakan format file ppm. Contoh penggunaan (menggunakan ImageMagick):

convert IVYvE.png -compress none ppm:-| (time /path/to/cjam-0.6.4.jar 1.cjam) |display

Yah, ini terlalu panjang dan terlalu lambat ... Berjalan sekitar satu menit sebagai contoh.

Saya mengubah ukuran kasus pengujian (dan menambahkan beberapa lainnya) untuk membuat pengujian lebih mudah.

Tampaknya informasi ruang warna hilang sehingga warnanya sedikit berbeda.

jimmy23013
sumber
2

Python, 690 651 610 606 594 569 byte

Script membaca nama gambar dari stdin.

Ini mendeteksi tepi setiap persegi panjang, mengurutkannya dengan jumlah warna berbeda yang dikandungnya (persegi panjang tanpa hambatan hanya berisi 1 warna, dan kemudian muncul di akhir daftar)

Daftar ini digunakan untuk menggambar ulang suatu gambar. Urutan menggambar ulang diputuskan dengan memilih permutasi daftar yang akan menghasilkan gambar output yang memiliki perbedaan pixel paling sedikit dengan input.

dari PIL import Image sebagai l, ImageDraw as D; dari itertools import *; O, R, I, Z, k = [], range, l.open (raw_input ()), {}, lambda x: -x [1 ]; (W, H), Q = I.size, I.load ()
untuk i, j dalam produk (R (W), R (H)):
 c = Q [i, j]
 jika c dalam Z: x, y, X, Y = Z [c]; Z [c] = [x, y, maks (X, i), maks (Y, j)]
 lain: Z [c] = [i, j, 0,0]
untuk n dalam permutasi (diurutkan ([(c, len ({Q [g] untuk g dalam produk (R (x, X), R (y, Y))})) untuk c, (x, y, X, Y) dalam Z.items ()], key = k) [1: -1]): o = l.new (I.mode, I.size, 0xFFFFFF); [D.Draw (o) .rearangle (Z) [c], isi = c) untuk c, _ in n]; O + = [(o, jumlah (abs (ab) untuk t, T di zip (I.getdata (), o.getdata ()) untuk a, b dalam zip (t, T)))]
maks (O, kunci = k) [0] .show ()
pelaku diet
sumber
0

Java - 1483 byte

Saya bukan pegolf kode yang hebat, biarkan itu menjadi jelas; jadi verbositas itu bukan sepenuhnya kesalahan Java ;-) Namun, ini sepertinya tantangan yang sangat menyenangkan. Saya sudah memecahkannya dengan cara yang - saya pikir - sedikit membosankan dan bertele-tele, tapi hei. Ini bekerja, itu (relatif) cepat dan, terutama, itu menyenangkan!

Idenya adalah sebagai berikut: Periksa setiap piksel mulai dari sudut kiri atas sampai ke kanan bawah. Apakah ini piksel putih? Mengabaikan. Apakah ini berwarna? Keren, mari kita catat dan coba tentukan batasannya (kiri atas, kanan atas, kiri bawah, kanan bawah).

Setelah selesai, periksa area masing-masing persegi panjang. Apakah itu mengandung warna yang berbeda dari warna persegi panjang? Kemudian cari tahu apa persegi panjang milik warna itu dan perbarui indeks z persegi panjang yang tumpang tindih dengan 1.

Dan akhirnya, gambar semua persegi panjang sambil memperhitungkan z-index. Ini benar-benar berfungsi seperti z-index yang Anda tahu dari CSS dan hal-hal 3D lainnya. Segi empat dengan indeks-z terendah diambil pertama, indeks-z tertinggi terakhir.

import java.awt.*;import java.awt.image.*;import java.io.File;import java.util.*;import java.util.List;import javax.imageio.*;class A{class R{public Color k=new Color(-1);public int z;public Point a;public Point b;public Point c;public Point d;}public static void main(String[]w)throws Exception{BufferedImage i=ImageIO.read(new File(w[0]));List<R>r=new Vector<R>();for(int y=0;y<i.getHeight();y++){for(int x=0;x<i.getWidth();x++){Color c=new Color(i.getRGB(x,y));if(c.getRGB()==-1){continue;}R t=null;for(R s:r){if(s.k.equals(c)){t=s;}}if(t==null){t=new A().new R();r.add(t);}if(t.a==null){t.a=new Point(x, y);t.b=new Point(x, y);t.c=new Point(x, y);t.d=new Point(x, y);t.k=new Color(c.getRGB());}if(x<t.a.x){t.a.x=x;t.c.x=x;}if(x>t.b.x){t.b.x=x;t.d.x=x;}t.c.y=y;t.d.y=y;}}for(R s:r){List<Color>b=new Vector<Color>();for(int y=s.a.y;y<=s.c.y;y++){for(int x = s.a.x;x<=s.b.x;x++){if(i.getRGB(x, y)!=s.k.getRGB()){Color a=new Color(i.getRGB(x,y));boolean q=false;for(Color l:b){if(l.equals(a)){q=true;}}if(!q){b.add(a);} else {continue;}R f=null;for(R k:r){if(k.k.equals(a)){f=k;}}f.z=s.z+1;}}}}Collections.sort(r,new Comparator<R>(){public int compare(R a, R b){return a.z>b.z?1:(a.z==b.z?0:-1);}});for(int ii=r.size();ii>0;ii--){BufferedImage d=new BufferedImage(i.getWidth(),i.getHeight(),2);Graphics2D g=(Graphics2D)d.getGraphics();for(R s : r.subList(0, ii)){g.setColor(s.k);g.fillRect(s.a.x,s.a.y,s.b.x-s.a.x,s.c.y-s.a.y);}ImageIO.write(d,"png",new File(r.size()-ii+".png"));}}}

Kode lengkap yang sedikit - dan itu meremehkan ;-) - ditulis lebih jelas, dapat ditemukan di sini: http://pastebin.com/UjxUUXRp

Juga, sekarang saya melihat penyerahan diet, saya bisa membuat beberapa bagian lebih mudah. Tidak perlu menemukan kotak yang warnanya tumpang tindih dengan kotak lain. Aku memang bisa menghitung jumlah warna 'menyerbu'.

Sander
sumber