Created
November 23, 2016 15:03
-
-
Save hieuhtr/feb59eb6eae5c4169490bbb3793220dc to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#Info: Huynh Trung Hieu - 51201076 | |
#Reference: http://www.gamefaqs.com/pc/932088-mummy-maze-deluxe/faqs/42610 | |
import copy, logging, math, time | |
#all x-y cordinates use the row-column numbers, starting from 1 | |
#DIRECTIONS | |
RIGHT,DOWN,LEFT,UP,STAY=1,2,3,4,5 | |
ExplorerMoves=[RIGHT,DOWN,LEFT,UP,STAY] | |
MoveStrs=['RIGHT','DOWN','LEFT','UP','STAY'] | |
def Move2Str(m): | |
return MoveStrs[ExplorerMoves.index(m)] | |
class CMummyMaze(object): | |
def __init__(self,row,col): | |
self.mazesize=[row,col] | |
self.MovableItems={ | |
'explorer':None, | |
'mummies':[], | |
'redmummies':[], | |
'scorpions':[], | |
'redscorpions':[], | |
'XDirections':[] #Forbidden Directions | |
} | |
self.traps=[] | |
self.gate=None | |
self.key=None | |
self.exit=None | |
self.Checked=[] | |
self.CheckedSol=[] | |
self.solution=[] | |
self.SingleSolMode=False | |
self.TryNo=0 | |
self.TotalSolutions=[] | |
def CanMoveInDirection(self,x,y,d,CheckWalls=True): | |
#whether move in direction d at (x,y) is blocked by boundries, or walls(when CheckWalls is True). | |
newx,newy=x,y | |
if((not CheckWalls) or ([x,y,d] not in self.MovableItems['XDirections'])): | |
if(d==RIGHT): newy+=1 | |
elif(d==DOWN): newx+=1 | |
elif(d==LEFT): newy-=1 | |
elif(d==UP): newx-=1 | |
elif(d==STAY): pass | |
if(1<=newx<=self.mazesize[0] and 1<=newy<=self.mazesize[1]): | |
return [True,[newx,newy]] | |
else: | |
return [False,[newx,newy]] | |
else: | |
return [False,[newx,newy]] | |
#find the reverse direction of d | |
def ReverseDir(self,d): | |
a=[RIGHT,DOWN,LEFT,UP] | |
r=[LEFT,UP,RIGHT,DOWN] | |
return r[a.index(d)] | |
def DelDumplicates(self,lofl): | |
ret=[] | |
for l in lofl: | |
if l not in ret: | |
ret.append(l) | |
return [ret,len(ret)<len(lofl)] | |
#[list(b) for b in set([tuple(a) for a in lofl])] using set for this purpose will change the list item order | |
def Setup(self,barlist,itemstr): | |
self.__SetXDFromWalls(barlist) | |
self.__SetMovableItems(itemstr) | |
def __SetXDFromWalls(self,barlist): | |
for bar in barlist: | |
x,y=bar[:2] | |
for d in bar[2:]: | |
self.MovableItems['XDirections'].append([x,y,d]) | |
ret,pos=self.CanMoveInDirection(x, y, d,False) | |
if(ret): | |
self.MovableItems['XDirections'].append([pos[0],pos[1],self.ReverseDir(d)]) | |
self.MovableItems['XDirections'],dump=self.DelDumplicates(self.MovableItems['XDirections']) | |
def __SetMovableItems(self,itemstr): | |
abbrs=['x','g','k','t','e','rm','m','rs','s'] | |
fullnames=['exit','gate','key','traps','explorer','redmummies','mummies','redscorpions','scorpions'] | |
items=itemstr.split('/') | |
for item in items: | |
if(len(item)>=4): | |
item=item.replace(' ','').lower() | |
mark=[] | |
for c in item: | |
if(c.isalpha()): | |
mark.append(c) | |
else: | |
break | |
mark=''.join(mark) | |
if(mark in abbrs): | |
spos=len(mark) | |
fn=fullnames[abbrs.index(mark)] | |
one=[int(i) for i in item[spos:].split(',')] | |
multis=[[int(i) for i in x.split(',')] for x in item[spos:].split(';')] | |
if(mark=='e'): | |
self.MovableItems['explorer']=one | |
elif(mark=='x'): | |
self.exit=one | |
elif(mark=='t'): | |
self.traps=multis | |
elif(mark=='g'): | |
self.gate=one | |
self.gate.append(DOWN) | |
elif(mark=='k'): | |
self.key=one | |
elif(fn in self.MovableItems): | |
self.MovableItems[fullnames[abbrs.index(mark)]]=multis | |
#else:(eval('self.'+fn))=one | |
else: | |
raise Exception('there\'s sth wrong in the item str') | |
def NewPosAfterOneStep(self,t,curpos): | |
#a animal of type t at current position(curpos) tries to move towards the explorer | |
#the newpos returned | |
epos=self.MovableItems['explorer'] | |
newpos=curpos | |
H=[1,LEFT,RIGHT] | |
V=[0,UP,DOWN] | |
if(t=='mummies' or t=='scorpions'): | |
decisions=[H,V] | |
elif(t=='redmummies' or t=='redscorpions'): | |
decisions=[V,H] | |
bCanMov=False | |
for i,d1,d2 in decisions: | |
if(curpos[i]!=epos[i]): | |
if(curpos[i]>epos[i]): mdir=d1 | |
else: mdir=d2 | |
bCanMov,newpos=self.CanMoveInDirection(curpos[0],curpos[1],mdir) | |
if(bCanMov): | |
break | |
if(bCanMov): #the animal can move to a new position | |
self.LoseCheck(newpos) | |
if(newpos==self.key): #it steps on the key | |
self.ToggleGate() | |
return newpos | |
def LoseCheck(self,pos): | |
if(self.MovableItems['explorer']==pos): | |
raise Exception('lose') | |
def EatCheck(self): | |
foodchains=['redmummies','mummies','redscorpions','scorpions'] | |
for t in foodchains: | |
self.MovableItems[t],dump=self.DelDumplicates(self.MovableItems[t]) | |
if(dump): | |
logging.debug("%s eat %s", t,t) | |
for i in range(len(foodchains)-1): | |
hunter=foodchains[i] | |
preys=foodchains[i+1:] | |
for pos in self.MovableItems[hunter]: | |
for prey in preys: | |
if(pos in self.MovableItems[prey]): | |
logging.debug("%s eat %s", hunter ,prey) | |
self.MovableItems[prey].remove(pos) | |
def ToggleGate(self): | |
if(self.gate in self.MovableItems['XDirections']): | |
logging.debug('now gate opens') | |
self.MovableItems['XDirections'].remove(self.gate) | |
x,y,d=self.gate | |
ret,pos=self.CanMoveInDirection(x, y, d,False) | |
if(ret): | |
self.MovableItems['XDirections'].remove([pos[0],pos[1],self.ReverseDir(d)]) | |
else: | |
logging.debug('now gate closes') | |
self.MovableItems['XDirections'].append(self.gate) | |
x,y,d=self.gate | |
ret,pos=self.CanMoveInDirection(x, y, d,False) | |
if(ret): | |
self.MovableItems['XDirections'].append([pos[0],pos[1],self.ReverseDir(d)]) | |
def UpdateLattice(self,d,epos): | |
#explorer move in direction d, and the new postition is epos | |
#explorer move | |
self.MovableItems['explorer']=epos | |
if(d!=STAY and epos==self.key): | |
self.ToggleGate() | |
#scorpions and redscorpions move first | |
#or todo: nearest to the explorer move first. i'm not sure | |
foodchains=['redmummies','mummies','redscorpions','scorpions'] | |
foodchains.reverse() | |
for t in foodchains[:2]: | |
if(len(self.MovableItems[t])>0): | |
self.MovableItems[t]=[self.NewPosAfterOneStep(t,s) for s in self.MovableItems[t]] | |
self.EatCheck() | |
#mummies's 1st move | |
for t in foodchains[2:]: | |
if(len(self.MovableItems[t])>0): | |
self.MovableItems[t]=[self.NewPosAfterOneStep(t,s) for s in self.MovableItems[t]] | |
self.EatCheck() | |
#mummies's 2nd move | |
for t in foodchains[2:]: | |
if(len(self.MovableItems[t])>0): | |
self.MovableItems[t]=[self.NewPosAfterOneStep(t,s) for s in self.MovableItems[t]] | |
self.EatCheck() | |
def PrintCurrentStatus(self): | |
if(len(self.solution)==0): | |
logging.debug("=========initial status=========") | |
logging.debug('%d Forbidden Moves:', len(self.MovableItems['XDirections'])) | |
for x,y,d in self.MovableItems['XDirections']: | |
logging.debug('%d, %d, %s', x, y, Move2Str(d)) | |
else: | |
logging.debug("=========#{0}=========".format(self.TryNo)) | |
logging.debug(SolStr(self.solution)) | |
logging.debug('') | |
#always print explorer info first. dict can not assure that. | |
logging.debug('explorer: %s',self.MovableItems['explorer']) | |
for k,v in self.MovableItems.items(): | |
if(k!='explorer' and k!='XDirections' and len(v)): | |
if(isinstance(v[0],list)): | |
logging.debug('%s: %s',k,','.join([str(i) for i in v])) | |
else: | |
logging.debug('%s: %s',k,v) | |
logging.debug('') | |
def DFSolve(self,depth=0): | |
self.TryNo+=1 | |
self.PrintCurrentStatus() | |
if(self.MovableItems in self.Checked): | |
alreadyindex=self.Checked.index(self.MovableItems) | |
if(len(self.solution)>=self.CheckedSol[alreadyindex]): | |
logging.debug('u have been here before') | |
return | |
else: | |
self.CheckedSol[alreadyindex]=len(self.solution) #UPDATE info | |
else: | |
self.Checked.append(copy.deepcopy(self.MovableItems)) | |
self.CheckedSol.append(len(self.solution)) | |
saved=copy.deepcopy(self.MovableItems) | |
curpos=self.MovableItems['explorer'] | |
PrefMoves=[] | |
for d in ExplorerMoves: | |
ret,epos=self.CanMoveInDirection(curpos[0],curpos[1],d) | |
if(ret and epos not in self.traps): | |
PrefMoves.append([math.fabs(epos[0]-self.exit[0])+math.fabs(epos[1]-self.exit[1]),d,epos]) | |
PrefMoves.sort(key=lambda x: x[0]) | |
for dump,d,epos in PrefMoves: | |
try: | |
self.UpdateLattice(d,epos) | |
if([epos[0],epos[1]] == self.exit): | |
l=self.solution[:] | |
l.append(d) | |
self.TotalSolutions.append(l) | |
if(self.SingleSolMode): | |
raise Exception('Done') | |
else: | |
self.MovableItems=copy.deepcopy(saved) | |
continue | |
except Exception as e: | |
if(e.args[0]=='lose'): | |
self.MovableItems=copy.deepcopy(saved) #very trival mistake: deepcopy needed | |
continue | |
else: | |
raise | |
self.solution.append(d) | |
logging.debug('trying %s at level %d...', Move2Str(d),depth) | |
self.DFSolve(depth+1) | |
logging.debug('backforce popping...') | |
self.solution.pop() | |
logging.info(SolStr(self.solution)) | |
self.MovableItems=copy.deepcopy(saved) #very trival mistake: deepcopy needed | |
if(depth==0 and self.SingleSolMode): | |
logging.info("hmm..., no solution found.") | |
def SolStr(sol): | |
s=[] | |
for i in sol: | |
s.append(Move2Str(i)) | |
return "Solution: After {:d} steps:\n".format(len(sol))+(', '.join(s)) | |
def InitFromTaM(TaMStr): #Theseus and the Minotaur | |
TaMlist=[i.strip() for i in TaMStr.split('\n') if i!=''] | |
lattice=TaMlist[1:10] | |
walls=[] | |
for i in range(9): | |
if(lattice[i][0]=='6'): | |
break | |
for j in range(14): | |
cell=lattice[i][j] | |
if(cell=='6'): | |
break | |
elif(cell!='0'): | |
if(cell=='1'): | |
walls.append([i+1,j+1,LEFT]) | |
elif(cell=='2'): | |
walls.append([i+1,j+1,UP]) | |
elif(cell=='3'): | |
walls.append([i+1,j+1,UP,LEFT]) | |
if(i==8):i=9 | |
if(j==13):j=14 | |
mm.mazesize=[i,j] | |
items='m{0},{1}/e{2},{3}/x{4},{5}'.format(int(TaMlist[15])+1,int(TaMlist[14])+1,int(TaMlist[12])+1,int(TaMlist[11])+1, | |
int(TaMlist[18])+1,int(TaMlist[17])+1) | |
mm.Setup(walls,items) | |
if __name__ == '__main__': | |
logging.basicConfig(level=logging.INFO,format='%(message)s') | |
#init | |
#the 14th puzzle in Pharaoh's Tomb, has the solution with most moves | |
mm=CMummyMaze(10,10) | |
walls=[[1,5,DOWN],[1,6,DOWN],[1,7,DOWN],[1,8,DOWN],[1,9,LEFT],[1,10,LEFT],[\ | |
2,2,DOWN],[2,7,DOWN],[3,1,DOWN],[3,2,DOWN],[3,6,LEFT],[3,10,LEFT],[4,\ | |
2,DOWN],[4,4,DOWN,LEFT],[4,5,DOWN],[4,8,DOWN],[4,9,DOWN,LEFT],[4,10,\ | |
DOWN,LEFT],[5,1,DOWN],[5,4,DOWN],[5,5,DOWN],[5,8,DOWN],[5,9,DOWN],[6,\ | |
2,DOWN],[6,4,DOWN],[6,8,LEFT],[6,9,LEFT],[7,1,DOWN],[7,3,DOWN,LEFT],[\ | |
7,8,DOWN,LEFT],[7,10,LEFT],[8,2,LEFT],[8,5,DOWN,LEFT],[8,7,LEFT],[8,\ | |
10,LEFT],[9,5,LEFT],[9,6,DOWN],[9,8,DOWN],[9,9,DOWN,LEFT],[10,6,LEFT],\ | |
[10,9,LEFT]] | |
#items='x4,10/e7,1/t2,1/rs5,4/rm8,6' #gate always faces down, see also class's __SetMovableItems func | |
#mm.Setup(walls,items) | |
#level 87 of game: Theseus and the Minotaur | |
#0-empty 1-wall at left, 2-wall at top, 3-wall at both left and top | |
#6-border | |
#Theseus/Minotaur/Goal coordinates orignating from the upper-left corner (0,0) | |
TaMStr=''' | |
Theseus and the Minotaur Level | |
00100000001000 | |
01021320121331 | |
02300020021100 | |
01022130210111 | |
01111121111100 | |
00000110111133 | |
02221001001001 | |
23113201202021 | |
00002200122200 | |
Theseus | |
12 | |
5 | |
Minotaur | |
6 | |
3 | |
Goal | |
13 | |
5 | |
End | |
85 | |
''' | |
InitFromTaM(TaMStr) | |
#True: find a solution | |
#False: find the best solution with least moves | |
mm.SingleSolMode=False | |
StartingTime = time.time() | |
try: | |
mm.DFSolve() | |
except: | |
pass | |
EndingTime= time.time() | |
logging.info("total time: {:.2f}s, {:d} tries".format(EndingTime-StartingTime,mm.TryNo)) | |
l=[len(sol) for sol in mm.TotalSolutions] | |
l.sort() | |
logging.info("total %d solutions found:%s",len(mm.TotalSolutions),l) | |
minv=float('Infinity') | |
mins=[] | |
for sol in mm.TotalSolutions: | |
logging.debug(SolStr(sol)) | |
if(len(sol)<minv): | |
minv=len(sol) | |
mins=sol | |
logging.info("Best solution is:") | |
logging.info(SolStr(mins)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment