The Ice Tower Solver
from random import shuffle
import time
import os
import copy
CHAR_WALL="#";
CHAR_FIRE="@";
CHAR_ICE="%";
CHAR_SPACE="."
CONST_QUEUE_SIZE=30000
CONST_MAX_EXEC_TIME=60000
def getRelativeFile(relpath):
__location__=os.path.realpath(
os.path.join(os.getcwd(), os.path.dirname(__file__)))
return os.path.join(__location__,relpath)
def clone():
pass
class Map():
"""docstring for Map"""
def __init__(self):
pass
def createMap(self,raw):
mapd=MapData()
arr=raw.split("\n")
mapd.height=len(arr)
preferredWidth=-1
for i in range(mapd.height):
map_row=list(arr[i])
width=len(map_row)
arr[i]=map_row
for j in range(width):
arr[i][j]=MapCell(arr[i][j])
if (preferredWidth>=0 and preferredWidth!=width):
raise Exception("Map width inconsistent. Preferred "+preferredWidth+" but found "+width+" in row #"+str(i+1)+".")
preferredWidth=width
mapd.width=preferredWidth
mapd.data=arr
self.currentMap=mapd
return mapd
class MapData:
height=0
width=0
data=None
def __init__(self,data=None):
if data:self.data=data
def dump(self):
rtn=""
for i in range(self.height):
rtn+="\n"
for j in range(self.width):
rtn+=self.getCell(Point(i,j)).type
return rtn
def clone(self):
return copy.deepcopy(self)
def tryPush(self,pt,dir):
obj=self.getCell(pt)
legal=False;
if(not obj.moveable):
raise Exception("Specified object is not moveable: "+pt.toString()+".")
nextPt=pt
while True:
newPt=nextPt.getAdjacent(dir)
if(not self.canGo(newPt)):
if(self.getCell(newPt).type==CHAR_FIRE):
self.setCell(newPt,MapCell(CHAR_SPACE))
self.setCell(pt,MapCell(CHAR_SPACE))
return True
else: break
nextPt=newPt
legal=True
self.setCell(nextPt,MapCell(obj.type))
self.setCell(pt,MapCell(CHAR_SPACE))
return legal
def getCell(self,pt):
if(not self.inRange(pt)):
return None
return self.data[pt.x][pt.y]
def setCell(self,pt,cell):
if(not self.inRange):
raise Exception("Can't set cells that are out of the boundary.")
self.data[pt.x][pt.y]=cell
return True
def count(self):
d={}
for i in xrange(self.height):
for j in xrange(self.width):
t=self.getCell(Point(i,j)).type
if d.get(t):
d[t]+=1
else:
d[t]=1
return d
def solvable(self):
fireCnt=0
iceCnt=0
for i in xrange(self.height):
for j in xrange(self.width):
t=self.getCell(Point(i,j)).type
if(t==CHAR_ICE):iceCnt+=1
elif(t==CHAR_FIRE):fireCnt+=1
return fireCnt<=iceCnt
def isFinished(self):
for i in range(self.height):
for j in range(self.width):
if(self.getCell(Point(i,j)).type==CHAR_FIRE):
return False
return True
def canGo(self,pt):
obj=self.getCell(pt)
if(not obj):return False
return obj.type==CHAR_SPACE
def getMoveablePoints(self):
rtn=[]
for i in range(self.height):
for j in range(self.width):
pt=Point(i,j)
if(self.getCell(pt).type==CHAR_ICE):
rtn.append(pt)
return rtn
def inRange(self,pt):
return pt.x>=0 and pt.x<self.height and pt.y>=0 and pt.y<self.width
class Point():
def __init__(self,x,y):
self.x=x
self.y=y
def getAdjacent(self,dir):
if(dir==1):
return Point(self.x-1,self.y)
if(dir==2):
return Point(self.x,self.y+1)
if(dir==3):
return Point(self.x+1,self.y)
if(dir==4):
return Point(self.x,self.y-1)
raise Exception("Invalid direction.")
def isEqual(self,that):
return self.x==that.x and self.y==that.y
def toString(self):
return "("+str(self.x)+","+str(self.y)+")";
class MapStat():
mapd=None
prevState=None
movement=None
depth=0
def __init__(self,mapd):
if(not isinstance(mapd,MapData)):
raise Exception("Can't construct MapStat.")
self.mapd=mapd
def isEqual(self,that):
m1=self.mapd.data
m2=that.mapd.data
for i in range(self.mapd.height):
for j in range(self.mapd.width):
if(m1[i][j].type!=m2[i][j].type):
return False
return True
def traceHierarchical(self):
curr=self
arr=[]
while curr!=None:
if(curr.mapd):
arr.append(curr.mapd.dump())
curr=curr.prevState
return arr[::-1]
class MapCell():
def __init__(self,t):
if(not t):
raise Exception("Type is required.")
self.type=t
self.isStatic=(t==CHAR_WALL)
self.moveable=(t==CHAR_ICE)
class MapMovement():
def __init__(self,pt,dir):
self.point=pt
self.dir=dir
def main():
f=open(getRelativeFile("input.txt"),'r').read()
print f
startSolve(f)
m=Map()
'''def statInQueue(queue,target):
for i in xrange(len(queue)-1,0,-1):
if(queue[i].isEqual(target)):
return True
return False'''
def startSolve(data):
m.createMap(data)
im=m.currentMap
#print im.data[0]
#return
if not im.solvable():
print "Impossible Game!"
return
ts=time.time()
leastStep=im.count()[CHAR_FIRE]
print im.count()
for depth in xrange(leastStep,10):
print "Start depth="+str(depth)
answer=iidfs(im,depth)
if len(answer):
break
if not len(answer):
print "No solution found :("
et=time.time()-ts
print "IDDFS ended... ET= "+str(et)+"s"
def iidfs(im,depthLimit):
stack=[MapStat(im)]
answer=[]
cnt=0
while len(stack):
ts=time.time()
oriStat=stack.pop()
if oriStat.depth>depthLimit:
continue
ori=oriStat.mapd
moveable=list(ori.getMoveablePoints())
shuffle(moveable)
if ori.isFinished():
print "Solution Found!"
print "\n".join(oriStat.traceHierarchical())
answer.append(oriStat)
break
#print ori.getMoveablePoints()
if not moveable:
continue
for pt in moveable:
dirArr=[1,2,3,4]
shuffle(dirArr)
for d in dirArr:
#print pt.toString(),d
d_op=(d+1)%4+1
facePt=pt.getAdjacent(d)
if ori.canGo(facePt):
currStat=MapStat(ori.clone())
curr=currStat.mapd
isLegal=curr.tryPush(pt,d_op)
if(isLegal):
currStat.prevState=oriStat
currStat.movement=MapMovement(pt,d)
currStat.depth=oriStat.depth+1
stack.append(currStat)
et=time.time()-ts
if et>=CONST_MAX_EXEC_TIME:
raise Exception("Max execution time reached!")
return answer
main()
This is a solver for The Ice Tower. Written in Python.
I have been using BFS, DFS and IDDFS, but they don't seem to be efficient.
For the game, you can download here: http://host.zjes.tyc.edu.tw/~junlang/data/p-4.htm