Das-ist-das-Haus-vom-Ni-ko-laus

Entwickelt: 2001-11-21 / Aktualisiert: 2022-01-13

Dienstreise, ich saß abends gelangweilt im Hotel einer kleinen norddeutschen Stadt rum, ein (oder zwei - oder drei?) Bierchen hatte ich in der Hotelbar wohl auch schon vertilgt, da kam mir das Nikolaus-Haus in den Sinn.
Kennst Du das Spielchen? Ohne abzusetzen und ohne eine Linie mehr als einmal zu zeichnen (aber jede Linie muss gezeichnet werden - sonst ist das Haus ja instabil), muss das Haus vom Nikolaus entstehen - siehe rechts. Der Startpunkt kann frei gewählt werden.
Ich überlegte mir, wie viele Möglichkeiten es wohl dafür gibt. Im Prinzip handelt es sich um eine simple Variante des Vertreter- oder Postboten-Problems, nämlich ein Netz von Strecken abzulaufen, ohne eine auszulassen oder eine Strecke mehrmals latschen zu müssen.
Das Ergebnis ist hier zu bewundern. Es handelt sich um ein kleines C-Programm, das die Ergebnisse als Streckenplan ausgibt (also z. B.: D -> C -> B -> A -> C -> E -> D -> B -> E). Nein, ich verrate nicht, wieviele das sind ;-)

Das Programm arbeitet fast ausschließlich mit dynamisch allozierten Datenstrukturen und verketteten Listen - inklusive wildem Pointerschießen. Die Wegeprüfung erfolgt in einer rekursiv arbeitenden Funktion. Da hat bei mir offenbar der Ballmer Peak voll zugeschlagen ;-) Das war auch die Phase, in der ich sprechende Variablennamen für puren Luxus hielt: Solange die Buchstaben nicht alle sind, reicht einer. Immerhin habe ich ein paar Kommentare hinterlassen.
Übrigens: Wenn Du wissen willst, wie viele Wege es gibt, dann ruf das Programm wie folgt auf:
nikohaus | wc -l - die Wege links + rechts entlang werden übrigens separat gezählt, eine Route über B ist also eine andere als die spiegelverkehrte über C.

Installation: Archiv entpacken, dann kompilieren: gcc -o nikohaus nikohaus.c
oder einfach make nikohaus. Ich musste übrigens 2022 nur den #include <string.h> ergänzen, dann lief der Compile ohne Murren durch.

Download: nikohaus.tgz
sha256: 5fff2d4599deff9f63b1818251ca8d44cd71744baee7b85f3091800cd6059bf3