If there's anything confusing, please refer to "Disposable teleports"
Link: http://bradyisstudying.blogspot.tw/2014/04/checkiopython-disposable-teleports.html
--
Some tricks are used for this task.
(1) map refinement to avoid 2x2 quad dead-lock
(2) path recording to avoid circular dead-lock
There is a strong relation between (1) and (2) and I believe (2) is a more general solution.
I will review my code sooner or later to make it more clear and intuitive
--
Following is the "raw" source code which is counter-intuitive, confusing, and containing lots of redundant code right now.LOL
def is_north_valid(cur_pos, maze_map):
if cur_pos[0] - 1 < 0:
return False
if maze_map[ cur_pos[0] - 1][cur_pos[1]] == 0:
return True
return False
def is_south_valid(cur_pos, maze_map):
if cur_pos[0] + 1 >= len(maze_map):
return False
if maze_map[ cur_pos[0] + 1][cur_pos[1]] == 0:
return True
return False
def is_east_valid(cur_pos, maze_map):
if cur_pos[1] + 1 >= len(maze_map):
return False
if maze_map[ cur_pos[0]][cur_pos[1]+1] == 0:
return True
return False
def is_west_valid(cur_pos, maze_map):
if cur_pos[1] - 1 < 0:
return False
if maze_map[ cur_pos[0]][cur_pos[1]-1] == 0:
return True
return False
def get_num_to_go(cur_pos, maze_map):
count = 0
if is_south_valid(cur_pos, maze_map):
count += 1
if is_north_valid(cur_pos, maze_map):
count += 1
if is_west_valid(cur_pos, maze_map):
count += 1
if is_east_valid(cur_pos, maze_map):
count += 1
return count
def suggest_go(cur_pos, maze_map, prev_dir, direct):
num_to_go = get_num_to_go(cur_pos, maze_map)
if num_to_go > 1 and prev_dir == direct:
return False
else:
return True
def never_go(cur_pos, record_map, direct):
record = record_map[ cur_pos[0] ][ cur_pos[1] ]
#print(record)
#print(direct)
if direct not in record:
return True
else:
return False
def which_dir(cur_pos, l_path, maze_map, record_map, pop):
#print ('qq: '+str(record_map[9][5]))
if pop == False:
prev_dir = ''
if len(l_path) > 0:
prev_dir = l_path[ len(l_path) - 1 ]
if is_south_valid(cur_pos, maze_map) == True and prev_dir != 'N' and never_go(cur_pos, record_map, 'S') == True:
l_path.append('S')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('S')
pop = False
cur_pos[0] += 1
return 'south'
elif is_east_valid(cur_pos, maze_map) == True and prev_dir != 'W' and never_go(cur_pos, record_map, 'E') == True:
l_path.append('E')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('E')
pop = False
cur_pos[1] += 1
return 'east'
elif is_west_valid(cur_pos, maze_map) == True and prev_dir != 'E' and never_go(cur_pos, record_map, 'W') == True:
l_path.append('W')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('W')
cur_pos[1] -= 1
pop = False
return 'west'
elif is_north_valid(cur_pos, maze_map) == True and prev_dir != 'S' and never_go(cur_pos, record_map, 'N') == True:
l_path.append('N')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')
cur_pos[0] -= 1
pop = False
return 'north'
else:
#return 'dead'
print('d')
pop = True
return which_dir(cur_pos, l_path, maze_map, record_map, pop)
else: # pop case
prev_dir = l_path.pop()
prev_2_dir = l_path[ len(l_path) - 1 ]
if prev_dir == 'S':
cur_pos[0] -= 1
if is_east_valid(cur_pos, maze_map) == True and prev_2_dir != 'W':
l_path.append('E')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('E')
cur_pos[1] += 1
pop = False
return 'east'
elif is_west_valid(cur_pos, maze_map) == True and prev_2_dir != 'E':
l_path.append('W')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('W')
cur_pos[1] -= 1
pop = False
return 'west'
elif is_north_valid(cur_pos, maze_map) == True and prev_2_dir != 'S':
l_path.append('N')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')
cur_pos[0] -= 1
pop = False
return 'north'
else:
#return 'dead'
pop = True
return which_dir(cur_pos, l_path, maze_map, record_map, pop)
elif prev_dir == 'E':
cur_pos[1] -= 1
if is_west_valid(cur_pos, maze_map) == True and prev_2_dir != 'E':
l_path.append('W')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('W')
cur_pos[1] -= 1
pop = False
return 'west'
elif is_north_valid(cur_pos, maze_map) == True and prev_2_dir != 'S':
l_path.append('N')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')
cur_pos[0] -= 1
pop = False
return 'north'
else:
#return 'dead'
pop = True
return which_dir(cur_pos, l_path, maze_map, record_map, pop)
elif prev_dir == 'W':
cur_pos[1] += 1
if is_north_valid(cur_pos, maze_map) == True and prev_2_dir != 'S':
l_path.append('N')
record_map[ cur_pos[0] ][ cur_pos[1] ].append('N')
cur_pos[0] -= 1
pop = False
return 'north'
else:
#return 'dead'
pop = True
return which_dir(cur_pos, l_path, maze_map, record_map, pop)
elif prev_dir == 'N':
cur_pos[0] += 1
#return 'dead'
pop = True
return which_dir(cur_pos, l_path, maze_map, record_map, pop)
def only_one_exit(row, col, maze_map):
count = 0
exit_code = 0
if maze_map[row][col-1] == 0:
exit_code = 1
count += 1
if maze_map[row+1][col-1] == 0:
exit_code = 2
count += 1
if maze_map[row-1][col] == 0:
exit_code = 3
count += 1
if maze_map[row-1][col+1] == 0:
exit_code = 4
count += 1
if maze_map[row+2][col] == 0:
exit_code = 5
count += 1
if maze_map[row+2][col+1] == 0:
exit_code = 6
count += 1
if maze_map[row][col+2] == 0:
exit_code = 7
count += 1
if maze_map[row+1][col+2] == 0:
exit_code = 8
count += 1
if count == 1:
return [True, exit_code]
else:
return [False, exit_code]
def refine_map(maze_map):
#case 1 : quad all zero
# 1 1 1 1
# 1 0 0 1
# 1 0 0 1
# 1 1 1 1
for row in range(2, len(maze_map) - 2): #dont need to touch (1,1) and (10, 10)
for col in range(2, len(maze_map) - 2):
if maze_map[row][col] == 0 and maze_map[row][col+1] == 0 and maze_map[row+1][col] == 0 and maze_map[row+1][col+1] == 0:
#print ('found quad: '+ str(row) +' '+ str(col))
l_map_scanner = only_one_exit(row, col, maze_map)
if l_map_scanner[0] == True:
#print ('found quad with one exit: '+ str(row) +' '+ str(col))
if l_map_scanner[1] == 1 or l_map_scanner[1] == 7:
maze_map[row + 1][col] = 1
maze_map[row + 1][col + 1] = 1
if l_map_scanner[1] == 2 or l_map_scanner[1] == 8:
maze_map[row][col] = 1
maze_map[row][col + 1] = 1
if l_map_scanner[1] == 3 or l_map_scanner[1] == 5:
maze_map[row][col + 1] = 1
maze_map[row + 1][col + 1] = 1
if l_map_scanner[1] == 4 or l_map_scanner[1] == 6:
maze_map[row ][col] = 1
maze_map[row + 1][col] = 1
return maze_map
def get_record_map(dim):
l_record_map = [ ]
ll_record_map = [ ]
for row in range(0, dim):
for col in range(0, dim):
l_record_map.append([ ])
ll_record_map.append(l_record_map)
l_record_map = [ ]
return ll_record_map
def checkio(maze_map):
l_path = [ ]
cur_pos = [1, 1]
maze_map = refine_map(maze_map)
record_map = get_record_map(len(maze_map))
#print(maze_map)
#for i in range(0, 50):
while cur_pos != [10, 10]:
dir = which_dir(cur_pos, l_path, maze_map, record_map, False)
#print(dir)
return ''.join(l_path)
沒有留言:
張貼留言