Checkio| Open Labyrinth

# Open Labyrinth
from collections import deque

class DepthLabyrinth:
    moves = {
        'N': [-1,0],
        'S': [1,0],
        'W': [0,-1],
        'E': [0,1]
    }
    histories = []
    def __init__(self, graph, start, end):
        self.graph = graph
        self.start = start
        self.end = end
        self.find_path(self.start, [self.start])

    @property
    def history(self):
        return min(self.histories, key=len)

    def find_path(self, curr, path):
        for next in self.get_next_steps(curr, path):
            _path = path.copy()
            _path.append(next)
            if next == self.end:
                self.histories.append(_path)
            self.find_path(next, _path)


    def get_next_steps(self, curr, path):
        for move in self.moves.values():
            next = [curr[0] + move[0], curr[1] + move[1]]
            if next not in path and self.is_may_step(next):
                # print(f'path: {path}')
                yield next

    def is_may_step(self, step):
        val = self.graph[step[0]][step[1]]
        return True if val == 0 else False

    def get_path(self):
        return ''.join(self.read_history())

    def read_history(self):
        directions = []
        m_keys = list(self.moves.keys())
        m_vals = list(self.moves.values())

        for i in range(len(self.history) - 1):
            step = [
                self.history[i+1][0] - self.history[i][0],
                self.history[i+1][1] - self.history[i][1],
            ]
            directions.append(
                m_keys[
                    m_vals.index(step)
                ]
            )
        return directions

class BestFirstSearchLabyrinth:
    moves = {
        'N': [-1,0],
        'S': [1,0],
        'W': [0,-1],
        'E': [0,1]
    }
    history = []
    def __init__(self, graph, start, end):
        self.graph = graph
        self.start = start
        self.end = end
        self.turn = deque([[self.start, [self.start]]])
        self.find_path()

    def find_path(self):
        while len(self.turn):
            curr, path = self.turn.popleft()
            for next in self.get_next_steps(curr, path):
                _path = path.copy()
                _path.append(next)
                if next == self.end:
                    self.history = _path
                    return
                self.turn.append([next, _path])


    def get_next_steps(self, curr, path):
        for move in self.moves.values():
            next = [curr[0] + move[0], curr[1] + move[1]]
            if next not in path and self.is_may_step(next):
                yield next

    def is_may_step(self, step):
        val = self.graph[step[0]][step[1]]
        return True if val == 0 else False

    def get_path(self):
        return ''.join(self.read_history())

    def read_history(self):
        directions = []
        m_keys = list(self.moves.keys())
        m_vals = list(self.moves.values())

        for i in range(len(self.history) - 1):
            step = [
                self.history[i+1][0] - self.history[i][0],
                self.history[i+1][1] - self.history[i][1],
            ]
            directions.append(
                m_keys[
                    m_vals.index(step)
                ]
            )
        return directions

for i, LabClass in enumerate(
    [
        DepthLabyrinth,
        BestFirstSearchLabyrinth
    ],
    start=1
):
    labyrinth = LabClass(
        [
            [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
            [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
            [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
            [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
            [1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1],
            [1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1],
            [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
            [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
            [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
            [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
        ],
        [1, 1],
        [10, 10]
    )
    answer = labyrinth.get_path()
    print(f'answer{i}: "{answer}"')