Das Tangram ist ein Dissektionspuzzle aus sieben Formen: Fünf unterschiedlich große Dreiecke, ein Parallelogramm und ein Quadrat. Bei einer gegebenen Form besteht das Ziel darin, die Form unter Verwendung aller Teile und ohne Überlappung wiederherzustellen. Es gibt offensichtlich unendlich viele Möglichkeiten, diese Gruppe von Stücken in der Ebene anzuordnen. Eine interessante Untergruppe sind die
Gitter Tangrams
Wir können das "normale" Tangram-Quadrat in ein größeres Quadrat zeichnen, das durch ein Gitter in 16 kleinere Quadrate unterteilt ist. Gitter-Tangrams sind nur Formen, die aus den Tangram-Teilen bestehen, sodass sich alle Eckpunkte der Teile auf den Gitterpunkten befinden.
Dies sind die Arten von Tangram-Rätseln, die wir bei dieser Herausforderung berücksichtigen möchten, da sie wahrscheinlich einfacher zu handhaben sind als die allgemeineren.
Als Randnotiz: Die chinesischen Mathematiker Chuan-Chin Hsiung und Fu Traing Wang bewiesen 1942, dass es nur 13 konvexe Tangrams gibt. Sie zeigten zunächst, dass das Problem auf Gittertangrams reduziert werden kann, und verwendeten dann einige kombinatorische und geometrische Argumente. Dies sind alles diese 13:
Herausforderung
Geben Sie bei einem lösbaren Gittertangram eine Zerlegung des Gittertangrams in die sieben Tangramteile aus.
IO
Ein Tangram wird als Schwarz-Weiß-Bild (die Form ist schwarz, der Hintergrund weiß) mit beidseitigen Vielfachen von 50 Pixel angegeben. Das Raster hat eine Breite von genau 50px. Die Gitterlinien verlaufen parallel zu den Bildseiten.
BEARBEITEN: Das Bild kann als Eingabe akzeptiert und als Ausgabe in jedem geeigneten Rasterbildformat wie PNG, TIFF, PBM usw. zurückgegeben werden. Eine Darstellung als binäres 2D-Array oder String oder Matrix ist jedoch zulässig.
Die Ausgabe sollte wieder die gleiche Größe und Form haben, aber bei jedem Stück eine andere Farbe haben oder alternativ mit weißen Linien, die alle Stücke trennen. Es ist erwähnenswert, dass das nicht rechteckige Viereck umgedreht werden kann.
Die Pixel am Rand der Teile müssen nicht genau mit denen der Form übereinstimmen, auch wenn es Aliasing-Effekte oder andere Unschärfen gibt, ist dies immer noch in Ordnung.
Beispiel für Ein- und Ausgabe:
Beispiele:
Mögliche Lösungen:
quelle
Antworten:
BBC BASIC,
570 514490 Bytes ASCIILaden Sie den Interpreter unter http://www.bbcbasic.co.uk/bbcwin/download.html herunter
435 Bytes tokenisiert
Das vollständige Programm zeigt eine Eingabe von
L.bmp
auf dem Bildschirm an und ändert sie dann, um eine Lösung zu finden.Erläuterung
Beachten Sie, dass in BBC basic ein Abstand von 1 Pixel = 2 Einheiten gilt, sodass das 50x50-Pixel-Raster zu einem 100x100-Raster wird.
Wir verwenden eine rekursive Funktion, um die beiden großen Dreiecke, das mittlere Dreieck, das Quadrat und das Parallelogramm in die Form zu bringen. Die frühere Form in der Liste wird gezeichnet, bevor der nächste rekursive Aufruf erfolgt. Wenn ein rekursiver Aufruf zurückkehrt, ohne eine Lösung zu finden, wird die frühere Form schwarz überzeichnet und eine neue Position der früheren Form versucht.
Sobald diese fünf Formen gezeichnet sind, ist das Platzieren der beiden kleinen Dreiecke nur eine Formalität. Es ist jedoch notwendig, eine davon zu zeichnen, um sie zu unterscheiden, wenn sie eine gemeinsame Kante haben. Wir färben nur eines der beiden kleinen Dreiecke. Der andere ist in natürlichem Schwarz gehalten.
Es wird versucht, jede Form an verschiedenen x-, y-Koordinaten und in vier verschiedenen Rotationen zu platzieren. Um zu testen, ob Platz zum Zeichnen einer Form frei ist, verwenden wir die folgende Vorlage mit einem Winkel von 45 Grad. Die Rotationen werden um die
*
und die getesteten 8 Pixel in 2 Halbkreisen mit Radius 9 und 81 Einheiten durchgeführt und fallen auf Strahlungslinien mit ungeraden Vielfachen von 22,5 Grad zur x- und y-Achse.Für ein großes Dreieck müssen alle 8 Felder frei sein. Bei anderen Formen müssen nur einige der Zellen frei sein, damit eine Maske angewendet wird.
Sobald festgestellt wurde, dass eine Form passt, muss sie gezeichnet werden. Wenn es sich um ein Dreieck handelt, mit dem es gezeichnet ist
PLOT 85
, und wenn es sich um ein Parallelogramm handelt, ist die Zahl 32 höher (beachten Sie, dassPLOT
wir ein Quadrat für Zwecke als spezielles Parallelogramm betrachten). In beiden Fällen müssen 3 aufeinanderfolgende Eckpunkte angegeben werden. Der zweite Scheitelpunkt ist der Ursprung der Form (*
in der obigen Tabelle markiert ), mit Ausnahme des großen Dreiecks, bei dem es sich (vor der Drehung) um den Ursprung handelt.-1,-1.
Die anderen beiden Scheitelpunkte können x- und y-Koordinaten haben,-1,0 or 1
die aus der Basis 3 extrahiert werden codierte Zahlen, dann um 99 skaliert und bei Bedarf durch Transformation mitc
und gedrehts
.Ungolfed Code
Ausgabe
Dies ist eine Montage der vom Programm gefundenen Lösungen für die Testfälle. Die Verwendung von 99 statt 100 aus Golfgründen hinterlässt einige kleine schwarze Lücken. Da die Formen während der Suche neu gezeichnet werden, kann es in einigen Fällen einige Sekunden dauern, bis sie ausgeführt werden. Das Anschauen ist sehr faszinierend.
quelle