Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement