Solución al reto 4 de la Semic Challenge del grupo "josep_pon" en la HackEPS 2017

hackeps-2017-challenge-4.py

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