solve_toxic_maze.py

import Queue as queue

WORLD_SIZE = 25

world = open("grid1.txt").read().replace("S","-1").replace("E","-1").split("\n")[:WORLD_SIZE]
map_state = []

for i in range(WORLD_SIZE):
	world[i] = world[i].split(",")
	world[i] = map(int, world[i])

	map_state.append([0]*WORLD_SIZE)
	for j in range(WORLD_SIZE):
		map_state[i][j] = {}

#print world

def gen_new_state(st, nx, ny, pv):
	global world

	ns = { 
		"pos" : [ nx, ny ], 
		"d" : st["d"] + world[ny][nx], # + st["m"],
		"m" : st["m"] + 1,
		"path" : st["path"] + pv
	}

	rem_step = (WORLD_SIZE - 1 - ns["pos"][0] + WORLD_SIZE - 1 - ns["pos"][1])
	done_step = ns["m"]
	rem_dmg = (rem_step + done_step) * (rem_step + done_step + 1) / 2 - (done_step * (done_step + 1) / 2)
	exp_dmg = ns["d"] #+ rem_dmg

	return (exp_dmg, 0, ns)

def worth_adding(st):
	ms = map_state[st["pos"][0]][st["pos"][1]]
	
	for x in ms:
		if int(x) <= st["m"] and ms[x] <= st["d"]:
			return False

	ms[str(st["m"])] = st["d"]
	return True

def eval_path(path):
	v = 0
	m = 0
	px, py = 0, 0
	for l in path:
		if l == "L":
			px -= 1
			v += world[py][px] + m
		if l == "R":
			px += 1
			v += world[py][px] + m
		if l == "U":
			py -= 1
			v += world[py][px] + m
		if l == "D":
			py += 1
			v += world[py][px] + m
		m += 1
	return v

#print eval_path("DRRDDDDDRRDDLLDDDRRDRRRRDDDDRRRRRRRRDRDRDDRRDRRDRDDR")
#DRRDDDDDRRDDLDDDRRDDDDDRRRRRRRRRRRDRRDDDRRDRRDRDDR
#exit()

state = queue.PriorityQueue()
state.put((0, 0 ,{ "pos" : [ 0, 0 ], "d" : 0, "m" : 0, "path": "" }))
map_state[0][0]["0"] = 0

smallest_val = 9999
smallest_path = ""

while True:
	if state.qsize() == 0:
		break

	st = state.get()[2]
	ms = map_state[st["pos"][0]][st["pos"][1]]

	#print state.qsize()
	#print st

	if not ms[str(st["m"])] == st["d"]:
		#print "Discard found better way !"
		continue

	if st["pos"][0] > 0:
		new_x = st["pos"][0] - 1
		new_y = st["pos"][1]
		ns = gen_new_state(st, new_x, new_y, "L")

		if worth_adding(ns[2]):
			state.put(ns)

	if st["pos"][0] <= WORLD_SIZE - 2:
		new_x = st["pos"][0] + 1
		new_y = st["pos"][1]
		ns = gen_new_state(st, new_x, new_y, "R")

		if world[new_y][new_x] == -1:
			tdmg = eval_path(st["path"])

			if tdmg < smallest_val:
				smallest_val = tdmg
				smallest_path = st["path"] + "R"
			
			#print "Found !"
			#print st["path"] + "R"
			#print st["d"]
			#print eval_path(st["path"])


		else:
			if worth_adding(ns[2]):
				state.put(ns)

	if st["pos"][1] > 0:
		new_x = st["pos"][0]
		new_y = st["pos"][1] - 1
		ns = gen_new_state(st, new_x, new_y, "U")

		if worth_adding(ns[2]):
			state.put(ns)

	if st["pos"][1] <= WORLD_SIZE - 2:
		new_x = st["pos"][0]
		new_y = st["pos"][1] + 1
		ns = gen_new_state(st, new_x, new_y, "D")

		if world[new_y][new_x] == -1:
			tdmg = eval_path(st["path"])
			
			if tdmg < smallest_val:
				smallest_val = tdmg
				smallest_path = st["path"] + "D"

			#print "Found !"
			#print st["path"] + "D"
			#print st["d"]
			#print eval_path(st["path"])
		else:
			if worth_adding(ns[2]):
				state.put(ns)

print smallest_path
print smallest_val