[VI] Squares

class Squares(Problem):
    def __init__(self, initial, house):
        super().__init__(initial, house)

    def goal_test(self, state):
        return state == self.goal

    @staticmethod
    def check_valid(state):
        #print(state)
        for x in state:
            if x < 0 or x > 4:
                return False
        for y in state:
            if y < 0 or y > 4:
                return False
        return True

    def successor(self, state):
        succ = {}
        s1=state[0]
        s2=state[1]
        s3=state[2]
        s4=state[3]
        s5=state[4]

        if self.check_valid((s1[0],s1[1]+1)):
            succ["Pomesti kvadratche 1 gore"] = ((s1[0],s1[1]+1),s2,s3,s4,s5)
        if self.check_valid((s1[0],s1[1]-1)):
            succ["Pomesti kvadratche 1 dolu"] = ((s1[0],s1[1]-1),s2,s3,s4,s5)
        if self.check_valid((s1[0]-1,s1[1])):
            succ["Pomesti kvadratche 1 levo"] = ((s1[0]-1,s1[1]),s2,s3,s4,s5)
        if self.check_valid((s1[0]+1,s1[1])):
            succ["Pomesti kvadratche 1 desno"] = ((s1[0]+1,s1[1]),s2,s3,s4,s5)

        if self.check_valid((s2[0],s2[1]+1)):
            succ["Pomesti kvadratche 2 gore"] = (s1,(s2[0],s2[1]+1),s3,s4,s5)
        if self.check_valid((s2[0],s2[1]-1)):
            succ["Pomesti kvadratche 2 dolu"] = (s1,(s2[0],s2[1]-1),s3,s4,s5)
        if self.check_valid((s2[0]-1,s2[1])):
            succ["Pomesti kvadratche 2 levo"] = (s1,(s2[0]-1,s2[1]),s3,s4,s5)
        if self.check_valid((s2[0]+1,s2[1])):
            succ["Pomesti kvadratche 2 desno"] = (s1,(s2[0]+1,s2[1]),s3,s4,s5)

        if self.check_valid((s3[0],s3[1]+1)):
            succ["Pomesti kvadratche 3 gore"] = (s1,s2,(s3[0],s3[1]+1),s4,s5)
        if self.check_valid((s3[0],s3[1]-1)):
            succ["Pomesti kvadratche 3 dolu"] = (s1,s2,(s3[0],s3[1]-1),s4,s5)
        if self.check_valid((s3[0]-1,s3[1])):
            succ["Pomesti kvadratche 3 levo"] = (s1,s2,(s3[0]+1,s3[1]),s4,s5)
        if self.check_valid((s3[0]+1,s3[1])):
            succ["Pomesti kvadratche 3 desno"] = (s1,s2,(s3[0]-1,s3[1]),s4,s5)

        if self.check_valid((s4[0],s4[1]+1)):
            succ["Pomesti kvadratche 4 gore"] = (s1,s2,s3,(s4[0],s4[1]+1),s5)
        if self.check_valid((s4[0],s4[1]-1)):
            succ["Pomesti kvadratche 4 dolu"] = (s1,s2,s3,(s4[0],s4[1]-1),s5)
        if self.check_valid((s4[0]-1,s4[1])):
            succ["Pomesti kvadratche 4 levo"] = (s1,s2,s3,(s4[0]-1,s4[1]),s5)
        if self.check_valid((s4[0]+1,s4[1])):
            succ["Pomesti kvadratche 4 desno"] = (s1,s2,s3,(s4[0]+1,s4[1]),s5)

        if self.check_valid((s5[0],s5[1]+1)):
            succ["Pomesti kvadratche 5 gore"] = (s1,s2,s3,s4,(s5[0],s5[1]+1))
        if self.check_valid((s5[0],s5[1]-1)):
            succ["Pomesti kvadratche 5 dolu"] = (s1,s2,s3,s4,(s5[0],s5[1]-1))
        if self.check_valid((s5[0]-1,s5[1])):
            succ["Pomesti kvadratche 5 levo"] = (s1,s2,s3,s4,(s5[0]-1,s5[1]))
        if self.check_valid((s5[0]+1,s5[1])):
            succ["Pomesti kvadratche 5 desno"] = (s1,s2,s3,s4,(s5[0]+1,s5[1]))

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

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


if __name__ == '__main__':
    # ((x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5))
    initial_state = tuple()
    for _ in range(5):
        initial_state += (tuple(map(int, input().split(','))), )

    goal_state = ((0, 4), (1, 3), (2, 2), (3, 1), (4, 0))

    squares = Squares(initial_state, goal_state)

    answer = breadth_first_graph_search(squares)

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