2.1.2.1 Kontrollierte Beleuchtungen für Bascetta-Sterne
Anekdote

Kontrollierte Beleuchtungen für Bascetta-Sterne

Ikosaeder-Netz mit 100 Klebepunkten

Bei den bunten Bascetta-Sternen muss man die Reihenfolge der Klebepunkte so wählen, dass die jeweilige Nachfolger-Farbe der Lichterkette auf einen Klebepunkt eines Dreiecks des Ikosaeders mit gleicher Nachfolger-Farbe führt. Dies ist anfangs in der Regel einfach, da man ausgehend vom aktuellen Klebepunkt ein Dreieck und Klebepunkt der Nachfolge-Farbe immer erreicht. Jedoch trifft man nach einiger Zeit immer wieder auf einen Klebepunkt, wo bereits eine LED verbaut ist. Zwar gibt es genügend weitere Klebepunkte der gleichen Farbe, die jedoch vom aktuellen Klebepunkt weit entfernt sind, meist mehr als 10 cm. Ich habe eine fünf-farbige Lichterkette mit 100 LEDs und einem Abstand der LEDs voneinander von nur 10 cm.

Was tun?

Zunächst macht man sich den Sachverhalt an einer Skizze klar. Auf einem Dreieck befinden sich bei einer Lichterkette mit 100 LEDs je fünf Klebepunkte.

Ikosaeder-Netz mit 100 Klebepunkten

Ikosaeder-Netz mit 100 Klebepunkten

Nun machen wir uns eine Tabelle mit den 100 Klebepunkten und zu jedem Klebepunkt eine Liste der erreichbaren Nachfolger. Diese Listen sind abhängig von der Größe des Sterns. Haben wir eine Reihenfolge für den größten Stern gefunden, kann man diese Reihenfolge auch für kleinere Sterne hernehmen. Unser größter Stern ist ein Stern, den man mit Modulen, die aus Quadraten der Kantenlänge 30 cm gefaltet sind, bauen kann. Betrachten wir beispielsweise das linke obere Dreieck (Magenta) und dort den Klebepunkt rechts unten. Als Nachfolge-Dreiecke kommen nur die grünen Dreiecke infrage und da die Dreiecke eine Kantenlänge von 12,43 cm haben offensichtlich nur das grüne Dreieck rechts daneben. Alle Klebepunkte der übrigen grünen Dreiecke sind zu weit entfernt. Auf dem benachbarten grünen Dreieck ist auch der Klebepunkt rechts unten zu weit entfernt, aber die anderen vier Klebepunkte sind erreichbar. Es ist sicher schon recht aufwändig, alle 100 Listen der erreichbaren Nachfolger aufzustellen, aber es ist einen Versuch wert. Als nächstes versuchen wir eine Reihenfolge intuitiv zu finden. Das ist meist besser, als alle Reihenfolgen durch einen Rechner überprüfen zu lassen (wir haben es hier mit ca. 10⁵⁸ Reihenfolgen zu tun). Bei den Versuchen stellt man rasch fest, dass man schnell mit bereits belegten Klebepunkten kollidiert und andere Klebepunkte niemals mehr erreichbar sind. Man ist also gut beraten, anfangs zu versuchen, nicht mehr erreichbare Klebepunkte zu vermeiden. Dies gelingt durchaus, aber es ist mir in der Regel nur gelungen ca. 80% der Lichterkette anzuordnen. Nach ein paar Wochen habe ich mich doch entschlossen diese Herausforderung dem Rechner zu überlassen. Nachdem das Programm fertig und fehlerfrei war, habe ich noch einmal überschlagen, dass, wenn man 1 Milliarde Rechner mit der Aufgabe betraut und jeder Rechner 1 Milliarde Überprüfungen pro Sekunde durchführen kann, das Weltall vorher untergegangen sein dürfte, bevor eine Lösung parat ist. Das geht also auch nicht. Aber ich habe dann die Liste der erreichbaren Nachfolger so abgewandelt, dass meine gefundenen 80% der Reihenfolge in den Listen der erreichbaren Nachfolger als erstes auftauchen und der Rechner diese 80% sofort findet und von dort aus alle weiteren Möglichkeiten probiert. Und was soll ich sagen? Der Rechner hat zwei Klebepunkte meiner 80% korrigiert und selbst im Debug - Modus nicht mehr als eine Sekunde gebraucht, um eine Lösung zu präsentieren. Ein Fall, wo Mensch und Maschine gemeinsam eine Lösung finden.