Esta imagem foi criada sobrepondo 7 retângulos de cores diferentes um sobre o outro:

Os retângulos preto e marrom estão desobstruídos , ou seja, nenhum outro retângulo está acima deles.

Escreva um programa que capte uma imagem como essa e remova qualquer retângulo desobstruído, produzindo a imagem resultante.

Exemplo

Se você executou seu programa na imagem acima e continuou executando-o novamente na saída, ele pode progredir assim.

Execução 1 - Preto removido (poderia ter sido marrom):

Execução 2 - Marrom removido (única opção):

Execução 3 - Amarelo removido (única opção):

Execução 4 - Azul removido (poderia ter sido verde):

Execução 5 - Verde removido (única opção):

Execução 6 - Marrom removido (única opção):

Execução 7 - Vermelho removido (única opção):

Qualquer execução adicional deve produzir a mesma imagem em branco.

^{Esperamos que o Stack Exchange não tenha compactado com perda nenhuma dessas imagens.}

A imagem sempre terá um fundo branco e cada retângulo terá uma cor RGB exclusiva que não é branca.

Você pode assumir que a imagem sempre pode ser interpretada como um conjunto de retângulos sobrepostos. Especificamente, você pode assumir que, para uma cor específica, o pixel com a cor mais próxima da parte superior da imagem faz parte da borda superior do retângulo dessa cor. O mesmo vale para as bordas inferior, esquerda e direita.

Assim, por exemplo, nesta imagem, a borda superior do retângulo vermelho estaria logo abaixo da borda inferior do retângulo amarelo, pois o retângulo laranja cobria a antiga borda superior vermelha:

Nesta imagem, o retângulo vermelho pode ser removido primeiro (junto com preto / marrom / laranja / cinza):

Quando a ordem dos retângulos inferiores é ambígua, você pode dar a eles qualquer ordem.

Por exemplo, a imagem da esquerda aqui pode se tornar do meio ou da direita:

A saída não deve ter sobreposições paradoxais (portanto, é possível torná-la com o algoritmo do pintor ). Portanto, nesta imagem ( obrigado user23013 ), teria que ser verde sob o retângulo laranja:

detalhes adicionais

• A imagem e os retângulos podem ter quaisquer dimensões.
• Os retângulos podem tocar na borda da imagem.
• Pode haver até 256 ³ - 1 retângulos.
• Se a entrada for totalmente branca, a saída também deve ser.
• Você pode usar bibliotecas de imagens.
• A entrada deve ser o nome do arquivo de imagem ou os dados brutos da imagem. Pode vir do stdin ou da linha de comando.
• A saída pode ser gravada no mesmo ou em outro arquivo de imagem, transmitida em bruto para stdout ou simplesmente exibida.
• É permitido qualquer formato comum de arquivo de imagem truecolor sem perdas .

O envio com o menor número de bytes vence.

CJam, 241 bytes

(com novas linhas removidas.)

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

Ele usa o formato de arquivo ppm. Exemplo de uso (usando o ImageMagick):

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

Bem, é muito longo e muito lento ... Corre cerca de um minuto para o exemplo.

Redimensionei os casos de teste (e adicionei alguns outros) para facilitar o teste.

Parece que as informações do espaço de cores estão perdidas, portanto as cores são ligeiramente diferentes.

Python, 690 651 610 606 594 569 bytes

O script lê o nome da imagem em stdin.

Ele detecta as arestas de todos os retângulos, classifica-as pelo número de cores diferentes que elas contêm (os retângulos desobstruídos contêm apenas 1 cor e aparecem no final da lista)

Esta lista é usada para redesenhar uma imagem. A ordem de redesenho é decidida escolhendo a permutação da lista que geraria uma imagem de saída com a menor diferença de pixels com a entrada.

from PIL import Image como l, ImageDraw como D; from itertools import *; O, R, I, Z, k = [], range, l.open (raw_input ()), {}, lambda x: -x [1 ]; (W, H), Q = tamanho I., I.load ()
para i, j no produto (R (W), R (H)):
 c = Q [i, j]
 se c em Z: x, y, X, Y = Z [c]; Z [c] = [x, y, max (X, i), max (Y, j)]
 mais: Z [c] = [i, j, 0,0]
para n em permutações (classificado ([(c, len ({Q [g] para g no produto (R (x, X), R (y, Y))}})) para c, (x, y, X, Y) em Z.items ()], chave = k) [1: -1]): o = l.new (modo I, tamanho I., 0xFFFFFF); [D.Draw (o) .rectângulo (Z [c], preencha = c) para c, _ em n]; O + = [(o, soma (abs (ab) para t, T em zip (I.getdata (), o.getdata ()) para a, b em zip (t, T))]]
max (O, tecla = k) [0] .show ()

Java - 1483 bytes

Eu não sou um grande jogador de códigos, deixe isso claro; então a verbosidade não é inteiramente culpa do Java ;-) No entanto, isso parecia um desafio muito divertido. Eu resolvi isso de uma maneira que - eu acho - é um pouco chata e detalhada, mas ei. Funciona, é (relativamente) rápido e, especialmente, foi divertido!

A idéia é a seguinte: Verifique cada pixel, começando no canto superior esquerdo até o canto inferior direito. É um pixel branco? Ignorar. É colorido? Legal, vamos acompanhar e tentar determinar seus limites (canto superior esquerdo, canto superior direito, canto inferior esquerdo, canto inferior direito).

Feito isso, verifique a área de cada retângulo. Ele contém uma cor diferente da cor do retângulo? Em seguida, descubra qual retângulo pertence a essa cor e atualize o índice z desse retângulo sobreposto em 1.

E, finalmente, desenhe todos os retângulos, levando em consideração os índices z. Na verdade, ele funciona como um índice z que você conhece de CSS e outras coisas 3D. Os retângulos com o menor índice z são desenhados primeiro, o mais alto último.

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"));}}}

O código completo que é um pouco - e isso é um eufemismo ;-) - escrito mais claramente, pode ser encontrado aqui: http://pastebin.com/UjxUUXRp

Além disso, agora que vejo a submissão da dieta, eu poderia ter facilitado algumas partes. Não é realmente necessário encontrar o retângulo cuja cor se sobrepõe a outro retângulo. Eu poderia realmente contar o número de cores 'invasoras'.