powered by 
Ganz unten in den Stollen wohnt der Mampfer, und er nimmt immer den kürzesten Weg zu Pip. Du zählst Schritte, nutzt das Licht der alten Lampen und schreibst am Ende selbst die Suche, mit der er Pip findet.
Ein paar Tage später summt der große Funkenstein, den Bello aus der Tiefe mitgebracht hat. Nachts glüht er rot. Der Wichtel dreht ihn in den Händen und wird blass.
Nach jedem Schritt von Pip geht der Mampfer ein Feld weiter, auf dem kürzesten
Weg zu Pip. Ein Schritt ist jeder Befehl außer say: auch eine Drehung und das
Aufheben eines Steins. Bleibt Pip stehen, holt der Mampfer Pip also ein, auch
wenn dein Plan zu Ende ist, bevor Pip an der Lampe ist. Steht er auf Pips Feld
oder Pip auf seinem, schnappt er zu.
Bevor Pip losläuft: Auf dieser Karte macht Pip einen Schritt nach rechts.
######## #...1M2# #.####.# #..P...# ########
Pip macht auf der Karte oben einen Schritt nach rechts. Wohin geht der Mampfer danach?
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Der Mampfer geht auf Feld 2, obwohl Pip links unter ihm zu stehen scheint. Er geht nicht dorthin, wo Pip näher aussieht, sondern den Weg, der kürzer ist: Links um den Felsen herum wären es neun Felder bis zu Pip, rechts herum fünf.
Der Mampfer ist aufgewacht und kommt. Bring Pip zur Lampe, bevor er Pip erreicht.
Jeder Befehl ist ein Schritt, auch eine Drehung, und nach jedem Schritt kommt der Mampfer ein Feld näher.
Nach rechts dreht sich Pip mit drei Drehungen nach links.
Der Mampfer ist aufgewacht und kommt. Bring Pip zur Lampe, bevor er Pip erreicht.
Jeder Befehl ist ein Schritt, auch eine Drehung, und nach jedem Schritt kommt der Mampfer ein Feld näher.
Nach rechts dreht sich Pip mit drei Drehungen nach links.
Der Mampfer ist aufgewacht und kommt. Bring Pip zur Lampe, bevor er Pip erreicht.
Jeder Befehl ist ein Schritt, auch eine Drehung, und nach jedem Schritt kommt der Mampfer ein Feld näher.
Nach rechts dreht sich Pip mit drei Drehungen nach links.
Die Lampen, die Pip unterwegs angezündet hat, brennen noch. In ihr Licht, die neun Felder um eine brennende Lampe, geht der Mampfer nicht, auch nicht, wenn Pip darin steht. Pip schon. Auf der Karte ist das Licht ein heller Schein auf dem Boden.
Pip steht im Licht einer alten Lampe. Links im Dunkeln liegt ein Funkenstein. Hol ihn und bring Pip dann zur Lampe ganz rechts.
Solange Pip mitten im Licht steht, findet der Mampfer keinen Weg zu Pip und wartet.
Zähl mit: Wie viele Schritte braucht der Mampfer bis zum Stein, sobald Pip das Licht verlässt? Jede Drehung zählt.
Umdrehen kostet zwei Drehungen nach links. Kein Schritt darf übrig sein.
Pip steht im Licht einer alten Lampe. Links im Dunkeln liegt ein Funkenstein. Hol ihn und bring Pip dann zur Lampe ganz rechts.
Solange Pip mitten im Licht steht, findet der Mampfer keinen Weg zu Pip und wartet.
Zähl mit: Wie viele Schritte braucht der Mampfer bis zum Stein, sobald Pip das Licht verlässt? Jede Drehung zählt.
Umdrehen kostet zwei Drehungen nach links. Kein Schritt darf übrig sein.
Pip steht im Licht einer alten Lampe. Links im Dunkeln liegt ein Funkenstein. Hol ihn und bring Pip dann zur Lampe ganz rechts.
Solange Pip mitten im Licht steht, findet der Mampfer keinen Weg zu Pip und wartet.
Zähl mit: Wie viele Schritte braucht der Mampfer bis zum Stein, sobald Pip das Licht verlässt? Jede Drehung zählt.
Umdrehen kostet zwei Drehungen nach links. Kein Schritt darf übrig sein.
Zwei Funkensteine liegen im Dunkeln, einer links und einer rechts vom Licht. Durchs Licht kann der Mampfer nicht, er muss oben herum. Hol beide Steine und bring Pip zur Lampe.
Der Mampfer nimmt immer den kürzesten Weg, und durchs Licht führt keiner.
Auf welcher Seite ist der Mampfer näher? Mit welchem Stein fängst du an?
Zuerst der rechte Stein: Währenddessen läuft der Mampfer oben herum nach rechts, und links ist frei.
Zwei Funkensteine liegen im Dunkeln, einer links und einer rechts vom Licht. Durchs Licht kann der Mampfer nicht, er muss oben herum. Hol beide Steine und bring Pip zur Lampe.
Der Mampfer nimmt immer den kürzesten Weg, und durchs Licht führt keiner.
Auf welcher Seite ist der Mampfer näher? Mit welchem Stein fängst du an?
Zuerst der rechte Stein: Währenddessen läuft der Mampfer oben herum nach rechts, und links ist frei.
Zwei Funkensteine liegen im Dunkeln, einer links und einer rechts vom Licht. Durchs Licht kann der Mampfer nicht, er muss oben herum. Hol beide Steine und bring Pip zur Lampe.
Der Mampfer nimmt immer den kürzesten Weg, und durchs Licht führt keiner.
Auf welcher Seite ist der Mampfer näher? Mit welchem Stein fängst du an?
Zuerst der rechte Stein: Währenddessen läuft der Mampfer oben herum nach rechts, und links ist frei.
Woher kennt der Mampfer den kürzesten Weg? Er sucht von Pip aus, wie eine Welle: erst die Felder einen Schritt von Pip entfernt, dann die zwei Schritte entfernten und so weiter, bis er bei seinem eigenen Feld ankommt. Zu jedem Feld merkt er sich, von welchem Feld aus er es gefunden hat, seinen Vorgänger. Der Vorgänger seines eigenen Feldes liegt einen Schritt näher an Pip: Dorthin geht er.
Das ist die Breitensuche aus dem Handbuch Graphen, nur
auf der Karte: Jedes freie Feld ist ein Knoten, verbunden mit den freien
Feldern rechts, oben, links und unten. Die Nachbarn eines Feldes nimmt der
Mampfer immer in der Reihenfolge Osten, Norden, Westen, Süden. Ein Feld heißt
nach seiner Spalte und seiner Zeile, 5,3 ist Spalte 5 in Zeile 3, gezählt ab
0 und nach unten.
breadth_first_search(graph, start, goal): predecessor ← { start: null } queue ← [start] while queue not empty: node ← take the front node from queue if node == goal: return path_back(predecessor, goal) for each neighbor of node: if neighbor not in predecessor: predecessor[neighbor] ← node add neighbor at the back of queue no path
Hier steht Pip auf 5,3, der Mampfer auf 1,1, und um den Felsen in der
Mitte führen zwei gleich lange Wege. Gelb sind die Felder in der Queue, lila
die schon herausgenommenen; jeder Pfeil zeigt von einem Feld auf seinen
Vorgänger. Am Ende steht der Weg von Pip zum Mampfer da, und der Pfeil, der
vom Feld des Mampfers ausgeht, ist sein nächster Schritt.
Welcher der beiden gleich langen Wege es wird, entscheidet die Reihenfolge der Nachbarn: Von Pip aus kommt Norden vor Westen, also findet die Suche den Weg oben herum zuerst.
Edward F. Moore (1925–2003), amerikanischer Mathematiker bei den Bell Labs. 1957 zeigte er, wie man den kürzesten Weg durch ein Labyrinth findet: vom Start aus erst alle Felder einen Schritt weit, dann alle zwei Schritte weit und so weiter, bis das Ziel dabei ist. So sucht die Breitensuche, und so sucht der Mampfer nach Pip.
Gedruckt erschien das 1959 als »The Shortest Path Through a Maze«. Nach ihm heißen auch die Moore-Automaten und die acht Nachbarn einer Zelle im Game of Life, die Moore-Nachbarschaft.
Jetzt schreibst du diese Suche selbst. Die Karte des Wichtels ist eine Liste
von Zeilen, jede Zeile ein Text, mit denselben Zeichen wie oben: # Fels,
. Boden, P Pip, M der Mampfer, L die Lampe, o ein Funkenstein.
Ein Feld schreibst du als seine Position:
cave = ['#######', '#P..#L#', '#.#...#', '#######'] puts cave[1][5] # L: Zeile 1, Spalte 5 pip = [1, 1] # eine Position: [x, y]
cave = ['#######', '#P..#L#', '#.#...#', '#######'] print(cave[1][5]) # L: Zeile 1, Spalte 5 pip = (1, 1) # eine Position als Tupel: (x, y)
Positionen sind hier Tupel, keine Listen: Nur ein Tupel kann Schlüssel eines Dictionarys sein, und die Suche braucht Dictionarys mit Positionen.
const cave = ['#######', '#P..#L#', '#.#...#', '#######']; console.log(cave[1][5]); // L: Zeile 1, Spalte 5 const pip = [1, 1]; // eine Position: [x, y]
Erst kommt die Zeile, cave[y], dann in ihr die Spalte, cave[y][x].
Der Wichtel gibt dir seine Karte: eine Liste von Zeilen, jede ein Text, # ist Fels. Schreib eine Funktion find(cave, tile), die die Stelle von tile auf der Karte als [x, y] zurückgibt, x die Spalte und y die Zeile, beide ab 0, und nil, wenn es nicht vorkommt. Kommt es mehrmals vor, gilt das erste von oben, in seiner Zeile das erste von links.
Geh die Zeilen mit ihrem Index durch; in jeder Zeile sucht index (Python: find, JavaScript: indexOf) das Zeichen.
Der Wichtel gibt dir seine Karte: eine Liste von Zeilen, jede ein Text, # ist Fels. Schreib eine Funktion find(cave, tile), die die Stelle von tile auf der Karte als Tupel (x, y) zurückgibt, x die Spalte und y die Zeile, beide ab 0, und None, wenn es nicht vorkommt. Kommt es mehrmals vor, gilt das erste von oben, in seiner Zeile das erste von links.
Geh die Zeilen mit ihrem Index durch; in jeder Zeile sucht index (Python: find, JavaScript: indexOf) das Zeichen.
Der Wichtel gibt dir seine Karte: eine Liste von Zeilen, jede ein Text, # ist Fels. Schreib eine Funktion find(cave, tile), die die Stelle von tile auf der Karte als [x, y] zurückgibt, x die Spalte und y die Zeile, beide ab 0, und null, wenn es nicht vorkommt. Kommt es mehrmals vor, gilt das erste von oben, in seiner Zeile das erste von links.
Geh die Zeilen mit ihrem Index durch; in jeder Zeile sucht index (Python: find, JavaScript: indexOf) das Zeichen.
Schreib neighbors(cave, x, y): die Felder neben dem Feld x, y, auf die man gehen kann, also alles außer #, als Liste von Positionen ([x, y]), in der Reihenfolge Osten, Norden, Westen, Süden: rechts, oben, links, unten. Nach unten wird y größer. Jede Karte hat ringsum Fels, du musst also nicht prüfen, ob du über den Rand schaust.
Die vier Richtungen als Liste von Verschiebungen: [1, 0], [0, -1], [-1, 0], [0, 1]. Für jede schaust du in cave[y + dy][x + dx].
Schreib neighbors(cave, x, y): die Felder neben dem Feld x, y, auf die man gehen kann, also alles außer #, als Liste von Positionen (Tupel (x, y)), in der Reihenfolge Osten, Norden, Westen, Süden: rechts, oben, links, unten. Nach unten wird y größer. Jede Karte hat ringsum Fels, du musst also nicht prüfen, ob du über den Rand schaust.
Die vier Richtungen als Liste von Verschiebungen: [1, 0], [0, -1], [-1, 0], [0, 1]. Für jede schaust du in cave[y + dy][x + dx].
Schreib neighbors(cave, x, y): die Felder neben dem Feld x, y, auf die man gehen kann, also alles außer #, als Liste von Positionen ([x, y]), in der Reihenfolge Osten, Norden, Westen, Süden: rechts, oben, links, unten. Nach unten wird y größer. Jede Karte hat ringsum Fels, du musst also nicht prüfen, ob du über den Rand schaust.
Die vier Richtungen als Liste von Verschiebungen: [1, 0], [0, -1], [-1, 0], [0, 1]. Für jede schaust du in cave[y + dy][x + dx].
Schreib distance(cave, start, goal): wie viele Schritte der kürzeste Weg von start nach goal hat, beide Positionen wie bei find, und nil, wenn es keinen Weg gibt. So sucht der Mampfer: eine Breitensuche, die sich zu jedem gefundenen Feld merkt, wie weit es vom Start ist. Nimm deine Funktion neighbors von oben mit hinein.
Ein Hash steps merkt sich zu jedem gefundenen Feld seinen Abstand; der Start hat 0.
Eine Queue, am Anfang nur der Start. Nimm vorne eines heraus (shift): Jeder Nachbar, der noch nicht in steps steht, bekommt den Abstand des Feldes plus 1 und kommt hinten in die Queue.
Schreib distance(cave, start, goal): wie viele Schritte der kürzeste Weg von start nach goal hat, beide Positionen wie bei find, und None, wenn es keinen Weg gibt. So sucht der Mampfer: eine Breitensuche, die sich zu jedem gefundenen Feld merkt, wie weit es vom Start ist. Nimm deine Funktion neighbors von oben mit hinein.
Ein Dictionary steps merkt sich zu jedem gefundenen Feld seinen Abstand; der Start hat 0. Positionen als Tupel gehen als Schlüssel, Listen nicht.
Eine Queue (collections.deque), am Anfang nur der Start. Nimm vorne eines heraus (popleft): Jeder Nachbar, der noch nicht in steps steht, bekommt den Abstand des Feldes plus 1 und kommt hinten hinein.
Schreib distance(cave, start, goal): wie viele Schritte der kürzeste Weg von start nach goal hat, beide Positionen wie bei find, und null, wenn es keinen Weg gibt. So sucht der Mampfer: eine Breitensuche, die sich zu jedem gefundenen Feld merkt, wie weit es vom Start ist. Nimm deine Funktion neighbors von oben mit hinein.
Ein Objekt steps merkt sich zu jedem gefundenen Feld seinen Abstand; der Start hat 0. Ein Array als Schlüssel wird zum Text: steps[[3, 1]] ist steps['3,1'], und [3, 1] in steps fragt danach.
Eine Queue, am Anfang nur der Start. Nimm vorne eines heraus (shift): Jeder Nachbar, der noch nicht in steps steht, bekommt den Abstand des Feldes plus 1 und kommt hinten hinein.
Schreib way(cave, start, goal): den kürzesten Weg als Liste der Felder von start bis goal, beide mitgezählt, und nil, wenn es keinen gibt. Wie in der Breitensuche des Handbuchs: Merk dir zu jedem Feld seinen Vorgänger, und geh am Ende vom Ziel aus zurück bis zum Start.
Wie distance, nur merkst du dir statt des Abstands den Vorgänger: das Feld, von dem aus du den Nachbarn gefunden hast. Der Start hat keinen.
Vom Ziel aus: Füg das Feld vorne an den Weg an und geh zu seinem Vorgänger, bis keiner mehr da ist.
Schreib way(cave, start, goal): den kürzesten Weg als Liste der Felder von start bis goal, beide mitgezählt, und None, wenn es keinen gibt. Wie in der Breitensuche des Handbuchs: Merk dir zu jedem Feld seinen Vorgänger, und geh am Ende vom Ziel aus zurück bis zum Start.
Wie distance, nur merkst du dir statt des Abstands den Vorgänger: das Feld, von dem aus du den Nachbarn gefunden hast. Der Start hat keinen.
Vom Ziel aus: Füg das Feld vorne an den Weg an und geh zu seinem Vorgänger, bis keiner mehr da ist.
Schreib way(cave, start, goal): den kürzesten Weg als Liste der Felder von start bis goal, beide mitgezählt, und null, wenn es keinen gibt. Wie in der Breitensuche des Handbuchs: Merk dir zu jedem Feld seinen Vorgänger, und geh am Ende vom Ziel aus zurück bis zum Start.
Wie distance, nur merkst du dir statt des Abstands den Vorgänger: das Feld, von dem aus du den Nachbarn gefunden hast. Der Start hat keinen.
Vom Ziel aus: Füg das Feld vorne an den Weg an und geh zu seinem Vorgänger, bis keiner mehr da ist.
Zwei neue Fragen geben Pip die Karte des Wichtels und sagen, wohin Pip schaut. Wie die anderen Fragen kosten sie keinen Schritt.
| Befehl | Was Pip bekommt |
|---|---|
cave_map |
die Karte, wie sie gerade ist, als Liste von Zeilen, mit Pip und dem Mampfer, wo sie jetzt stehen |
facing |
wohin Pip schaut: "east", "north", "west" oder "south"
|
| Befehl | Was Pip bekommt |
|---|---|
cave_map() |
die Karte, wie sie gerade ist, als Liste von Zeilen, mit Pip und dem Mampfer, wo sie jetzt stehen |
facing() |
wohin Pip schaut: "east", "north", "west" oder "south"
|
| Befehl | Was Pip bekommt |
|---|---|
caveMap() |
die Karte, wie sie gerade ist, als Liste von Zeilen, mit Pip und dem Mampfer, wo sie jetzt stehen |
facing() |
wohin Pip schaut: "east", "north", "west" oder "south"
|
Schreib eine Funktion face(direction), die Pip so lange nach links dreht, bis Pip in die Richtung direction schaut: "east", "north", "west" oder "south". Wohin Pip gerade schaut, sagt facing. Die Prüfung ruft face auf drei Karten auf, mit "south", "north" und "east".
Eine Schleife: turn_left until facing == direction. Schaut Pip schon richtig, dreht sie gar nicht.
Schreib eine Funktion face(direction), die Pip so lange nach links dreht, bis Pip in die Richtung direction schaut: "east", "north", "west" oder "south". Wohin Pip gerade schaut, sagt facing(). Die Prüfung ruft face auf drei Karten auf, mit "south", "north" und "east".
Eine Schleife: while facing() != direction: und darin turn_left(). Schaut Pip schon richtig, dreht sie gar nicht.
Schreib eine Funktion face(direction), die Pip so lange nach links dreht, bis Pip in die Richtung direction schaut: "east", "north", "west" oder "south". Wohin Pip gerade schaut, sagt facing(). Die Prüfung ruft face auf drei Karten auf, mit "south", "north" und "east".
Eine Schleife: while (facing() !== direction) turnLeft();. Schaut Pip schon richtig, dreht sie gar nicht.
Jetzt alles zusammen: Lies mit cave_map die Karte, such mit deiner Funktion way den kürzesten Weg von Pip zur Lampe und lauf ihn ab, mit face vor jedem Schritt. Der Mampfer ist so schnell wie Pip, nur der kürzeste Weg ist schnell genug. Die Prüfung schickt Pip durch drei Höhlen; zwei baut der Wichtel für dich.
find(cave, 'P') und find(cave, 'L') geben dir Start und Ziel für way.
Von einem Feld zum nächsten: x + 1 ist Osten, y − 1 Norden, x − 1 Westen, y + 1 Süden. Ein Dictionary von der Verschiebung zur Richtung hilft.
Jetzt alles zusammen: Lies mit cave_map() die Karte, such mit deiner Funktion way den kürzesten Weg von Pip zur Lampe und lauf ihn ab, mit face vor jedem Schritt. Der Mampfer ist so schnell wie Pip, nur der kürzeste Weg ist schnell genug. Die Prüfung schickt Pip durch drei Höhlen; zwei baut der Wichtel für dich.
find(cave, 'P') und find(cave, 'L') geben dir Start und Ziel für way.
Von einem Feld zum nächsten: x + 1 ist Osten, y − 1 Norden, x − 1 Westen, y + 1 Süden. Ein Dictionary von der Verschiebung zur Richtung hilft.
Jetzt alles zusammen: Lies mit caveMap() die Karte, such mit deiner Funktion way den kürzesten Weg von Pip zur Lampe und lauf ihn ab, mit face vor jedem Schritt. Der Mampfer ist so schnell wie Pip, nur der kürzeste Weg ist schnell genug. Die Prüfung schickt Pip durch drei Höhlen; zwei baut der Wichtel für dich.
find(cave, 'P') und find(cave, 'L') geben dir Start und Ziel für way.
Von einem Feld zum nächsten: x + 1 ist Osten, y − 1 Norden, x − 1 Westen, y + 1 Süden. Ein Dictionary von der Verschiebung zur Richtung hilft.
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Ein Extra für Schnelle: Die Seite ist ohne dieses Kapitel vollständig.
Zwei Katas, die nicht mitzählen.
Schreib next_step(cave): das Feld, auf das der Mampfer (M) als Nächstes geht, wenn Pip (P) einen Schritt macht. Er sucht von Pip aus, die Nachbarn in der Reihenfolge Osten, Norden, Westen, Süden, und geht auf den Vorgänger seines Feldes. Findet er keinen Weg, bleibt er stehen. Lampen gibt es hier keine.
Mit find und way: der Weg von Pip zum Mampfer. Das Feld vor seinem letzten ist das, auf das der Mampfer geht.
Schreib next_step(cave): das Feld, auf das der Mampfer (M) als Nächstes geht, wenn Pip (P) einen Schritt macht. Er sucht von Pip aus, die Nachbarn in der Reihenfolge Osten, Norden, Westen, Süden, und geht auf den Vorgänger seines Feldes. Findet er keinen Weg, bleibt er stehen. Lampen gibt es hier keine.
Mit find und way: der Weg von Pip zum Mampfer. Das Feld vor seinem letzten ist das, auf das der Mampfer geht.
Schreib nextStep(cave): das Feld, auf das der Mampfer (M) als Nächstes geht, wenn Pip (P) einen Schritt macht. Er sucht von Pip aus, die Nachbarn in der Reihenfolge Osten, Norden, Westen, Süden, und geht auf den Vorgänger seines Feldes. Findet er keinen Weg, bleibt er stehen. Lampen gibt es hier keine.
Mit find und way: der Weg von Pip zum Mampfer. Das Feld vor seinem letzten ist das, auf das der Mampfer geht.
Ein Weg ist eine Liste von Feldern, wie way sie liefert. Schreib steps(path, facing): wie viele Schritte er Pip kostet, wenn Pip am Anfang in Richtung facing schaut ('east', 'north', 'west' oder 'south') und sich nur nach links drehen kann. Jeder Schritt vorwärts zählt, jede Drehung auch.
Nach links dreht Pip in der Reihenfolge Osten, Norden, Westen, Süden weiter. Wie viele Drehungen von einer Richtung zur anderen? Der Abstand in dieser Liste, modulo 4.
Ein Weg ist eine Liste von Feldern, wie way sie liefert. Schreib steps(path, facing): wie viele Schritte er Pip kostet, wenn Pip am Anfang in Richtung facing schaut ('east', 'north', 'west' oder 'south') und sich nur nach links drehen kann. Jeder Schritt vorwärts zählt, jede Drehung auch.
Nach links dreht Pip in der Reihenfolge Osten, Norden, Westen, Süden weiter. Wie viele Drehungen von einer Richtung zur anderen? Der Abstand in dieser Liste, modulo 4.
Ein Weg ist eine Liste von Feldern, wie way sie liefert. Schreib steps(path, facing): wie viele Schritte er Pip kostet, wenn Pip am Anfang in Richtung facing schaut ('east', 'north', 'west' oder 'south') und sich nur nach links drehen kann. Jeder Schritt vorwärts zählt, jede Drehung auch.
Nach links dreht Pip in der Reihenfolge Osten, Norden, Westen, Süden weiter. Wie viele Drehungen von einer Richtung zur anderen? Der Abstand in dieser Liste, modulo 4.
Den Mampfer hat 0x72 gezeichnet, als »big demon« im 16x16 DungeonTileset II (CC0); er war schon das Monster der alten Hackschule.