Entfernen Sie ein nicht blockiertes Rechteck

20

Dieses Bild wurde erstellt, indem 7 verschiedenfarbige Rechtecke übereinander gelegt wurden:

Hauptbild

Das schwarze und das kastanienbraune Rechteck sind frei, dh keine anderen Rechtecke befinden sich über ihnen.

Schreiben Sie ein Programm, das ein solches Bild aufnimmt, und entfernen Sie jedes einzelne unversperrte Rechteck, und geben Sie das resultierende Bild aus.

Beispiel

Wenn Sie Ihr Programm auf dem obigen Bild ausgeführt haben und es weiterhin auf der Ausgabe ausgeführt haben, könnte es so weitergehen.

Lauf 1 - Schwarz entfernt (hätte kastanienbraun sein können):

Lauf 1

Lauf 2 - Maroon entfernt (nur Auswahl):

Lauf 2

Lauf 3 - Gelb entfernt (nur Auswahl):

Lauf 3

Lauf 4 - Blau entfernt (hätte grün sein können):

Lauf 4

Lauf 5 - Grün entfernt (nur Auswahl):

Lauf 5

Lauf 6 - Brown entfernt (nur Auswahl):

Lauf 6

Lauf 7 - Rot entfernt (nur Auswahl):

Lauf 7

Alle zusätzlichen Läufe sollten dasselbe weiße Bild erzeugen.

Hoffentlich hat Stack Exchange keines dieser Bilder verlustbehaftet komprimiert.

Das Bild hat immer einen weißen Hintergrund und jedes Rechteck hat eine eindeutige RGB-Farbe, die nicht weiß ist.

Sie können davon ausgehen, dass das Bild immer als Satz überlappender Rechtecke interpretiert werden kann. Insbesondere können Sie davon ausgehen, dass für eine bestimmte Farbe das Pixel, dessen Farbe dem oberen Rand des Bilds am nächsten liegt, Teil der oberen Kante des Rechtecks ​​dieser Farbe ist. Dasselbe gilt für die unteren, linken und rechten Kanten.

In diesem Bild befindet sich beispielsweise die Oberkante des roten Rechtecks ​​direkt unter der Unterkante des gelben Rechtecks, da das orangefarbene Rechteck die alte rote Oberkante bedeckt:

Beispiel 1

In diesem Bild könnte das rote Rechteck zuerst entfernt werden (zusammen mit Schwarz / Kastanienbraun / Orange / Grau):

Beispiel 2

Wenn die Reihenfolge der unteren Rechtecke nicht eindeutig ist, können Sie ihnen eine beliebige Reihenfolge geben.

Beispielsweise könnte das linke Bild hier das mittlere oder das rechte werden:

Beispiel 3 Beispiel 4 Beispiel 5

Die Ausgabe sollte keine paradoxen Überlappungen aufweisen (daher sollte es möglich sein , sie mit dem Algorithmus des Malers zu erstellen). In diesem Bild ( danke user23013 ) müsste es also unter dem orangefarbenen Rechteck grün sein:

Beispiel 6

Zusätzliche Details

  • Das Bild und die Rechtecke können beliebige Abmessungen haben.
  • Die Rechtecke berühren möglicherweise den Bildrand.
  • Es können bis zu 256 3 - 1 Rechtecke vorhanden sein.
  • Wenn der Eingang vollständig weiß ist, sollte auch der Ausgang weiß sein.
  • Sie können Bildbibliotheken verwenden.
  • Die Eingabe sollte der Bilddateiname oder die Rohbilddaten sein. Es kann von stdin oder der Kommandozeile kommen.
  • Die Ausgabe kann in dieselbe oder eine andere Bilddatei geschrieben, roh auf stdout gespuckt oder einfach angezeigt werden.
  • Jedes gängige verlustfreie TrueColor- Bilddateiformat ist zulässig.

Die Einsendung mit den wenigsten Bytes gewinnt.

Calvins Hobbys
quelle
Technisch gibt es in den Anforderungen nichts, was besagt, dass die Ausgabe keine paradoxen Überlappungen aufweisen darf. Sollte es hinzugefügt werden, oder sind beide Interpretationen des Testfalls OK?
John Dvorak
Können Sie bitte "truecolor" klären?
FUZxxl
@FUZxxl RGB mit 8 Bits pro Kanal
Martin Ender
@JanDvorak Ich hatte die Hoffnung, dass dies impliziert wurde, aber Sie haben Recht, es ist unklar, deshalb habe ich einen Hinweis hinzugefügt.
Calvins Hobbys

Antworten:

10

CJam, 241 Bytes

(Mit entfernten Zeilenumbrüchen.)

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

Es wird das ppm-Dateiformat verwendet. Anwendungsbeispiel (mit ImageMagick):

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

Nun, es ist zu lang und zu langsam ... Läuft für das Beispiel ungefähr eine Minute.

Ich habe die Größe der Testfälle geändert (und einige andere hinzugefügt), um das Testen zu vereinfachen.

Es scheint, dass die Farbrauminformationen verloren gehen, sodass die Farben leicht abweichen.

jimmy23013
quelle
2

Python, 690 651 610 606 594 569 Bytes

Das Skript liest den Bildnamen von stdin.

Es erkennt die Kanten aller Rechtecke, sortiert sie nach der Anzahl der verschiedenen Farben, die sie enthalten (die nicht blockierten Rechtecke enthalten nur eine Farbe und erscheinen dann am Ende der Liste).

Diese Liste wird verwendet, um ein Bild neu zu zeichnen. Die Neuzeichnungsreihenfolge wird durch Auswahl der Permutation der Liste festgelegt, die ein Ausgabebild erzeugen würde, das den geringsten Pixelunterschied zur Eingabe aufweist.

aus PIL importieren Bild als l, ImageDraw als D; aus itertools importieren *; O, R, I, Z, k = [], Bereich, l.open (raw_input ()), {}, Lambda x: -x [1 ]; (W, H), Q = I.size, I.load ()
für i, j im Produkt (R (W), R (H)):
 c = Q [i, j]
 wenn c in Z: x, y, x, y = z [c]; z [c] = [x, y, max (x, i), max (y, j)]
 sonst: Z [c] = [i, j, 0,0]
für n in Permutationen (sortiert ([(c, len ({Q [g] für g in Produkt (R (x, X), R (y, Y))}) für c, (x, y, X, Y) in Z.items ()]: key = k) [1: -1]): o = l.new (I.mode, I.size, 0xFFFFFF); [D.Draw (o) .rectangle (Z [c], fill = c) für c, _ in n]; O + = [(o, sum (abs (ab) für t, T in zip (I.getdata (), o.getdata ()) für a, b in zip (t, T)))]
max (O, key = k) [0] .show ()
Dieter
quelle
0

Java - 1483 Bytes

Ich bin kein großartiger Code-Golfer. Die Ausführlichkeit ist also nicht ganz Javas Schuld ;-) Trotzdem schien dies eine wirklich lustige Herausforderung zu sein. Ich habe es auf eine Art gelöst, die - ich denke - ein bisschen langweilig und wortreich ist, aber hey. Es funktioniert, es ist (relativ) schnell und vor allem hat es Spaß gemacht!

Die Idee ist wie folgt: Überprüfen Sie jedes Pixel von der linken oberen Ecke bis zur rechten unteren Ecke. Ist es ein weißes Pixel? Ignorieren. Ist es gefärbt? Cool, lassen Sie uns den Überblick behalten und versuchen, die Grenzen zu bestimmen (oben links, oben rechts, unten links, unten rechts).

Überprüfen Sie anschließend den Bereich jedes Rechtecks. Enthält es eine andere Farbe als die Farbe des Rechtecks? Finden Sie dann heraus, welches Rechteck zu dieser Farbe gehört, und aktualisieren Sie den Z-Index des überlappenden Rechtecks ​​um 1.

Und schließlich zeichnen Sie alle Rechtecke unter Berücksichtigung der Z-Indizes. Es funktioniert tatsächlich wie ein Z-Index, den Sie aus CSS und anderen 3D-Inhalten kennen. Die Rechtecke mit dem niedrigsten Z-Index werden zuerst gezeichnet, der höchste Z-Index zuletzt.

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

Der vollständige Code, der ein bisschen - und das ist eine Untertreibung ;-) - klarer geschrieben ist, ist hier zu finden: http://pastebin.com/UjxUUXRp

Jetzt, wo ich Dieter's Beitrag sehe, hätte ich auch einige Teile einfacher machen können. Es ist nicht wirklich notwendig, das Rechteck zu finden, dessen Farbe ein anderes Rechteck überlappt. Ich könnte in der Tat nur die Anzahl der "eindringenden" Farben zählen.

Sander
quelle