[VI] Football

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

    def actions(self, state):
        return self.successor(state).keys()

    def result(self, state, action):
        return self.successor(state)[action]

    def goal_test(self, state):
        ball_pos = state[1]
        return ball_pos in self.goal

    @staticmethod
    def check_valid(state, opponents):
        man_pos = state[0]
        ball_pos = state[1]
        #print(ball_pos)
        return man_pos[0] >= 0 and man_pos[0] < 8 and \
            man_pos[1] >= 0 and man_pos[1] < 6 and \
            ball_pos[0] >= 0 and ball_pos[0] < 8 and \
            ball_pos[1] >= 0 and ball_pos[1] < 6 and ball_pos not in \
            ((2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4), (3, 5), (3, 6), (4, 5), (4, 6),(5, 4), (5, 5), (5, 6))

    def successor(self, state):
        successors = dict()

        man_pos = state[0]
        ball_pos = state[1]
        opp_pos = state[2]

        if self.check_valid(((man_pos[0], man_pos[1]+1), ball_pos), opp_pos):
            successors["Pomesti coveche gore"] = ((man_pos[0], man_pos[1]+1), ball_pos, opp_pos)

        if self.check_valid(((man_pos[0], man_pos[1]-1), ball_pos), opp_pos):
            successors["Pomesti coveche dolu"] = ((man_pos[0], man_pos[1]-1), ball_pos, opp_pos)

        if self.check_valid(((man_pos[0] + 1, man_pos[1]), ball_pos), opp_pos):
            successors["Pomesti coveche desno"] = ((man_pos[0] + 1, man_pos[1]), ball_pos, opp_pos)

        if self.check_valid(((man_pos[0] + 1, man_pos[1] + 1), ball_pos), opp_pos):
            successors["Pomesti coveche gore-desno"] = ((man_pos[0] + 1, man_pos[1] + 1), ball_pos, opp_pos)

        if self.check_valid(((man_pos[0]+1, man_pos[1]-1), ball_pos), opp_pos):
            successors["Pomesti coveche dolu-desno"] = ((man_pos[0] + 1, man_pos[1] - 1), ball_pos, opp_pos)

        if man_pos[0] == ball_pos[0] and man_pos[1] == ball_pos[1] - 1 and self.check_valid(
                ((man_pos[0], man_pos[1] + 1), (ball_pos[0], ball_pos[1] + 1)), opp_pos):
            successors["Turni topka gore"] = ((man_pos[0], man_pos[1] + 1), (ball_pos[0], ball_pos[1] + 1), opp_pos)

        if man_pos[0] == ball_pos[0] and man_pos[1] == ball_pos[1] + 1 and self.check_valid(
                ((man_pos[0], man_pos[1] - 1), (ball_pos[0], ball_pos[1] - 1)), opp_pos):
            successors["Turni topka dolu"] = ((man_pos[0], man_pos[1] - 1), (ball_pos[0], ball_pos[1] - 1), opp_pos)

        if man_pos[1] == ball_pos[1] and man_pos[0] == ball_pos[0] - 1 and self.check_valid(
                ((man_pos[0] + 1, man_pos[1]), (ball_pos[0] + 1, ball_pos[1])), opp_pos):
            successors["Turni topka desno"] = ((man_pos[0] + 1, man_pos[1]), (ball_pos[0] + 1, ball_pos[1]), opp_pos)

        if man_pos[1] == ball_pos[1] - 1 and man_pos[0] == ball_pos[0] - 1 and self.check_valid(
                ((man_pos[0] + 1, man_pos[1] + 1), (ball_pos[0] + 1, ball_pos[1] + 1)), opp_pos):
            successors["Turni topka gore-desno"] = ((man_pos[0] + 1, man_pos[1] + 1), (ball_pos[0] + 1, ball_pos[1] + 1), opp_pos)

        if man_pos[1] == ball_pos[1] + 1 and man_pos[0] == ball_pos[0] - 1 and self.check_valid(
                ((man_pos[0] + 1, man_pos[1] - 1), (ball_pos[0] + 1, ball_pos[1] - 1)), opp_pos):
            successors["Turni topka dolu-desno"] = ((man_pos[0] + 1, man_pos[1] - 1), (ball_pos[0] + 1, ball_pos[1] - 1), opp_pos)

        return successors


if __name__ == '__main__':
    man_pos = tuple(map(int, input().split(',')))
    ball_pos = tuple(map(int, input().split(',')))

    opponents = ((3, 3), (5, 4))

    goal_state = ((7, 2), (7, 3))

    football = Football((man_pos, ball_pos, opponents), goal_state)

    answer = breadth_first_graph_search(football)
    if answer is None:
        print("None")
    else:
        print(answer.solution())