1 Problem statement#
This program will find the shortest path from a starting point with 15 units of light through a cave to the location of a treasure. Light can be collected at various points, but each step takes away one unit of light and you must have at least one unit of light to take a step. You may pick up 15 units of light at cells having 't'. You may not visit cells with 'x', '|', or '-'. You may visit a legal cell as many times as you desire, but you may only collect light from each cell which has light, once, even though you may visit that cell more than once.
Idea for algorithm:
- Keep a queue of open world states. A state is \((x, y, d, t)\).
- \(x, y\) is the location of the explorer
- \(d\) is the number of steps taken so far
- \(t\) is a set of locations of torches picked up
- The open queue starts with \((x, y, 0, \{\})\) for the start location \(x, y\).
- Keep a set of world states we’ve seen.
- Dequeue a state \(s = (x, y, d, t)\).
- If \(x, y\) is our goal, stop.
- If we still have light (\(15 + 15|t| - d > 0\)), then look at successors \((x, y, d, t) \rightarrow (x + \Delta x, y + \Delta y, d + 1, t \cup t’)\) where:
- Can’t walk through walls: location \(x + \Delta x, y + \Delta y\) does not contain a wall (
x
or|
or-
) - Pick up torches: \(t’ = \{(x + \Delta x, y + \Delta y)\}\) if we picked up a torch (\(t\) must not already contain the torch) or \(t’ = \{\}\) otherwise
- Can’t walk through walls: location \(x + \Delta x, y + \Delta y\) does not contain a wall (
- Add these successors to both the open queue and the seen set.
- Return to step 4.
Let’s define a (partial) ordering on states \(s_1, s_2\): \((x_1, y_1, d_1, t_1) >= (x_2, y_2, d_2, t_2)\) if \(x_1 = x_2\) and \(y_1 = y_2\) and \(s_1 <= s_2\) and \(15|t_1| - d_1 >= 15|t_2| - d_2\). The idea is that we want to define the conditions under which we’ll re-evaluate a location. Either it’s a shorter distance or we have more light this time. If we have two states where \(s_1 < s_2\), then we don’t need to evaluate \(s_1\).
Update: this partial ordering is too aggressive, as I discovered later. Ugh.
2 input#
Let’s represent the map as an array of strings. This is the simplest representation.
map = open("CodeQuest2014/cave.dat").readlines() print("".join(map))
Let’s find the coordinates of a landmark (start or end point) is on the map:
def find_landmark(map, landmark): for y in range(len(map)): x = map[y].find(landmark) if x >= 0: return (x, y) return None
and test it:
map = open("CodeQuest2014/cave.dat").readlines() print(find_landmark(map, 'T')) print(find_landmark(map, 'H')) print(find_landmark(map, 'X'))
3 output#
for debugging, let’s print out the areas we’ve explored, and how much light is left in each
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")
and test it with a very simple input:
map = open("CodeQuest2014/cave.dat").readlines() print_map_compact(map, [])
4 search algorithm#
This mostly follows the algorithm I wrote above, but instead of states being \((x, y, d, t)\), I use ((x, y), distance, torch-set, parent-state)
so that I can retrace my steps to construct a path. I partition the seen
by location so that it’s easy to look them up. And instead of storing the entire state, I collapse the seen
set to only the parts I care about: the distance (steps taken) and the range (light remaining). This saves quite a bit of processing, because there are many states with the same distance and range and there’s no point in storing them all.
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
5 trying it out#
Let’s write a function to read a cave and run search on it:
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")
And finally, let’s run it:
for f in ["", "1", "2", "3", "4A", "5", "5A", "5B", "5F", "5G", "5H", "5x", "6", "6-1", "7", "8"]: run("CodeQuest2014/cave" + f + ".dat")
6 trying it out on a harder problem#
Also trying out an html map drawing function – you can mouse over any explored spot to see how much light is available there.
map = open("CodeQuest2014/Prob16.in.txt").readlines() start = find_landmark(map, 'H') goal = find_landmark(map, 'T') results, path = search(map, start, goal) print_map_html(map, results, path)
This fails
The shortest path is 190 but my algorithm finds a 200-len path. It turns out my pruning is too aggressive. I tried making it more precise but it ran far too slowly, and I haven’t tried to figure this out. Ugh. The incorrect pruning seems to work on most of the tests.
import time, collections DIRS = [(1, 0), (0, -1), (-1, 0), (0, 1)] WALL_CHARS = "x-|" def search2(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: list of (distance, light, torches)} seen[start] = [(0, 15, set())] DMAP = map[:] while open: state = open.popleft() loc, distance, torches, _ = state if loc == goal: break DEBUG = (5,30) in torches if DEBUG or loc == (14, 22): (x, y) = loc print(loc, distance, torches, 15 + 15 * len(torches) - distance) DMAP[y] = DMAP[y][:x] + "#" + DMAP[y][x+1:] COUNT += 1 if 15 + 15 * len(torches) - distance <= 0: OUT_OF_LIGHT += 1 if DEBUG: print("OUT OF LIGHT") 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, []) light2 = 15 + 15 * len(torches2) - distance2 for (d, l, t) in seen[loc2]: if d <= distance2 and l >= light2 and t == torches2: # we've been here before with better conditions PRUNED += 1 # if DEBUG: print("PRUNE because {} has a better option d={} l={} vs d={} l={} TORCH STATUS: {} -- {}:{}".format(loc2, d, l, distance2, light2, t == torches2, t, torches2)) break else: open.append((loc2, distance2, torches2, state)) seen[loc2].append((distance2, light2, torches2)) # 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() print("".join(DMAP)) # 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 map = open("CodeQuest2014/Prob16.in.txt").readlines() start = find_landmark(map, 'H') goal = find_landmark(map, 'T') #results, path = search2(map, start, goal) #print_map_compact(map, path) #print_map_html(map, results, path)
I’m not happy with the visualization but don’t want to spend a lot more time on this.
7 more#
The complete code is here.
A further improvement would be to use A* instead of Breadth First Search. A* introduces additional prioritization that lets us find the goal faster. I think it’d help quite a bit on most of these tests, especially cave4A, which has lots of torches, but I can’t be sure unless I try it.
Right now I visit nodes in the order they’re found, so distance
never decreases. That means the newly found node is never better than a node already in the open
queue. With the improved prioritization of A*, it’s possible for the new node to be better. That may complicate the logic a little bit, as we may have to remove nodes in the open
queue that are worse than the newly found one. I’m not sure this is absolutely necessary.
Another approach I thought of was to go backwards, marking each location with the amount of light needed to reach the goal. At the goal, it’s 0. Each step away from the goal you add 1. At a torch, you subtract 15. However, I don’t know how to make this work.