geknac’t: Der c’t-NerdCube
Unsere Knobelaufgabe – ein Zauberwürfel mit Abkürzungen aus der IT-Welt – hat so manchen c’t-Leser beschäftigt. Nun ist es an der Zeit, die Auflösung zu verraten und zu zeigen, wie man so etwas programmiert.
- Dr. Harald Bögeholz
Eigentlich sollte der NerdCube dazu anregen, ihn per Computer zu lösen, aber ich hatte die Aufgabe bewusst so gestaltet, dass es auch ohne Computer geht. Und so haben nur 10 der insgesamt 59 Einsender etwas programmiert, die anderen 49 haben den Würfel von Hand gelöst – entweder nur mit Papier und Bleistift oder unter Zuhilfenahme verschiedener Basteleien.
Der NerdCube ist im Prinzip ein klassischer Rubik’s Cube, aber mit Buchstaben statt Farben. Im gelösten Zustand zeigt jede Seite senkrecht und waagerecht Abkürzungen aus der IT-Welt. Der verdrehte Würfel wurde im c’t-Artikel vertrac’t – Knobelaufgabe: Der c’t-NerdCube veröffentlicht und die Liste seiner Bezwinger auf der Projektseite zum NerdCube.
Hier ist nun also die Lösung, zu sehen in den nebenstehenden Bildern. Wer jetzt noch das Bedürfnis verspürt, sich einen NerdCube zu basteln, hat es leichter: Die Datei NerdCube-solved.pdf enthält das Gitternetz im gelösten Zustand zum Ausdrucken, Ausschneiden und Aufkleben.
Lösungsansätze
Egal ob per Computer oder von Hand: Zwei Lösungsansätze sind den NerdCube-Bezwingern eingefallen. Zauberwürfel-Kenner haben sich einfach einen Würfel mit den Buchstaben beklebt oder beschriftet und sich dann mit den aus den 80er-Jahren bekannten Lösungsverfahren Schicht für Schicht durchgearbeitet. Wenn man mit dem c’t-Kreuz auf der Oberseite beginnt, steht dadurch die Orientierung der Buchstaben auf den benachbarten Seiten schon fest, sodass man passende Ecken suchen kann und so weiter.
Aber es ist gar nicht nötig, den Zauberwürfel zu beherrschen, um die NerdCube-Aufgabe zu lösen. Der zweite Ansatz läuft darauf hinaus, den Würfel in seine Einzelklötzchen zu zerlegen und ihn dann Schritt für Schritt wieder zusammenzusetzen. Ob dies rein im Kopf mit Papier und Bleistift, durch gebastelte Papierecken, mit Holzwürfelchen oder per Computer geschieht, läuft dabei auf dasselbe hinaus – all diese Varianten waren bei den Einsendungen dabei.
NerdCube-Lösungen ohne Computer (38 Bilder)
(Bild: Friedhelm Hoerner)
Ich selber habe natürlich beim Entwickeln des Puzzles auch ein Lösungsprogramm geschrieben, das der Einfachheit halber den zweiten Ansatz verfolgt: zertrümmern und neu zusammensetzen. Das geht natürlich nicht völlig beliebig, sondern man muss sich schon ein wenig um die Mechanik des Würfels kümmern.
Würfelmechanik
Man darf die Flächen mit den Buchstaben nicht isoliert betrachten, sondern muss beachten, dass sie auf kleinen Würfeln angebracht sind. Davon gibt es drei Sorten, die ich Ecken, Kanten und Mitten nenne: Ecken tragen drei Buchstaben, Kanten zwei und Mitten nur einen.
Das Kreuz bestehend aus den sechs Mitten steht im Prinzip fest: Die Mittenflächen kann man zwar drehen, aber die relative Lage der sechs Buchstaben zueinander bleibt. Eine Ecke kann man durch Drehen der sechs Seiten an jede der acht Eckpositionen bringen, eine Kante an jede der zwölf Kantenpositionen.
Die Orientierung der Buchstaben lässt sich dabei aber nicht beliebig verändern, sondern sie folgt einem festen Muster: Wenn ein Buchstabe aufrecht in der linken oberen Ecke einer Würfelseite steht, dann behält er diese Eigenschaft bei beliebiger Verdrehung des Würfels bei. Das heißt: Schaut man auf die Seite mit dem betreffenden Buchstaben und hält sie so, dass der Buchstabe aufrecht steht, dann ist er wieder oben links. Auf dem Würfelgitter sieht das so aus:
Wenn man den Würfel nun virtuell zertrümmert, sei es auf Papier oder im Computer, dann muss man beim Zusammensetzen der Einzelwürfelchen die relative Orientierung der Buchstaben zueinander gemäß dieser mechanischen Gegebenheiten beachten.
Ein Lösungsprogramm
Ich habe mein Lösungsprogramm in meiner Lieblings-Sprache Haskell entwickelt. Das ist eine rein funktionale Programmiersprache und der Anblick dürfte für viele ungewohnt sein. Aber auch wenn Sie die folgenden Code-Zeilen nicht verstehen, hoffe ich doch, dass die Grundidee des Lösungsverfahrens rüberkommt. Eine kleine Einführung in Haskell gibt der c’t-Artikel Kunst mit Funktion – Slitherlink-Puzzles lösen in Haskell in c’t 23/12, S. 182.
Um das Problem im Computer zu repräsentieren, wollte ich nicht mit dreidimensionalen Koordinaten hantieren, sondern ich betrachte alles auf dem flach ausgebreiteten Würfelgitter. Das Zertrümmern und wieder Zusammensetzen des Würfels kann man sich dann so vorstellen, dass man die Aufkleber mit den Buchstaben vom Würfelgitter abpult und an anderer Stelle wieder aufklebt, wobei man aber die mechanischen Eigenschaften des Zauberwürfels beachten muss.
Am Beginn eines Lösungsprogramms stehen die Datenstrukturen, für die man sich in Haskell zunächst die pasenden Datentypen definiert. Da wäre zunächst einmal die Orientierung eines Buchstabens:
data Orientation = Upright | TurnedLeft | TurnedRight | UpsideDown
| UpDown | LeftRight | Any | Invalid deriving (Eq, Ord, Enum)
C-Programmierer können sich hier eine Art enum vorstellen: Eine Variable vom Typ Orientation kann genau die hier aufgezählten Werte annehmen. Neben den vier offensichtlichen Ausrichtungen eines Buchstabens gibt es noch die "unsicheren" Orientierungen für symmetrische Buchstaben wie I, denen man die genaue Orientierung nicht ansieht: UpDown bedeutet aufrecht, aber vielleicht auf dem Kopf (also Upright oder UpsideDown), LeftRight steht für TurnedLeft oder TurnedRight.
Dinge drehen
Im Laufe des Lösens wird man Buchstaben drehen müssen, also eine Orientierung in eine andere überführen. Also müssen Hilfsfunktionen dafür her. Als Erstes ein Datentyp für eine solche Funktion:
type Xform = Orientation -> Orientation
Und dann eine Funktion namens turnLeft, die einen Buchstaben um 90 Grad nach links dreht:
turnLeft :: Xform
turnLeft Upright = TurnedLeft
turnLeft TurnedLeft = UpsideDown
turnLeft UpsideDown = TurnedRight
turnLeft TurnedRight = Upright
turnLeft UpDown = LeftRight
turnLeft LeftRight = UpDown
turnLeft x = x
Die erste Zeile deklariert den Typ der Funktion: Das :: kann man lesen als "ist ein" oder "hat den Typ". Die übrigen Zeilen definieren, was die Funktion für alle möglichen Eingabewerte liefern soll. Für turnLeft ist das noch etwas mühsam, aber die anderen Funktionen erfordern schon weniger Tipp-Arbeit, weil man sie mit turnLeft ausdrücken kann:
turnAround :: Xform
turnAround = turnLeft . turnLeft
inverse :: Xform -> Xform
inverse f = f . f . f
turnRight :: Xform
turnRight = inverse turnLeft
Auf den Kopf stellen ist zweimal nach links drehen. Der Operator . verkettet zwei Funktionen. Die Schreibweise erinnert an die mathematische Notation, wo man statt des Punktes einen kleinen Kreis schreibt: f . g liest man "f nach g", es wird also zuerst die Funktion g und dann die Funktion f angewandt. Die Umkehrung einer Transformation inverse kann man später noch gebrauchen; man erhält sie, indem man die Transformation einfach dreimal ausführt. Nach rechts drehen ist dann die Umkehrung von nach links drehen.
Würfel durchnummerieren
Als Nächstes geht es darum, zu beschreiben, welche Flächen auf dem Würfel zu Klötzchen zusammengehören. Dazu habe ich erst einmal alle Flächen auf dem Würfelgitter durchnummeriert:
Ein Würfelchen besteht nun aus zwei oder drei Flächen (Kante beziehungsweise Ecke). Zusätzlich zu den Nummern der Flächen braucht das Programm die Information, wie herum ein Buchstabe gedreht würde, wenn man ihn auf die entsprechende Fläche rangierte. Ein aufrecht stehendes E auf der Eckfläche 13 würde, wenn man das Klötzchen drehen würde, auf der Eckfläche 7 nach links gedreht zu liegen kommen, auf der Eckfläche 12 dagegen nach rechts gedreht (all diese Angaben immer bezogen auf das ausgebreitete Würfelgitter). Ähnliches gilt beispielsweise für das Kantenklötzchen aus den Flächen 14 und 8:
Im Haskell-Code definiere ich zunächst einen Datentyp für die Flächen, die zu einem Würfelchen gehören:
type CubeLocation = [(Int, Xform)]
Das ist eine Liste von Paaren aus Flächennummer und zugehöriger Transformation. Die oben abgebildete Ecke sieht dann in Haskell so aus:
[(13, id), (7, turnLeft), (12, turnRight)]
Und die Kante so:
[(14, id), (8, turnAround)]
Die in Haskell vordefinierte Funktion id ist dabei die Identität im mathematischen Sinne: id x ist einfach x für jedes erdenkliche x. Angewandt auf eine Orientation ergibt sie dieselbe Orientation.
Aufklebe-Anleitung
Was kann man nun mit einer solchen Zeile anfangen? Sie lässt sich als Anleitung interpretieren, wie man Aufkleber mit Buchstaben auf dem Würfel anbringt. Beispiel: Ein nach links gekipptes A, ein nach rechts gekipptes R und ein nach rechts gekipptes P würden gemäß Anleitung [(13, id), (7, turnLeft), (12, turnRight)] wie folgt auf dem Würfel landen:
Wenn man nun diese drei Buchstaben einfach durchrotiert, also in der Reihenfolge RPA abarbeitet, dann klebt dieselbe Anleitung die Buchstaben in korrekter Orientierung so auf das Eckwürfelchen, als hätte man es gekippt:
Die Anleitung (aka CubeLocation) für ein anderes Eckwürfelchen lautet
[(15, turnRight), (16, id), (9, turnAround)]
Wendet man diese Anleitung auf dieselben drei Buchstaben ARP an, dann landen sie in korrekter Orientierung an einer anderen Ecke, so als hätte man die Oberseite des Würfels um die Mittelfläche 23 um 90 Grad im Uhrzeigersinn gedreht:
Hier die vollständige Liste der Klötzchen:
cubeLocations :: [CubeLocation]
cubeLocations = [ [(2, id), (53, turnAround)]
, [(4, turnLeft), (11, id)]
, [(6, turnRight), (17, id)]
, [(14, id), (8, turnAround)]
, [(19, turnLeft), (49, turnLeft)]
, [(22, turnLeft), (21, turnRight)]
, [(24, turnRight), (25, turnLeft)]
, [(27, turnRight), (51, turnRight)]
, [(29, turnAround), (40, turnLeft)]
, [(32, turnAround), (38, id)]
, [(35, turnAround), (42, turnRight)]
, [(44, turnAround), (47, id)]
, [(13, id), (7, turnLeft), (12, turnRight)]
, [(15, turnRight), (16, id), (9, turnAround)]
, [(31, turnLeft), (30, turnAround), (37, id)]
, [(33, turnAround), (39, turnRight), (34, turnLeft)]
, [(46, id), (43, turnLeft), (28, turnLeft)]
, [(48, turnRight), (36, turnAround), (45, turnAround)]
, [(54, turnAround), (3, turnRight), (18, turnRight)]
, [(52, turnLeft), (10, id), (1, id)]
]
In dieser Liste steckt alles nötige Wissen um die Mechanik des Würfels: Welche Flächen zu Klötzchen zusammengehören und wie die Orientierungen der Buchstaben sich beim Verdrehen des Würfels verändern.
Nun gehts an die Datentypen für die Repräsentation einer konkreten Beschriftung des Würfels. Ein Aufkleber Label ist ein Buchstabe und eine Orientierung (und noch eine Id, auf deren Bedeutung ich hier nicht eingehe):
data Label = Label { lChar :: Char
, lOrientation :: Orientation
, lId :: Int }
| Blank
C-Programmierer mögen hier an ein struct mit drei Feldern denken, wobei eine Variable vom Typ Label alternativ auch den Wert Blank annehmen kann. Ein Klötzchen (Piece) besteht dann einfach aus einer Liste von Aufklebern ([Label]) und der ganze Würfel (Cube) lässt sich als eindimensionales Array beschreiben, das jeder Feldnummer ein Label zuordnet:
type Piece = [Label]
type Cube = Array Int Label
Der grobe Ablauf des Lösungsalgorithmus ist nun der folgende:
- Einlesen des verdrehten Würfels aus einer Datei (ergibt einen
Cube) - Zerlegen in Einzelklötzchen (beziehungsweise Abpulen der Aufkleber, wenn man sich das so vorstellen will)
- Alle Möglichkeiten durchprobieren, wie sich die Klötzchen wieder zu einem Würfel zusammensetzen lassen, sodass auf jeder Seite alle Buchstaben dieselbe Orientierung haben
Aufkleber abpulen
Der Code fürs Einlesen ist langweilig und soll hier verschwiegen werden. Für das Zerlegen in Einzelklötzchen kommt die oben beschriebene Liste CubeLocations zum Einsatz mit den Anleitungen, wie Aufkleber auf dem Würfelgitter anzubringen sind. Achtung: Beim Abziehen der Aufkleber muss man mit den Orientierungen der Buchstaben die umkehrten Transformationen durchführen wie beim Aufkleben. Um das obige Beispiel noch einmal aufzugreifen: Die Anleitung [(13, id), (7, turnLeft), (12, turnRight)] umgedreht bewirkt:
Erst einmal eine Hilfsfunktion: rotate wendet eine Transformation auf ein Label an, indem sie sie auf die Orientation-Komponente anwendet. Ein unbeschriftetes Label (Blank) bleibt von jeder Transformation unberührt.
rotate :: Xform -> Label -> Label
rotate f (Label c o i) = Label c (f o) i
rotate _ Blank = Blank
Die Buchstaben eines Klötzchens abpulen geht so: Man nehme die Anleitung für ein Klötzchen (CubeLocation), hole für jedes erwähnte Feld den Buchstaben vom Würfel und drehe ihn anders herum, als es in der Anleitung steht:
readPiece :: Cube -> CubeLocation -> Piece
readPiece cube faces = map rp faces
where rp (i, f) = rotate (inverse f) (cube!i)
Ein typisch funktionales Konstrukt ist die Funktion map: Sie wendet die hier ad hoc definierte Funktion rp auf eine Liste an und liefert eine Liste der Ergebnisse. readPiece jetzt einfach auf die ganze Liste cubeLocations angewandt ergibt eine Liste aller Klötzchen:
cube2pieces :: Cube -> [Piece]
cube2pieces cube = map (readPiece cube) cubeLocations
Damit lässt sich das Einlesen und Zertrümmern des Würfels wie folgt formulieren:
readPuzzle :: String -> Puzzle
readPuzzle s = Puzzle centerCube pieces
where cube = readCube s
pieces = cube2pieces cube
centerCube = listArray (1,54) (replicate 54 Blank)
// map centerFace centers
centerFace i = (i, rotate (const Any) (cube!i))
Hier stecken noch ein paar nicht erwähnte Funktionen und Variablen drin; es mag vielleicht als ungefähre Erklärung genügen, dass die Funktion einen leeren Würfel hernimmt und dann aus der Eingabedatei nur die Mittelbuchstaben jeder der sechs Würfelflächen übernimmt und dabei deren Orientierung auf Any setzt. Das Ergebnis ist das zu lösende Puzzle, wobei ich diesen Datentyp noch schuldig bin. Ein (teilweise gelöstes) Puzzle setzt sich zusammen aus einem (teilweise beschrifteten) Cube und einer Liste der noch nicht verwendeten Klötzchen:
data Puzzle = Puzzle { pCube :: Cube
, pUnused :: [Piece]
} deriving (Show)
So sieht die Ausgabe von readPuzzle aus, wenn man die Funktion auf den Inhalt der Datei nerdcube_scrambled.cube anwendet, die den verdrehten NerdCube aus der Aufgabenstellung enthält (zur Erinnerung rechts noch mal das Bild):
Puzzle {pCube = array (1,54) [(1,. ),(2,. ),(3,. ),(4,. ),(5,O ),(6,. ),(7,. ),(8,. ),(9,. ),(10,. ),(11,. ),(12,. ),(13,. ),(14,. ),(15,. ),(16,. ),(17,. ),(18,. ),(19,. ),(20,S ),(21,. ),(22,. ),(23,' ),(24,. ),(25,. ),(26,P ),(27,. ),(28,. ),(29,. ),(30,. ),(31,. ),(32,. ),(33,. ),(34,. ),(35,. ),(36,. ),(37,. ),(38,. ),(39,. ),(40,. ),(41,I ),(42,. ),(43,. ),(44,. ),(45,. ),(46,. ),(47,. ),(48,. ),(49,. ),(50,O ),(51,. ),(52,. ),(53,. ),(54,. )], pUnused = [[E^,Vv],[E^,C^],[Tv,D<],[D>,T<],[M^,I|],[P>,P>],[S-,S-],[Mv,P>],[T<,D^],[Fv,P<],[S|,C>],[C>,Cv],[C>,R^,P>],[Pv,I-,D>],[Dv,P^,Fv],[I|,O|,X-],[R>,P>,A<],[S|,O-,S|],[F<,H|,T<],[I|,S|,C>]]}
Würfel zusammenpuzzeln
Jetzt müssen die Klötzchen wieder zum Würfel zusammengefügt werden oder, in der anderen Bildsprache ausgedrückt, die Aufkleber wieder auf dem Würfelgitter angebracht werden, und zwar auf alle erdenklichen Arten, bei denen alle Buchstaben auf jeder Würfelseite die gleiche Orientierung haben.
Zunächst eine kleine Hilfsfunktion, die zwei Orientierungen miteinander in Einklang bringt. Zur Erinnerung: Der Datentyp Orientation enthält neben den vier konkreten Orientierungen Upright, TurnedLeft, TurnedRight und UpsideDown auch "unentschlossene" wie LeftRight für nach links oder rechts gekippt oder Any für irgendeine Orientierung. Wenn sich zu einem Buchstaben, der noch nicht recht weiß, ob er nach links oder nach rechts gekippt ist (LeftRight), einer hinzugesellen möchte, der TurnedLeft ist, dann ist das Ergebnis TurnedLeft. Einer, der aufrecht steht, wäre damit aber nicht vereinbar; das Ergebnis wäre Invalid. Ich habe die Funktion aus einer Laune heraus als Operator ><< geschrieben; in Haskell kann man jede beliebige Folge von Symbolen mal eben so als Infix-Operator benutzen. Die Definition zählt einfach alle möglichen Fälle auf, wobei zu beachten ist, dass Haskell die Regeln von oben nach unten prüft und die jeweils erste passende Gleichung den Funktionswert definiert:
(><<) :: Orientation -> Orientation -> Orientation
Any ><< x = x
x ><< Any = x
LeftRight ><< TurnedLeft = TurnedLeft
TurnedLeft ><< LeftRight = TurnedLeft
LeftRight ><< TurnedRight = TurnedRight
TurnedRight ><< LeftRight = TurnedRight
UpDown ><< Upright = Upright
Upright ><< UpDown = Upright
UpDown ><< UpsideDown = UpsideDown
UpsideDown ><< UpDown = UpsideDown
x ><< y
| x == y = x
| otherwise = Invalid
Die letzte Regel sagt dabei: Wenn keine der zuvor genannten Spezialisierungen der Orientierung vorliegt, dann müssen die beiden Orientierungen übereinstimmen, andernfalls sind sie unvereinbar (Invalid).
Nun gehts ans Anbringen eines einzelnen Aufklebers. Die Funktion fillFace braucht dazu einen Würfel (Cube), Ort und Transformation ((Int, Xform)) sowie den Aufkleber (Label) und liefert eine Liste aller Möglichkeiten, wie dieser Aufkleber in dieser Orientierung auf dem Würfel angebracht werden kann. Klingt hochtrabend, aber es gibt für diese Liste nur zwei Möglichkeiten: Wenn der Aufkleber in der gewünschten Orientierung mit den übrigen bereits auf derselben Seite angebrachten Aufklebern harmoniert, enthält die Liste den erfolgreich beklebten Würfel, sonst ist sie leer.
Um zu schauen, ob die Orientierung des anzubringenden Aufklebers passt, versucht die Funktion fillFace sie über den soeben definierten Operator ><< mit der Orientierung des Aufklebers in der Mitte der entsprechenden Würfelseite in Einklang zu bringen. (Die hier nicht gezeigte Funktion center liefert zu einer Flächennummer i die Nummer der Mittelfläche derselben Würfelseite.)
fillFace :: Cube -> ((Int, Xform), Label) -> [Cube]
fillFace cube ((i, f), l) =
if faceOrientation /= Invalid
then [cube // [(i, l'), (j, rotate (const faceOrientation) cl)]]
else []
where l' = rotate f l
j = center i
cl = cube ! j
faceOrientation = lOrientation cl ><< lOrientation l'
Hiermit lässt sich nun fillLocation formulieren, eine Funktion, die zu einem teilweise beklebten Würfel (Puzzle) und einer Aufklebeanleitung für ein Klötzchen (CubeLocation) alle Möglichkeiten liefert, dieses Klötzchen mit einem noch nicht verwendeten Satz von Aufklebern zu bekleben. Das Ergebnis ist wieder eine Liste von Puzzles ([Puzzle]).
fillLocation :: Puzzle -> CubeLocation -> [Puzzle]
fillLocation (Puzzle cube pieces) loc =
[Puzzle cube' pieces' | (piece, pieces') <- takeOne pieces
, length piece == length loc
, piece' <- shifts piece
, cube' <- foldM fillFace cube (zip loc piece')
]
Ja, das ist tatsächlich schon alles, wobei ich die beiden kleinen Hilfsfunktionen takeOne und shifts nicht weiter ausführe. Die hier verwendete Haskell-Notation für sogenannte List Comprehensions erinnert an die mathematische Notation für die Definition von Mengen und besagt: Das Ergebnis ist eine Liste aller Puzzle cube' pieces', wobei
(piece, pieces')alle Möglichkeiten durchläuft, aus der Listepiecesein Teilpieceherauszunehmen und die Listepieces'übrig zu behalten- der ausgewählte Satz Aufkleber (
piece) genauso viele Aufkleber enthält, wie die Aufklebeanleitunglocangibt piece'alle Möglichkeiten durchläuft, wie man die Aufkleber auspiecein eine andere Reihenfolge rotieren kann-
cube'alle Möglichkeiten durchläuft, die Aufkleber gemäß Anleitung konfliktfrei anzubringen (das ist eine oder keine).
Wenn man weiß, wie man ein Klötzchen beschriftet, dann ist die Lösung schließlich nur noch ein Einzeiler: Man beschrifte alle Klötzchen:
solve :: Puzzle -> [Puzzle]
solve puzzle = foldM fillLocation puzzle cubeLocations
Die Haskell-Funktion foldM kam oben schon einmal unauffällig vor. Sie mutet vermutlich ziemlich magisch an, aber das M steht nicht für Magie, sondern für Monade. Das ist ein sehr abstraktes Konzept, das anderswo ganze Buchkapitel füllt. Hier mag als Erklärung genügen, dass foldM den Schritt fillLocation, der ein Klötzchen beschriftet, der Reihe nach für alle cubeLocations anwendet, wobei es alle Kombinationen durchspielt – jeder Aufruf von fillLocation macht ja aus einem Puzzle eine ganze Liste von Puzzle, jedes davon muss wieder den nächsten Schritt durchlaufen und so weiter. Irgendwie steht das M wohl doch ein bisschen für Magie.
3072 Würfel – 4 plausible – 1 richtiger
Für den NerdCube liefert die Funktion solve nach ein paar Sekunden Rechenzeit eine Liste mit 3072 zusammengepuzzelten Würfeln. Die meisten davon sind allerdings noch keine wirklichen NerdCube-Lösungen, weil die Bedingung noch nicht berücksichtigt ist, dass auf der Oberseite senkrecht und waagerecht jeweils C’T stehen muss. Wenn man die Lösungen danach filtert, bleiben noch 16 übrig, unter denen es aber nur vier verschiedene gibt, die jeweils vierfach auftauchen.
Der Grund dafür ist leicht erklärt: Es gibt zwei symmetrische Kantenklötzchen, mit einem scharfen Blick in die oben ausgegebene Klötzchenliste zu erkennen als [P>,P>],[S-,S-]. Der Algorithmus merkt das nicht und betrachtet die Lösungen als verschieden, die entstehen, wenn man keines, eines oder beide dieser Klötzchen kippt. Unter den dann übrig bleibenden vier Lösungen erkennt man schließlich die richtige anhand der plausibelsten Abkürzungen.
Es wäre natürlich effizienter gewesen, von vornherein mit den Buchstaben C’T auf der Oberseite zu beginnen, statt erst Tausende von Lösungen zu berechnen und dann einen Großteil davon wegzuwerfen. Ich habe aber so herum angefangen, weil ich in der Entwicklungsphase der Aufgabe ein Gefühl für die Komplexität des Problems bekommen wollte.
Downloads und Links
Wenn Sie den Code genauer studieren oder damit herumspielen wollen: Das vollständige Programm steht auf GitHub zum Download bereit. Es wurde mit Haskell for Mac entwickelt, sollte sich aber auch mit dem ganz normalen Haskell-Compiler ghc und auch unter anderen Betriebssystemen übersetzen lassen.
- Quelltext-Repository auf GitHub
- c’t-Artikel über Haskell for Mac
- Haskell for Mac im Mac App Store
- Haskell-Website mit kostenlosem Compiler
- Einführung in Haskell (englisch): Learn You a Haskell for Great Good
(bo)
