Um zu schwere Felder von mawe's Pythoban zu knacken dieser Code:
Code: Alles auswählen
#!/usr/bin/env python
import levelset1, sys, copy, time
###>>> diese Variablen anpassen:
ZeigAlleLoesungen = 0 # 1=sucht nach allen Moeglichkeiten: viel Zeit/RAM
# 0=erster Loesungsweg wird gezeigt und dann Exit
MaxVersuche = 5000000 #
MaxVerlauf = 300 # max Schritte bis Loesung:
# zu klein=evtl keine Loesung, zu gross=viel Zeit/RAM
###<<<
Mauer = "#"
Ziel = "."
Mann = "@"
Diamant = "$"
DiamantZiel = "*"
leer = " "
MannZiel = "+"
ausserhalb = " "
VersuchNr = 0
FeldHoehe = 0
FeldBreite = 0
Feld1 = {}
Feld1bew = {}
StartZeit = time.time()
VersuchtListe = [] # bereits probierte Felder - kein Ergebnis
ProbierListe = [] # Felder(inkl. Verlauf) die noch probiert werden muessen
BingoListe = [] # gefundene Ergebnisse(ganzer Verlauf)
def Fehler(s):
print s
sys.exit(1)
# setzt die Variablen FeldBreite/FeldHoehe/Feld1/Feld1bew
def setFeld1(F):
f = F.split("\n")
global FeldBreite
global FeldHoehe
global Feld1
global Feld1bew
FeldBreite = 0
FeldHoehe = len(f)
for i in range(len(f)): # maximale Breite rausbekommen
while (len(f[i])>0) and (f[i][len(f[i])-1]==" "):
f[i] = f[i][0:len(f[i])-1]
if len(f[i]) > FeldBreite :
FeldBreite = len(f[i])
for y in range(FeldHoehe):
for x in range(FeldBreite):
try:
if f[y][x] in [" ",".","*","@","+","#","$","?"]:
Feld1[(y,x)] = f[y][x]
if f[y][x] in [".","*","@","+","$"]:
Feld1bew[(y,x)] = f[y][x]
except:
Feld1[(y,x)] = ausserhalb
global VersuchtListe
VersuchtListe = FeldHoehe * [[0]]
for y in range(FeldHoehe):
VersuchtListe[y] = FeldBreite * [[0]]
def Bingo(F): # true = Yeah, Weg gefunden
for i in F.keys():
if F[i] in ["+",".","$"]:
return 0
return 1
def MannPos(F): # wo ist der Mann ?
for i in F.keys():
if F[i] in ["@","+"]:
return i
def IstNeuesFeld(y,x,F): # noch nie benutzte Feld-Konstellation
return VersuchtListe[y][x].count(F) == 0
def DPos(s):
komma = s.find(",")
y = s[1:komma]
x = s[komma+1:len(s)-1]
return[int(y),int(x)]
def DiamantInEcke(Feld): # noch weiterprobieren > Quatsch
for i in Feld.keys():
if Feld[i] == "$":
yx = DPos(str(i))
y = yx[0]
x = yx[1]
if (y-1>=0) and (x-1>=0): # links oben
if Feld1[(y,x-1)] == Mauer: #links
if Feld1[(y-1,x)] == Mauer: #oben
return 1
if (y-1>=0) and (x+1<FeldBreite): # rechts oben
if Feld1[(y,x+1)] == Mauer: #rechts
if Feld1[(y-1,x)] == Mauer: #oben
return 1
if (y+1<FeldHoehe) and (x+1<FeldBreite): # rechts unten
if Feld1[(y,x+1)] == Mauer:
if Feld1[(y+1,x)] == Mauer:
return 1
if (y+1<FeldHoehe) and (x-1>=0): # links unten
if Feld1[(y,x-1)] == Mauer:
if Feld1[(y+1,x)] == Mauer:
return 1
return 0
def ErgebnisZeigen(s):
print s
if len(BingoListe) < 1:
print "Kein Ergebnis gefunden..."
sys.exit(0)
print "Suchzeit : ",time.time() - StartZeit," Sek."
F1 = Feld1.copy()
for i in F1.keys():
if F1[i] in ["@",".","*","+","$"]:
F1[i] = leer
yxalt = [0,0]
yxneu = [0,0]
for x in range(len(BingoListe)):
print
print "Ergebnis ",x + 1
for i in range(len(BingoListe[x])):
print
print "Schritt", i," ",
F = F1.copy()
d = BingoListe[x][i]
d = d.keys()
for dd in d:
F[dd] = BingoListe[x][i][dd]
yxalt = yxneu
yxneu = MannPos(BingoListe[x][i])
if i > 0:
if yxneu[0] < yxalt[0]: # nach oben
print "hoch"
elif yxneu[0] > yxalt[0]: # nach unten
print "runter"
elif yxneu[1] < yxalt[1]: # links
print "links"
elif yxneu[1] > yxalt[1]: # rechts
print "rechts"
else:
print
for y2 in range(FeldHoehe):
s = ""
for x2 in range(FeldBreite):
s = s + F[(y2,x2)]
print s
sys.exit(0)
# hier findet die eigentliche/meiste Suche statt
def GehZuFeld(vonX,vonY,nachX,nachY,nachX2,nachY2,Verlauf,neu):
# erstmal checken ob ueberhaupt gesprungen werden kann...
if (nachX < 0) or (nachX > FeldBreite-1): return 0
if (nachY < 0) or (nachY > FeldHoehe-1): return 0
if (Feld1[(nachY,nachX)] in [Mauer]): return 0
neu = copy.copy(neu)
# Diamant verschieben geht nicht ?
if neu.has_key((nachY,nachX)):
if (neu[(nachY,nachX)] in [Diamant,DiamantZiel]):
if (nachX2 < 0) or (nachY2 < 0): return 0
if (nachX2 > FeldBreite-1) or (nachY2 > FeldHoehe-1): return 0
if (Feld1[(nachY2,nachX2)] in [Mauer]): return 0
if neu.has_key((nachY2,nachX2)):
if (neu[(nachY2,nachX2)] in [Mauer,Diamant,DiamantZiel]): return 0
else:
neu[(nachY2,nachX2)] = leer
else:
neu[(nachY,nachX)] = leer
# Es kann gesprungen werden
if neu[(vonY,vonX)] == Mann: # Altes Feld wieder herstellen
del neu[(vonY,vonX)]
elif neu[(vonY,vonX)] == MannZiel:
neu[(vonY,vonX)] = Ziel
if neu[(nachY,nachX)] == Diamant:
neu[(nachY,nachX)] = Mann
if neu[(nachY2,nachX2)] == leer: neu[(nachY2,nachX2)] = Diamant
elif neu[(nachY2,nachX2)] == Ziel: neu[(nachY2,nachX2)] = DiamantZiel
elif neu[(nachY,nachX)] == DiamantZiel:
neu[(nachY,nachX)] = MannZiel
if neu[(nachY2,nachX2)] == leer: neu[(nachY2,nachX2)] = Diamant
elif neu[(nachY2,nachX2)] == Ziel: neu[(nachY2,nachX2)] = DiamantZiel
if neu[(nachY,nachX)] == Ziel: neu[(nachY,nachX)] = MannZiel
elif neu[(nachY,nachX)] == leer: neu[(nachY,nachX)] = Mann
if Bingo(neu): # alle Diamanten im Ziel?
Verlauf = copy.copy(Verlauf)
Verlauf.append(neu)
global BingoListe
BingoListe.append(Verlauf)
if not ZeigAlleLoesungen:
ErgebnisZeigen('Bei der 1. Loesung Suche abgebrochen...')
return 0
else:
if DiamantInEcke(neu) or (not IstNeuesFeld(vonY,vonX,neu)):
#if (not IstNeuesFeld(neu,vonY,vonX)):
pass
else:
# diese Konstellation gabs noch nicht, in Versuchsliste uebernehmen
global VersuchtListe
VersuchtListe[vonY][vonX].append(neu)
Verlauf = copy.copy(Verlauf)
neu = copy.copy(neu)
Verlauf.append(neu)
global ProbierListe
ProbierListe.append(Verlauf)
return 1
def Knacken(Verlauf): # Vorarbeit
global VersuchNr
if (len(VersuchtListe) > MaxVersuche):
ErgebnisZeigen('Nach '+str(MaxVersuche)+' Versuchen sollte abgebrochen werden...')
if (VersuchNr > MaxVersuche):
ErgebnisZeigen('Nach '+str(MaxVersuche)+' Versuchen sollte abgebrochen werden.')
VersuchNr = VersuchNr + 1
if len(Verlauf) >= MaxVerlauf: return 0 #nicht weiter suchen
Feld = Verlauf[len(Verlauf)-1]
yx = MannPos(Feld)
y = yx[0]
x = yx[1]
# oben
#b1 = GehZuFeld(x,y,x,y-1,x,y-2,copy.deepcopy(Verlauf),copy.deepcopy(Feld))
# unten
#b2 = GehZuFeld(x,y,x,y+1,x,y+2,copy.deepcopy(Verlauf),copy.deepcopy(Feld))
# rechts
#b3 = GehZuFeld(x,y,x+1,y,x+2,y,copy.deepcopy(Verlauf),copy.deepcopy(Feld))
# links
#b4 = GehZuFeld(x,y,x-1,y,x-2,y,copy.deepcopy(Verlauf),copy.deepcopy(Feld))
# oben
#GehZuFeld(x,y,x,y-1,x,y-2,Verlauf,copy.copy(Feld))
# unten
#GehZuFeld(x,y,x,y+1,x,y+2,Verlauf,copy.copy(Feld))
# rechts
#GehZuFeld(x,y,x+1,y,x+2,y,Verlauf,copy.copy(Feld))
# links
#GehZuFeld(x,y,x-1,y,x-2,y,Verlauf,copy.copy(Feld))
# oben
#GehZuFeld(x,y,x,y-1,x,y-2,copy.copy(Verlauf),copy.copy(Feld))
# unten
#GehZuFeld(x,y,x,y+1,x,y+2,copy.copy(Verlauf),copy.copy(Feld))
# rechts
#GehZuFeld(x,y,x+1,y,x+2,y,copy.copy(Verlauf),copy.copy(Feld))
# links
#GehZuFeld(x,y,x-1,y,x-2,y,copy.copy(Verlauf),copy.copy(Feld))
#cV = copy.copy(Verlauf)
#cF = copy.copy(Feld)
# oben
#b1 = GehZuFeld(x,y,x,y-1,x,y-2,cV,cF)
# unten
#b2 = GehZuFeld(x,y,x,y+1,x,y+2,cV,cF)
# rechts
#b3 = GehZuFeld(x,y,x+1,y,x+2,y,cV,cF)
# links
#b4 = GehZuFeld(x,y,x-1,y,x-2,y,cV,cF)
#b1 = GehZuFeld(x,y,x,y-1,x,y-2,(Verlauf),(Feld.copy()))
# unten
#b2 = GehZuFeld(x,y,x,y+1,x,y+2,(Verlauf),(Feld.copy()))
# rechts
#b3 = GehZuFeld(x,y,x+1,y,x+2,y,(Verlauf),(Feld.copy()))
# links
#b4 = GehZuFeld(x,y,x-1,y,x-2,y,(Verlauf),(Feld.copy()))
GehZuFeld(x,y,x,y-1,x,y-2,Verlauf,Feld)
# unten
GehZuFeld(x,y,x,y+1,x,y+2,Verlauf,Feld)
# rechts
GehZuFeld(x,y,x+1,y,x+2,y,Verlauf,Feld)
# links
GehZuFeld(x,y,x-1,y,x-2,y,Verlauf,Feld)
def Suchen():
level = levelset1.levels
if len(sys.argv) <= 1: Fehler("Kein Parameter uebergeben, z.B.: 2")
try:
L = int(sys.argv[1])
except:
Fehler("Als Parameter nur eine Zahl...")
if (L<0) or (L > len(level)-1): Fehler("Zahl zu gross/klein")
setFeld1(level[L])
global VersuchtListe
yx = MannPos(Feld1bew)
VersuchtListe[yx[0]][yx[1]].append(Feld1bew)
global ProbierListe
ProbierListe.append(Feld1bew)
while len(ProbierListe) > 0:
d = ProbierListe[0]
if type(d) == type({}):
d2 = []
d2.append(d)
Knacken(d2)
else:
Knacken(d)
del ProbierListe[0]
if ZeigAlleLoesungen:
ErgebnisZeigen('')
Suchen()
). Das was so lange dauert ist Listen mit Dict's zu kopieren - hab noch keinen schnelleren Weg gefunden als wie mit copy.copy()Das Programm nutzt mawe's levelset1.py -als Parameter die Nummer des gewünschten Feldes übergeben.
Beispiel:(wenn Code den Namen knacksoko.py bekommt)
knacksoko.py 1 > Loesung.txt
In diesem Fall wird das 2.Feld gecheckt und ein Lösungsweg in Loesung.txt gespeichert.
Zerreisst mich nicht wenn ihr den Code so grausam findet - noch nicht so lange Python...
Ist ja witzig!
wollte zeigen das ich einiges probiert habe. Genau dieser Punkt hatte mir am meisten Probleme gemacht - wusste nicht das diese Variablen wie Pointer sind...nur deshalb muß ich die Listen kopieren und Programm so langsam... 
