Esta imagen se hizo superponiendo 7 rectángulos de diferentes colores uno encima del otro:

Los rectángulos negro y granate no están obstruidos , es decir, no hay otros rectángulos encima.

Escriba un programa que tome una imagen como esta y elimine cualquier rectángulo sin obstrucciones, generando la imagen resultante.

Ejemplo

Si ejecutó su programa en la imagen de arriba y lo siguió ejecutando en la salida, podría progresar así.

Run 1 - Black eliminado (podría haber sido granate):

Run 2 - Maroon eliminado (única opción):

Ejecución 3 - Amarillo eliminado (única opción):

Ejecutar 4 - Azul eliminado (podría haber sido verde):

Ejecutar 5 - Verde eliminado (única opción):

Run 6 - Brown eliminado (única opción):

Ejecución 7 - Rojo eliminado (única opción):

Cualquier ejecución adicional debe producir la misma imagen en blanco.

^{Esperemos que Stack Exchange no haya comprimido ninguna de estas imágenes.}

La imagen siempre tendrá un fondo blanco y cada rectángulo tendrá un color RGB único que no sea blanco.

Puede suponer que la imagen siempre se puede interpretar como un conjunto de rectángulos superpuestos. Específicamente, puede suponer que, para un color en particular, el píxel con ese color más cercano a la parte superior de la imagen es parte del borde superior del rectángulo de ese color. Lo mismo vale para los bordes inferior, izquierdo y derecho.

Entonces, por ejemplo, en esta imagen, el borde superior del rectángulo rojo estaría justo debajo del borde inferior del rectángulo amarillo, ya que el rectángulo naranja cubría el viejo borde superior rojo:

En esta imagen, el rectángulo rojo podría eliminarse primero (junto con negro / granate / naranja / gris):

Cuando el orden de los rectángulos inferiores es ambiguo, puede darles cualquier orden.

Por ejemplo, la imagen izquierda aquí podría convertirse en el medio o la derecha:

La salida no debería tener superposiciones paradójicas (por lo que debería ser posible hacerlo con el algoritmo del pintor ). Entonces, en esta imagen ( gracias user23013 ), tendría que ser verde debajo del rectángulo naranja:

Detalles adicionales

• La imagen y los rectángulos pueden tener cualquier dimensión.
• Los rectángulos pueden tocar el borde de la imagen.
• Puede haber hasta 256 rectángulos ³ - 1.
• Si la entrada es completamente blanca, la salida también debería serlo.
• Puede usar bibliotecas de imágenes.
• La entrada debe ser el nombre del archivo de imagen o los datos de imagen sin procesar. Puede provenir de stdin o la línea de comando.
• El resultado puede escribirse en el mismo archivo de imagen u otro, arrojarse sin formato a stdout, o simplemente mostrarse.
• Se permite cualquier formato de archivo de imagen truecolor sin pérdida común .

El envío con la menor cantidad de bytes gana.

CJam, 241 bytes

(con nuevas líneas eliminadas)

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

Utiliza el formato de archivo ppm. Ejemplo de uso (usando ImageMagick):

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

Bueno, es demasiado largo y demasiado lento ... Corre alrededor de un minuto para el ejemplo.

Cambié el tamaño de los casos de prueba (y agregué algunos otros) para facilitar las pruebas.

Parece que la información del espacio de color se pierde, por lo que los colores son ligeramente diferentes.

Pitón, 690 651 610 606 594 569 bytes

El script lee el nombre de la imagen de stdin.

Detecta los bordes de cada rectángulo, ordénelos por el número de colores diferentes que contienen (los rectángulos sin obstáculos contienen solo 1 color y luego aparecen al final de la lista)

Esta lista se usa para volver a dibujar una imagen. El orden de redibujado se decide eligiendo la permutación de la lista que generaría una imagen de salida que tenga la menor diferencia de píxeles con la 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 = I.tamaño, I.carga ()
para i, j en producto (R (W), R (H)):
 c = Q [i, j]
 si c en Z: x, y, X, Y = Z [c]; Z [c] = [x, y, max (X, i), max (Y, j)]
 de lo contrario: Z [c] = [i, j, 0,0]
para n en permutaciones (ordenado ([(c, len ({Q [g] para g en producto (R (x, X), R (y, Y))})) para c, (x, y, X, Y) en Z.items ()], clave = k) [1: -1]): o = l.nuevo (I.mode, I.size, 0xFFFFFF); [D.Draw (o) .rectangle (Z [c], relleno = c) para c, _ en n]; O + = [(o, suma (abs (ab) para t, T en zip (I.getdata (), o.getdata ()) para a, b en zip (t, T)))]
max (O, clave = k) [0] .show ()

Java - 1483 bytes

No soy un gran jugador de código, que quede claro; así que la verbosidad no es del todo culpa de Java ;-) Sin embargo, esto parecía un desafío realmente divertido. Lo he resuelto de una manera que, creo, es un poco aburrida y detallada, pero bueno. Funciona, es (relativamente) rápido y, especialmente, ¡fue divertido!

La idea es la siguiente: verifique cada píxel desde el inicio en la esquina superior izquierda hasta la esquina inferior derecha. ¿Es un píxel blanco? Ignorar. ¿Es de color? Genial, hagamos un seguimiento e intentemos determinar sus límites (arriba a la izquierda, arriba a la derecha, abajo a la izquierda, abajo a la derecha).

Una vez hecho esto, verifique el área de cada rectángulo. ¿Contiene un color diferente al color del rectángulo? Luego, averigüe qué rectángulo pertenece a ese color y actualice el índice z de ese rectángulo superpuesto en 1.

Y, por último, dibuje todos los rectángulos teniendo en cuenta los índices z. Funciona realmente como un índice z que conoces de CSS y otras cosas en 3D. Los rectángulos con el índice z más bajo se dibujan primero, el índice z más alto al final.

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

El código completo, que es un poco, y eso es un eufemismo ;-), escrito más claramente, se puede encontrar aquí: http://pastebin.com/UjxUUXRp

Además, ahora que veo la sumisión de dieter, podría haber hecho algunas partes más fáciles. No es realmente necesario encontrar el rectángulo cuyo color se superpone a otro rectángulo. De hecho, podría contar la cantidad de colores 'invasores'.