Cette image a été créée en superposant 7 rectangles de couleurs différentes les uns sur les autres:

Les rectangles noirs et marron ne sont pas obstrués , c'est-à-dire qu'aucun autre rectangle n'est au-dessus d'eux.

Écrivez un programme qui prend une image comme celle-ci et supprimez tout rectangle non obstrué, en sortie l'image résultante.

Exemple

Si vous avez exécuté votre programme sur l'image ci-dessus et l'avez continué à relancer sur la sortie, il pourrait progresser comme ceci.

Piste 1 - Noir retiré (aurait pu être marron):

Run 2 - Maroon supprimé (seul choix):

Run 3 - Jaune retiré (seul choix):

Run 4 - Blue supprimé (aurait pu être vert):

Course 5 - Vert retiré (seul choix):

Run 6 - Brown enlevé (seul choix):

Run 7 - Red supprimé (seul choix):

Tout essai supplémentaire devrait produire la même image blanche.

^{J'espère que Stack Exchange n'a compressé aucune de ces images avec perte.}

L'image aura toujours un fond blanc et chaque rectangle aura une couleur RVB unique qui n'est pas blanche.

Vous pouvez supposer que l'image peut toujours être interprétée comme un ensemble de rectangles se chevauchant. Plus précisément, vous pouvez supposer que, pour une couleur particulière, le pixel dont la couleur est la plus proche du haut de l'image fait partie du bord supérieur du rectangle de cette couleur. Il en va de même pour les bords inférieur, gauche et droit.

Ainsi, par exemple, dans cette image, le bord supérieur du rectangle rouge serait juste en dessous du bord inférieur du rectangle jaune, car le rectangle orange recouvrait l'ancien bord supérieur rouge:

Dans cette image, le rectangle rouge pourrait être supprimé en premier (avec le noir / marron / orange / gris):

Lorsque l'ordre des rectangles inférieurs est ambigu, vous pouvez leur donner n'importe quel ordre.

Par exemple, l'image de gauche ici pourrait devenir le milieu ou la droite:

La sortie ne doit pas avoir de chevauchements paradoxaux (donc la rendre possible avec l' algorithme du peintre devrait être possible). Donc dans cette image ( merci user23013 ), il faudrait que ce soit vert sous le rectangle orange:

Détails supplémentaires

• L'image et les rectangles peuvent avoir n'importe quelle dimension.
• Les rectangles peuvent toucher la bordure de l'image.
• Il peut y avoir jusqu'à 256 rectangles ³ - 1.
• Si l'entrée est entièrement blanche, la sortie devrait l'être également.
• Vous pouvez utiliser des bibliothèques d'images.
• L'entrée doit être le nom du fichier image ou les données d'image brutes. Il peut provenir de stdin ou de la ligne de commande.
• La sortie peut être écrite dans le même fichier ou dans un autre fichier image, rejetée crue dans stdout ou simplement affichée.
• Tout format de fichier d'image truecolor sans perte commun est autorisé.

La soumission avec le moins d'octets est gagnante.

CJam, 241 octets

(avec les nouvelles lignes supprimées.)

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

Il utilise le format de fichier ppm. Exemple d'utilisation (en utilisant ImageMagick):

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

Eh bien, c'est trop long et trop lent ... Exécute environ une minute pour l'exemple.

J'ai redimensionné les cas de test (et ajouté quelques autres) pour faciliter les tests.

Il semble que les informations de l'espace colorimétrique soient perdues, les couleurs sont donc légèrement différentes.

Python, 690 651 610 606 594 569 octets

Le script lit le nom de l'image depuis stdin.

Il détecte les bords de tous les rectangles, les trie par le nombre de couleurs différentes qu'ils contiennent (les rectangles non obstrués ne contiennent qu'une seule couleur, puis apparaissent à la fin de la liste)

Cette liste est utilisée pour redessiner une image. L'ordre de redessin est décidé en choisissant la permutation de la liste qui générerait une image de sortie qui aurait le moins de différence de pixels avec l'entrée.

depuis PIL import Image comme l, ImageDraw as D; depuis itertools import *; O, R, I, Z, k = [], range, l.open (raw_input ()), {}, lambda x: -x [1 ]; (W, H), Q = I. taille, I. charge ()
pour i, j dans le produit (R (W), R (H)):
 c = Q [i, j]
 si c dans Z: x, y, X, Y = Z [c]; Z [c] = [x, y, max (X, i), max (Y, j)]
 sinon: Z [c] = [i, j, 0,0]
pour n en permutations (triées ([(c, len ({Q [g] pour g dans le produit (R (x, X), R (y, Y)))})) pour c, (x, y, X, Y) dans Z.items ()], key = k) [1: -1]): o = l.new (I.mode, I.size, 0xFFFFFF); [D.Draw (o) .rectangle (Z [c], fill = c) for c, _ in n]; O + = [(o, sum (abs (ab) for t, T in zip (I.getdata (), o.getdata ()) for a, b en zip (t, T)))]
max (O, clé = k) [0] .show ()

Java - 1483 octets

Je ne suis pas un grand golfeur de code, que ce soit clair; donc la verbosité n'est pas entièrement la faute de Java ;-) Néanmoins, cela semblait être un défi vraiment amusant. Je l'ai résolu d'une manière qui - je pense - est un peu ennuyeuse et verbeuse, mais bon. Ça marche, c'est (relativement) rapide et surtout c'était amusant!

L'idée est la suivante: Vérifiez chaque pixel en partant du coin supérieur gauche jusqu'en bas à droite. Est-ce un pixel blanc? Ignorer. Est-il coloré? Cool, suivons-le et essayons de déterminer ses limites (en haut à gauche, en haut à droite, en bas à gauche, en bas à droite).

Une fois cela fait, vérifiez la zone de chaque rectangle. Contient-il une couleur différente de celle du rectangle? Découvrez ensuite quel rectangle appartient à cette couleur et mettez à jour l'index z de ce rectangle qui se chevauchent de 1.

Et enfin, dessinez tous les rectangles en tenant compte des z-indices. Cela fonctionne en fait comme un z-index que vous connaissez de CSS et d'autres trucs 3D. Les rectangles avec le z-index le plus bas sont dessinés en premier, le z-index le plus élevé en dernier.

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

Le code complet qui est un peu - et c'est un euphémisme ;-) - écrit plus clairement, peut être trouvé ici: http://pastebin.com/UjxUUXRp

De plus, maintenant que je vois la soumission de Dieter, j'aurais pu rendre certaines parties plus faciles. Il n'est pas vraiment nécessaire de trouver le rectangle dont la couleur chevauche un autre rectangle. Je pourrais en effet juste compter le nombre de couleurs «envahissantes».