Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /
- -S-
- /
- 0 0 0 0
- 0 + 0 + 0
- 0 0 0 + + 0
- 0 + 0 + 0 + 0
- 0 0 + + 0 0 + 0
- 0 0 + 0 + 0 0 + 0
- E 0 + 0 0 + + 0
- + + 0 + 0 + 0
- 0 0 0 0 0 +
- + 0 + + +
- 0 S 0 0
- >>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF
- + 0 0 0 0 0 0
- 0 0 0 0 0 + + 0
- 0 0 E 0 + 0 0 + 0
- 0 0 0 0 0 0 0 +
- 0 + 0 0 + + +
- 0 0 + + 0 0
- S + 0 0 0
- >>>Invalid maze!
- 0 E S
- >>>LF
- E + 0
- 0 + + +
- 0 0 S
- + +
- >>>FFLF
- E
- 0 +
- 0 + +
- 0 +
- S
- >>>RFFLFF
- 0 E + 0 0
- 0 + 0 0 + +
- + 0 + + + 0
- + 0 + 0 + 0
- + + + 0 S
- >>>FFLFLFFRFRFFRFF
- E 0 + + 0
- 0 + 0 + + 0
- + + + 0 + 0
- + 0 0 0 0 0
- + + + + 0
- + 0 S 0
- >>>FLFFRFFRFLF
- z=zip;d=z((-1,1,-2,2,-1,1),(-1,-1,0,0,1,1));E=enumerate;D={};t=tuple;o=list;b=o.index
- for y,i in E(M.split('n')):
- for x,j in E(o(i)):
- c=(x,y);D[c]=j
- if j=='S':s=c
- if j=='E':e=c
- def P(s,e,D,p):
- p=o(p);p.append(s);D=D.copy();D[s]=''
- for i in d:
- c=t(x+y for x,y in z(s,i))
- if c not in p and c in D:
- if D[c]=='E':L.append(p+[c])
- if D[c]=='+':P(c,e,D,p)
- def R(p):
- a=[0,1,3,5,4,2];h=d[0];x=p[0];s=''
- for c in p[1:]:
- r=t(x-y for x,y in z(c,x));n=0
- while h!=r:n+=1;h=d[a[(b(a,b(d,h))+1)%6]]
- s+=['L'*(6-n),'R'*n][n<3]+'F';x=t(x+y for x,y in z(x,h))
- return s
- L=[];P(s,e,D,[])
- try:l=len(min(L))
- except ValueError:print"Invalid maze!"
- else:print min([R(i)for i in L if len(i)==l],key=len)
- maze = """
- 0 0 0 0
- 0 + 0 + 0
- 0 0 0 + + 0
- 0 + 0 + 0 + 0
- 0 0 + + 0 0 + 0
- 0 0 + 0 + 0 0 + 0
- E 0 + 0 0 + + 0
- + + 0 + 0 + 0
- 0 0 0 0 0 +
- + 0 + + +
- 0 S 0 0
- """
- directions = [(-1, -1), (1, -1),
- (-2, 0), (2, 0),
- (-1, 1), (1, 1)]
- maze_dict = {}
- maze_lines = maze.split('n')
- for y, row in enumerate(maze_lines):
- if row:
- for x, item in enumerate(list(row)):
- coordinates = (x, y)
- maze_dict[coordinates] = item
- if item == 'S':
- start = coordinates
- elif item == 'E':
- end = coordinates
- list_of_paths = []
- def find_path(start, end, maze_dict, current_path=None):
- if current_path is None:
- current_path = []
- current_path = list(current_path)
- current_path.append(start)
- current_dict = maze_dict.copy()
- current_dict[start] = '0'
- for direction in directions:
- new_coordinate = (start[0] + direction[0], start[1] + direction[1])
- if new_coordinate in current_path:
- pass
- elif new_coordinate in current_dict:
- if current_dict[new_coordinate] == 'E':
- list_of_paths.append(current_path + [new_coordinate])
- break
- elif current_dict[new_coordinate] == '+':
- find_path(new_coordinate, end, current_dict, current_path)
- find_path(start, end, maze_dict)
- def find_route(path):
- heading_R = [0, 1, 3, 5, 4, 2]
- heading = (-1, -1)
- current_pos = path[0]
- current_heading = directions.index(heading)
- output_string = []
- for coordinate in path[1:]:
- required_heading = (coordinate[0] - current_pos[0], coordinate[1] - current_pos[1])
- count_R = 0
- while heading != required_heading:
- count_R += 1
- heading_index = directions.index(heading)
- heading_order = (heading_R.index(heading_index) + 1) % len(heading_R)
- heading = directions[heading_R[heading_order]]
- if count_R:
- if count_R > 3:
- output_string += ['L'] * (6 - count_R)
- else:
- output_string += ['R'] * count_R
- output_string.append('F')
- current_pos = (current_pos[0] + heading[0], current_pos[1] + heading[1])
- return ''.join(output_string)
- routes = []
- try:
- min_len = len(min(list_of_paths))
- except ValueError:
- print "Invalid maze!"
- else:
- for i in list_of_paths:
- if len(i) == min_len:
- routes.append(find_route(i))
- print 'Shortest route to end: {}'.format(min(routes, key=len))
Add Comment
Please, Sign In to add comment