import sys
import bisect

"""
Опис на дефиницијата на состојбата
Иницијалната состојба ми е претставена како tuple од tuples.
Еден tuple е во форматот (x,y,z) каде што х претставува џ координатата на
тенкот на таблата, у претставува у координата на таблата,а z претставува тежината на тенкот
што му соодвестуваат координатите х и у. Полињата коишто немаат тенк не се означени. Ако z добие
-1 тоа значи дека тој тенк не е дел од состојбата односно не се зема во предвид

Опис на функциите за транзиција од една во друга состојба
Дефинирани се функциите pukajElement(a, intq) ,pukajDole(a, intq) ,pukajGore(a, intq) pukajLevo(a, intq)
pukajDesno(a,intq) каде што а е една од tuples a intq e копија од state.
Во pukajElement се намалува тежината на а односно z = z-1. Потоа во зависност на позицијата на а
секој наблизок сосед по -x , x , y , -y (Gore , Dole , Levo, Desno ) оската исто така му се намалува z.
Oваа нова состојба се запипшува во нов tuple којшто претставува новата состојба и се додава во речникот
Овој процес се повторува за сите "jazili" a кој што се дел од state.
"""




class Queue:
    """Queue is an abstract class/interface. There are three types:
        Stack(): A Last In First Out Queue.
        FIFOQueue(): A First In First Out Queue.
        PriorityQueue(order, f): Queue in sorted order (default min-first).
    Each type supports the following methods and functions:
        q.append(item)  -- add an item to the queue
        q.extend(items) -- equivalent to: for item in items: q.append(item)
        q.pop()         -- return the top item from the queue
        len(q)          -- number of items in q (also q.__len())
        item in q       -- does q contain item?
    Note that isinstance(Stack(), Queue) is false, because we implement stacks
    as lists.  If Python ever gets interfaces, Queue will be an interface."""

    def __init__(self):
        raise NotImplementedError

    def extend(self, items):
        for item in items:
            self.append(item)

def Stack():
    """A Last-In-First-Out Queue."""
    return []

class FIFOQueue(Queue):
    """A First-In-First-Out Queue."""

    def __init__(self):
        self.A = []
        self.start = 0

    def append(self, item):
        self.A.append(item)

    def __len__(self):
        return len(self.A) - self.start

    def extend(self, items):
        self.A.extend(items)

    def pop(self):
        e = self.A[self.start]
        self.start += 1
        if self.start > 5 and self.start > len(self.A) / 2:
            self.A = self.A[self.start:]
            self.start = 0
        return e

    def __contains__(self, item):
        return item in self.A[self.start:]

class PriorityQueue(Queue):
    """A queue in which the minimum (or maximum) element (as determined by f and
    order) is returned first. If order is min, the item with minimum f(x) is
    returned first; if order is max, then it is the item with maximum f(x).
    Also supports dict-like lookup. This structure will be most useful in informed searches"""

    def __init__(self, order=min, f=lambda x: x):
        self.A = []
        self.order = order
        self.f = f

    def append(self, item):
        bisect.insort(self.A, (self.f(item), item))

    def __len__(self):
        return len(self.A)

    def pop(self):
        if self.order == min:
            return self.A.pop(0)[1]
        else:
            return self.A.pop()[1]

    def __contains__(self, item):
        return any(item == pair[1] for pair in self.A)

    def __getitem__(self, key):
        for _, item in self.A:
            if item == key:
                return item

    def __delitem__(self, key):
        for i, (value, item) in enumerate(self.A):
            if item == key:
                self.A.pop(i)

class Node:
    """A node in a search tree. Contains a pointer to the parent (the node
    that this is a successor of) and to the actual state for this node. Note
    that if a state is arrived at by two paths, then there are two nodes with
    the same state.  Also includes the action that got us to this state, and
    the total path_cost (also known as g) to reach the node.  Other functions
    may add an f and h value; see best_first_graph_search and astar_search for
    an explanation of how the f and h values are handled. You will not need to
    subclass this class."""

    def __init__(self, state, parent=None, action=None, path_cost=0):
        "Create a search tree Node, derived from a parent by an action."
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost
        self.depth = 0
        if parent:
            self.depth = parent.depth + 1

    def __repr__(self):
        return "<Node %s>" % (self.state,)

    def __lt__(self, node):
        return self.state < node.state

    def expand(self, problem):
        "List the nodes reachable in one step from this node."
        return [self.child_node(problem, action)
                for action in problem.actions(self.state)]

    def child_node(self, problem, action):
        "Return a child node from this node"
        next = problem.result(self.state, action)
        return Node(next, self, action,
                    problem.path_cost(self.path_cost, self.state,
                                      action, next))

    def solution(self):
        "Return the sequence of actions to go from the root to this node."
        return [node.action for node in self.path()[1:]]

    def solve(self):
        "Return the sequence of states to go from the root to this node."
        return [node.state for node in self.path()[0:]]

    def path(self):
        "Return a list of nodes forming the path from the root to this node."
        x, result = self, []
        while x:
            result.append(x)
            x = x.parent
        return list(reversed(result))

    # We want for a queue of nodes in breadth_first_search or
    # astar_search to have no duplicated states, so we treat nodes
    # with the same state as equal. [Problem: this may not be what you
    # want in other contexts.]

    def __eq__(self, other):
        return isinstance(other, Node) and self.state == other.state

    def __hash__(self):
        return hash(self.state)

class Problem:
    """The abstract class for a formal problem.  You should subclass this and
    implement the method successor, and possibly __init__, goal_test, and
    path_cost. Then you will create instances of your subclass and solve them
    with the various search functions."""

    def __init__(self, initial, goal=None):
        """The constructor specifies the initial state, and possibly a goal
        state, if there is a unique goal.  Your subclass's constructor can add
        other arguments."""
        self.initial = initial
        self.goal = goal

    def successor(self, state):
        """Given a state, return a dictionary of {action : state} pairs reachable
        from this state. If there are many successors, consider an iterator
        that yields the successors one at a time, rather than building them
        all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
        raise NotImplementedError

    def actions(self, state):
        """Given a state, return a list of all actions possible from that state"""
        raise NotImplementedError

    def result(self, state, action):
        """Given a state and action, return the resulting state"""
        raise NotImplementedError

    def goal_test(self, state):
        """Return True if the state is a goal. The default method compares the
        state to self.goal, as specified in the constructor. Implement this
        method if checking against a single self.goal is not enough."""
        return state == self.goal

    def path_cost(self, c, state1, action, state2):
        """Return the cost of a solution path that arrives at state2 from
        state1 via action, assuming cost c to get up to state1. If the problem
        is such that the path doesn't matter, this function will only look at
        state2.  If the path does matter, it will consider c and maybe state1
        and action. The default method costs 1 for every step in the path."""
        return c + 1

    def value(self):
        """For optimization problems, each state has a value.  Hill-climbing
        and related algorithms try to maximize this value."""
        raise NotImplementedError

def tree_search(problem, fringe):
    """Search through the successors of a problem to find a goal.
    The argument fringe should be an empty queue."""
    fringe.append(Node(problem.initial))
    while fringe:
        node = fringe.pop()
        # print(node.state)
        if problem.goal_test(node.state):
            return node
        fringe.extend(node.expand(problem))
    return None
def breadth_first_tree_search(problem):
    "Search the shallowest nodes in the search tree first."
    return tree_search(problem, FIFOQueue())

def proverka(tmp,lista):
    for a in lista:
        if a.__eq__(tmp) and a[2] != -1:
            return True
    return False

def pukajElement(tmp, lista):
    for a in lista:
        if a.__eq__(tmp) and a[2] != -1:
            x = lista.index(a)
            tup = (a[0], a[1], a[2] - 1)
            tmplista = lista[:x] + (tup,) + lista[x + 1:]
            # print(tmplista)
            lista = tmplista
    return lista


def pukajDesno(tmp, lista):
    razlika = 50
    flag = False
    for a in lista:
        neisti = a.__ne__(tmp)
        if a[0] == tmp[0] and a[2] != -1 and neisti and tmp[1] < a[1]:
            if razlika > (a[1] - tmp[1]):
                razlika = tmp[1] - a[1]
                element = a
                flag = True
                # print("elementot e ")
                # print(element)
    if flag:
        for a in lista:
            isti = a.__eq__(element)
            if isti:
                x = lista.index(a)
                tup = (a[0], a[1], a[2] - 1)
                tmplista = lista[:x] + (tup,) + lista[x + 1:]
                # print(tmplista)
                lista = tmplista
                return lista
    else:
        #print("FLAZI22222222")
        return lista


def pukajLevo(tmp, lista):
    razlika = 50
    flag = False
    for a in lista:
        neisti = a.__ne__(tmp)
        if a[0] == tmp[0] and a[2] != -1 and neisti and tmp[1] > a[1]:
            if razlika > (tmp[1] - a[1]):
                razlika = tmp[1] - a[1]
                element = a
                flag = True
    if flag:
        for a in lista:
            isti = a.__eq__(element)
            if isti:
                x = lista.index(a)
                tup = (a[0], a[1], a[2] - 1)
                tmplista = lista[:x] + (tup,) + lista[x + 1:]
                # print(tmplista)
                lista = tmplista
                return lista
    else:
        # print("FLAZI22222222")
        return lista


def pukajGore(tmp, lista):
    razlika = 50
    flag = False
    for a in lista:
        neisti = a.__ne__(tmp)
        if a[1] == tmp[1] and a[2] != -1 and neisti and tmp[0] > a[0]:
            if razlika > (tmp[0] - a[0]):
                razlika = tmp[0] - a[0]
                element = a
                flag = True
                # print("elementot e ")
                # print(element)
    if flag:
        for a in lista:
            isti = a.__eq__(element)
            if isti:
                x = lista.index(a)
                tup = (a[0], a[1], a[2] - 1)
                tmplista = lista[:x] + (tup,) + lista[x + 1:]
                # print(tmplista)
                lista = tmplista
                return lista
    else:
        #print("FLAZI22222222")
        return lista


def pukajDole(tmp,lista):
    razlika = 50
    flag = False
    for a in lista:
        neisti = a.__ne__(tmp)
        if a[1] == tmp[1] and a[2] != -1 and neisti and tmp[0] < a[0]:
            if razlika > (a[0] - tmp[0]):
                razlika = a[0] - tmp[0]
                element = a
                flag = True
                # print("elementot e ")
                # print(element)
    if flag:
        for a in lista:
            isti = a.__eq__(element)
            if isti:
                x = lista.index(a)
                tup = (a[0], a[1], a[2] - 1)
                tmplista = lista[:x] + (tup,) + lista[x + 1:]
                # print(tmplista)
                lista = tmplista
                return lista
    else:
        # print("FLAZI22222222")
        return lista

class WJ(Problem):

    def __init__(self,initial=((0, 2, 1), (1, 0, 0), (1, 2, 1), (1, 3, 0), (2, 2, 1), (3, 1, 2), (3, 3, 0)), goal = ((0, 2, -1), (1, 0,-1), (1, 2, -1), (1, 3, -1), (2, 2, -1), (3, 1, -1), (3, 3, -1))):
        self.initial = initial
        self.goal = goal

    def goal_test(self, state):
        """ Vraka true ako sostojbata e celna """
        g = self.goal
        return g.__eq__(state)

    def successor(self, state):
        successors = dict()
        x = 0
        for a in state:
                intq = state[:]
                if proverka(a, intq):
                    intq = pukajElement(a, intq)
                    intq = pukajDole(a, intq)
                    intq = pukajGore(a, intq)
                    intq = pukajLevo(a, intq)
                    intq = pukajDesno(a, intq)
                successors[x] = intq
                x += 1
        return successors

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

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


WJInstance = WJ()
print(WJInstance)
answer1 = breadth_first_tree_search(WJInstance)
print(answer1.solution)