29 Jul 2014

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

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.

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

----------------------
|xxxxt   x  xxxxxxxxx|
|xxx     x xxx   Txxx|
|xx  xx     x    xxxx|
|xx   xx xx    xxxxxx|
|xxx  xxxxxxxxxxxxxxx|
|xxx  xxx    t  xxxxx|
|xxx xxxx x xxx  xxxx|
|xxt        xxxx  xxx|
|x  xxxxxxxxxt   xxxx|
|xxxxxt    xxxx  xxxx|
|xxx  xx  xxx   xxxxx|
|xxxxx        xxxxxxx|
|H      xxxxxxxxxxxxx|
----------------------


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

(17, 2)
(1, 13)
None


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

----------------------
|xxxxt   x  xxxxxxxxx|
|xxx     x xxx   Txxx|
|xx  xx     x    xxxx|
|xx   xx xx    xxxxxx|
|xxx  xxxxxxxxxxxxxxx|
|xxx  xxx    t  xxxxx|
|xxx xxxx x xxx  xxxx|
|xxt        xxxx  xxx|
|x  xxxxxxxxxt   xxxx|
|xxxxxt    xxxx  xxxx|
|xxx  xx  xxx   xxxxx|
|xxxxx        xxxxxxx|
|H      xxxxxxxxxxxxx|
----------------------
###  NO PATH  ###


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

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

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

____________________ CodeQuest2014/cave.dat ________________________________________
processed: 169 ; hit wall: 271 ; out of light: 4 ; pruned: 220 ; path length: 73 ; time: 0ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 17, 16, 15, 14, 13, 12, 11, 10, 9, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
----------------------
|xxxx@@@@x  xxxxxxxxx|
|xxx@@  @x xxx  @@xxx|
|xx @xx @@@@x @@@xxxx|
|xx @ xx xx@@@@xxxxxx|
|xxx@ xxxxxxxxxxxxxxx|
|xxx@ xxx@@@@@@@xxxxx|
|xxx@xxxx@x xxx@@xxxx|
|xxt@@@@@@  xxxx@ xxx|
|x  xxxxxxxxx@@@@xxxx|
|xxxxx@@@@ xxxx@ xxxx|
|xxx  xx@@xxx@@@xxxxx|
|xxxxx @@@@@@@xxxxxxx|
|@@@@@@@xxxxxxxxxxxxx|
----------------------

____________________ CodeQuest2014/cave1.dat ________________________________________
processed: 199 ; hit wall: 304 ; out of light: 2 ; pruned: 285 ; path length: 63 ; time: 0ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 19, 18, 17, 16, 15, 14, 13, 12]
----------------------
|xxxxt   x  xxxxxxxxx|
|xxx@@@@@x xxx  @@   |
|xx @xx @@@@x @@@xxxt|
|xx @ xx xx@@@@xxxxxx|
|xxx@ xxxxxxxxxxxxxxx|
|xxx@ xxx@@@@@@@xxxxx|
|xxx@xxxx@x xxx@@xxxx|
|xx@@@@@@@  xxxx@ xxx|
|x  xxxxxxxxxt  @xxx |
|xxxxxt    xxxx@@xxx |
|xxx  xx  xxx@@@xxxx |
|xxxxx       @xxxxxx |
|@@@@@@@@@@@@@@      |
----------------------

____________________ CodeQuest2014/cave2.dat ________________________________________
processed: 199 ; hit wall: 304 ; out of light: 2 ; pruned: 285 ; path length: 63 ; time: 0ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 19, 18, 17, 16, 15, 14, 13, 12]
----------------------
|xxxxt   x  xxxxxxxxx|
|xxx@@@@@x xxx  @@   |
|xx @xx @@@@x @@@xxxt|
|xx @ xx xx@@@@xxxxxx|
|xxx@ xxxxxxxxxxxxxxx|
|xxx@ xxx@@@@@@@xxxxx|
|xxx@xxxx@x xxx@@xxxx|
|xx@@@@@@@  xxxx@ xxx|
|x  xxxxxxxxxt  @xxx |
|xxxxxt    xxxx@@xxx |
|xxx  xx  xxx@@@xxxx |
|xxxxx       @xxxxxx |
|@@@@@@@@@@@@@@      |
----------------------

____________________ CodeQuest2014/cave3.dat ________________________________________
processed: 90 ; hit wall: 128 ; out of light: 4 ; pruned: 124 ; path length: 36 ; time: 0ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 17, 16, 15, 14, 13, 12, 11, 25, 24]
----------------------
|xxxxt   x  xxxxxxxxx|
|xxx     x xxx       |
|xx  xx     x    xxxt|
|xx   xx xx t  xxxxxx|
|xxx  xxxxxxxxxxxxxxx|
|xxx  xxx     @@xxxxx|
|xxx xxxx x xxx@@xxxx|
|xxt        xxxx@ xxx|
|x  xxxxxxxxx@@@@xxx |
|xxxxx@@@@ xxxx@ xxx |
|xxx  xx@@xxx@@@xxxx |
|xxxxx  @@@@@@xxxxxx |
|@@@@@@@@          T |
----------------------

____________________ CodeQuest2014/cave4A.dat ________________________________________
processed: 115638 ; hit wall: 8909 ; out of light: 0 ; pruned: 334597 ; path length: 82 ; time: 2339ms
light along the path: [15, 14, 13, 27, 41, 40, 54, 68, 67, 81, 80, 94, 108, 107, 121, 135, 134, 148, 162, 161, 175, 189, 203, 217, 231, 245, 259, 273, 287, 301, 300, 299, 313, 327, 326, 325, 339, 353, 367, 381, 395, 394, 393, 392, 391, 390, 389, 403, 417, 431, 445, 444, 443, 442, 441, 455, 469, 468, 467, 466, 465, 464, 478, 477, 476, 475, 474, 488, 502, 516, 515, 514, 528, 542, 556, 570, 569, 568, 582, 596, 595, 594, 593]
-------------------------------------------------------------------------------------
|tt      tttt   ttt  ttttt            ttttt   ttt  tttt   tttt ttttttttt  ttt       |
|ttttttt   t       tttttttt      tttttt   tt    tt   tttt      tttt   tttt     tttt |
|tttt  tt    tt             ttttttttt         tt   ttt     ttttt           ttt  ttt |
|tt        ttt    ttttt          ttttttt  ttt   ttt     t  tt ttt tt ttt   t    ttt |
|ttttt   ttttt    ttttttttt             tt   t   tttt  tttt   tttt t tt t   t t tt  |
|ttt          tt             ttttttttttt  tttt t t    ttttttt       tttt  ttt ttt  t|
|tttttttttttt        tt  tttt       tttt     ttt   tttt    t  t ttttt       ttt   tt|
|   tt   tttt     tt t        ttttt        tttt  ttt   ttt  t ttt           tt  ttt |
|    t    ttt   tttt tttttt        tttt      ttt   ttt  ttt   tt ttt                |
|ttttttt                         ttttttt      tt  ttt    tt  t         tttt ttt tttt|
|t           ttttttt    ttttttttttttttttt    tt  t  t  t  tttt  tttt   tttt         |
|ttt   tttt            ttt    tttt   tttt   ttt    t  t t     ttt      tttt   ttt   |
|tttt   tt  tttt  t ttttt  tt  ttt t   tt      tt         tt  tttttt           tt   |
|tt     t                   ttt  tt   ttt     tt    tttttt                tttt      |
|ttttt       tttttt    tt             t tt   ttt      ttt     ttttt  ttttttttt      |
|ttt      tttttt   tt  ttttttttttttttttttt       ttt          ttttttttt        tt  t|
|    ttt            tt      t  tttttttttttttttt  ttttt  tttt  ttttt     tttttttttt  |
| tt     tttt       t  ttt        ttttttttt     t     tt    tt       ttttttttttttt  |
| ttt tt                    ttt         ttt                     tttttt              |
|tttttttttttttttttt      tttttttttttt ttttttttttt ttttt ttttttttt     tttttttt      |
|       ttttttt          tttt                            tttt           ttttttt     |
|tttttt   tt      tttt        tttttttt  ttt       ttttttttttttttttttttttttt  ttt  tt|
|   ttttt  ttt   ttttttttttttttttttttt tttttttttt    ttttt    tttttttttt    ttt    t|
|t                tttt         tttttt   tttttt    tttttttttttttt           tt   t  t|
|tt  tttt    ttttttttt  tttttt    t t tttttttttt     tttttttttttttttttttttttt   tttt|
|t  tttttttttttttttt   tttttttttt  t  ttttttttt      ttttttt        t     t    t ttt|
|t ttt           tt  ttt    tttttt           ttttttt   ttttttttttttttttttttttt    tt|
|t t     t t ttttttttttttttttttttttttttttt  ttttttttt   tttttt    tttttt        t  t|
|t   ttttt t t   ttttttt    ttt         ttt  ttttttt  ttttttttttttttt    ttttt     t|
|t   tt     tttt  tttttt    ttttttttttttttt tttttt tt tt  tttttttttttt   ttttttttttt|
|t  ttttt ttt  ttttttttt    ttttt         t  tttttttttttttttt tt    tttt  tttt  tttt|
|t    ttt  ttttttttttttt    tttt    t  tt        tttttt  tt ttt  ttt    t  tt      t|
|t@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@t|
|tttttttttt         ttttttt  ttttttt tttttttttt  ttttt   tt  tt   tttttttttt    t @ |
|tttttttttttttttt                    ttttttttttt         ttttttt             ttttt@ |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave5.dat ________________________________________
processed: 3728 ; hit wall: 4553 ; out of light: 18 ; pruned: 6443 ; path length: 63 ; time: 27ms
light along the path: [15, 29, 43, 57, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xx    xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx                     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx xxxxxxxxx     xxxxxxxt      |
|       xxxxttt          xxxt                            txxt           txxxxxx     |
|xxxxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx    x|
|t                xxxx         xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx   x  x|
|xx  xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx   xtxx|
|x  xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t    x xxx|
|x xxx           xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx    xx|
|x x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxt        x  x|
|x@x   xxxxx x x   xxxxxxx    xxx       xxx  xxxxxxx  xxxxxxxxxxxxxxx    xxxxx     x|
|x@x          ttxx  xxxxxxxxxxxxxxxxxxxxx xxxxxx xx xxxxxxxxxtttxx    xxxxxxxxxxxxtt|
|x@x  xxxxx xxx  xxxxxxxxx    xxxxx       x  xxxxxxxxxxxxxxxx xx    xxxt  xxxt  xxxx|
|x@x                                                  x  xx xxt  xxx    x  xx      x|
|x@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ xx     x   txx xxxx  xx x|
|xxxxxxxxxx         xxxxxxx xxxxxxxx xxxxxxxxxx  xxxxx   xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxxt         xxtxxxx             xxxxx  |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave5A.dat ________________________________________
processed: 31 ; hit wall: 43 ; out of light: 0 ; pruned: 40 ; path length: 6 ; time: 0ms
light along the path: [15, 29, 43, 57, 56, 55, 54]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xx    xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx                     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx xxxxxxxxx     xxxxxxxt      |
|       xxxxttt          xxxt                            txxt           txxxxxx     |
|xxxxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx    x|
|t  ttttttttttttttttttt xxxx   xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx   x  x|
|xxt xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx   xtxx|
|xt xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t    x xxx|
|x@              xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx    xx|
|x@x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxt        x  x|
|x@x   xxxxx x x   xxxxxxx    xxx       xxx  xxxxxxx  xxxxxxxxxxxxxxx    xxxxx     x|
|x@x          ttxx  xxxxxxxxxxxxxxxxxxxxx xxxxxx xx xxxxxxxxxtttxx    xxxxxxxxxxxxtt|
|x@x  xxxxx xxx  xxxxxxxxx    xxxxx       x  xxxxxxxxxxxxxxxx xx    xxxt  xxxt  xxxx|
|x@x                                                  x  xx xxt  xxx    x  xx      x|
|x@                                                        xx     x   txx xxxx  xx x|
|xxxxxxxxxx         xxxxxxx xxxxxxxx xxxxxxxxxx  xxxxx   xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxxt         xxtxxxx             xxxxx  |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave5B.dat ________________________________________
processed: 23 ; hit wall: 24 ; out of light: 0 ; pruned: 42 ; path length: 10 ; time: 0ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5]
xxxxxxxxxxxxxx
x    x    x  x
x  @@xxxxxxxxx
x   @@@@@@@@ x
x          @ x
xxxxxxxxxxxxxx

____________________ CodeQuest2014/cave5F.dat ________________________________________
processed: 1336 ; hit wall: 1552 ; out of light: 20 ; pruned: 2373 ; path length: 85 ; time: 6ms
light along the path: [15, 29, 43, 57, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx@x   xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt    x@x   xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  x@xx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xxx@x xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx             x@x     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx x@xxxxxxx     xxxxxxxt      |
|       xxxxttt          xxxt                           x@xxt           txxxxxx     |
|xxxxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxx@xxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxx@    xxxxxxxxxx    xxx    x|
|t      x         xxxx         xxxxxx   xxxxxx    xxxxxxx@xxxxxx           xx   x  x|
|xx  xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxx@xxxxxxxxxxxxxxxxxxx   xtxx|
|x txxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxx@xt        t     t    x xxx|
|x xxx           xx  xxx    xxxxxx           xxxxxxx   xx@xxxxxxxxxxxxxxxxxxxx    xx|
|x x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   x@xxxx    xxxxxt        x  x|
|x@x   xxxxx x x   xxxxxxx    xxx       xxx  xxxxxxx  xxx@xxxxxxxxxxx    xxxxx     x|
|x@x          ttxx  xxxxxxxxxxxxxxxxxxxxx xxxxxx xx xxxxx@xxxtttxx    xxxxxxxxxxxxtt|
|x@x  xxxxx xxx  xxxxxxxxx    xxxxx       x  xxxxxxxxxxxx@xxx xx    xxxt  xxxt  xxxx|
|x@x                                                  x  @x xxt  xxx    x  xx      x|
|x@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@        @@ xx     x   txx xxxx  xx x|
|xxxxxxxxxx         xxxxxxx xxxxxxxx xxxxxxxxxx@ xxxxx  @xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxx@@@@@@@@@@xxtxxxx             xxxxx  |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave5G.dat ________________________________________
processed: 1293 ; hit wall: 1481 ; out of light: 20 ; pruned: 2316 ; path length: 85 ; time: 7ms
light along the path: [15, 29, 43, 57, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx@x   xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt    x@x   xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  x@xx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xxx@x xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx             x@x     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx x@xxxxxxx     xxxxxxxt      |
|       xxxxttt          xxxt                           x@xxt           txxxxxx     |
|xxxxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxx@xxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxx@    xxxxxxxxxx    xxx    x|
|t      x         xxxx         xxxxxx   xxxxxx    xxxxxxx@xxxxxx           xx   x  x|
|xx  xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxx@xxxxxxxxxxxxxxxxxxx   xtxx|
|x txxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxx@xt        t     t    x xxx|
|x xxx           xx  xxx    xxxxxx           xxxxxxx   xx@xxxxxxxxxxxxxxxxxxxx    xx|
|x x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   x@xxxx    xxxxxt        x  x|
|x@x   xxxxx x x   xxxxxxx    xxx       xxx  xxxxxxx  xxx@xxxxxxxxxxx    xxxxx     x|
|x@x          xxxx  xxxxxxxxxxxxxxxxxxxxx xxxxxx xx xxxxx@xxxtttxx    xxxxxxxxxxxxtt|
|x@x  xxxxx xxx  xxxxxxxxx    xxxxx       x  xxxxxxxxxxxx@xxx xx    xxxt  xxxt  xxxx|
|x@x                                                  x  @x xxt  xxx    x  xx      x|
|x@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@        @@ xx     x   txx xxxx  xx x|
|xxxxxxxxxx         xxxxxxx xxxxxxxx xxxxxxxxxx@ xxxxx  @xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxx@@@@@@@@@@xxtxxxx             xxxxx  |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave5H.dat ________________________________________
processed: 1372 ; hit wall: 1622 ; out of light: 22 ; pruned: 2402 ; path length: 119 ; time: 6ms
light along the path: [15, 29, 43, 57, 71, 70, 69, 68, 82, 81, 80, 79, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx @@@x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   x@x@@x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx x@xx@@@xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx  x@xx  @@        xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x@@xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x@ x  xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx       x@ xx xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxx@x               xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx@x   xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt    x@x   xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  x@xx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xxx@x xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx             x@x     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx x@xxxxxxx     xxxxxxxt      |
|       xxxxttt          xxxt                           x@xxt           txxxxxx     |
|xxxxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxx@xxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxx@    xxxxxxxxxx    xxx    x|
|@@@    x         xxxx         xxxxxx   xxxxxx    xxxxxxx@xxxxxx           xx   x  x|
|xx@ xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxx@xxxxxxxxxxxxxxxxxxx   xtxx|
|x@@xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxx@xt        t     t    x xxx|
|x@xxx           xx  xxx    xxxxxx           xxxxxxx   xx@xxxxxxxxxxxxxxxxxxxx    xx|
|x@x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   x@xxxx    xxxxxt        x  x|
|x@x   xxxxx x x   xxxxxxx    xxx       xxx  xxxxxxx  xxx@xxxxxxxxxxx    xxxxx     x|
|x@x          xxxx  xxxxxxxxxxxxxxxxxxxxx xxxxxx xx xxxxx@xxxtttxx    xxxxxxxxxxxxtt|
|x@x  xxxxx xxx  xxxxxxxxx    xxxxx       x  xxxxxxxxxxxx@xxx xx    xxxt  xxxt  xxxx|
|x@x                                                  x  @x xxt  xxx    x  xx      x|
|x@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@        @@ xx     x   txx xxxx  xx x|
|xxxxxxxxxx         xxxxxxx xxxxxxxx xxxxxxxxxx@ xxxxx  @xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxx@@@@@@@@@@xxtxxxx             xxxxx  |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave5x.dat ________________________________________
processed: 1225 ; hit wall: 1426 ; out of light: 24 ; pruned: 2154 ; path length: -1 ; time: 5ms
light along the path: []
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xx    xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx                     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx xxxxxxxxx     xxxxxxxt      |
|ttt    xxxxttt   x      xxxt                            txxt           txxxxxx     |
|xxxxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx    x|
|t                xxxx         xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx   x  x|
|xx  xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx   xtxx|
|x  xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t    x xxx|
|x xxx           xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx    xx|
|x x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxt        x  x|
|xtx   xxxxx x x   xxxxxxx    xxx       xxx  xxxxxxx  xxxxxxxxxxxxxxx    xxxxx     x|
|xtx            xx  xxxxxxxxxxxxxxxxxxxxx xxxxxx xx xxxxxxxxxtttxx    xxxxxxxxxxxx  |
|xtx  xxxxx xxx  xxxxxxxxx    xxxxx       x  xxxxxxxxxxxxxxxx xx    xxx   xxx  xxxxT|
|xtx                                                  x  xx xx   xxx    x  xx       |
|xH                                                               x    xx xxxx  xx x|
|xxxxxxxxxx         xxxxxxx xxxxxxxx xxxxxxxxxx  xxxxx   xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxxx         xxxxxxx             xxxxx  |
-------------------------------------------------------------------------------------

###  NO PATH  ###

____________________ CodeQuest2014/cave6.dat ________________________________________
processed: 7326 ; hit wall: 9992 ; out of light: 74 ; pruned: 11661 ; path length: 162 ; time: 37ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 16, 30, 44, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 35, 34, 33, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xx    xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx                     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx xxxxxxxxx     xxxxxxxt      |
|       xxxx@@@@         xxxt                            txxt           txxxxxx     |
|xxxxxx   xx  @@  xxxx        xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx@@ xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx    x|
|@@@@@@@@@@@@@@@  xxxx         xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx   x  x|
|xx@ xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx   xtxx|
|x@@xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t    x xxx|
|x@xxx           xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx    xx|
|x@x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxt        x  x|
|x@@@xxxxx x x   xxxxxxx    xxx         xxx  xxxxxxx  xxxxxxxxxxxxxxx    xxxxx     x|
|x@ @@@@@@xxxxx      xxxxxxxxxxxxxxx   xxxxxx xx xx  xxxxxxxxtttxx    xxxxxxxxxxxxtt|
|x@ xxxxx@xxx  xxxxxxxxx    xxxxx     @@@@x  xxxxxxxxxxxxxxxx xx    xxxt  xxxt  xxxx|
|x@   xxx@@xxxxxxxxxxxxx    xxxx    x@@xx@@@@@@@ xxxxxx  xx xx@@ xxx    x  xx  @@@@x|
|x@  xx xx@x xx xx xx xxxxxxxxxx  xx@@xxxxx    @ xxxx   @@@@@@@@x    txx  xxxx @xx@x|
|xxxxxxxxx@@@@@@@@@@xxxxxx@@@@xxxxxx@xxxxxxxxxx@ xxxxx  @xx  xx@@@xxxxxxxxxx@@@@x @ |
|xxxxxxxxxxxxxxxx  @@@@@@@@  @@@@@@@@xxxxxxxxxx@@@@@@@@@@xxxxxxx @@@@@@@@@@@@xxxxx@ |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave6-1.dat ________________________________________
processed: 950 ; hit wall: 1422 ; out of light: 16 ; pruned: 1342 ; path length: 162 ; time: 4ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 16, 30, 44, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 35, 34, 33, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xx    xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx                     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx xxxxxxxxx     xxxxxxxt      |
|       xxxx@@@@  x      xxxt                            txxt           txxxxxx     |
|xxxxxx   xx  @@  xxxx        xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx@@ xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx    x|
|@@@@@@@@@@@@@@@  xxxx         xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx   x  x|
|xx@ xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx   xtxx|
|x@@xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t    x xxx|
|x@xxx           xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx    xx|
|x@x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxt        x  x|
|x@@@xxxxx x x   xxxxxxx    xxx         xxx  xxxxxxx  xxxxxxxxxxxxxxx    xxxxx     x|
|x@ @@@@@@xxxxx      xxxxxxxxxxxxxxx   xxxxxx xx xx  xxxxxxxxtttxx    xxxxxxxxxxxxtt|
|x@ xxxxx@xxx  xxxxxxxxx    xxxxx     @@@@x  xxxxxxxxxxxxxxxx xx    xxxt  xxxt  xxxx|
|x@   xxx@@xxxxxxxxxxxxx    xxxx    x@@xx@@@@@@@ xxxxxx  xx xx@@ xxx    x  xx  @@@@x|
|x@  xx xx@x xx xx xx xxxxxxxxxx  xx@@xxxxx    @ xxxx   @@@@@@@@x    txx  xxxx @xx@x|
|xxxxxxxxx@@@@@@@@@@xxxxxx@@@@xxxxxx@xxxxxxxxxx@ xxxxx  @xx  xx@@@xxxxxxxxxx@@@@x @ |
|xxxxxxxxxxxxxxxx  @@@@@@@@  @@@@@@@@xxxxxxxxxx@@@@@@@@@@xxxxxxx @@@@@@@@@@@@xxxxx@ |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave7.dat ________________________________________
processed: 1081 ; hit wall: 1335 ; out of light: 7 ; pruned: 1789 ; path length: 44 ; time: 5ms
light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 18, 17, 16, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx      |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxt        xx  x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx     xxxxxxxxxx  |
| xx     txxx       t  xxx        xxxxxxttt     x     xx    xx       xxxxxxxxxxxxx  |
| xxx xx                    xxx         xxx                     xxxxxt              |
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx xxxxxxxxx     xxxxxxxt      |
|       xxxxttt          xxxt                            txxt           txxxxxx     |
|xxxxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx  xt|
|   xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx    x|
|t                xxxx         xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx   x  x|
|xx  xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx   xtxx|
|x  xxx@@@@xxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t    x xxx|
|x xxx @  @@@@@@@xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx    xx|
|x x@@@@ x x xxx@xxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxt        x  x|
|x  @xxxxx x x  @xtxxxxx    xxx         xxx  xxxxxxx  xxxxxxxxxxxxxxx    xxxxx     x|
|x @@xx  xxxxxx @@@@@xxxxxxxxxxxxxxx   xxxxxx xx xx  xxxxxxxxtttxx    xxxxxxxxxxxxtt|
|x @xxxxx xxx  xxxxx@xxx    xxxxx         x  xxxxxxxxxxxxxxxx xx    xxxt  xxxt  xxxx|
|x @  xxx  xxxxxxxxx@@xx    xxxx    x  xx        xxxxxx  xx xxt  xxx    x  xx      x|
|x@@ xx xx x xx xx xx@txxxxxxxxx  xx  xxxxx      xxxx    xx     x    txx  xxxx  xx x|
|xxxxxxxxxt         x@xxxxt  txxxxxx xxxxxxxxxx  xxxxx   xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx    @@@@@@@@@@       xxxxxxxxxxt         xxtxxxx            xxxxx  |
-------------------------------------------------------------------------------------

____________________ CodeQuest2014/cave8.dat ________________________________________
processed: 5192 ; hit wall: 6113 ; out of light: 14 ; pruned: 9142 ; path length: 49 ; time: 31ms
light along the path: [15, 29, 43, 57, 71, 85, 99, 113, 112, 126, 125, 124, 123, 122, 121, 120, 119, 118, 117, 116, 115, 114, 113, 112, 126, 125, 124, 123, 122, 121, 120, 119, 118, 117, 116, 115, 114, 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101]
-------------------------------------------------------------------------------------
|xt      xxxx  @xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x   @@  xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx @           xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt  @ xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx  @ xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx@            xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx   @    xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx  @@ xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx  @xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx    @@@@                 xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t          @xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx@@          xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx @xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x  @                xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt   @@@ xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx      |
|xxx     @xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxt        xx  x|
|    xxx @          xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx     xxxxxxxxxx  |
| xx  @@@@xxx       t  xxx        xxxxxxttt     x     xx    xx       xxxxxxxxxxxxx  |
| xxx @x                    xxx         xxx                     xxxxxt              |
|xxxxx@ xxxxxxxx         xxxxxxxxxxxx xxxxxxxxxxx xxxxx xxxxxxxxx     xxxxxxxt      |
| @@@@@ xxxxttt          xxxt                            txxt           txxxxxx     |
|x@xxxx   xx      xxxx        xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx  xt|
| @@xxxxx  xxx   xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx    x|
|t @ttttttttttttttttttt xxxx   xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx   x  x|
|xx@ xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx   xtxx|
|x@@xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t    x xxx|
|x@xxx           xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx    xx|
|x@x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxt        x  x|
|x@x   xxxxx x x   xxxxxxx    xxx       xxx  xxxxxxx  xxxxxxxxxxxxxxx    xxxxx     x|
|x@x          ttxx  xxxxxxxxxxxxxxxxxxxxx xxxxxx xx xxxxxxxxxtttxx    xxxxxxxxxxxxtt|
|x@x  xxxxx xxx  xxxxxxxxx    xxxxx       x  xxxxxxxxxxxxxxxx xx    xxxt  xxxt  xxxx|
|x@x                                                  x  xx xxt  xxx    x  xx      x|
|x@                                                        xx     x   txx xxxx  xx x|
|xxxxxxxxxx         xxxxxxx xxxxxxxx xxxxxxxxxx  xxxxx   xx  xx   xxxxxxxxxx    x   |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxxt         xxtxxxx             xxxxx  |
-------------------------------------------------------------------------------------


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

processed: 5816 ; hit wall: 7891 ; out of light: 84 ; pruned: 9216 ; path length: 200 ; time: 32ms light along the path: [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 17, 31, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 15, 14, 13, 12, 11, 10, 9, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 22, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10]
-------------------------------------------------------------------------------------
|xt      xxxx   xxx  xxxxt            xxxxx   xxx  xxxx   xxxx xxxxxxxxx  xxx       |
|xxxxxxx   x       xxxxxxxx      xxxxxx   xx    xx   xxxx      xxxx   xxxx     xxxx |
|xxxx  xx    xx             xxxxxxxxt         xx   xxx     xxxxx           xxx  xxx |
|xt        xxt    xxxxt          xxxxxxx  xxx   txx     x  xx xxx xx xxx   x    xxx |
|xxxxx   xxxxx    xxxxxxxxx             xx   x   xxxx  xxxt   xxxx x xx x   x x xx  |
|xxx          xx             xxxxxxxxxxx  xxxx x x    xxxxxxx       xxxx  xxx xxx  x|
|xxxxxxxxxxxx        xx  xxxx       xxxx     xxx   xxxx    x  x xxxxx       txx   xx|
|   xt   xxxx     xx t        xxxxx        xxxt  xxx   xxx  x xxt           xx  xxx |
|    x    xxx   xxxx xxxxxx        xxxx      xxx   xxx  xxx   xx xxx                |
|xxxxxxx                         xxxxxtt      xx  xxx    xx  x         xxxx xxx xxxt|
|t           xxxxxxx    xxxxxxxxxxxxxxxxx    xx  x  x  x  xxtx  xxxx   xxxx         |
|xxx   xxxx            xxt    xxxx   xxxx   xxx    x  x x     xxx      xxxx   xxx   |
|xxxx   xx  xxxx  x xxxxx  xx  xxx x   xt      xx         xx  xxxxxx           xx   |
|xx     x                   xxx  xx   xxx     xx    xxxxxx                xxxx      |
|xxxxt       xxxxxt    xx             t xx   xxx      xxx     xxxxx  xxxxxxxxx••••• |
|xxx      xxxxxx   xx  xxxxxxxxxxxxxxxxxxx       xxt          xxxxxxxxT••••••••xx •x|
|    xxx            xx      x  xxxxxxxxxxxxxxxx  xxxxx  xxxx  xxxxx ••• xxxxxxxxxx••|
| xx     txxx       t  xxx        xxxxxxttt     x     xx    xx ••••••xxxxxxxxxxxxx •|
| xxx xx                    xxx         xxx            •••••••••xxxxxt             •|
|xxxxxxxxxxxxxxxxxx      xxxxxxxxxxxx xxxxxxxxxxx xxxxx•xxxxxxxxx     xxxxxxxt     •|
|       xxxxTTT••••••••••xxxT••••••••••••••••••••••••••●●Txxt           txxxxxx  ••●|
|xxxxxx   xx  •   xxxx  ••••• xxxxxxxx  xxx       xxxxxxxxxxxxxxxxxxxxxxxxx  xxx •xT|
|   xxxxx  xxx•  xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx    xxxxx    xxxxxxxxxx    xxx••● x|
|T●●•••••••••••   xxxx         xxxxxx   xxxxxx    xxxxxxxxxxxxxx           xx ••x● x|
|xx• xxxx    xxxxxxxxx  xxxxxx    x x xxxxxxxxxx     xxxxxxxxxxxxxxxxxxxxxxxx • xTxx|
|x••xxxxxxxxxxxxxxxx   xxxxxxxxxx  x  xxxxxxxxx      xxxxxxt        t     t   •x xxx|
|x•xxx           xx  xxx    xxxxxx           xxxxxxx   xxxxxxxxxxxxxxxxxxxxxxx••••xx|
|x•x     x x xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  xxxxxxxxx   xxxxxx    xxxxxT••••••••x••x|
|x•  xxxxx x x   xxxxxxx    xxx         xxx  xxxxxxx  xxxxxxxxxxxxxxx••• xxxxx •••●x|
|x•  ttxx  xxxxxx    xxxxxxxxxxxxxxx   xxxxxx xx xx  xxxxxxxxtttxx••••xxxxxxxxxxxxTT|
|x•     x xxx  xxxxxxxxx    xxxxx         x  xxxxxxxxxxxxxxxx xx••• xxxt  xxxt  xxxx|
|x•   xxx  xxxxxxxxxxxxx    xxxx    x  xx        xxxxxx  xx xxT●•xxx    x  xx  ••••x|
|xH  xx xx x xx xx xx xxxxxxxxxx  xx  xxxxx      xxxx    xx    •x    txx  xxxx •xx•x|
|xxxxxxxxxt         xxxxxxt  txxxxxx xxxxxxxxxx  xxxxx   xx  xx•••xxxxxxxxxx••••x • |
|xxxxxxxxxxxxxxxx                    xxxxxxxxxxt         xxtxxxx ••••••••••••xxxxxT |
-------------------------------------------------------------------------------------


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()

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

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.