The Ice Tower Solver

_readme.md

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

solver_iddfs.py

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