Überfahrt ohne Zwischenfall (Linux-Magazin, Januar 2020)

Ob es Missionare und Kannibalen sind [3], die einander nicht an den Kragen dürfen, während der Fährmann übersetzt, oder beim klassischen Flussüberquerungsrätsel [2] Wolf, Ziege und Kohlkopf: die Lösung dieser Denksportaufgaben finden Kopfrechner durch Ausprobieren. Computer ermitteln sie hingegen mittels Bäumen von verketteten Zustandsfolgen, an einem derer Äste sich schließlich irgendwann der gewünschte Endzustand findet. Bei der Überquerung des Flusses befinden sich anfänglich Fährmann, Wolf, Ziege und Kohlkopf am Westufer, und der Fährmann kann jeweils einen der dreien mit ins Boot nehmen und ans Ostufer übersetzen. Während der Überfahrt muss er sicherstellen, dass er Wolf und Ziege nicht allein am Ufer zurücklässt, weil der Wolf die Ziege fressen würde. Das gleiche gilt für Ziege und Kohlkopf, weil die Ziege sich über den Kohlkopf hermachen würde.

Abbildung 1: Wie bringt der Fährmann Wolf, Ziege und Kohlkopf wohlbehalten ans andere Ufer? Quelle: Wikipedia

Das Rätsel scheint auf den ersten Blick unlösbar, denn wenn der Fährmann die Ziege übergesetzt hat und leer zurückgeschippert ist, hat er nur die Wahl zwischen dem Wolf und dem Kohlkopf als nächsten Kandidaten, von denen sich keiner am anderen Ufer mit der Ziege vertragen würde. Der Trick besteht nun darin, dass der Fährmann auf der Rückfahrt ebenfalls Passagiere befördern kann, und so sicherstellt, dass er niemals eine gefährliche Kombination (Ziege/Kohlkopf bzw. Wolf/Ziege) unbeaufsichtigt zurücklässt.

Fähren-Algorithmus

Um das Problem mit einem Algorithmus zu knacken, muss es dieser als Modell von Zuständen abbilden, die jeweils die Kandidaten entweder dem West- oder dem Ostufer zuweisen. Zu anfangs sitzen Fährmann, Wolf, Ziege und Kohlkopf alle am Westufer, das Ostufer ist leer. Im zweiten Zustand in Abbildung 2 sitzt die Ziege am Ostufer, und am Westufer sitzen Wolf, Kohlkopf, sowie der Fährmann, sobald er von seiner Rückreise angelegt hat. Jeder Zustand bietet also die beiden Ufer ab, wobei jedes Ufer eine Reihe von Kandidaten beherbergt. Von einem gegebenen Zustand aus kann das System in ein oder mehrere Folgezustände weiterwechseln, von denen manche illegal sind (weil zum Beispiel Wolf und Ziege unbeaufsichtigt am selben Ufer wären), und manche legal. Ausgehend vom Anfangszustand wird der Algorithmus der Reihe nach alle möglichen Folgezustände durchprobieren, ermitteln, ob sie legal sind, und falls ja, von diesen ausgehend weitere Folgezustände heimzusuchen. So setzt sich der Reigen fort, und findet sich das Programm irgendwann in einem Zustand wieder, bei dem auf einmal alle Kandidaten am Ostufer sitzen, ist der Kas gebissen und es kann den Pfad des mitprotokollierten Suchlaufs dem verblüfften User als Lösungsschritte ausgeben.

Abbildung 2: Der Fährmann hat die Ziege übergesetzt und fährt leer zurück, um den Wolf abzuholen.

Tiefgang oder Oberflächlich

Im Diagramm in Abbildung 3 startet das Programm im Zustand ganz oben, bei dem alle Teilnehmer (W=Wolf, G=Goat, C=Cabbage, F=Ferryman) im linken Teil des Rechtecks, also am Westufer liegen. Schreitet der Algorithmus dann nach links unten, findet es einen Zustand, bei dem Kohlkopf und Fährmann am rechten Ufer sitzen, aber am linken Ufer befinden sich Wolf und Ziege, aber das ist nach den Regeln illegal, also sortiert der Algorithmus diesen Zustand aus (im Diagramm mit einem roten X) und wird in dieser Sackgasse naturgemäß auch keine Folgezustände anfahren. Beim Abfahren der Zustände in dieser Baumstruktur bieten sich zwei Verfahren an: Breadth-first ("Breite zuerst") und Depth-First ("Tiefe zuerst"). Breadth-First fährt erst einmal alle direkten Folgezustände eines Zustands an, bevor es tiefer zu deren Nachfolgern vordringt, während Depth-First so tief bohrt wie es nur geht und Kinder und Kindeskinder aufsucht bevor es Brüdern auf gleicher Höhe einen Besuch abstattet. Im vorliegenden Flußüberquerungsrätsel geht es darum, eine Lösung mit möglichst wenig Schritten zu ermitteln, also ist Breadth-First der richtige Ansatz, während Depth-First womöglich erst auf eine viel zu umständliche Lösung stoßen würde.

Abbildung 3: Der Algorithmus wandert vom Ausgangszustand (oben) alle möglichen Folgezustände ab und sortiert illegale Zustände aus.

Damit steht das Rüstzeug für den Algorithmus fest und die Programmierung kann beginnen. Der Übersichtlichkeit halber wurde der Code in fünf Listings strukturiert, wer gleich losballern möchte, kann den Problemlöser gleich mit

    $ go build solver.go passenger.go sort.go \
      sort.go shore.go state.go
    $ ./solver

starten, weil er ohne jegliche Zusatzmodule läuft, also mit reinem Go auskommt. Die Passagiere und den Fährmann modelliert Listing 1 mit mittels const definierten Integerwerten. Die Zuweisung =iota instruiert den Compiler, den Konstanten Goat, Wolf, und so weiter die Integerwerte 0, 1, ... zuzuweisen. Damit sich diese nachher zur Unterhaltung des Users wieder in Textstrings verwandeln lassen, definiert die Methode String() auf den Typ Passenger ein Slice mit Strings, in das der Integerwert der Konstante (praktischerweise ab 0 genau wie die Indexnummern im Slice) genau an der richtigen Stelle hineingreift. Generell dient eine String()-Methode in Go dazu, selbstdefinierte Typen in Strings umzuwandeln, sobald diese sich in einem String-Kontext wiederfinden, zum Beispiel wenn Printf() sie mit "%s" als Strings ausgeben möchte.

Listing 1: passenger.go

    01 package main
    02 
    03 type Passenger int
    04 
    05 const (
    06   Goat Passenger = iota
    07   Wolf
    08   Cabbage
    09   Ferryman
    10 )
    11 
    12 func (p Passenger) String() string {
    13   return []string{"Goat", "Wolf",
    14     "Cabbage", "Ferryman"}[p]
    15 }

Weiter geht's mit Listing 2, das mit Shore eine Datenstruktur für die Darstellung einer Uferseite samt zugehöriger Methoden definiert. Die wartenden Passagiere speichert das Array passengers innerhalb der Shore-Struktur ab Zeile 8. Alle Elemente sind vom Typ Passenger, nehmen also die in Listing 1 definierten Integerwerte an und werden auch in Listing 2 mit den zugehörigen Konstanten (z.B. "Wolf") referenziert, da beide Listings im Package main stehen.

Tiefe Kopien

Generell bietet Go keine Möglichkeit, eine verschachtelte Struktur vollständig zu kopieren. Um eine "Deep Copy" anzulegen, muss der Programmierer selbst Hand anlegen und zum Beispiel in einer Struktur liegende Arrays explizit kopieren. Die Methode Copy() ab Zeile 17 in Listing 2 wirkt auf einem vorgegebenen Shore-Objekt, initialisiert ein neues, noch leeres, allokiert mit make einen passenger-Array gleicher Länge, kopiert alsdann mit der in Go eingebauten copy()-Funktion die Elemente des Originals in die Kopie, und gibt letztere an den Aufrufer zurück. So kann dieser einfach Spielzustände duplizieren und nächste Schritte durch graduelle Veränderungen einleiten.

Listing 2: shore.go

    01 package main
    02 
    03 import (
    04   "fmt"
    05   "sort"
    06 )
    07 
    08 type Shore struct {
    09   passengers []Passenger
    10 }
    11 
    12 func (s Shore) String() string {
    13   sort.Sort(Passengers(s.passengers))
    14   return fmt.Sprintf("%s", s.passengers)
    15 }
    16 
    17 func (s Shore) Copy() Shore {
    18   c := Shore{}
    19   c.passengers = make([]Passenger,
    20     len(s.passengers))
    21   copy(c.passengers, s.passengers)
    22   return c
    23 }
    24 
    25 func (s *Shore) Add(p Passenger) {
    26   s.passengers = append(s.passengers, p)
    27 }
    28 
    29 func (s *Shore) Remove(p Passenger) {
    30   result := []Passenger{}
    31   for _, passenger := range s.passengers {
    32     if passenger != p {
    33       result = append(result, passenger)
    34     }
    35   }
    36   s.passengers = result
    37 }
    38 
    39 func (s *Shore) Move(p Passenger,
    40                      t *Shore) {
    41   s.Remove(p)
    42   t.Add(p)
    43 }
    44 
    45 func (s Shore) Has(p Passenger) bool {
    46   for _, passenger := range s.passengers {
    47     if passenger == p {
    48       return true
    49     }
    50   }
    51   return false
    52 }
    53 
    54 func (s Shore) IsValid() bool {
    55   if s.Has(Ferryman) {
    56     return true
    57   }
    58   if s.Has(Wolf) && s.Has(Goat) {
    59     return false
    60   }
    61   if s.Has(Goat) && s.Has(Cabbage) {
    62     return false
    63   }
    64   return true
    65 }

Um einer Uferseite neue Passagiere zuzuordnen, sie wieder abzuziehen, einer neuen Uferseite zuzuweisen, oder abzufragen, ob ein Passagier am vorliegenden Ufer stationiert ist, dienen die Methoden Add(), Remove(), Move() und Has() in den Zeilen 25 bis 52 in Listing 2. So kann zum Beispiel ein Zustandsobjekt später eine seiner Uferseiten auswählen und mit west.Has(Wolf) eine Boolsche Antwort (true/false) auf die Frage erhalten, ob der Wolf anwesend ist. Hier zeigt sich ein Nachteil der als Array gewählten Datenstruktur zum Speichern der Passagiere: Um zu sehen, ob ein bestimmter Passagier anwesend ist, muss eine For-Schleife alle Elemente abfahren, bis sie ihn findet, oder bei einer erfolglosen Suche am Ende false zurückgeben. Das Entfernen eines Passagiers reißt gar ein Loch in den Array, den eine For-Schleife dann umständlich wieder zusammenflicken muss, indem sie ihn ab Zeile 31 kurzerhand ohne den entfernten Passagier wieder aufbaut. Eine Map böte performantere Zugriffe, hat aber den Nachteil, dass die in ihr gelagerten Daten unsortiert vorliegen, und zu Displayzwecken sortiert werden müssten.

Ob die auf einer Uferseite anwesenden Passagiere den Regeln des Spiels widersprechen, prüft die Methode IsValid() ab Zeile 54. Sie implementiert die "Business Logic" des Verfahrens. Ist zum Beispiel der Fährmann anwesend, ist der Zustand auf jeden Fall erlaubt, denn Wolf und Ziege kommen gut miteinander aus, solange ein Aufpasser da ist. Fehlt dieser jedoch, gibt IsValid() in Zeile 59 false zurück, denn der Wolf würde kurzerhand die Ziege verschlingen. Ähnliches gilt für Ziege und Kohlkopf, und die Methode gibt auch in diesem Fall false für illegale Zustände auf der Uferseite zurück, und true, falls alles in Ordnung ist.

Sortieren mit Go

Damit der Algorithmus später einfach feststellen kann, ob zwei Uferobjekte identische Passagiere aufweisen, vergleicht er deren mit String() ab Zeile 12 erzeugte Stringdarstellung Zeichen für Zeichen. Da diese Arrays beim Umbauen zwischen Spielzuständen ihre ursprüngliche Ordnung verlieren, sortiert Zeile 13 sie nach den Passagiernummern. Diese sind zwar vom Typ her reinrassige Integer, doch weigert sich der Go-Compiler, sie mit der Standardfunktion zur Integersortierung, sort.Ints() zu sortieren. Deswegen greift Listing 3 ihm unter die Arme, und bringt ihm bei, wie man einen Array von Passenger-Werten sortiert. Es definiert den Typ Passengers (Plural), sowie drei Methoden darauf, mit deren Hilfe Go beliebige Datentypen sortiert.

Die erste ist Len() und gibt die Länge des Arrays an, die es einfach mit der eingebauten Funktion len() ermittelt. Die zweite ist Swap() und zeigt dem Compiler, wie er während der Sortierung zwei Elemente an den Indexpositionen i und j miteinander vertauscht, was in Go sehr einfach ist, da es die Syntax a,b = b,a versteht. Und drittens braucht die Sortierfunktion eine Methode Less(), die immer dann einen wahren Wert zurückgibt, falls der erste hereingereichte Wert kleiner als der zweite ist. Beim vorliegenden Array von Integern führt der numerische Vergleich der beiden Elemente mit p[i] < p[j] zum Ziel.

Listing 3: sort.go

    01 package main
    02 
    03 type Passengers []Passenger
    04 
    05 func (p Passengers) Len() int {
    06   return len(p)
    07 }
    08 func (p Passengers) Swap(i, j int) {
    09   p[i], p[j] = p[j], p[i]
    10 }
    11 func (p Passengers) Less(i, j int) bool {
    12   return p[i] < p[j]
    13 }

Mit diesem Rüstzeug in Listing 3 kann nun Listing 2 sort.Sort(Passengers(...)) auf den Array mit Passenger-Typen aufrufen, den die Funktion dann In-Place [4] sortiert.

Von Zustand zu Zustand

Zustände des Spiels, also die Situation auf beiden Ufern, definiert Listing 4 mit dem Datentyp State. Go kennt ja keine Klassen, bietet aber Objektorientierung mit Structs und Methoden, die auf dem im Struct definierten Datentyp herumorgeln. Dabei ist es wichtig, den Unterschied zwischen schreibenden und lesenden Methoden zu beachten. Ein normaler "Receiver", das dem Funktionsnamen vorangestellte Objekt, wie zum Beispiel in der Funktion IsValid() in Zeile 13 erlaubt der Funktion nur lesenden Zugriff. Schreiben darf sie wohl, allerdings nur auf einer Kopie des Objekts, die nach Ablauf der Funktion auf Nimmerwiedersehen verschwindet.

Listing 4: state.go

    01 package main
    02 
    03 import (
    04   "fmt"
    05 )
    06 
    07 type State struct {
    08   west Shore
    09   east Shore
    10   prev *State
    11 }
    12 
    13 func (s State) IsValid() bool {
    14   return s.west.IsValid() &&
    15     s.east.IsValid()
    16 }
    17 
    18 func (s State) String() string {
    19   return fmt.Sprintf("%s | %s",
    20     s.west.String(),
    21     s.east.String(),
    22   )
    23 }
    24 
    25 func (s *State) Move(p Passenger) {
    26   from := &s.west
    27   to := &s.east
    28   if to.Has(Ferryman) {
    29     from, to = to, from
    30   }
    31   from.Move(p, to)
    32 }
    33 
    34 func (s State) IsFinished() bool {
    35   return len(s.west.passengers) == 0
    36 }
    37 
    38 func (s State) Copy() State {
    39   d := State{}
    40   d.west = s.west.Copy()
    41   d.east = s.east.Copy()
    42   return d
    43 }
    44 
    45 func (s State) Successors() []State {
    46   startShore := s.east
    47   if s.west.Has(Ferryman) {
    48       startShore = s.west
    49   }
    50   results := []State{}
    51 
    52   for _, passenger :=
    53          range startShore.passengers {
    54     candidate := s.Copy()
    55     candidate.Move(passenger)
    56     if passenger != Ferryman {
    57       candidate.Move(Ferryman)
    58     }
    59 
    60     if candidate.IsValid() {
    61       results = append(results, candidate)
    62     }
    63   }
    64 
    65   return results
    66 }

Für persistente schreibende Zugriffe muss ein sogenannter "Pointer Receiver" her, wie ihn zum Beispiel Move() ab Zeile 25 zeigt. Da der Aufruf von state.Move() genau gleich aussieht, egal ob Move() nun einen normalen Receiver oder einen Pointer definiert, muss der Programmierer aufpassen wie ein Haftelmacher, denn fehlt der Pointer aus Versehen, treten keine Fehler auf -- nur richtig geschrieben wird halt nichts, was wissenschaftlich belegt zu Tischhämmern und Haareraufen führen kann.

Das State-Objekt führt zwei Ufer-Objekte, west und east mit sich, sowie einen Pointer prev auf den Zustand, aus dem es ursprünglich hervorging. Findet der Algorithmus später eine Lösung, lässt sich über diese Pointerkette rückwärts der Weg zum Ziel nachvollziehen. Von welchem Ufer aus, west oder east, sich Fährmann und/oder Passagiere aus in Bewegung setzen, um in einem Folgezustand zu landen, hängt davon ab, wo der Fährmann sich gerade befindet. So legt Zeile 26 die Richtung West-Ost fest, vertauscht aber from und to in Zeile 29, falls es den Fährmann auf der Ostseite findet.

Chefsache und Knechtarbeit

Ein Zustand ist legal, falls, wie IsValid() ab Zeile 13 in Listing 4 prüft, die seine beiden Uferobjekte west und east mit ihren IsValid()-Methoden grünes Licht geben. Die String-Darstellung des State-Objekts errechnet dessen String()-Methode ab Zeile 18, die ihrerseits die Darstellung nur an die beiden Ufer-Objekte delegiert und, als Chefsache, beide Teilergebnisse mit einem trennenden Mittelstrich zu einem String zusammenfügt. Eine Kopie eines Zustands legt Copy() ab Zeile 38 an, indem es Kopien der beiden Ufer anlegt, ebenfalls indem es die harte Arbeit an die Ufer-Objekte delegiert.

Der Endzustand des Spiels ist erreicht, wenn IsFinished() ab Zeile 34 einen wahren Wert zurückgibt, und dazu prüft die Methode nur, ob auf der Westseite niemand mehr weilt. Falls nicht geschummelt wurde, sind dann Fährmann mitsamt allen Passagieren auf der Ostseite und das Ziel ist erreicht.

Die wichtigste Aufgabe eines State-Objekts ist es, Folgezustände zu finden, damit der Solver später den Suchbaum aufbauen kann. Die Methode Successors() ab Zeile 45 versucht hierzu, den Fährmann entweder allein oder mit einem am gleichen Ufer wartenden Passagier ans andere Ufer zu schicken. Sie probiert blind einfach alle Möglichkeiten durch, und prüft jeweils in Zeile 60 mit IsValid(), ob damit ein gültiger Zustand entstanden ist. Falls ja, hängt es ihn an die Ergebnisliste an, die die Methode an den aufrufenden Solver zurückreicht.

Abbildung 4: Die Breitensuche ("Breadth-First") erforscht den Baum schichtweise und findet den kürzesten Lösungspfad (Quelle: Wikipedia)

Des Rätsels Lösung

Dem Solver in Listing 5 bleibt nun nur noch, in main() den Startzustand anzulegen, dessen Westufer den Fährmann sowie alle Passagiere zuzuweisen, und solve() ab Zeile 8 aufzurufen. Dort bestimmt eine Todo-Liste in Form eines Arrays von State-Objekten noch zu untersuchende Zustände. Stellt sich einer davon als Zielzustand heraus, gibt IsFinished() in Zeile 25 einen wahren Wert zurück und die For-Schleife ab Zeile 27 trommelt den Pfad dorthin zusammen, indem sie die prev-Pointer der Zustände verfolgt, bis zum Startzustand, der einen uninitialisierten prev-Pointer aufweist, der also gemäß dem Go-Standard den Wert nil hält. Aus dieser verkehrten Folge baut Zeile 32 rückwärts ein Array auf, in dem es neue Elemente mit append() immer am Anfang des bestehenden Arrays einfügt und aus dem Ergebnis ein neues Array macht.

Listing 5: solver.go

    01 package main
    02 
    03 import (
    04   "errors"
    05   "fmt"
    06 )
    07 
    08 func solve(state State) ([]State, error) {
    09 
    10   seen := make(map[string]bool)
    11   todo := []State{state}
    12 
    13   for len(todo) > 0 {
    14     // pop off last element
    15     lastidx := len(todo) - 1
    16     s := todo[lastidx]
    17     todo = todo[:lastidx]
    18 
    19     // prevent cycles
    20     if _, ok := seen[s.String()]; ok {
    21       continue
    22     }
    23     seen[s.String()] = true
    24 
    25     if s.IsFinished() {
    26       path := []State{}
    27       for cs := &s; cs.prev != nil;
    28                     cs = cs.prev {
    29         c := cs.Copy()
    30         path = append([]State{c}, path...)
    31       }
    32       path = append([]State{state}, path...)
    33       return path, nil
    34     }
    35 
    36     for _, succ := range s.Successors() {
    37       // insert new element at end
    38       succ.prev = &s
    39       todo = append([]State{succ}, todo...)
    40     }
    41   }
    42 
    43   return []State{},
    44     errors.New("Can't solve")
    45 }
    46 
    47 func main() {
    48   var state State
    49 
    50   state.west.Add(Wolf)
    51   state.west.Add(Cabbage)
    52   state.west.Add(Ferryman)
    53   state.west.Add(Goat)
    54 
    55   solution, err := solve(state)
    56   if err != nil {
    57     panic(err)
    58   }
    59 
    60   fmt.Printf("Solution:\n")
    61 
    62   for _, step := range solution {
    63     fmt.Printf("[%s]\n", step)
    64   }
    65 }

Anfangs steht in der Todo-Liste nur der Startzustand mit allen Teilnehmern am Westufer. Die for-Schleife ab Zeile 13 entfernt in Zeile 17 mit Slice-Arithmetik immer das letzte Element. Am Ende der Schleife sucht dann Successors() mögliche Nachfolger des aktuellen Zustandes und fügt sie am Anfang (!) des todo-Array-Slices ein. Dadurch entsteht eine Warteschlange, bei der neue Elemente von links reingeschoben und von rechts abgeholt werden ("First in, last out"). Dieses Verfahren führt zu einer Breitensuche ("Breadth-First", [5] und Abbildng 4) im Suchbaum. Sie klappert die Knoten schichtweise ab, bis sie den Zielzustand findet. Fände statt einer Warteschlange ein Stack Verwendung ("First in, first out"), zum Beispiel in dem neue Zustände rechts an den Array angehängt und von dort auch wieder abgeholt würden, hätte dies ein Depth-First-Verhalten im Baum zur Folge. Der Algorithumus würde nicht schichtweise vorgehen, sondern immer sofort bis zum äußersten Astende vorstoßen -- wobei er möglicherweise schneller eine Lösung fände, aber nicht unbedingt die kürzeste, sondern vielleicht eine sehr umständliche.

Abbildung 5: Der Algorithmus löst das Rätsel in sieben Zügen.

Damit der Solver sich nicht festfährt und den Fährmann zum Beispiel immer leer hin und herfahren lässt, und so eine unendliche Reihe von Folgezuständen generiert, prüft Zeile 20, ob ein vorgeschlagener Folgezustand schon einmal bearbeitet wurde, in dem sie in der Map seen (einer Hashtabelle) nachsieht, ob die Stringdarstellung des Zustands dort als Schlüssel steht. Falls ja, ignoriert die continue-Anweisung in Zeile 21 diesen Eintrag und läutet die nächste Runde in der for-Schleife ein.

Abbildung 5 zeigt die Ausgabe des Solvers, der eine Lösung in insgesamt sieben Zügen gefunden hat. Zuerst bringt der Fährmann die Ziege ans Ostufer, fährt leer zurück, schippert den Wolf ans Ostufer, nimmt aber die Ziege wieder mit. Am Westufer angelangt, schnappt er sich den Kohl, lässt die Ziege da, bringt das Grünzeug ans Ostufer, an dem der Wolf wartet, aber den Kohl in Ruhe lässt. Bleibt dem Fährmann nur noch, leer zurückzufahren und die Ziege ans Ostufer zu bringen -- und die ganze Mannschaft ist ohne bedrohliche Zwischenfälle heil angekommen.

Abbildung 6: Mit einem Lachs als zusätzlichem Passagier findet sich ebenfalls eine Lösung, wenngleich auch umständlicher.

Noch mehr

Einmal programmiert, kann der Solver natürlich auch erweitert werden. Wie wäre es zum Beispiel mit einem zusätzlichen Passagier, der sich mit allen anderen gut verträgt, zum Beispiel einem Lachs? Flugs in Listing 1 im const-Konstrukt mit Salmon eingebaut und in der main()-Funktion in Listing 5 mit

    state.west.Add(Salmon)

verdrahtet, zeigt sich, dass der Solver auch hierfür eine Lösung findet, allerdings etwas umständlicher: Abbildung 6 zeigt die neun Schritte zum Ziel, wobei der Fährmann zuerst die Ziege rüberbringt, dann den Lachs, dann den Kohlkopf. Nun kann er allerdings nicht leer rüber zum einzig verbleibenden Wolf am Westufer, denn die Ziege würde den Kohlkopf verspeisen. Statt dessen bringt er die Ziege wieder zurück, setzt den Wolf über, um dann leer zurück zur Ziege am Westufer zu fahren und sie als letzte überzusetzen. Da hätte ein menschlicher Rätselfreund sicher eine Weile daran getüftelt, aber für den Algorithmus ist's nur Routine.

Infos

[1]

Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2020/01/snapshot/

[2]

https://de.wikipedia.org/wiki/Fluss%C3%BCberquerungsr%C3%A4tsel

[3]

David Kopec, "Classic Computer Science Problems in Python", Manning 2019, https://www.manning.com/books/classic-computer-science-problems-in-python

[4]

"In-Place-Algorithmus", Wikipedia, https://de.wikipedia.org/wiki/In-Place-Algorithmus

[5]

Breitensuche, Wikipedia, https://de.wikipedia.org/wiki/Breitensuche

Michael Schilli

arbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen.

POD ERRORS

Hey! The above document had some coding errors, which are explained below:

Around line 5:

Unknown directive: =desc