Rekursionen abbrechen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

andi_wand hat geschrieben:Backtracking->Rekursion, so wurde mir das erklärt, und daran muss ich mich (leider) halten, ...
Das ist aber schlicht falsch! Man kann Rekursion sehr einfach beim Backtracking einsetzen, aber identisch sind diese Begriffe nicht. Ich kann Backtracking auch ohne Rekursion anwenden.

Im übrigen: Ich habe Dir doch die Schritte beschrieben, wie ich meinen rekursiven Ansatz aufgebaut habe. Das ist doch nun wirklich einfach umzusetzen, oder nicht?

Alles, was ich davor über Optimierungen schrieb ist hier vollkommen irrelevant - wie ich ja auch schon vermutete.

Hätte ich diese Infos eher gehabt, hätte ich vermutlich auch die Rekursion weggelassen. Immerhin begrenzt diese die Größe der Labyrinthe drastisch. Zudem hätte man sich dann eher in Richtung A* orientieren können.
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
BlackJack

@Hyperion: Rekursion ist die einfachste Art so eine Backtracking-Lösung zu formulieren — wenn man Rekursion verstanden hat. Für eine Hausaufgabe könnte man das machen. Für reale Fälle muss man bei CPython halt immer schauen wie gross die Gefahr ist ins Rekursionslimit zu laufen. Wenn die Karten grösser sein können, dann würde ich eine iterative Lösung schreiben, die den Stack selbst verwaltet. Dann hat man im Übrigen auch keine Probleme sofort bei einer Lösung die Funktion zu verlassen.

@andi_wand: Irgendwie habe ich das Gefühl Du hast meinen Beitrag und den Quelltext im anderen Thread nicht gelesen. Das sieht ja immer noch so gruselig aus. :-P Wenn Du schon keine vernünftigen Datenstrukturen verwendest um diese ``if``\s zu vermeiden, könntest Du wenigstens die Existenz von ``elif`` anerkennen. :twisted:

Ich glaube mit diesen „Optimierungen“ solltest Du auch warten bis Du eine triviale aber funktionierende Lösung hast. Ich glaube kaum das der Geschwindigkeitsgewinn im Verhältnis zum Aufwand steht.
andi_wand
User
Beiträge: 37
Registriert: Samstag 3. Dezember 2011, 17:04

@BlackJack: Ich bin grad dabei, das Ding auf ein halbwegs anständiges Maß herunterzubrechen (damit es ähnlich wie dein Quelltext aussieht). Aber ein alter Mann ist nun mal kein D-Zug ;-)
elif mochte mein Python irgend wie nicht, das hat da immer herum gesponnen...
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

@BlackJack: Ja, das war mir schon klar ;-) Aber Du stimmst mir sicher zu, dass Backtracking und Rekursion nicht das gleiche sind, oder?

@andi_wand: Was fehlt Dir denn jetzt noch bzw. wo hakt es? Waren meine fünf Schritte nicht ausreichend verständlich?
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
BlackJack

@Hyperion: Ja klar, da stimme ich Dir zu. Backtracking heisst nur, dass man bei einer Sackgasse zu einem Punkt zurückkehrt, bei dem noch andere Lösungswege offen sind. Ob man sich die Daten dazu explizit in einer Liste merkt, oder sie implizit in den lokalen Namensräumen der Funktionsaufrufe stehen hat, ändert am Verfahren nichts grundsätzliches.
andi_wand
User
Beiträge: 37
Registriert: Samstag 3. Dezember 2011, 17:04

@Hyperion: Wenn es irgendwo zu haken anfängt, melde ich mich hier nochmal, ok? Bis jetzt gehts.
Vielen Dank für die Hilfe
BlackJack

Nur so zur Info: Ich habe es jetzt auch mal implementiert. :-)

Dabei bin ich in vier wesentlichen (?) Punkten von der Aufgabenstellung abgewichen, und hätte das auch gemacht wenn ich das als Uni-Hausaufgabe abgeben müsste. Natürlich mit Erklärungen.

1. Das wichtigste (!?) ist natürlich die Namensgebung. ;-) In Python verwendet man laut PEP 8 -- Style Guide for Python Code für alles ausser Klassen und „Konstanten“ Kleinbuchstaben mit Unterstrichen. Also zum Beispiel `search_maze()` statt `searchMaze()`.

2. Statt eines Dateinamens nimmt die `__init__` ein iterierbares Objekt über Zeilen des Labyrinths entgegen und für das Laden über einen Dateinamen gibt es eine Klassenmethode (→ `classmethod()`). Das man Labyrinthe über die `__init__` nur mittels einer Datei erstellen kann, wäre eine schlechte, weil unnötig einschränkende API. Man möchte Labyrinthe ja vielleicht auch per Code erstellen, aus einer Datenbank holen, oder für Tests direkt in den Quelltext schreiben, ohne das man jedes mal gezwungen ist mindestens temporär eine Datei zu erstellen um ein `Maze`-Exemplar zu erzeugen. Aus ``maze = Maze('maze1.txt')`` wird also ``maze = Maze.load('maze1.txt')``.

3. Statt einer Methode `getStart` gibt es ein Attribut `start`. Selbst wenn man sich später noch einmal umentscheiden sollte, kann man aus dem Attribut ein `property()` machen, ohne dass sich die API ändert.

4. Die API von `searchMaze()` ist redundant. Da ein `Maze` die Startposition kennt, macht es keinen Sinn, dass man `searchMaze()` mit der Startposition und dem Labyrinth aufrufen muss. Das Labyrinth reicht völlig aus.

In der rekursiven Lösung habe ich dann eine Ausnahme verwendet um bei einer gefundenen Lösung einfach aus den rekursiven Aufrufen heraus zu kommen.

Dann habe ich auch gleich noch eine iterative Alternative implementiert.
andi_wand
User
Beiträge: 37
Registriert: Samstag 3. Dezember 2011, 17:04

@BlackJack:
Zum Punkt 1: Hab ich auch so gemacht
Frage von meiner Seite aus: Ich habe die Funktion suggest() jetzt wie folgt implementiert:

Code: Alles auswählen

def suggest_dir(pos,env):
    (x,y)=pos
    result=list()
    for direction in DIRECTIONS:
        (x_new,y_new)=direction
        field=env[x+x_new][y+y_new]
        if(field==FINISH_CHAR):
            return [dir]
        if (field==FREE_CHAR):
            result.append(dir)
    return result
Der Rest analog zum Vorschlag oben.
Wenn ich jetzt für folgendes Labyrinth die Funktion aufrufe:

Code: Alles auswählen

#######
#S       F#
#######
und den Rückgabewert printen lasse, erhalte ich

Code: Alles auswählen

[<built-in function dir>, <built-in function dir>]
,
jedoch nicht den erwarteten Wert

Code: Alles auswählen

(1,0)
Wieso?
Vielen Dank
Benutzeravatar
sparrow
User
Beiträge: 4535
Registriert: Freitag 17. April 2009, 10:28

1. Versuch mal:

Code: Alles auswählen

help(dir)
2. Wo genau definierst du eigentlich dir, dessen Name so unglücklich gewählt ist?
andi_wand
User
Beiträge: 37
Registriert: Samstag 3. Dezember 2011, 17:04

Nirgends...
(Hätt ich aber auch selbst merken können)
andi_wand
User
Beiträge: 37
Registriert: Samstag 3. Dezember 2011, 17:04

@all:
So, meine Funktion ist rekursiv, und funktioniert.
Vielen Dank an alle für die Hilfe.
Wenn sich jemand das Ding noch zur Optimierung ansehen will:

Code: Alles auswählen

'''
Created on 07.12.2011

@author: Roland-User
'''
import threading
import time
import sys

DIRECTIONS = RIGHT, LEFT, UP, DOWN=[(1,0),(-1,0),(0,-1),(0,1)]
DIRECTION_TO_STR = { RIGHT: 'rechts', LEFT: 'links', UP: 'oben', DOWN: 'unten' }
FINISH_CHAR="F"
FREE_CHAR=" "
VISITED_CHAR="."

def suggest_dir(pos,env):
    (x,y)=pos
    result=list()
    for direction in DIRECTIONS:
        (x_new,y_new)=direction
        field=env[x+x_new][y+y_new]
        if(field==FINISH_CHAR):
            return [direction]
        if (field==FREE_CHAR):
            result.append(direction)
    return result

class maze:
    maze_Rows=[]
    
    def __init__(self,Input_Filename):
        self.Input_File=open(Input_Filename,'r');
        self.maze_File=self.Input_File.readlines();
        self.read_In()
    'Destruktor der Klasse, wird aufgerufen, wenn die Klasse nicht mehr existiert. Hier wird die Labyrinth-Datei wieder geschlossen'
    def __del__(self):
        self.Input_File.close()
    'read_In: Die Funktion bearbeitet die eingelesenen Daten so, dass Zeilenumbrueche wegfallen, und schreibt sie in die Variable maze_Rows'
    def read_In(self):
        for i in xrange(len(self.maze_File)):
            if i+1 < len(self.maze_File):
                self.storage=self.maze_File[i]
                self.storage=self.storage[:len(self.storage)-1]
                self.maze_File[i]=self.storage
        for i in xrange(len(self.maze_File)):
            storage=[]
            for j in xrange(len(self.maze_File[i])):
                storage.append(self.maze_File[i][j])
            self.maze_Rows.append(storage)
        'Nun muss noch x und y vertauscht werden'
        maze_Temp=[]
        for i in xrange(len(self.maze_Rows[0])):
            storage=[]
            for j in xrange(len(self.maze_Rows)):
                storage.append(self.maze_Rows[j][i])
            maze_Temp.append(storage)
        self.maze_Rows=maze_Temp
        #print self.maze_Rows
    '__getitem__ gibt einfach maze_Rows an der Stelle (x,y) aus'
    def __getitem__(self,args):
        print self.maze_Rows[args[0]][args[1]]
    'Die Funktion __setitem__ erlaubt es, bestimmte Zellen innerhalb des Labyrinths mit eigenen Daten zu fuellen'
    def __setitem__(self,args,input_args):
        self.maze_Rows[args[0]][args[1]]=input_args
        return 1
    'Diese Funktion ist fuer das korrekte funktionieren des Befehls "print <Klasse>" zustaendig'
    def __str__(self):
        druck=""
        '''
        j=len(self.maze_Rows)-1
        while j >=0:
            i=len(self.maze_Rows[0])-1
            while i >=0:
                druck=druck+str(self.maze_Rows[j][i])
                i=i-1
            druck=druck+str('\n')
            j=j-1
        '''
        j=len(self.maze_Rows[0])-1
        for i in xrange(len(self.maze_Rows)-1,-1,-1):
            for j in xrange(len(self.maze_Rows[i])-1,-1,-1):
                druck=druck + str(self.maze_Rows[i][j]) + " "
            druck=druck + str('\n')
        return druck
    'getStart gibt den Ort des Startpunktes zurueck'
    def getStart(self):
        for i in xrange(len(self.maze_Rows)):
            for j in xrange(len(self.maze_Rows[i])):
                if(self.maze_Rows[i][j]=='S'):
                    return i,j
                else:
                    pass
    'getFinish gibt den Ort des Zielpunktes zurueck'
    def getFinish(self):
        for i in xrange(len(self.maze_Rows)):
            for j in xrange(len(self.maze_Rows[i])):
                if(self.maze_Rows[i][j]=='F'):
                    return i,j
                else:
                    pass
                
    def solve_maze(self,pos):
        (x,y)=pos
        suggested_dir=suggest_dir(pos,self.maze_Rows)
        print self.__str__()
        #print suggest_dir(pos,self.maze_Rows)
        if (x, y) == self.getFinish():
                print self.__str__()
                print 'Finished'
                sys.exit()
        else:
            suggested_dir=suggest_dir(pos,self.maze_Rows)
            if(len(suggested_dir)==0):
                print "Sackgasse"
                print pos
                self.maze_Rows[pos[0]][pos[1]]=VISITED_CHAR
                return 1
            else:
                for direction in suggested_dir:
                    (x_delta,y_delta)=direction
                    self.maze_Rows[x][y]=VISITED_CHAR
                    self.solve_maze((x+x_delta,y+y_delta))
                    
        
        
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Oha... das sieht alles ein wenig unaufgeräumt auf. Wieso gibt es zwischen den Methode keine Leerzeilen? Alleine das dürfte schon Wuneder bewirken.

Da sind viele Hämmer drin, ich schnappe mir mal einige wichtige heraus.

- Vergiss mal, dass es einen Destruktor gibt! Der funktioniert nicht so, wie Du Dir das denkst!

- Dateien öffnet man mit ``with open() as handler``. Damit ist sichergestellt, dass die Datei auf jeden Fall geschlossen wird.

- ``sys.exit`` würde ich in einer Methode einer Klasse nicht erwarten / einsetzen!

- Du verwendest (immer noch) den absoluten Anit-Pattern: ``for i in xrange(len(iterable)):``. Man kann über Iterables direkt iterieren; benötigt man einen Index, verwendt man ``enumerate``:

Code: Alles auswählen

for index, item in enumerate(iterable):
- wieso testet Deine ``suggest_dir``-Funktion auf das Finish? Das bringt Dir doch rein gar nichts! Zudem: Wieso ist das auf einmal eine Funktion und keine Methode der Klasse?

- eine leere Liste hat den Wahrheitswert False. (Doku, Abschnitt4: Built-in Types, Abschnitt 4.1) Also kannst Du das ``if(len(suggested_dir)==0):`` einfach so schreiben:

Code: Alles auswählen

if not suggested_dir:
- Tupel kann man ohne "()" entapcken:

Code: Alles auswählen

False
>>> pos = (0, 1)
>>> x, y = pos
>>> print(x, y)
0 1
- wieso ``return 1``? Du fragst diesen Wert ja nie ab!

- ein ``else: pass`` ist eigentlich nie notwendig.

- DocStrings gehören imho direkt unter einen Deklarationskopf, also unter die ``class`` oder ``def`` Zeilen.

- Wenn Du Python 2.x benutzt, sollten Klassen von ``object`` erben.

- Bist Du sicher, dass ``maze_Rows`` ein Klassenattribut sein soll?

- Wozu importierst Du ``threading`` und ``time``?

- Es fehlt ein Encoding-Coockie und ein Shebang zu Beginn der Datei ;-)

Ganz wichtig zum Schluss: Ich sehe irgend wie nicht, wie Du Die den richtigen Pfad "merkst"? Insofern ist das imho kein richtiges Backtracking - aber vielleicht denke ich da auch zu "streng".
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
BlackJack

@andi_wand: Das wäre etwas schöner zu lesen, wenn Du Dich an den PEP 8 -- Style Guide for Python Code halten würdest und nicht alles so „aneinander kleben“ würde.

Falls die Zeichenketten mit den Kommentareb DocStrings werden sollten, dann stehen sie an der falschen Stelle. Die gehören *hinter* die Definitionszeilen. Nur dann werden sie von Python als DocStrings erkannt und entsprechend verarbeitet.

Um Bedingungen muss man keine Klammern setzen.

`__del__()` ist eine ganz böse Falle! Das ist *kein* deterministischer Destruktor. Vergiss am besten, dass es diese Methode überhaupt gibt. Wenn man nicht genau weiss wie das intern funktioniert, sollte man die Finger davon lassen. Selbst wenn `__del__()` das tun würde, was Du vermutest, wäre es unsinnig die Datei solange offen zu lassen wie das Objekt besteht.

`maze_Rows` auf Klassenebene hat da sicher nichts zu suchen.

Was Deine `readIn()`-Methode da macht, habe ich nicht verstanden!? Das sieht mir auch zu umständlich aus um es näher anzuschauen, denn alles was Du da machst ist sicher so nicht nötig. Das sieht auch nicht nach Python aus, sondern nach einer anderen Sprache.

Du führst ausserhalb der `__init__()` neue Attribute auf dem Objekt ein — das sollte man nicht machen. Ich denke auch nicht, dass die alle *überhaupt* auf das Objekt gehören.

`__getitem__()` ist falsch implementiert. Das muss den Wert *zurück-* und nicht *aus*geben. Und das ist in der Regel zusammen mit `__setitem__()` in der Regel auch der Ort wo die Koordinaten „vertauscht“ werden, damit die Daten weiterhin als Sequenz von Zeilen repräsentiert werden können. Diese interne Darstellung zu transponieren, macht den Rest des Programms nur umständlicher.

`__setitem__()` sollte keinen Wert zurück geben. Der Rückgabewert wird sowieso „verschluckt“.

Die `__str__()` ist nur so kompliziert, weil Du die interne Darstellung transponiert hast. Sonst wäre das ein Einzeiler ohne die ganzen gruseligen Indexe und das ``for i in xrange(len(obj)):``-Anti-Pattern. Das ist kein idiomatisches Python.

Das gleiche gilt für `getStart()` und `getFinnish()`. Man kann über Elemente in Listen *direkt* iterieren, ohne einen Umweg über einen Index zu gehen. Falls man den Index *zusätzlich* benötigt, gibt es die `enumerate()`-Funktion.

Die „magischen“ Methoden sollte man nicht direkt aufrufen, wenn man nicht muss. Für `__str__()` sollte das nie der Fall sein.

Ein `sys.exit()` in einer Methode die einen allgemeinen Algorithmus implementiert ist der Hammer. Stell Dir mal vor die Aufgabe würde ganz leicht anders lauten: Lösen sie alle Labyrinthe in Verzeichnis ``spam/``. Normaler Code sollte niemals das Programm einfach so beenden.

Laut Aufgabenstellung soll `solve_maze()` als Funktion implementiert werden.

`suggest_dir()` solltest Du das `maze`-Exemplar übergeben und nicht die interne Repräsentation des selben. Und wenn Du die `__getitem__()` reparierst, dann kannst Du auch über den Index-Operator auf die Felder zugreifen und musst nicht überall über die interne Repräsentation gehen.

Bei Containerobjekten sind leere Container im Wahrheitskontext falsch. Das wird üblicherweise auch ausgenutzt, also statt ``if len(things) == 0:`` schreibt man ``if not things:``.

Last but not least funktioniert der Code so nicht, weil bereits besuchte Felder nicht wieder freigegeben werden, man also am Ende mehr als den Pfad mit '.' markiert haben kann.

Die Module `time` und `threading` scheinen nirgends verwendet zu werden!?
Benutzeravatar
/me
User
Beiträge: 3561
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Hyperion hat geschrieben:Da sind viele Hämmer drin, ich schnappe mir mal einige wichtige heraus.
Ergänzung: Die Klammern bei den if-Statements sind überflüssig.
Benutzeravatar
/me
User
Beiträge: 3561
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

andi_wand hat geschrieben:Wenn sich jemand das Ding noch zur Optimierung ansehen will:
Ich habe mir die Methoden __init__, __del__ und read_In einmal angesehen. Dabei habe ich neben dem Code noch ein paar Namen optimiert. Übrig bleibt das da:

Code: Alles auswählen

    def __init__(self, input_filename):
        with open(input_filename, 'r') as fp:
            maze_data = fp.readlines()
        self.parse_file_data(maze_data)

    def parse_file_data(self, maze_data):
        data = [list(row.strip()) for row in maze_data]
        self.maze = [list(row) for row in itertools.izip(*data)]
Ich frage mich auch, wozu du das Vertauschen der x- und y-Koordinaten brauchst. Soll die Ausgabe nicht einfach genau so aussehen wie in der eingelesenen Datei? In dem Fall kannst du hier das Vertauschen weglassen und die __str__-Methode wird zu einem Einzeiler. (Gut, das geht auch jetzt schon als Einzeiler, aber etwas unübersichtlicher mit doppelter Verwendung von reversed())
Benutzeravatar
/me
User
Beiträge: 3561
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Ich hätte es selber sicher anders implementiert, aber das hier ist eine aufgeräumtere (und funktionierende) Version des bestehenden Codes. Verbesserungspotenzial ist noch vorhanden, aber ich wollte mich jetzt auch nicht ewig damit beschäftigen.

Code: Alles auswählen

# -*- coding: utf-8 -*-

from __future__ import print_function
from __future__ import unicode_literals

import itertools

FIELD_START = 'S'
FIELD_TARGET = 'F'
FIELD_FREE = " "
FIELD_VISITED = "."

DIRECTIONS = RIGHT, LEFT, UP, DOWN = [(1, 0), (-1, 0), (0, -1), (0, 1)]
#DIRECTION_TO_STR = {RIGHT: 'rechts', LEFT: 'links', UP: 'oben', DOWN: 'unten'}

class Maze(object):
    def __init__(self, input_filename):
        self.labyrinth = []
        self.start_location = None
        self.target_location = None
        with open(input_filename, 'r') as fp:
            maze_data = fp.readlines()
        self.parse_file_data(maze_data)

    def __str__(self):
        """String-Repräsentation des Labyrinths"""
        return '\n'.join(' '.join(row) for row in self.labyrinth)

    def get_location(self, key):
        for i, row in enumerate(self.labyrinth):
            for j, field in enumerate(row):
                if field == key:
                    return i, j

    def parse_file_data(self, maze_data):
        """Konvertiert die Daten in die interne Struktur"""
        self.labyrinth = [list(row.strip()) for row in maze_data]
        self.start_location = self.get_location(FIELD_START)
        self.target_location = self.get_location(FIELD_TARGET)


    def print_maze(self, pos, maze, *args):
        print('{x}/{y}\n{maze}\n{extra}\n'.format(
            x=pos[1],
            y=pos[0],
            maze=maze,
            extra='\n'.join(args)))

    def solve(self, pos=None):
        if pos:
            x, y = pos
        else:
            x, y = pos = self.start_location
        if (x, y) == self.target_location:
            self.print_maze(pos, self, 'Finished')
            return True
        else:
            suggested_direction = self.suggest_direction(pos)
            if not suggested_direction:
                self.labyrinth[pos[0]][pos[1]] = FIELD_VISITED
                self.print_maze(pos, self, 'Sackgasse')
                self.labyrinth[pos[0]][pos[1]] = FIELD_FREE
            else:
                for direction in suggested_direction:
                    x_delta, y_delta = direction
                    self.labyrinth[x][y] = FIELD_VISITED
                    self.print_maze(pos, self)
                    found = self.solve((x + x_delta, y + y_delta))
                    if found:
                        return True
                    self.labyrinth[x][y] = FIELD_FREE
        return False

    def suggest_direction(self, pos):
        x, y = pos
        result = []
        for direction in DIRECTIONS:
            x_new, y_new = direction
            field = self.labyrinth[x + x_new][y + y_new]
            if field == FIELD_TARGET:
                return [direction]
            if field == FIELD_FREE:
                result.append(direction)
        return result

def main():
    maze = Maze('maze.txt')
    maze.solve()

if __name__ == '__main__':
    main()
BlackJack

Meine Implementierung. Die Suchfunktion ist zweimal vorhanden — einmal rekursiv und einmal iterativ. Die Aufgabe erwähnt Fehler in Labyrinthen auf die man achten soll, darum prüfe ich die Anzahl der Start- und Zielfelder in der `__init__()`.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-


TEST_DATA = """\
########
#F     #
# ######
#      #
# ## ###
#  #  S#
########
""".splitlines()


class Maze(object):
    
    WALL = '#'
    FREE = ' '
    VISITED = '.'
    START = 'S'
    FINISH = 'F'
    
    def __init__(self, rows):
        self.rows = [list(row) for row in rows]
        self.start = None
        self.finish = None
        for coordinate, field in self:
            if field == self.START:
                if self.start is not None:
                    raise ValueError('More than one starting position')
                self.start = coordinate
            elif field == self.FINISH:
                if self.finish is not None:
                    raise ValueError('More than one finish position')
                self.finish = coordinate
        if not self.start:
            raise ValueError('No start found')
        if not self.finish:
            raise ValueError('No finish found')
    
    def __str__(self):
        return '\n'.join(''.join(row) for row in self.rows)
    
    def __getitem__(self, coordinate):
        x, y = coordinate
        return self.rows[y][x]
    
    def __setitem__(self, coordinate, value):
        x, y = coordinate
        self.rows[y][x] = value
    
    def __iter__(self):
        for y, row in enumerate(self.rows):
            for x, field in enumerate(row):
                yield (x, y), field
    
    def iter_candidates(self, coordinate):
        x, y = coordinate
        for x_delta, y_delta in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            candidate = (x + x_delta, y + y_delta)
            if self[candidate] in [self.FREE, self.FINISH]:
                yield candidate
    
    @classmethod
    def load(cls, filename):
        with open(filename) as lines:
            return cls(line.rstrip() for line in lines)

#{ Rekursive Suche

def search_maze(maze):
    path = list()
    
    def search(position):
        path.append(position)
        maze[position] = maze.VISITED
        if position == maze.finish:
            return True
        for candidate in maze.iter_candidates(position):
            if search(candidate):
                return True
        maze[position] = maze.FREE
        path.pop()
        return False
    
    search(maze.start)
    return path

#{ Iterative Suche

class Frame(object):
    def __init__(self, position, candidates=None):
        self.position = position
        self.candidates = candidates


def search_maze(maze):
    stack = [Frame(maze.start)]
    while stack:
        frame = stack[-1]
        
        if frame.candidates is None:
            maze[frame.position] = maze.VISITED
            if frame.position == maze.finish:
                break
            frame.candidates = maze.iter_candidates(frame.position)

        try:
            stack.append(Frame(frame.candidates.next()))
        except StopIteration:
            maze[frame.position] = maze.FREE
            stack.pop()
    
    return [frame.position for frame in stack]

#}

def main():
    maze = Maze(TEST_DATA)
    print maze
    print search_maze(maze)
    print maze


if __name__ == '__main__':
    main()
Edit: Ausnahme aus der rekursiven und das redundante `path` aus der iterativen Lösung entfern.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Na dann mal meine Variante. Ich hatte die vor Posting der Aufgabenstellung gebaut; insofern ohne Klasse.
Link
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
BlackJack

Mir fällt gerade bei meiner iterativen Lösung auf, dass `path` redundant ist. Die Information steckt ja auch in den Objekten auf dem `stack` schon.
Benutzeravatar
pillmuncher
User
Beiträge: 1530
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Meine Lösung ist Q&D-fähig[*]:

Code: Alles auswählen

START = 'S'
GOAL = 'F'
FREE = ' '
VISITED = '.'


class Maze(object):

    def __init__(self, maze_lines):
        self._data = [list(line.rstrip()) for line in maze_lines if line.strip()]
        for row, fields in enumerate(self._data):
            try:
                self.start = fields.index(START), row
                break
            except ValueError:
                continue
        else:
            raise ValueError('Maze has no starting point.')

    def neighbours(self, (x, y)):
        if 0 <= x - 1:
            yield x - 1, y
        if x + 1 < len(self._data[y]):
            yield x + 1, y
        if 0 <= y - 1:
            yield x, y - 1
        if y + 1 < len(self._data):
            yield x, y + 1

    def __getitem__(self, (x, y)):
        return self._data[y][x]

    def __setitem__(self, (x, y), item):
        self._data[y][x] = item

    def __str__(self):
        return '\n'.join(''.join(line) for line in self._data)


def search_maze(current, maze):
    for neighbour in maze.neighbours(current):
        field = maze[neighbour]
        if field == GOAL:
            return True
        elif field == FREE:
            maze[neighbour] = VISITED
            if search_maze(neighbour, maze):
                return True
            maze[neighbour] = FREE


raw_maze = """
########
#F     #
# ######
#      #
# ## ###
#  #  S#
########
""".splitlines()


if __name__ == '__main__':

    maze = Maze(raw_maze)
    print maze
    print
    search_maze(maze.start, maze)
    print maze
Ergebnis:

Code: Alles auswählen

########
#F     #
# ######
#      #
# ## ###
#  #  S#
########

########
#F     #
#.######
#....  #
# ##.###
#  #..S#
########
[*]quick & dirty
In specifications, Murphy's Law supersedes Ohm's.
Antworten