def find_landmark(map, landmark): for y in range(len(map)): x = map[y].find(landmark) if x >= 0: return (x, y) return None def print_map_compact(map, path): for y, row in enumerate(map): for x, char in enumerate(row): if (x, y) in path: print("@", end="") else: print(char, end="") print() if len(path) == 0: print(" ### NO PATH ###\n\n") # I'm also defining an html output for debugging def print_map_html(map, explored, path): light_left = {} max_light = 1 for location, dt_list in explored.items(): for (distance, light, *_) in dt_list: light_left[location] = max(light, light_left.get(location, 0)) max_light = max(max_light, light) print('
')
for y, row in enumerate(map):
for x, char in enumerate(row):
if char == '\n':
print()
else:
style = []
title = []
if WALL_CHARS.find(char) >= 0:
style.append("background:#999;color:#999")
if (x, y) in path:
style.append("color:green")
for i, loc in enumerate(path):
if loc == (x, y): title.append("@step {}".format(i))
if char == ' ':
count = path.count((x, y))
if count == 1: char = '•'
elif count == 2: char = '●'
else: char = '◉'
if char == 't':
char = 'T'
if (x, y) in light_left:
if char == 't' or char == 'T':
style.append("background:yellow")
else:
style.append("background:hsl(60,50%,{:.0%})".format(
0.5 * (1 + light_left[(x, y)] / max_light)))
if not style:
style.append("background:hsl(240,20%,70%)")
if char == ' ':
char = " " # ugh, not sure why this is needed
print("{}".format(
";".join(style), "; ".join(title), char), end="")
print('
')
import time, collections
DIRS = [(1, 0), (0, -1), (-1, 0), (0, 1)]
WALL_CHARS = "x-|"
def search(map, start, goal):
start_time, COUNT, HIT_WALL, PRUNED, OUT_OF_LIGHT = time.time(), 0, 0, 0, 0
open = collections.deque() # state
open.append((start, 0, set(), None))
seen = {} # {loc: set of (distance, light)}
seen[start] = set([(0, 15)])
while open:
state = open.popleft()
loc, distance, torches, _ = state
if loc == goal: break
COUNT += 1
if 15 + 15 * len(torches) - distance <= 0:
OUT_OF_LIGHT += 1
continue # can't take any distance because we're out of light
(x, y) = loc
for (dx, dy) in DIRS:
x2 = x + dx
y2 = y + dy
loc2 = (x2, y2)
distance2 = distance + 1
torches2 = torches
if WALL_CHARS.find(map[y2][x2]) >= 0:
# can't walk into a wall
HIT_WALL += 1
continue
if map[y2][x2] == 't' and (x2, y2) not in torches:
# pick up the torch if it's still there
torches2 = torches.copy()
torches2.add(loc2)
seen.setdefault(loc2, set())
light2 = 15 + 15 * len(torches2) - distance2
for (d, l) in seen[loc2]:
if d <= distance2 and l >= light2:
# we've been here before with better conditions
PRUNED += 1
break
else:
open.append((loc2, distance2, torches2, state))
seen[loc2].add((distance2, light2))
# reconstruct the path
path = []
light_levels = []
if state[0] == goal:
current = state
while current != None:
loc, distance, torches, parent = current
path.append(loc)
light_levels.append(15 + 15 * len(torches) - distance)
current = parent
light_levels.reverse()
path.reverse()
# some stats
print("processed:", COUNT, "; hit wall:", HIT_WALL, "; out of light:", OUT_OF_LIGHT, "; pruned:", PRUNED, "; path length:", len(path)-1, "; time: %dms" % (1000*(time.time()-start_time)))
print("light along the path:", light_levels)
return seen, path
def run(filename):
print("_"*20, filename, "_"*40)
map = open(filename).readlines()
start = find_landmark(map, 'H')
goal = find_landmark(map, 'T')
results, path = search(map, start, goal)
print_map_compact(map, path)
print("\n\n\n")