Rekursionen abbrechen

[andi_wand]

@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))
                    
        
        

[Hyperion]

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".

[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!?

[/me]

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

Ergänzung: Die Klammern bei den if-Statements sind überflüssig.

[/me]

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())

[/me]

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.

[Hyperion]

Na dann mal meine Variante. Ich hatte die vor Posting der Aufgabenstellung gebaut; insofern ohne Klasse.
Link

[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.

[pillmuncher]

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

[andi_wand]

So, aktueller Stand ist wie folgt:

Code: Alles auswählen

'''
Created on 07.12.2011

@author: Roland-User
'''
# -*- coding: iso-8859-1 -*-

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:
    
    def __init__(self,Input_Filename):
        self.Input_File=open(Input_Filename,'r')
        self.maze_File=self.Input_File.readlines()
        self.maze_Rows=[]
        self.correct=False
        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)
        self.Input_File.close()
        print self.maze_Rows
        print len(self.maze_Rows)
    '__getitem__ gibt einfach maze_Rows an der Stelle (x,y) aus'
    def __getitem__(self,(x,y)):
        return self.maze_Rows[y][x]
    'Die Funktion __setitem__ erlaubt es, bestimmte Zellen innerhalb des Labyrinths mit eigenen Daten zu fuellen'
    def __setitem__(self,(x,y),input_args):
        try:
            self.maze_Rows[y][x]=input_args
        except IndexError:
            print "Der angegebene Index ist ausserhalb des Labyrinths"
        except:
            print "Ein Fehler ist aufgetreten"
    'Diese Funktion ist fuer das korrekte funktionieren des Befehls "print <Klasse>" zustaendig'
    def __str__(self):
        return '\n'.join(' '.join(line) for line in self.maze_Rows)
    '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.__getitem__((j, i))=='S'):
                    return i,j
                else:
                    pass
        return False
    '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.__getitem__((j,i))=='F'):
                    return i,j
                else:
                    pass
        return False        
    def solve_maze(self,pos):
        print self.__str__()
        if (self.getFinish() and self.getStart()) or self.correct:
            self.correct=True
            (x,y)=pos
            suggested_dir=suggest_dir(pos,self.maze_Rows)
            #print suggest_dir(pos,self.maze_Rows)
            if (x, y) == self.getFinish():
                    print self.__str__()
                    print 'Maze solved'
            else:
                suggested_dir=suggest_dir(pos,self.maze_Rows)
                if not suggested_dir:
                    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))
        else:
            print "Das Labyrinth ist nicht loesbar, da wichtige Punkte fehlen. Bitte geben Sie ein gueltiges Labyrinth an und starten Sie"
            print "dann das Skript erneut"
                    
        
        

Folgendes Problem habe ich noch: Wie kann ich denn jetzt herausfinden, ob ich evtl. schon die letzte Sackgasse besucht habe, d.h. ob das Labyrinth überhaupt lösbar ist?
@BlackJack: Der Style Guide ist grad in der Umsetzung, ebenso werden die Kommentare noch umgesetzt

[andi_wand]

Meine Idee dazu war, dass ich mir merke, wie viele Kreuzungen ich bereits besucht habe, und diese nacheinander wieder abklappere. Wenn ich keine Kreuzung mehr habe, aber das Ziel noch nicht erreicht habe->Labyrinth ist nicht lösbar.
Aber das Programm zählt ja auf dem Hinweg alle Kreuzungen, auf dem Rückweg leider nicht...

[/me]

So, aktueller Stand ist wie folgt:

Code: Alles auswählen

[...]
    def getStart(self):
        for i in xrange(len(self.maze_Rows)):
            for j in xrange(len(self.maze_Rows[i])):
                if(self.__getitem__((j, i))=='S'):
                    return i,j
                else:
                    pass
        return False
[...]

Ich muss es leider so deutlich sagen: Das liefert zwar wahrscheinlich das gewünschte Ergebnis, ist aber vom Stil her immer noch ein Haufen Müll.

Folgendes Problem habe ich noch: Wie kann ich denn jetzt herausfinden, ob ich evtl. schon die letzte Sackgasse besucht habe, d.h. ob das Labyrinth überhaupt lösbar ist?

Was dir fehlt ist ein passender Rückgabewert aus der rekursiven Funktion der anzeigt, ob das Zielfeld gefunden wurde. Schau dir doch mal die bereits geposteten Lösungen an. Meine baut ja sogar auf deinem Programm auf.

[andi_wand]

So, letzer Stand:

Code: Alles auswählen

import time

DIRECTIONS = RIGHT, LEFT, UP, DOWN = [(1,0),(-1,0),(0,-1),(0,1)]
FINISH_CHAR="F"
FREE_CHAR=" "
VISITED_CHAR="."
BLOCK_CHAR="*"

def suggest_dir(pos,env):                           #"""Die Funktion suggest_dir prueft, in welche Richtungen ein Laufen moeglich ist"""
    (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:                                         #"""Klasse Maze"""
    
    def __init__(self,Input_Filename):              #"""Konstruktor der Klasse Maze, liest das Labyrinth ein"""
        try:
            self.Input_File=open(Input_Filename,'r')
        except IOError:
            print "File does not exist"
        self.maze_Rows=[]
        self.correct=False
        self.LabSolved=False
        self.convert_data(self.Input_File)
        self.recursion_deep=0
        
        
    def convert_data(self,maze_File):               #"""convert_data wandelt den eingelesenen String in eine mehrdimensionale Liste um"""
        self.maze_Rows=[list(row.strip()) for row in maze_File]
    
    def __getitem__(self,(x,y)):                    #"""__getitem__ liefert den Wert des Labyrinths an der Stelle x,y zurueck"""
        return self.maze_Rows[y][x]
    
    def __setitem__(self,(x,y),input_args):         #"""Mit __setitem__ kann man den Wert des Labyrinths an der Stelle (x,y) auf den Wert input_args setzen"""
        try:
            self.maze_Rows[y][x]=input_args
        except IndexError:
            print "Der angegebene Index ist ausserhalb des Labyrinths"
        except:
            print "Ein Fehler ist aufgetreten"
    
    def __str__(self):                              #"""Diese Funktion ist fuer das korrekte funktionieren des Befehls "print <Klasse>" zustaendig"""
        maze_clear=self.maze_Rows
        for i,row in enumerate(maze_clear):
            for j,position in enumerate(row):
                if(position==BLOCK_CHAR):
                    maze_clear[i][j]=" "
                else:
                    pass
        return '\n'.join(' '.join(line) for line in maze_clear)
    
    def getPosition(self, key):                     #"""getPosition gibt den Ort eines beliebigen Wertes zurueck"""
        for i,row in enumerate(self.maze_Rows):
            for j,position in enumerate(row):
                if(position==key):
                    return i,j
                else:
                    pass
        return False
    
    def getFinish(self):                            #"""getFinish gibt den Ort des Zielpunktes zurueck"""
        return self.getPosition("F")
    
    def getStart(self):                             #"""getStart gibt den Ort des Startpunktes zurueck"""
        return self.getPosition("S")
           
    def solve_maze(self,pos):                       #"""solve_maze loest das uebergebene Labyrinth"""
        print self.recursion_deep
        #time.sleep(0.5)
        if pos:
            (x,y)=pos
        else:
            pos=self.getStart()
        if pos==self.getFinish():
            print self.__str__()
            print "Maze solved"
            self.LabSolved=True
        if (self.getFinish() and self.getStart()) or self.correct:
            if not self.LabSolved:
                self.correct=True
                suggested_dir=suggest_dir(pos,self.maze_Rows)
                if not suggested_dir:
                    if(self.recursion_deep==1):
                        print "Labyrinth kann nicht geloest werden"
                        return False
                    else:
                        self.maze_Rows[pos[0]][pos[1]]=BLOCK_CHAR
                        #print "Sackgasse"
                        #print pos
                        #self.maze_Rows[pos[0]][pos[1]]=FREE_CHAR
                else:
                    for direction in suggested_dir:
                        (x_delta, y_delta)=direction
                        self.maze_Rows[x][y]=VISITED_CHAR
                        print self.__str__()
                        self.recursion_deep=self.recursion_deep+1
                        value=self.solve_maze((x+x_delta,y+y_delta))
                        if value:
                            return True
                        self.maze_Rows[x][y]=FREE_CHAR
                self.recursion_deep=self.recursion_deep-1
                return False
            else:
                return True
        else:
            print "Das Labyrinth ist nicht loesbar, da wichtige Punkte fehlen. Bitte geben Sie ein gueltiges Labyrinth an und starten Sie"
            print "dann das Skript erneut"
        return False
        

Ich hoffe, ich habe jetzt alle Konventionen eingehalten.
Einziger Fehler: Wenn das Labyrinth nicht lösbar ist, dann bleibt der Läufer irgend wann stehen. Wie kann ich denn den Lauf abbrechen?
Vielen Dank für eure Hilfe

[andi_wand]

Hat sich erledigt, ich denke, die restlichen Optimierungen kann ich mir schenken.
Vielen Dank an alle, die mir hier geholfen haben

[BlackJack]

@andi_wand: Die Kommentare zu den Funktionen/Methoden sind immer noch falsch. Die gehören als Zeichenkette *unter* die Definitionen, damit es DocStrings sind.

Code: Alles auswählen

def suggest_dir(pos,env):
    """Die Funktion suggest_dir prueft, in welche Richtungen ein Laufen
    moeglich ist
    """
    (x,y)=pos
    # ...

Nur *so* wird das vom Compiler erkannt und kann zur Laufzeit oder von diversen Werkzeugen ausgewertet werden.

Deine Fehlerbehandlung ist keine, da sie selber fehlerhaft ist. Wenn es zum Beispiel beim öffnen der Datei zu einer Ausnahme kommst, gibst Du den Text aus, dass die Datei nicht existiert — was nebenbei gesagt gar nicht der Fall sein muss — und machst dann einfach weiter. Was zwangsläufig zu einem `AttributeError` vier Zeilen später führt. Das ist Murks.

Genau so das ignorieren von Ausnahmen in `__setitem__()`. Einfach einen Text ausgeben und so weiter machen als wäre nichts passiert, ist keine vernünftige Fehlerbehandlung. Wenn man an einer Stelle nicht sinnvoll auf eine Ausnahme reagieren kann, dann sollte man es auch gar nicht erst versuchen. Es ist doch vollkommen in Ordnung wenn die `__setitem__()`-Methode einen `IndexError` auslöst, wenn die Koordinaten nicht im Labyrinth liegen. Der Aufrufer kann dann entscheiden was er in dem Fall tun möchte.

Und mit einem nackten ``except:`` *alle* möglichen Ausnahmen mit einer "Ein Fehler ist aufgetreten"-Ausgabe zu verschlucken ist so gar keine gute Idee.

``else: pass``!?

`recursion_deep` sollte wohl eher `recurcion_depth` heissen. Und Du solltest Dich bei der Namensgebung auf `Maze` oder `Labyrinth` festlegen. Laut Aufgabenstellung soll es `Maze` sein. Dann ist `LabSolved` aber vielleicht auch besser ein `maze_solved`. Oder nur `solved`, denn das `maze` steckt schon im Datentyp. Den Sinn dieses Attributs habe ich nicht so ganz verstanden!? `self.correct` und dass in jedem rekursiven Aufruf `getStart()` und `getFinish()` ausgeführt werden, letzteres sogar *zweimal*, ist auch etwas schräg.

Du rufst immer noch `__str__()` direkt auf.

[andi_wand]

Wie soll ich denn das sonst mit dem "except:" machen? Ich dachte mir, dass ich dann einfach alle Fehler, die sonst noch auftreten, abfange, oder mache ich das anders?

[EyDu]

Wenn du einen Fehler nicht sinnvoll behandeln kannst, dann muss dieser eben zum Absturz des gesamten Programms führen. Wenn du mit einem except alle Fehler abfängst, dan behauptest du, dass sich das Programm anschließend in einem konsistenten Zustand befindet, was aber gar nicht der Fall ist. Zu einem späteren Zeitpunkt wird das unweigerlich an einer anderen Stelle zu einer Exception springen und das Spiel geht von vorne los. Zwischendurch kann natürlich alles mögliche passieren, wie das Fehlerhafte schreiben von Datein oder sonst etwas. Hinzu kommt, dass Fehler bei einem leeren Except nicht mehr nachvollziehbar sind. Es ist zwar schön, dass du anzeigst, dass ein Fehler aufgetreten ist, aber viel wichtiger ist WELCHER Fehler aufgetreten ist, damit du das korrigieren kannst.

[andi_wand]

Vorschlag:

Code: Alles auswählen

except:
   print "Fehler"
   sys.exit()

Würde das dann gehen? Das Programm wird ja zuverlässig gestoppt.

[EyDu]

Nein, das ist total sinnlos. Du willst wissen um welchen Fehler an welcher Stelle es sich handelt. Wie willst du nach einem Fehler suchen, wenn du nicht einmal weißt um was für einen Fehler es sich handelt? Entweder lässt du also die Exception durchlaufen oder schreibst den Fehler inklusive Traceback in ein Log.