Stellen Sie sich ein Bündel von Rechtecken in der Ebene vor, wobei jedes Rechteck seine Scheitelpunkte an ganzzahligen Koordinaten und seine Seiten parallel zu den Achsen hat:
Die Rechtecke unterteilen die Ebene in mehrere nicht zusammenhängende Bereiche, darunter rot und blau gefärbt:
Ihr Ziel ist es, die Anzahl solcher Regionen zu finden, die perfekte Quadrate sind. Im obigen Beispiel gibt es drei:
Beachten Sie, dass das große Quadrat in der Mitte nicht gezählt wird, da es sich nicht um eine einzelne Region handelt, sondern aus mehreren kleineren, nicht zusammenhängenden Regionen besteht.
Eingang
Sie können eine Funktion oder ein vollständiges Programm für diese Herausforderung schreiben.
Die Eingabe erfolgt durch nicht 4n
negative Ganzzahlen, die n
Rechtecke in der Ebene definieren. Jedes Rechteck wird durch zwei gegenüberliegende Eckpunkte dargestellt, z. B. 4 9 7 8
das Rechteck mit den gegenüberliegenden Eckpunkten (4, 9)
und (7, 8)
. Beachten Sie, dass dieses Rechteck auch als 7 8 4 9
oder dargestellt werden kann 4 8 7 9
.
Das genaue Eingabeformat ist flexibel (z. B. durch Leerzeichen getrennte Zeichenfolge, durch Kommas getrennte Zeichenfolge, ein einzelnes Array von Ganzzahlen, eine Liste von Koordinatentupeln usw.). Seien Sie jedoch vernünftig und geben Sie ein Beispiel für die Ausführung Ihres Codes in Ihrem Beitrag. Sie können die Eingabe möglicherweise nicht neu anordnen.
Der Einfachheit halber können Sie davon ausgehen, dass sich keine zwei Kanten überlappen werden - dies schließt das Überlappen an einem Scheitelpunkt ein. Dies bedeutet insbesondere, dass sich keine zwei Rechtecke von Kante zu Kante oder von Ecke zu Ecke berühren und die Rechtecke eine Fläche ungleich Null haben.
Ausgabe
Ihr Programm sollte eine einzelne Ganzzahl ausgeben oder zurückgeben, dh die Anzahl der quadratischen Bereiche.
Wertung
Das ist Codegolf, also gewinnt der Code mit den wenigsten Bytes.
Testfälle
Eingang:
0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2
Ausgabe:
4
Dies sind einfach vier disjunkte Quadrate:
Eingang:
2 1 3 11
1 10 5 19
6 10 11 3
8 8 15 15
13 13 9 5
15 1 19 7
17 19 19 17
Ausgabe:
3
Dies ist der Beispieltestfall zu Beginn des Posts.
Eingang:
0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8
Ausgabe:
7
Eingang:
5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14
Ausgabe:
14
Eingang:
0 99999 100000 0
Ausgabe:
0
Dies ist nur ein großes Rechteck.
Eingang:
0 99999 100000 0
2 1 142857 285714
Ausgabe:
1
Zwei große Rechtecke, die sich überlappen.
Python 2,
480 436 386352 BytesNimmt eine Liste von Koordinatenpaaren durch STDIN in folgendem Format auf:
und gibt das Ergebnis an STDOUT aus.
Das eigentliche Programm nach dem Ersetzen der Zeichenfolge lautet:
Erläuterung
Anstatt sich mit komplexen Polygonen zu beschäftigen, behandelt dieses Programm einfache Liniensegmente. Für jedes Eingaberechteck fügen wir jede der vier Kanten einzeln zu einer kollektiven Segmentliste hinzu. Das Hinzufügen eines Segments zur Liste erfolgt folgendermaßen: Wir testen jedes der vorhandenen Segmente auf Schnittmenge mit dem neuen Segment. Wenn wir eine Kreuzung finden, teilen wir beide Segmente am Schnittpunkt und fahren fort. Zur Vereinfachung führen wir zwei separate Segmentlisten: eine horizontale und eine vertikale. Da sich Segmente nicht überlappen, können horizontale Segmente nur vertikale Segmente schneiden und umgekehrt. Besser noch, es bedeutet, dass alle Schnittpunkte (ohne Berücksichtigung der Kanten desselben Rechtecks) "korrekt" sind, dh wir haben keine T-förmigen Schnittpunkte, sodass "beide Seiten" jedes Segments wirklich geteilt sind.
Sobald wir die Segmentliste (n) erstellt haben, beginnen wir mit dem Zählen der Quadrate. Für jede Kombination von vier Segmenten (insbesondere zwei horizontalen und zwei vertikalen Segmenten) prüfen wir, ob sie ein Quadrat bilden. Außerdem stellen wir sicher, dass kein Eckpunkt innerhalb dieses Quadrats liegt (was beispielsweise passieren kann, wenn wir ein kleines Quadrat innerhalb eines größeren Quadrats haben). Dies gibt uns die gewünschte Menge. Beachten Sie, dass, obwohl das Programm jede Kombination viermal in unterschiedlicher Reihenfolge testet, die bestimmte Reihenfolge der Segmentkoordinaten garantiert, dass wir jedes Quadrat nur einmal zählen.
quelle
itertools
für die Schleifen zu verwenden, aber es endete länger. Ich kann ein paar Bytes mitexec
+ String-Ersetzungen rasieren , aber nichts zu aufregend.Haskell,
276 266 250 237 225 222217 BytesEs wird immer kürzer ... und verschleierter.
Bewerten Sie
n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]
für den ersten Testfall. Ich glaube, ich bin fast an die Grenzen des Golfspiels mit diesem Algorithmus auf Haskell gestoßen.Diese Funktion ist so langsam (mindestens O (n 3 ), wobei n der Gesamtumfang aller Rechtecke in der Eingabe ist), dass ich sie in den letzten beiden Testfällen nicht bewerten kann. Als ich es mit aktivierten Optimierungen kompilierte und es in der 400-fach verkleinerten Version
[(0,249,250,0),(2,1,357,714)]
des letzten Tests ausführte, war es in etwas mehr als 12 Sekunden fertig. Auf dieser Grundlage würde der eigentliche Testfall in etwa 25 Jahren abgeschlossen sein.Erklärung (teilweise, ich werde dies erweitern, wenn ich Zeit habe)
Wir erstellen zuerst zwei Listen
h
undv
wie folgt. Für jedes Rechteck in der Eingabe teilen wir seinen Rand in Segmente der Länge 1 auf. Die Westendpunkte der horizontalen Segmente werden inh
und die Südendpunkte der vertikalen Segmente inv
als Listen[x,y]
der Länge 2v
gespeichert . Die Koordinaten in werden in umgekehrter Reihenfolge gespeichert Form wie[y,x]
aus Golfgründen. Dann durchlaufen wir beide Listen und suchen nach horizontaler[x,j]
und vertikaler Kante,[i,y]
so dassx < i
undi-x == j-y
(also die nordwestliche und südöstliche Ecke eines Quadrats), und überprüfen, ob die Ränder des Quadrats in den richtigen Listenh
undv
im Inneren sind Koordinaten sind nicht. Die Anzahl der positiven Instanzen der Suche ist die Ausgabe.quelle