pac/nedovrsen

from utils import Problem
from uninformed_search import *


def move_left(x, y, obs):
    if 0 <= x - 1 and (x - 1, y) not in obs:
        return [(x - 1, y), "zapad"]
    return 0


def move_right(x, y, obs):
    if x + 1 < 10 and (x + 1, y) not in obs:
        return [(x + 1, y), "istok"]
    return 0


def move_up(x, y, obs):
    if y + 1 < 10 and (x, y + 1) not in obs:
        return [(x, y + 1), "sever"]
    return 0


def move_down(x, y, obs):
    if y - 1 >= 0 and (x, y - 1) not in obs:
        return [(x, y - 1), "jug"]
    return 0


class Pacman(Problem):
    def __init__(self, initial, obs, goal=None):
        super().__init__(initial, goal)
        self.obs = obs

    def successor(self, state):
        """За дадена состојба, врати речник од парови {акција : состојба}
        достапни од оваа состојба. Ако има многу следбеници, употребете
        итератор кој би ги генерирал следбениците еден по еден, наместо да
        ги генерирате сите одеднаш.
        :param state: дадена состојба
        :return:  речник од парови {акција : состојба} достапни од оваа
                  состојба
        :rtype: dict
        """
        # (i, j, facing, positions)
        successors = dict()

        pac_x, pac_y = state[0], state[1]
        side = state[2]
        ball_pos = state[3]

        if side == "istok":
            left = move_up(pac_x, pac_y, self.obs)
            right = move_down(pac_x, pac_y, self.obs)
            forward = move_right(pac_x, pac_y, self.obs)
            back = move_left(pac_x, pac_y, self.obs)
        if side == "zapad":
            left = move_down(pac_x, pac_y, self.obs)
            right = move_up(pac_x, pac_y, self.obs)
            forward = move_left(pac_x, pac_y, self.obs)
            back = move_right(pac_x, pac_y, self.obs)
        if side == "sever":
            left = move_left(pac_x, pac_y, self.obs)
            right = move_right(pac_x, pac_y, self.obs)
            forward = move_up(pac_x, pac_y, self.obs)
            back = move_down(pac_x, pac_y, self.obs)
        if side == "jug":
            left = move_right(pac_x, pac_y, self.obs)
            right = move_left(pac_x, pac_y, self.obs)
            forward = move_down(pac_x, pac_y, self.obs)
            back = move_up(pac_x, pac_y, self.obs)

        if forward != 0:
            successors["ProdolziPravo"] = (forward[0][0], forward[0][1], forward[1],
                                           tuple([p for p in ball_pos if p != [forward[0][0], forward[0][1]]]))
        if back != 0:
            successors["ProdolziNazad"] = (back[0][0], back[0][1], back[1],
                                           tuple([p for p in ball_pos if p != [back[0][0], back[0][1]]]))
        if left != 0:
            successors["SvrtiLevo"] = (left[0][0], left[0][1], left[1],
                                       tuple([p for p in ball_pos if p != [left[0][0], left[0][1]]]))
        if right != 0:
            successors["SvrtiDesno"] = (right[0][0], right[0][1], right[1],
                                        tuple([p for p in ball_pos if p != [right[0][0], right[0][1]]]))

        return successors

    def actions(self, state):
        """За дадена состојба state, врати листа од сите акции што може да
        се применат над таа состојба
        :param state: дадена состојба
        :return: листа на акции
        :rtype: list
        """
        return self.successor(state).keys()

    def result(self, state, action):
        """За дадена состојба state и акција action, врати ја состојбата
        што се добива со примена на акцијата над состојбата
        :param state: дадена состојба
        :param action: дадена акција
        :return: резултантна состојба
        """
        return self.successor(state)[action]

    def goal_test(self, state):
        """Врати True ако state е целна состојба. Даденава имплементација
        на методот директно ја споредува state со self.goal, како што е
        специфицирана во конструкторот. Имплементирајте го овој метод ако
        проверката со една целна состојба self.goal не е доволна.
        :param state: дадена состојба
        :return: дали дадената состојба е целна состојба
        :rtype: bool
        """
        return len(state[-1]) == 0


if __name__ == "__main__":
    i, j = int(input()), int(input())
    facing = input()
    num_balls = int(input())
    positions = []

    obstacles = [(0, 6), (0, 8), (0, 9), (1, 2), (1, 3), (1, 4), (1, 9), (2, 9), (3, 6), (3, 9), (4, 1), (4, 5),
                 (4, 6), (4, 7), (5, 1), (5, 6), (6, 0), (6, 1), (6, 2), (6, 9), (8, 1), (8, 4), (8, 7), (8, 8), (9, 4),
                 (9, 7), (9, 8)]
    for k in range(num_balls):
        balls = list(input())
        positions.append([int(balls[0]), int(balls[2])])
    new_pos = tuple(positions)
    pacman = Pacman((i, j, facing, positions), obstacles)

    result = breadth_first_tree_search(pacman)
    print(result)