Herausforderung
Schreiben Sie ein Programm, das bei einem zweidimensionalen booleschen Array (äquivalent eine monochromatische Bitmap) eine Reihe von Polygonen ausgibt, die den Umriss des Bereichs beschreiben, der „wahr“ ist (1).
Die Eingabe erfolgt als Folge von '#'
(Hash), ' '
(Leerzeichen) und \n
(Zeilenumbruch) Zeichen. Linien können unterschiedlich lang sein. In diesem Fall werden die fehlenden Teile als Leerzeichen angenommen. Die Ausgabe sollte eine (durch Zeilenumbrüche getrennte) Liste von Polygonen sein, wobei jedes Polygon durch eine (durch Kommas getrennte) Liste von Koordinaten dargestellt wird.
Beispiele & Anforderungen
Die Koordinaten müssen im Uhrzeigersinn aufgelistet sein. Eingang:
#
Akzeptable Ausgaben umfassen:
(0,0), (1,0), (1,1), (0,1) (1,0), (1,1), (0,1), (0,0) (1,1), (0,1), (0,0), (1,0) (0,1), (0,0), (1,0), (1,1)
Disjunkte Regionen müssen mehrere Polygone zurückgeben. Eingang:
# #
Beispielausgabe (die tatsächliche Ausgabe muss aus zwei Zeilen bestehen):
(0,0), (1,0), (1,1), (0,1) (2,0), (3,0), (3,1), (2,1)
Löcher in einem Polygon müssen als separates Polygon aufgeführt werden, jedoch gegen den Uhrzeigersinn. Eingang:
### # # ###
Beispielausgabe:
(0,0), (3,0), (3,3), (0,3) (1,1), (1,2), (2,2), (2,1)
Sie können frei wählen, ob sich diagonal benachbarte Scheitelpunkte verbinden oder nicht. Eingang:
# #
Beispielausgabe:
(0,0), (1,0), (1,1), (0,1) (1,1), (2,1), (2,2), (1,2)
oder
(0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (1,1), (0, 1)
Die Koordinatenlisten müssen nicht optimal kurz sein. Zum Beispiel:
##
Akzeptable Ergebnisse:
(0,0), (2,0), (2,1), (0,1) // Redundant coordinates along a straight line are acceptable (0,0), (1,0), (2,0), (2,1), (1,1), (0,1) // Duplicate start- and end-point are acceptable (0,0), (2,0), (2,1), (0,1), (0,0)
Wie üblich „gewinnt“ das kürzeste Programm.
Antworten:
Perl,
345311265 ZeichenEinschränkungen
Angenommen, die Eingabe ist nicht breiter als 64 Zeichen (ihre Höhe ist jedoch im Prinzip unbegrenzt). Dies kann durch Ändern der relevanten Konstanten auf 512 oder 8192 oder eine andere Zweierpotenz erweitert werden, wodurch der Code nur geringfügig länger wird.
Etwas besser lesbare Version
Ein gewisser Kredit geht an Mob, weil die erste Zeile meine Wiederverwendung seiner Idee in Lasern ist . Der Rest ist ganz meine Arbeit.
Bearbeitungen
$x
beim Abbiegen keine Aktualisierung erforderlich ist, da die nächste Iteration dies bereits ausführt1
= down,2
= left to1
= left,2
= down und aktualisieren Sie$d
über XOR anstatt direktquelle
Python, 607 Zeichen
Der Code führt eine Liste der erkannten Grenzen, sofern # Symbole in der Eingabereihenfolge verarbeitet werden. Die Grenzen werden in einer Tabelle E gespeichert, die Kanten (4-Tupel von x_start, y_start, x_end, y_end) einer Liste von Kanten zuordnet, die die Grenze eines Polygons bilden. Während wir jedes neue # verarbeiten, kann es mit einem Polygon über (p) oder links davon (q) verbunden sein. Der Code findet p und q mit E und führt dann die Grenze des aktuellen # (r) mit p und q zusammen, falls vorhanden. Der Fall, in dem p == q Löcher erzeugt.
quelle