Gausi - Sa 12.12.09 11:29
Titel: AGS 2009 - Tipp/Lösung zu Paranuss 3

---

Guten morgen, zusammen. :D

Normalerweise geben wir für die Paranüsse ja keine Hinweise. Aber wir denken, dass bei dieser Nuss etwas Hilfe nicht schaden kann.

• Der Header des Formates besteht aus genau einem Integer, und die Idee zu dem Dateiformat kam dem Weihnachtsmann, als er mit seinen IT-Wichteln Urlaub auf Samos gemacht hat.

Viel Spaß beim weiterknobeln. :D

Sylvus - Sa 12.12.09 14:37

---

danke :)

Martok - So 13.12.09 03:14

---

Okay, Punkt 1 war klar. Und ansonsten: der Weihnachtsmann hatte zuviel Griechischen Wein ;)

Flamefire - So 13.12.09 17:27

---

Er muss echt verdammt viel gesoffen haben, als er das Ding erstellt hat.
Aber echt genial gemacht!

BenBE - Mo 14.12.09 01:24

---

Jap. Also echt mal. Da muss man schon ganz schön *** sein, um auf solch verquere Ideen zu kommen!

Gausi - Fr 25.12.09 12:31

---

Und hier jetzt die Lösung hierzu: Das Bild zeigt eine Glocke.

Der Tipp war dabei ein Hinweis auf Pythagoras von Samos. Das ist der nette Mensch mit dem a^2 + b^2 = c^2 in einem rechtwinkligen Dreieck mit Hypothenuse c. ;-)

Das Format speichert nicht eine Pixelmatrix, wie es z.B. BMP tut, sondern eine Abstandsmatrix der schwarzen Pixel. D.h. wenn das Bild 100 schwarze Pixel enthält, wird eine 100x100 Matrix gespeichert, in der die (Quadrate der) Abstände der schwarzen Pixel untereinander notiert sind. Aus diesen Daten kann man (bis auf Spiegelung, Verschiebung, Rotation) das Bild wieder rekonstruieren.

Die Lösung im Anhang ist zwar mit Photonentorpedos auf Spatzen geschossen, ist aber wohl recht nett anzuschauen. Dabei werden die schwarzen Pixel zuerst zufällig angeordnet. Aus diesen geratenen Positionen und der Distanzmatrix wird eine Funktion erstellt (mit ganz furchtbar vielen Unbekannten), die dann mit einem iterativen Verfahren minimiert wird.
Dieses Verfahren funktioniert auch dann recht gut, wenn die Distanzmatrix unvollständig und/oder fehlerhaft ist. Man kann es z.B. anwenden, um einen gegebenen Graphen "schön zu zeichnen". Dabei berechnet man zuerst die kürzesten Wege zwischen allen Knotenpaaren, was eine Annäherung an eine Distanzmatrix sein sollte. Diese Matrix gibt man diesem iterativen Verfahren als Eingabe, und heraus kommt (oft) eine halbwegs übersichtliche Zeichnung des Graphen.

Die einfachere Methode hier ist natürlich, die Positionen der Pixel eine nach der anderen über Schnittpunkte von Kreisen zu berechnen. Aber das kann jemand anderes vorstellen, wenn er möchte. :D

Flamefire - So 27.12.09 12:11

---

Ich habe das ganze mittels der Abstände gelöst.
Wenn man die Abstände in die Summe aus 2 Quadratzahlen zerlegt (was manchmal nicht eindeutig ist, aber egal...Ist ja write only ^^) dann kommt man für jeden Punkt, von einem anderen ausgehend, auf 8 mögliche Punkte.
Demzufolge sah der Algo dann so aus:

- 1. Punkt in die Mitte setzen
- Für jeden Punkt:
-Berechne die 8 Möglichen Punkte in Abhängigkeit der Position der Punkte mit kleineren Index und bilde die Schnittmenge davon
-im Optimalfall kommt eine Lösung raus. sonst einfach die erste nehmen

Erklärung: der 1. Punkt ist egal, der gibt nur die Position an. Der 2. Punkt hat noch 8 Freiheitsgrade-->Rotation dadurch verändert
Der Rest ist mehr oder weniger eindeutig. Es war gut, immer nur die nächsten Punkte für die Entfernungsberechnung zu verwenden, da sich z.b. 5 nur in 5=1^2+2^2 zerlegen lässt. Wärend eine große Zahl da zu viel Spielraum hat.