Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Path backtracking solution in Clear category for Forgetful Prisoner by cimarronm
from collections import OrderedDict
DIRS = OrderedDict((('N', (-1, 0)), ('S', (1, 0)),
('W', (0, -1)), ('E', (0, 1))))
CODES = {'N': 0, 'S': 1, 'W': 2, 'E': 3}
OPPOSITE_DIR = {0: 'S', 1: 'N', 2: 'E', 3: 'W'}
BACKTRACED = 1<<2
CODESIZE = 3 # 2 bits for direction and 1 bit for backtrace flag
DEPTHSIZE = 5 # 32 maximum of 31 entries
MEMORYSIZE = 100
def been_there(memory, depth, movement):
loc = (0, 0)
check = DIRS[movement]
while depth:
delta = DIRS[OPPOSITE_DIR[memory & CODESIZE]]
loc = loc[0] + delta[0], loc[1] + delta[1]
if loc == check:
return True
memory >>= CODESIZE
depth -= 1
return False
def find_path(scanner, memory):
'''
Employ a DFS search with backtracing
'''
# get move count depth from memory
depth = memory & (1 << DEPTHSIZE)-1
memory >>= DEPTHSIZE
for dir in DIRS:
# look for path we have never been down
if scanner[dir] > 0 and not been_there(memory, depth, dir):
memory <<= CODESIZE
memory |= CODES[dir]
depth += 1
break
else: # no new possible moves, backtrack
# find last position not already backtraced
while memory & BACKTRACED:
memory >>= CODESIZE
depth -= 1
# get opposite direction and mark as backtraced
dir = OPPOSITE_DIR[memory & CODESIZE]
memory |= BACKTRACED
# add opposite move
memory <<= CODESIZE
memory |= BACKTRACED | CODES[dir]
depth += 1
memory <<= DEPTHSIZE
memory |= depth if depth < (1<= 2 ** 100:
print("The memory number should be an integer from 0 to 2**100.")
return False
for act in result:
if step >= MAX_STEP:
print("You are tired and your scanner is off. Bye bye.")
return False
r, c = player[0] + DIR[act][0], player[1] + DIR[act][1]
if maze[r][c] == WALL:
print("BAM! You in the wall at {}, {}.".format(r, c))
return False
elif maze[r][c] == EXIT:
print("GRATZ!")
return True
else:
player = r, c
step += 1
assert checker(find_path, (1, 1), [
"XXXXXXXXXXXX",
"X..........X",
"X.XXXXXXXX.X",
"X.X......X.X",
"X.X......X.X",
"X.X......X.X",
"X.X......X.X",
"X.X......X.X",
"X.X......X.X",
"X.XXXXXXXX.X",
"X.........EX",
"XXXXXXXXXXXX",
]), "Simple"
assert checker(find_path, (1, 4), [
"XXXXXXXXXXXX",
"XX...X.....X",
"X..X.X.X.X.X",
"X.XX.X.X.X.X",
"X..X.X.X.X.X",
"XX.X.X.X.X.X",
"X..X.X.X.X.X",
"X.XX.X.X.X.X",
"X..X.X.X.X.X",
"XX.X.X.X.X.X",
"XE.X.....X.X",
"XXXXXXXXXXXX",
]), "Up Down"
assert checker(find_path, (10, 10), [
"XXXXXXXXXXXX",
"X..........X",
"X.XXXXXXXX.X",
"X.X......X.X",
"X.X.XX.X.X.X",
"X.X......X.X",
"X.X......X.X",
"X.X..E...X.X",
"X.X......X.X",
"X.XXXX.XXX.X",
"X..........X",
"XXXXXXXXXXXX",
]), "Left"
April 13, 2015
Comments:
