Backtracking und Python

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
canlot
Beiträge: 393
Registriert: Di Mär 08, 2011 11:01 pm
Wohnort: NRW

Backtracking und Python

Beitrag von canlot » Di Jun 03, 2014 5:08 pm

Hat jemand Ahnung von Backtracking und Python? :D
unser Prof hat ne Aufgabe gegeben wo wir rekursiv den kürzesten Weg aus einem Labyrinth finden sollten.
So weit so gut, das Attest habe ich schon also bestanden der Labyrinth ist nicht schwer gewesen, wo ich jetzt aber zu Hause mit anderen Labyrinthen probiere funktioniert es ab und zu und ab und zu nicht. Das Problem kann ich nicht genau identifizieren, schein aber so wenn um das Ziel nur einen Weg gibt versagt es.

Code: Alles auswählen

__author__ = 'Jakob'
import random
import copy
import sys
import os
import time

delimiter = "x"
finish = "E"


def feld_erstellen(feld, file):
    datei = open(file, "r")
    x = 0
    y = 0
    for line in datei:
        feld.append([])
        for char in line.rstrip():
            feld[x].append(char)
            y += 1
        y = 0
        x += 1



def feld_ausgeben(feld, route):
    x = 0
    y = 0
    temp = ""
    i = 0
    while i < route.__len__():
        while x < feld.__len__():
            while y < feld[x].__len__():
                if(route[i][0] == x and route[i][1] == y):
                    temp += "O"
                else:
                    temp += feld[x][y]
                y += 1
            print(temp)
            temp = ""
            y = 0
            x += 1
        x = 0
        time.sleep(0.5)
        os.system("cls")
        i += 1


def check(zeichen):
    if(zeichen == finish):
        return True
    elif(zeichen == delimiter):
        return False


def schon_gegangen(x,y, route):
    i = 0
    while i < route.__len__():
        if(route[i][0] == x and route[i][1] == y):
            return True
        i += 1

    return False


def backtrack(x,y, feld, route):
    if(schon_gegangen(x, y, route)):
        return False
    else:
        route.append((x, y))

    if(check(feld[x][y]) == True):
        return route
    elif(check(feld[x][y]) == False):
        return False

    
    i = 0
    returnvalue = 0
    temp_route = []
    
    while i < 4: # im Uhrzeigersinn
        if(i == 0):
            returnvalue = backtrack(x-1, y, feld, copy.copy(route))
        elif(i == 1):
            returnvalue = backtrack(x, y+1, feld, copy.copy(route))
        elif(i == 2):
            returnvalue = backtrack(x+1, y, feld, copy.copy(route))
        elif(i == 3):
            returnvalue = backtrack(x, y-1, feld, copy.copy(route))
        i += 1
        

        if(returnvalue != False):

            if(temp_route.__len__() == 0):
                temp_route = returnvalue
            if(returnvalue.__len__() < temp_route.__len__()):
                temp_route = returnvalue
            
    if(temp_route.__len__ == 0):
        return False
    else:
        return temp_route





x = 1
y = 1

route = []
feld = []

file = input("Geben Sie die Datei ein: ")

feld_erstellen(feld, file)
lol = backtrack(1, 1, feld, route)


feld_ausgeben(feld, lol)
mit dem Labyrinth funktioniert es(aus der Aufgabe):

Code: Alles auswählen

xxxxxxx
x x   x
x xx  x
x     x
xxxx  x
x     x
x xx xx
x E   x
xxxxxxx
mit dem nicht:

Code: Alles auswählen

xxxxxxx
x x   x
x xx  x
x     x
xxxx  x
x     x
x xx xx
x E   x
xxxxxxx
Unwissenheit ist ein Segen

mfro
Beiträge: 346
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Backtracking und Python

Beitrag von mfro » Di Jun 03, 2014 6:19 pm

ich kann zwischen den beiden Labyrinthen keinen Unterschied erkennen?
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Backtracking und Python

Beitrag von cloidnerux » Di Jun 03, 2014 7:10 pm

ich kann zwischen den beiden Labyrinthen keinen Unterschied erkennen?
Laut dem diffchecker gibt es auch keinen Unterschied zwischen den beiden :D
Redundanz macht wiederholen unnötig.
quod erat expectandum

canlot
Beiträge: 393
Registriert: Di Mär 08, 2011 11:01 pm
Wohnort: NRW

Re: Backtracking und Python

Beitrag von canlot » Di Jun 03, 2014 8:37 pm

haha ja stimmt moment :D :D

Code: Alles auswählen

xxxxxxxxx
x x     x
x xx xxxx
x       x
xxxx xxxx
x       x
xxxxxxx x
xE      x
xxxxxxxxx
mit dem funktioniert nicht
Unwissenheit ist ein Segen

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Backtracking und Python

Beitrag von cloidnerux » Di Jun 03, 2014 9:13 pm

Müssen die Zeilen nicht alle gleich lang sein?
http://www.diffchecker.com/aiukvzfg(Nur gültig in der nächsten Stunde)
Redundanz macht wiederholen unnötig.
quod erat expectandum

canlot
Beiträge: 393
Registriert: Di Mär 08, 2011 11:01 pm
Wohnort: NRW

Re: Backtracking und Python

Beitrag von canlot » Di Jun 03, 2014 9:23 pm

cloidnerux hat geschrieben:Müssen die Zeilen nicht alle gleich lang sein?
http://www.diffchecker.com/aiukvzfg(Nur gültig in der nächsten Stunde)
Ne das ist egal, weder Zeilen noch Spalten müssen gleich lang sein, oder meintest du was anderes?
Die Anzahl der Zeilen und Spalten wird im Programm ermittelt.
Also folgendes Labyrinth funktioniert auch:

Code: Alles auswählen

xxxxxxxxxxxxxxxx
x xxxxxx x   xxx
x      x x x x x
xxxxxx x xxx x x
x              x
x xxxxxxxxxxxx x
x x xxxx       x
x x    x x x x x
x xxxx   x x x x
x      x x x x x
xxxx  x xx x x x
x     x    x x x
x         E  x x
xxxxxxxxxxxxxxxx
Unwissenheit ist ein Segen

mfro
Beiträge: 346
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Backtracking und Python

Beitrag von mfro » Mi Jun 04, 2014 6:39 am

Ich hab' mal (auch um mal wieder ein bißchen mit Python zu spielen) in deinen Code reingeschaut und ich muß leider sagen: er gefällt mir nicht. Bei mir hättest Du dafür (mit Verlaub) keine gute Note bekommen.

Auch wenn Python das kann, es ist alles andere als guter Stil, wenn eine Funktion - wie's ihr grade einfällt - mal ein bool und mal eine Liste zurückgibt.

Bei der dreiwertigen Logik (mal True, mal False oder eben doch was anderes) hat's mir die Zehennägel hochgebogen und ich habe aufgegeben, das verstehen zu wollen. Python mag das können, ich kann's (und will's) nicht...

Immerhin bin ich so weit gekommen, daß ich dir sagen kann, daß der Ausgang auch im zweiten Labyrinth richtig gefunden wird. Die Kenntnis des Erfolges geht nur leider irgendwo bei der Rückkehr aus der Rekursion verloren. An der Stelle hab' ich dann auch die Lust verloren.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

canlot
Beiträge: 393
Registriert: Di Mär 08, 2011 11:01 pm
Wohnort: NRW

Re: Backtracking und Python

Beitrag von canlot » Mi Jun 04, 2014 8:58 am

mfro hat geschrieben:Ich hab' mal (auch um mal wieder ein bißchen mit Python zu spielen) in deinen Code reingeschaut und ich muß leider sagen: er gefällt mir nicht. Bei mir hättest Du dafür (mit Verlaub) keine gute Note bekommen.
Ich habe dafür auch keine Note bekommen nur ein Attest.
mfro hat geschrieben:Bei der dreiwertigen Logik (mal True, mal False oder eben doch was anderes) hat's mir die Zehennägel hochgebogen und ich habe aufgegeben, das verstehen zu wollen. Python mag das können, ich kann's (und will's) nicht...
Ja Python kann ich seit ca. einem Monat, uns wurde es in den ersten zwei Stunden beigebracht. Rheine Übungsstunden sind vielleicht mal 10 oder 12 die ich mit Python verbracht habe, sicher ich will und werde irgendwann einen vernünftigen Code schreiben aber erstmal weiß ich nicht besser wenn keiner mir die Fehler sagt und da ich bisher nur C/C++ C# und PHP programmiert habe fällt mir der Einstieg in Python nicht leicht. Das Fach heißt AUD -> Algorithmen und Datenstrukturen, dabei geht es weniger um Python sondern dass man die Algorithmen versteht und sie nachprogrammieren kann. Da Python eine sehr Anfängerfreundliche Programmiersprache ist und unser Prof sich damit auskennt ist die Wahl natürlich leicht gefallen. Nebenbei haben wir auch C/C++ aber da lernen wir eher die Sprache als irgendwas anderes. Beim darüberschauen hat er sich auch schwer getan meinen Code zu verstehen und hat mich auch gefragt ob ich aus der C Ecke komme :roll:
mfro hat geschrieben:Immerhin bin ich so weit gekommen, daß ich dir sagen kann, daß der Ausgang auch im zweiten Labyrinth richtig gefunden wird. Die Kenntnis des Erfolges geht nur leider irgendwo bei der Rückkehr aus der Rekursion verloren. An der Stelle hab' ich dann auch die Lust verloren.
Gut wenn du meinst der Rest sein in Ordnung, muss ich noch mal darüberschauen und den Fehler ausfindig machen, aber manches ist schon nicht leicht in Python wie Umgang mit Listen dass sie immer per Referenz übergeben werden und die Variablen immer kopiert werden sowie autonome Datentypen, gut in PHP sind sie auch.
Und jetzt entschuldige mich, ich muss die Welt retten... :P ;)
Unwissenheit ist ein Segen

Antworten