Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import heapq
- import fileinput
- class Node:
- def __init__(self, state, parent=None, action=None, cost=0):
- self.state = state
- self.parent = parent
- self.action = action
- self.cost = cost
- def get_path_action(self):
- path_actions = []
- node = self
- while node.parent is not None:
- path_actions.append(node.action)
- node = node.parent
- path_actions.reverse()
- return path_actions
- def __str__(self):
- return "-- Node {0} --\n Parent: {1}\n Action: {2}\n Cost: {3}" \
- .format(self.state, self.parent, self.action, self.cost)
- def __lt__(self, other):
- return self.cost < other.cost
- class MazeSolver(object):
- def __init__(self, maze_rows):
- self.maze_rows = maze_rows
- self.start, self.end = self._get_start_end()
- self.FRINGE = 0
- self.EXPANDED = 1
- self.path = None
- def _get_start_end(self):
- start = end = (0, 0)
- for i, _ in enumerate(self.maze_rows):
- for j, _ in enumerate(self.maze_rows[i]):
- if self.maze_rows[i][j] == 'A':
- start = (i, j)
- continue
- if self.maze_rows[i][j] == 'B':
- end = (i, j)
- continue
- return start, end
- def solve(self):
- # Solved with A* algorithm
- fringe = []
- nss = dict()
- heapq.heappush(fringe, (0, Node(self.start)))
- nss[self.start] = (self.FRINGE, 0)
- while fringe:
- n = heapq.heappop(fringe)[1]
- state = n.state
- if nss[state] == self.EXPANDED:
- continue
- if state == self.end:
- self.path = n.get_path_action()
- nss[n] = (self.EXPANDED, n.cost)
- for s, a, c in self._get_successors(n):
- cost = n.cost + c
- heuristic_cost = self._manhattan_distance(s)
- ns = Node(s, n, a, cost)
- if ns.state not in nss:
- total_cost = ns.cost + heuristic_cost
- heapq.heappush(fringe, (total_cost, ns))
- nss[ns.state] = (self.FRINGE, ns.cost)
- elif nss[ns.state][1] > ns.cost and nss[ns.state][0] == self.FRINGE:
- nss[ns.state] = (self.FRINGE, ns.cost)
- def _get_successors(self, node):
- x = node.state[0]
- y = node.state[1]
- actions = ['Right', 'Left', 'Up', 'Down']
- states = [(x,y+1), (x,y-1), (x-1,y), (x+1,y)]
- act_dict = {a: s for a, s in zip(actions, states) if self._is_valid_state(s)}
- for a in act_dict:
- yield act_dict[a], a, 1
- def _is_valid_state(self, state):
- x = state[0]
- y = state[1]
- return x >= 0 and x < len(self.maze_rows) and \
- y >= 0 and y < len(self.maze_rows[0]) and \
- self.maze_rows[x][y] != '#'
- def _manhattan_distance(self, state):
- return abs(self.end[0] - state[0]) + abs(self.end[1] - state[1])
- def draw(self):
- if not self.path:
- print('Error! Path is not computed!')
- return
- curr_x = self.start[0]
- curr_y = self.start[1]
- prev_act = None
- act = None
- next_act = None
- for i in range(len(self.path)):
- prev_act = self.path[i-1] if i > 0 else None
- act = self.path[i]
- next_act = self.path[i+1] if i < len(self.path) - 1 else None
- if act == 'Right':
- curr_y += 1
- elif act == 'Left':
- curr_y -= 1
- elif act == 'Up':
- curr_x -= 1
- elif act == 'Down':
- curr_x += 1
- if act == 'Right' and next_act == 'Up':
- self._set_char(curr_x, curr_y, '┘')
- elif act == 'Right' and next_act == 'Down':
- self._set_char(curr_x, curr_y, '┐')
- elif act == 'Left' and next_act == 'Up':
- self._set_char(curr_x, curr_y, '└')
- elif act == 'Left' and next_act == 'Down':
- self._set_char(curr_x, curr_y, '┌')
- elif act == 'Up' and next_act == 'Left':
- self._set_char(curr_x, curr_y, '┐')
- elif act == 'Up' and next_act == 'Right':
- self._set_char(curr_x, curr_y, '┌')
- elif act == 'Down' and next_act == 'Left':
- self._set_char(curr_x, curr_y, '┘')
- elif act == 'Down' and next_act == 'Right':
- self._set_char(curr_x, curr_y, '└')
- elif act == 'Down' or act == 'Up':
- self._set_char(curr_x, curr_y, '|')
- elif act == 'Right' or act == 'Left':
- self._set_char(curr_x, curr_y, '-')
- def _set_char(self, x, y, c):
- if self.maze_rows[x][y] != 'A' and self.maze_rows[x][y] != 'B':
- row = list(self.maze_rows[x])
- row[y] = c
- self.maze_rows[x] = "".join(row)
- def print_maze(self):
- for r in self.maze_rows:
- print(r)
- def main():
- n_mazes = 0
- current_maze = 0
- mazes = dict()
- solved_mazes = dict()
- # Parse input
- for line in fileinput.input():
- line = line.strip()
- if n_mazes == 0:
- n_mazes = int(line)
- else:
- if line.isdigit():
- current_maze = int(line)
- mazes[current_maze] = []
- else:
- mazes[current_maze].append(line)
- # Solve input mazes
- print(n_mazes)
- for m in mazes.keys():
- print(m)
- maze_solver = MazeSolver(mazes[m])
- maze_solver.solve()
- maze_solver.draw()
- maze_solver.print_maze()
- if __name__ == '__main__':
- main()
Add Comment
Please, Sign In to add comment