Eingang

Ihre Eingabe in dieser Herausforderung ist eine Liste von ganzzahligen Paaren. Sie repräsentieren die südwestlichen Ecken der Einheitsquadrate in der Ebene und die Liste repräsentiert ihre Vereinigung als Teilmenge der Ebene. Zum Beispiel die Liste

[(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)]

stellt den roten Satz in diesem Bild dar:

Ausgabe

Ihre Ausgabe ist eine Liste von ganzzahligen Vierfachen, die rechteckige Teilmengen der Ebene darstellen. Genauer (x,y,w,h)gesagt , ein Vierfacher entspricht einem Rechteck mit Breite w > 0und Höhe, h > 0dessen südwestliche Ecke sich in befindet (x,y). Die Rechtecke müssen eine exakte Abdeckung des Eingabebereichs bilden, in dem Sinne, dass jedes der Einheitsquadrate eine Teilmenge eines Rechtecks ​​ist, jedes Rechteck eine Teilmenge des Bereichs ist und zwei Rechtecke nur an ihren Rändern überlappen dürfen. Um triviale Lösungen zu verbieten, darf die Abdeckung keine zwei Rechtecke enthalten, die zu einem größeren Rechteck zusammengefügt werden könnten.

Zum Beispiel die Liste

[(0,0,2,1),(0,1,3,1),(1,2,2,1)]

vertritt die rechtliche Abdeckung

der oben genannten Region, während die Bedeckung gegeben durch

[(0,0,2,2),(2,1,1,1),(1,2,1,1),(2,2,1,1)]

ist illegal, da die benachbarten 1-zu-1-Quadrate zusammengeführt werden könnten:

Regeln

Sie können ein vollständiges Programm oder eine Funktion angeben. Die genaue Formatierung der Ein- und Ausgabe ist aus vernünftigen Gründen nicht wichtig. Die kürzeste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Sie werden aufgefordert, eine Erläuterung Ihres Algorithmus und einige Beispielausgaben anzugeben.

Testfälle

Eine U-förmige Region:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5)]

Ein großes Dreieck:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(6,0),(6,1),(6,2),(6,3),(7,0),(7,1),(7,2),(8,0),(8,1),(9,0)]

Ein Quadrat mit Löchern:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,7),(5,8),(5,9),(6,1),(6,2),(6,3),(6,5),(6,6),(6,7),(6,8),(6,9),(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9)]

Nicht verbundene Regionen:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(4,0),(4,1),(4,2),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(6,0),(6,1),(6,2),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,7),(9,8),(9,9),(10,0),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9)]

Verifizierer

Verwenden Sie dieses Python 2-Programm, um Ihre Lösung zu überprüfen. Es wird von STDIN eine Liste von Tupeln (die Eingabe) und eine Liste von Vierfachen (Ihre Ausgabe) durch Komma getrennt.

Ich habe auch dieses Python 2-Programm geschrieben, um die Bilder zu generieren, und Sie können es auch verwenden. Es nimmt von STDIN eine Liste von entweder Tupeln oder Vierfachen und erzeugt eine Datei mit dem Namen out.png. Es erfordert die PIL-Bibliothek. Sie können bei Bedarf auch die Größe der Gitterzellen und die Breite der Gürtellinien ändern.

Python: 196 193 182 Zeichen

def g(r):
 for p in r:
  for q in r:
   for h in 0,1:
    if p[h::2]==q[h::2]and p[1-h]+p[~h]==q[1-h]:p[~h]+=q[~h];r.remove(q);return g(r)
 return r
f=lambda P:g([x+[1,1]for x in P])

Meine erste Lösung verwendete genau den gleichen Algorithmus wie KSFT, daher habe ich mit anderen Methoden experimentiert.

Zuerst mache ich eine Vorverarbeitung, ich konvertiere alle Punkte in kleine 1x1 Rechtecke {x+(1,1)for x in P}. Mit diesen Rechtecken rufe ich die Funktion auf g. gDurchläuft jede Kombination von Rechtecken. Wenn 2 Rechtecke gefunden werden, die zu einem größeren zusammengeführt werden können, werden beide gelöscht und das neue angefügt. Danach ruft es sich mit dem neuen Satz Rechtecke auf.

Verwendung

f([[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]])

Ergebnisse

Hier sehen Sie die Visualisierung der Ergebnisse. Beachten Sie, dass sie in der aktuellen Version etwas anders sein können. Die Idee ist jedoch, dass es keine erkennbaren Muster gibt.

Eine U-förmige Region:

Ein großes Dreieck

Ein Quadrat mit Löchern:

Nicht verbundene Regionen:

Just for fun: Pyth: 73 69 Zeichen

D!HFGHFZHV2I&q%2>GN%2>ZNqs%2>G-1N@Z-1N X-3NG@Z-3NR!-H]Z)))RH!m+d*2]1Q

Funktioniert nur in der Offline-Version. Fehler in der Online-Version behoben. Probieren Sie es hier aus: Pyth Compiler / Executor . Erwartet eine Liste von Listen, keine Liste von Tupeln.

edit: Benutzte eine Idee aus @ edc65: Anstatt beide Rechtecke zu löschen und ein neues zu erstellen, bearbeite ich eines und lösche nur eines. In der Python-Lösung konnte ich die Sets und die Tupel-Listen-Tupel-Casts reiten lassen. -11 Zeichen in Python / -4 Zeichen in Python

Python - 272 261 258 251 224

Ich denke, ich kann das mehr Golf spielen. Ich bin mir ziemlich sicher, dass dies funktioniert, aber ich habe noch nicht alle Testfälle getestet. Ich habe es ausprobiert. Es funktioniert für alle Testfälle.

a=sorted(input())
b=[]
r=range
for i in a:
 c=set(a)-set(b);w=h=1;x,y=i
 if i in b:continue
 while not{(x,y+h)}-c:h+=1
 while all((x+w,y+j)in c for j in r(h)):w+=1
 for j in r(w):
  for k in r(h):b+=(j+x,k+y),
 print x,y,w,h

Ich arbeite daran, Bilder der Ergebnisse hinzuzufügen. Bearbeiten: Hier sind die Ergebnisse aus dem Beispiel und den Testfällen:

Ich versuche, dies in Perl zu schreiben, aber ich kann nicht herausfinden, wie man mehrdimensionale Arrays aus stdin ohne eine große Anzahl von Zeichen erhält. Hat jemand irgendwelche Vorschläge?

Python 2, 139

Das Programm akzeptiert Listen geordneter Paare, die bei der Standardeingabe von geschweiften Klammern umgeben sind. Z.B,{(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)}

s=input()
while s:x,y=min(s);w=h=0;exec"while(x+w,y)in s:w+=1\nwhile%s<=s:s-=%s;h+=1"%(("{(X,y+h)for X in range(x,x+w)}",)*2);print x,y,w,h

Es ist oft irritierend (nicht nur im Golf), dass Python eine Zuweisung innerhalb eines Loop-Tests nicht zulässt. Um dies zu umgehen, habe ich Zeichenfolgenformatierungsoperationen verwendet.

Mathematica - 315 285 267 Bytes

f=(r={};For[m=MemberQ;t=Table;s=Sort@#,s!={},For[{x,y,w,h}=#~Join~{1,1}&@@s;i=j=0,i<1||j<1,If[s~m~{x+w,y+a-1}~t~{a,h}==True~t~{h},w++,i++];If[s~m~{x+a-1,y+h}~t~{a,w}==True~t~{w},h++,j++]];s=s~Cases~_?(!m[Join@@t[{x+a,y+b}-1,{a,w},{b,h}],#]&);r~AppendTo~{x,y,w,h}];r)&

Mit etwas Hilfe von @ MartinBüttner.

Ungolfed:

f = (
    rectangles = {};
    For[squares = Sort[#], squares != {},
        For[{x, y, w, h} = Join[squares[[1]], {1, 1}]; i = j = 0, i < 1 || j < 1,
            If[Table[MemberQ[squares, {x + w, y + a - 1}], {a, h}] == Table[True, {h}], w++, i++];
            If[Table[MemberQ[squares, {x + a - 1, y + h}], {a, w}] == Table[True, {w}], h++, j++];
        ];
        squares = Cases[squares, _ ? (!MemberQ[Join@@Table[{x + a - 1, y + b - 1}, {a, w}, {b, h}], #] &)];
        AppendTo[rectangles, {x, y, w, h}]
    ];
    rectangles
)&

Verwendung:

In: f @ {{0,0},{1,0},{0,1},{1,1},{2,1},{1,2},{2,2}}
Out: {{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

Testfälle

Eine U-förmige Region

{{0, 0, 6, 2}, {0, 2, 2, 4}, {4, 2, 2, 4}}

Ein großes Dreieck

{{0, 0, 6, 5}, {0, 5, 3, 3}, {0, 8, 2, 1}, {0, 9, 1, 1}, {3, 5, 2, 1}, {3, 6, 1, 1}, {6, 0, 3, 2}, {6, 2, 2, 1}, {6, 3, 1, 1}, {9, 0, 1, 1}}

Ein Quadrat mit Löchern

{{0, 0, 6, 3}, {0, 3, 3, 6}, {1, 9, 9, 1}, {3, 4, 3, 2}, {3, 6, 2, 3}, {4, 3, 6, 1}, {5, 7, 5, 2}, {6, 1, 4, 2}, {6, 5, 4, 2}, {7, 0, 3, 1}, {7, 4, 3, 1}}

Nicht verbundene Regionen

{{0, 0, 2, 5}, {0, 5, 1, 4}, {1, 6, 2, 4}, {2, 1, 1, 5}, {4, 0, 3, 3}, {4, 4, 3, 6}, {5, 3, 1, 1}, {8, 0, 3, 4}, {8, 4, 1, 6}, {9, 7, 2, 3}, {10, 4, 1, 3}}

Haskell, 158

f[]=[]
f s@((x,y):_)=(x,y,w-x,h-y):f[r|r@(a,b)<-s,a<x||a>=w||b<y||b>=h]where w=[i|i<-[x..],notElem(i,y)s]!!0;h=[i|i<-[y..],not$all(\x->elem(x,i)s)[x..w-1]]!!0

Testfälle und Bilder folgen in Kürze.

Algorithmus: Nehmen Sie das erste Quadrat. Greifen Sie ganz nach rechts, ohne auf ein Feld zu stoßen, das nicht in der Eingabe enthalten ist. Greifen Sie dann so weit wie möglich nach oben, ohne ein Quadrat auf der Eingabe zu haben. Wir haben jetzt ein Rechteck ohne fehlendes Quadrat. Fügen Sie es der Ausgabe hinzu, entfernen Sie alle seine Quadrate von der Eingabe und rufen Sie rekursiv auf.

JavaScript (ES6) 148 155 199

Edit2 Noch ein bisschen Tuning
Edit Ein bisschen Golfen + Umschreiben mit Rekursion. Habe nicht mit einer solchen Reduzierung gerechnet. Jetzt ist es etwas schwierig zu folgen, aber der Algorithmus ist der gleiche.

Der Algorithmus ähnelt der Antwort von @jakube.

1. Jeder Punkt wird zu einem 1x1-Quadrat (Vorverarbeitung)
2. Überprüfen Sie für jedes Element, ob es mit einem anderen zusammengeführt werden kann
   . Das erste Element wächst, das zweite Element wird gelöscht. Beginnen Sie erneut mit Schritt 2.
   Andernfalls fahren Sie mit dem nächsten Element fort

F=l=>
  (l.map(x=>x.push(1,1)),R=f=>
    l.some(u=>
      (l=l.filter(t=>
        [0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))
      ),f)
    )?R():l
  )()

Test im Snippet

F=l=>(l.map(x=>x.push(1,1)),R=f=>l.some(u=>(l=l.filter(t=>[0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))),f))?R():l)()

// Test
MyCanvas.width= 600;
MyCanvas.height = 220;
var ctx = MyCanvas.getContext("2d");
ctx.fillStyle="#f23";

Draw=(x,y,f,l)=>l.forEach(p=>ctx.fillRect(x+p[0]*f,y+p[1]*f,p[2]*f-1||f-1,p[3]*f-1||f-1));

test=[
[[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,0],[2,1],[3,0],[3,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[6,0],[6,1],[6,2],[6,3],[7,0],[7,1],[7,2],[8,0],[8,1],[9,0]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[3,0],[3,1],[3,2],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,7],[5,8],[5,9],[6,1],[6,2],[6,3],[6,5],[6,6],[6,7],[6,8],[6,9],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7],[7,8],[7,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8],[9,9]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,6],[1,7],[1,8],[1,9],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[4,0],[4,1],[4,2],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[5,8],[5,9],[6,0],[6,1],[6,2],[6,4],[6,5],[6,6],[6,7],[6,8],[6,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,7],[9,8],[9,9],[10,0],[10,1],[10,2],[10,3],[10,4],[10,5],[10,6],[10,7],[10,8],[10,9]]
]

Draw(0,0,10,test[0]),Draw(0,110,10,F(test[0]))
Draw(50,0,10,test[1]),Draw(50,110,10,F(test[1]))
Draw(130,0,10,test[2]),Draw(130,110,10,F(test[2]))
Draw(250,0,10,test[3]),Draw(250,110,10,F(test[3]))
Draw(370,0,10,test[4]),Draw(370,110,10,F(test[4]))

<canvas id=MyCanvas></canvas>

Mathematica, 153 151 144 136 133

Sort[{##,1,1}&@@@Input[]]//.{a___,r:{x_,y_,__},b___,{X_,Y_,W_,H_},c___}/;r=={x,Y,X-x,H}||r=={X,y,W,Y-y}:>{a,r+Sign@{0,0,X-x,Y-y},b,c}

Beispiel:

Eingang:

{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 1}, {1, 2}, {2, 2}}

Ausgabe:

{{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

Eingang:

{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}, {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}, {4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {4, 9}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}, {5, 7}, {5, 8}, {5, 9}, {6, 1}, {6, 2}, {6, 3}, {6, 5}, {6, 6}, {6, 7}, {6, 8}, {6, 9}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 6}, {8, 7}, {8, 8}, {8, 9}, {9, 0}, {9, 1}, {9, 2}, {9, 3}, {9, 4}, {9, 5}, {9, 6}, {9, 7}, {9, 8}, {9, 9}}

Ausgabe:

{{0, 0, 3, 9}, {1, 9, 9, 1}, {3, 0, 3, 3}, {3, 4, 1, 5}, {4, 3, 1, 6}, {5, 3, 1, 3}, {5, 7, 1, 2}, {6, 1, 1, 3}, {6, 5, 1, 4}, {7, 0, 3, 9}}

Algorithmus:

Bedecke die Region mit Quadraten und füge sie dann zusammen.