29 Jul 2014

Table of Contents

#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:

  1. 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
  2. The open queue starts with \((x, y, 0, \{\})\) for the start location \(x, y\).
  3. Keep a set of world states we’ve seen.
  4. Dequeue a state \(s = (x, y, d, t)\).
  5. If \(x, y\) is our goal, stop.
  6. 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
  7. Add these successors to both the open queue and the seen set.
  8. 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.

#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'))

#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, [])

#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

#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")

#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.

#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.