Universität Ulm,
Fakultät für Mathematik und Wirtschaftswissenschaften,
SAI
Lösung zu Blatt 5 --- Allgemeine Informatik II (WS 1999)
6. Really no way out?
MODULE PathFinder;
IMPORT Args := UnixArguments, ASCII, Read, Streams, UnixFiles, Write;
CONST
maxsize = 128; (* maximale Seitenlaenge eines Labyrinths *)
minsize = 3; (* Minimalgroesse, alles darunter ist nicht sinnvoll *)
space = " "; (* alles andere wird als Wand betrachtet *)
walk = "*"; (* Markierung des durchlaufenen Weges *)
TYPE
MazeSize = INTEGER; (* [0..maxsize] *)
MazeIndex = INTEGER; (* [0..maxsize - 1] *)
Maze = ARRAY maxsize, maxsize OF CHAR;
(* Labyrinth in der graphischen Notierung auf Basis von
ASCII-Zeichen, genau so wie es auch in der Eingabe
erwartet wird. Hinzu kommen nur Wegemarkierungen.
*)
VAR
maze: Maze;
width, height: MazeSize; (* Weite und Hoehe des Labyrinths *)
entry, exit: MazeIndex; (* Zeilenindizes von Eingang und Ausgang *)
(* Kommandozeilenargumente *)
stepwise: BOOLEAN; (* alle Zwischenstaende ausgeben? *)
query: BOOLEAN; (* impliziert stepwise, jeweils mit Rueckfrage *)
input: Streams.Stream; (* von hier ist das Labyrinth einzulesen *)
PROCEDURE Error(msg: ARRAY OF CHAR);
(* Ausgabe einer Fehlermeldung auf stderr mitsamt Zeilenende *)
BEGIN
Write.LineS(Streams.stderr, msg);
END Error;
PROCEDURE ProcessArgs;
VAR
flag: CHAR;
filename: ARRAY 512 OF CHAR;
BEGIN
query := FALSE; stepwise := FALSE;
Args.Init("[-q] [-s] [maze]");
WHILE Args.GetFlag(flag) DO
CASE flag OF
| "q": query := TRUE; stepwise := TRUE;
| "s": stepwise := TRUE;
ELSE
Args.Usage;
END;
END;
IF Args.GetArg(filename) THEN
IF ~UnixFiles.Open(input, filename, UnixFiles.read, Streams.onebuf,
NIL) THEN
Write.StringS(Streams.stderr, "Error opening File ");
Error(filename);
END;
ELSE
input := Streams.stdin;
IF query THEN
Error("-q vertraegt sich nicht mit einem Labyrinth von stdin!");
HALT(1);
END;
END;
Args.AllArgs;
END ProcessArgs;
PROCEDURE ReadMaze(input: Streams.Stream;
VAR maze: Maze;
VAR width, height: INTEGER;
VAR entry, exit: MazeIndex) : BOOLEAN;
(* Einlesen eines Labyrinths von ``input'':
- Bei Problemen wird eine Fehlermeldungen ausgegeben und
FALSE zurueckgeliefert.
- Im Erfolgsfall wird in maze das Labyrinth in der
vorgefundenen Form abgelegt.
- Die beiden Seitenlaengen (des Rechtecks) werden in
width und height zurueckgegeben.
- Auf der linken Seite wird ein Eingang erwartet und
auf der rechten Seite der Ausgang. Die entsprechenden
Zeilenindizes werden in entry und exit zurueckgeliefert.
*)
VAR
line, column: INTEGER; (* aktuelle Position im Labyrinth *)
ch: CHAR; (* zuletzt eingelesenes Zeichen *)
entryFound, exitFound: BOOLEAN; (* Ein- und Ausgang gefunden? *)
spaceSeen: BOOLEAN; (* Freiraum in der letzten Zeile? *)
BEGIN
line := 0; column := 0; width := 0;
entryFound := FALSE; exitFound := FALSE;
spaceSeen := FALSE;
WHILE Streams.ReadByte(input, ch) DO
IF ch = ASCII.nl THEN
IF line = 0 THEN
IF column < minsize THEN
Write.Line("Labyrinth ist zu klein!");
RETURN FALSE
END;
width := column;
ELSIF column # width THEN
Write.Line("Das Labyrinth ist nicht rechteckig!");
RETURN FALSE
END;
INC(line); column := 0;
ELSE
IF ch = space THEN
IF line = 0 THEN
Write.Line("Bitte keinen Eingang in der 1. Zeile!");
RETURN FALSE
ELSIF column = 0 THEN
IF entryFound THEN
Write.Line("Mehr als einen Eingang gefunden!");
RETURN FALSE
ELSE
entry := line; entryFound := TRUE;
END;
ELSIF column = width-1 THEN
IF exitFound THEN
Write.Line("Mehr als einen Ausgang gefunden!");
RETURN FALSE
ELSE
exit := line; exitFound := TRUE;
END;
END;
spaceSeen := TRUE;
ELSIF column = 0 THEN
spaceSeen := FALSE;
END;
IF (line >= maxsize) OR (column >= maxsize) THEN
Write.Line("Das Labyrinth ist zu gross!");
RETURN FALSE
END;
IF ch = walk THEN
Write.Line("Bitte keine Markierungszeichen verwenden!");
RETURN FALSE
END;
maze[line, column] := ch; INC(column);
END;
END;
height := line;
IF (width < minsize) OR (height < minsize) THEN
Write.Line("Labyrinth ist zu klein!"); RETURN FALSE
ELSIF spaceSeen THEN
Write.Line("Bitte keinen Ausgang in der letzten Zeile!");
RETURN FALSE
ELSIF ~entryFound THEN
Write.Line("Keinen Eingang gefunden!");
RETURN FALSE
ELSIF ~exitFound THEN
Write.Line("Keinen Ausgang gefunden!");
RETURN FALSE
ELSIF maze[entry, 1] # space THEN
Write.Line("Eingang ist verbarrikadiert!");
RETURN FALSE
END;
IF column # 0 THEN
Write.Line("Das Ende der letzten Zeile wird vermisst!");
RETURN FALSE
END;
RETURN TRUE
END ReadMaze;
PROCEDURE WriteMaze(maze: Maze; width, height: MazeSize);
(* Ausgabe des Labyrinths auf stdout *)
VAR
line, column: INTEGER;
BEGIN
line := 0;
WHILE line < height DO
column := 0;
WHILE column < width DO
Write.Char(maze[line, column]);
INC(column);
END;
Write.Ln;
INC(line);
END;
END WriteMaze;
PROCEDURE SolveMaze(VAR maze: Maze;
width, height: MazeSize;
startx, starty: MazeIndex);
(* Finden und Markieren eines Weges durch das Labyrinth `maze'
mit den gegebenen Seitenlaengen `width' und `height' und
mit der Startposition (startx, starty)
nach der rechten Hand-Regel;
bei einer Startposition in der Mitte des Labyrinths kann
der Algorithmus beliebig lange laufen, wenn es Inseln oder
Einschluesse gibt;
die Optionen (globale Variablen) stepwise und query werden honoriert
*)
CONST
east = 0;
south = 1;
west = 2;
north = 3;
(* (east, south, west, north) linke Hand-Regel
(east, north, west, south) rechte Hand-Regel
Wichtig ist, dass east zuerst genannt wird, weil
der Eingang auf der linken Seite liegt und wir
nicht das Labyrinth sofort wieder verlassen moechten.
*)
TYPE
Direction = INTEGER; (*(east, south, west, north); *)
Delta = INTEGER; (* [-1..1] *)
(* Datentyp fuer die Differenz einer Zeilen- oder
Spaltenposition
*)
VAR
dx, dy: ARRAY 4 OF Delta;
(* Differenzen der Zeilen- und Spaltenpositionen, die
bei den einzelnen Richtungen zu verwenden sind, um
eine entsprechende Bewegung durchzufuehren
*)
x, y: MazeIndex;
(* aktuelle Zeilen- und Spaltenposition im Labyrinth *)
direction: Direction;
(* aktuelle Richtung, beginnt mit MIN(Direction) *)
PROCEDURE Weiter() : BOOLEAN;
(* Implementierung der Option -q *)
VAR
answer: CHAR;
BEGIN
Write.String("Weiter?"); Read.Byte(answer);
RETURN answer # "n"
END Weiter;
PROCEDURE Exit(x, y: MazeIndex) : BOOLEAN;
(* Liegt (x,y) am Rand des Labyrinths? *)
BEGIN
RETURN (x = 0) OR (x = height-1) OR
(y = 0) OR (y = width-1) OR
(x = startx) & (y = starty)
END Exit;
PROCEDURE PreviousDirection(dir: Direction) : Direction;
(* nach rechts schauen *)
BEGIN
IF dir = 0 THEN
RETURN 3
ELSE
DEC(dir); RETURN dir
END;
END PreviousDirection;
PROCEDURE NextDirection(dir: Direction) : Direction;
(* nach links schauen *)
BEGIN
IF dir = 3 THEN
RETURN 0
ELSE
INC(dir); RETURN dir
END;
END NextDirection;
PROCEDURE Wall(x, y: MazeIndex; dir: Direction) : BOOLEAN;
VAR
ch: CHAR;
BEGIN
ch := maze[x + dx[dir], y + dy[dir]];
RETURN (ch # space) & (ch # walk)
END Wall;
PROCEDURE Find(x, y: MazeIndex; dir: Direction) : Direction;
(* entsprechend der Rechte-Hand-Regel umschauen und
nach einem freien Weg suchen;
Vorbedingung: Es muss mindestens einen freien Weg geben
*)
BEGIN
dir := PreviousDirection(dir); (* nach rechts schauen *)
LOOP
IF ~Wall(x, y, dir) THEN
RETURN dir
END;
dir := NextDirection(dir); (* naechste links untersuchen *)
END;
END Find;
BEGIN (* SolveMaze *)
dx[east] := 0; dx[south] := 1; dx[west] := 0; dx[north] := -1;
dy[east] := 1; dy[south] := 0; dy[west] := -1; dy[north] := 0;
direction := 0; x := startx; y := starty;
REPEAT
maze[x, y] := walk;
IF stepwise THEN
WriteMaze(maze, width, height);
IF query & ~Weiter() THEN
RETURN
END;
END;
direction := Find(x, y, direction);
INC(x, dx[direction]); INC(y, dy[direction]);
UNTIL Exit(x, y);
maze[x, y] := walk;
END SolveMaze;
BEGIN
ProcessArgs;
IF ReadMaze(input, maze, width, height, entry, exit) THEN
SolveMaze(maze, width, height, entry, 0);
WriteMaze(maze, width, height);
END;
END PathFinder.
And the Recursive Version
MODULE BestPath;
IMPORT Args := UnixArguments, ASCII, Read, Streams, UnixFiles, Write;
CONST
maxsize = 128; (* maximale Seitenlaenge eines Labyrinths *)
minsize = 3; (* Minimalgroesse, alles darunter ist nicht sinnvoll *)
space = " "; (* alles andere wird als Wand betrachtet *)
walk = "*"; (* Markierung des durchlaufenen Weges *)
east = 0;
south = 1;
west = 2;
north = 3;
(* (east, south, west, north) linke Hand-Regel
(east, north, west, south) rechte Hand-Regel
Wichtig ist, dass east zuerst genannt wird, weil
der Eingang auf der linken Seite liegt und wir
nicht das Labyrinth sofort wieder verlassen moechten.
*)
TYPE
MazeSize = INTEGER; (* [0..maxsize] *)
MazeIndex = INTEGER; (* [0..maxsize - 1] *)
Maze = ARRAY maxsize, maxsize OF CHAR;
(* Labyrinth in der graphischen Notierung auf Basis von
ASCII-Zeichen, genau so wie es auch in der Eingabe
erwartet wird. Hinzu kommen nur Wegemarkierungen.
*)
Direction = INTEGER; (*(east, south, west, north); *)
Delta = INTEGER; (* [-1..1] *)
(* Datentyp fuer die Differenz einer Zeilen- oder
Spaltenposition
*)
VAR
maze, bestmaze: Maze;
width, height: MazeSize; (* Weite und Hoehe des Labyrinths *)
entry, exit: MazeIndex; (* Zeilenindizes von Eingang und Ausgang *)
(* Kommandozeilenargumente *)
stepwise: BOOLEAN; (* alle Zwischenstaende ausgeben? *)
query: BOOLEAN; (* impliziert stepwise, jeweils mit Rueckfrage *)
input: Streams.Stream; (* von hier ist das Labyrinth einzulesen *)
best, bestl, bestr: INTEGER; (* Der kuerzeste Pfad bis jetzt *)
calls: INTEGER; (* # Aufrufe *)
dx, dy: ARRAY 4 OF Delta;
(* Differenzen der Zeilen- und Spaltenpositionen, die
bei den einzelnen Richtungen zu verwenden sind, um
eine entsprechende Bewegung durchzufuehren
*)
PROCEDURE Error(msg: ARRAY OF CHAR);
(* Ausgabe einer Fehlermeldung auf stderr mitsamt Zeilenende *)
BEGIN
Write.LineS(Streams.stderr, msg);
END Error;
PROCEDURE ProcessArgs;
VAR
flag: CHAR;
filename: ARRAY 512 OF CHAR;
BEGIN
query := FALSE; stepwise := FALSE;
Args.Init("[-q] [-s] [maze]");
WHILE Args.GetFlag(flag) DO
CASE flag OF
| "q": query := TRUE; stepwise := TRUE;
| "s": stepwise := TRUE;
ELSE
Args.Usage;
END;
END;
IF Args.GetArg(filename) THEN
IF ~UnixFiles.Open(input, filename, UnixFiles.read, Streams.onebuf,
NIL) THEN
Write.StringS(Streams.stderr, "Error opening File ");
Error(filename);
END;
ELSE
input := Streams.stdin;
IF query THEN
Error("-q vertraegt sich nicht mit einem Labyrinth von stdin!");
HALT(1);
END;
END;
Args.AllArgs;
END ProcessArgs;
PROCEDURE ReadMaze(input: Streams.Stream;
VAR maze: Maze;
VAR width, height: INTEGER;
VAR entry, exit: MazeIndex) : BOOLEAN;
(* Einlesen eines Labyrinths von ``input'':
- Bei Problemen wird eine Fehlermeldungen ausgegeben und
FALSE zurueckgeliefert.
- Im Erfolgsfall wird in maze das Labyrinth in der
vorgefundenen Form abgelegt.
- Die beiden Seitenlaengen (des Rechtecks) werden in
width und height zurueckgegeben.
- Auf der linken Seite wird ein Eingang erwartet und
auf der rechten Seite der Ausgang. Die entsprechenden
Zeilenindizes werden in entry und exit zurueckgeliefert.
*)
VAR
line, column: INTEGER; (* aktuelle Position im Labyrinth *)
ch: CHAR; (* zuletzt eingelesenes Zeichen *)
entryFound, exitFound: BOOLEAN; (* Ein- und Ausgang gefunden? *)
spaceSeen: BOOLEAN; (* Freiraum in der letzten Zeile? *)
BEGIN
line := 0; column := 0; width := 0;
entryFound := FALSE; exitFound := FALSE;
spaceSeen := FALSE;
WHILE Streams.ReadByte(input, ch) DO
IF ch = ASCII.nl THEN
IF line = 0 THEN
IF column < minsize THEN
Write.Line("Labyrinth ist zu klein!");
RETURN FALSE
END;
width := column;
ELSIF column # width THEN
Write.Line("Das Labyrinth ist nicht rechteckig!");
RETURN FALSE
END;
INC(line); column := 0;
ELSE
IF ch = space THEN
IF line = 0 THEN
Write.Line("Bitte keinen Eingang in der 1. Zeile!");
RETURN FALSE
ELSIF column = 0 THEN
IF entryFound THEN
Write.Line("Mehr als einen Eingang gefunden!");
RETURN FALSE
ELSE
entry := line; entryFound := TRUE;
END;
ELSIF column = width-1 THEN
IF exitFound THEN
Write.Line("Mehr als einen Ausgang gefunden!");
RETURN FALSE
ELSE
exit := line; exitFound := TRUE;
END;
END;
spaceSeen := TRUE;
ELSIF column = 0 THEN
spaceSeen := FALSE;
END;
IF (line >= maxsize) OR (column >= maxsize) THEN
Write.Line("Das Labyrinth ist zu gross!");
RETURN FALSE
END;
IF ch = walk THEN
Write.Line("Bitte keine Markierungszeichen verwenden!");
RETURN FALSE
END;
maze[line, column] := ch; INC(column);
END;
END;
height := line;
IF (width < minsize) OR (height < minsize) THEN
Write.Line("Labyrinth ist zu klein!"); RETURN FALSE
ELSIF spaceSeen THEN
Write.Line("Bitte keinen Ausgang in der letzten Zeile!");
RETURN FALSE
ELSIF ~entryFound THEN
Write.Line("Keinen Eingang gefunden!");
RETURN FALSE
ELSIF ~exitFound THEN
Write.Line("Keinen Ausgang gefunden!");
RETURN FALSE
ELSIF maze[entry, 1] # space THEN
Write.Line("Eingang ist verbarrikadiert!");
RETURN FALSE
END;
IF column # 0 THEN
Write.Line("Das Ende der letzten Zeile wird vermisst!");
RETURN FALSE
END;
RETURN TRUE
END ReadMaze;
PROCEDURE WriteMaze(maze: Maze; width, height: MazeSize);
(* Ausgabe des Labyrinths auf stdout *)
VAR
line, column: INTEGER;
BEGIN
line := 0;
WHILE line < height DO
column := 0;
WHILE column < width DO
Write.Char(maze[line, column]);
INC(column);
END;
Write.Ln;
INC(line);
END;
END WriteMaze;
PROCEDURE Weiter() : BOOLEAN;
(* Implementierung der Option -q *)
VAR
answer: CHAR;
BEGIN
Write.String("Weiter?"); Read.Byte(answer);
RETURN answer # "n"
END Weiter;
PROCEDURE Exit(x, y: MazeIndex) : BOOLEAN;
(* Liegt (x,y) am Rand des Labyrinths? *)
BEGIN
RETURN (x = 0) OR (x = height -1) OR
(y = 0) OR (y = width -1) OR
(x = entry) & (y = 0)
END Exit;
PROCEDURE PreviousDirection(dir: Direction) : Direction;
(* nach rechts schauen *)
BEGIN
RETURN (dir - 1) MOD 4
END PreviousDirection;
PROCEDURE NextDirection(dir: Direction) : Direction;
(* nach links schauen *)
BEGIN
RETURN (dir + 1) MOD 4
END NextDirection;
PROCEDURE Longer(depth, startx, starty: INTEGER): BOOLEAN;
BEGIN
RETURN depth + ABS(startx - exit) + ABS(starty - (width - 1))
>= best;
END Longer;
PROCEDURE SolveMaze(VAR maze: Maze; depth: INTEGER;
width, height: MazeSize;
startx, starty: MazeIndex);
(* Finden und Markieren eines Weges durch das Labyrinth `maze'
mit den gegebenen Seitenlaengen `width' und `height' und
mit der Startposition (startx, starty)
nach der rechten Hand-Regel;
bei einer Startposition in der Mitte des Labyrinths kann
der Algorithmus beliebig lange laufen, wenn es Inseln oder
Einschluesse gibt;
die Optionen (globale Variablen) stepwise und query werden honoriert
*)
VAR
x, y: MazeIndex;
(* aktuelle Zeilen- und Spaltenposition im Labyrinth *)
direction: Direction;
(* aktuelle Richtung *)
clockwise: BOOLEAN;
(* Bessere Richtung zum Ausgang *)
BEGIN (* SolveMaze *)
INC(calls);
IF (startx < 0) OR (starty < 0) OR (startx = height) OR (starty = width)
OR (maze[startx, starty] # space) OR (Longer(depth, startx, starty))
THEN RETURN END;
IF Exit(startx, starty) & ((startx # entry) OR (starty # 0)) THEN
best := depth;
bestmaze := maze;
bestmaze[startx, starty] := walk;
RETURN
END;
x := startx; y := starty;
maze[x, y] := walk;
direction := east;
IF stepwise THEN
WriteMaze(maze, width, height);
IF query & ~Weiter() THEN
HALT(1);
END;
END;
REPEAT
INC(x, dx[direction]); INC(y, dy[direction]);
SolveMaze(maze, depth + 1, width, height, x, y);
DEC(x, dx[direction]); DEC(y, dy[direction]);
direction := NextDirection(direction);
UNTIL direction = east;
maze[x, y] := space;
END SolveMaze;
BEGIN
ProcessArgs;
dx[east] := 0; dx[south] := 1; dx[west] := 0; dx[north] := -1;
dy[east] := 1; dy[south] := 0; dy[west] := -1; dy[north] := 0;
calls := 0; best := MAX(INTEGER);
IF ReadMaze(input, maze, width, height, entry, exit) THEN
bestmaze := maze;
best := width * height;
SolveMaze(maze, 0, width, height, entry, 0);
WriteMaze(bestmaze, width, height);
Write.String("Kuerzester Weg: "); Write.Int(best, 3);
Write.String(". #Aufrufe: "); Write.Int(calls, 3); Write.Ln;
END;
END BestPath.
Ingo Melzer, 26. Mai 1999