[ВИ] лаб 2.2 Молекула

"""Неинформирано пребарување (2)

Молекула Problem 2 (0 / 0)
Предложете соодветна репрезентација и напишете ги потребните функции во Python за да се реши следниот проблем за кој
една можна почетна состојба е прикажана на слика 1:

enter image description here

Слика 1

“На табла 7x9 поставени се три атоми (внимавајте, двата H-атоми се различни: едниот има линк надолу, а другиот има линк
нагоре). Полињата обоени во сива боја претставуваат препреки. Играчот може да ја започне играта со избирање на кој било
од трите атоми. Играчот во секој момент произволно избира точно еден од трите атоми и го „турнува“ тој атом во една од
четирите насоки: горе, долу, лево или десно. Движењето на „турнатиот“ атом продолжува во избраната насока се’ додека
атомот не „удри“ во препрека или во некој друг атом (атомот секогаш застанува на првото поле што е соседно на препрека
или на друг атом во соодветната насока). Целта на играта е атомите да се доведат во позиција во која ја формираат
„молекулата“ прикажана десно од таблата. Играта завршува во моментот кога трите атоми ќе бидат поставени во бараната
позиција, во произволни три соседни полиња од таблата. Не е возможно ротирање на атомите (линковите на атомите секогаш
ќе бидат поставени како што се на почетокот на играта). Исто така, не е дозволено атомите да излегуваат од таблата.
Потребно е проблемот да се реши во најмал број на потези.”

За сите тест примери изгледот и големината на таблата се исти како на примерот даден на сликата. За сите тест примери
положбите на препреките се исти. За секој тест пример се менуваат почетните позиции на сите три атоми, соодветно.

Во рамки на почетниот код даден за задачата се вчитуваат влезните аргументи за секој тест пример. Во променливите
H1AtomRedica и H1AtomKolona ги имате редицата и колоната во која на почетокот се наоѓа првиот H атом - со линк надолу
(ако таблата ја гледате како матрица); во променливите ОAtomRedica и ОAtomKolona ги имате редицата и колоната во која на
почетокот се наоѓа О атомот (ако таблата ја гледате како матрица); во променливите H2AtomRedica и H2AtomKolona ги имате
редицата и колоната во која на почетокот се наоѓа вториот H атом - со линк нагоре (ако таблата ја гледате како матрица).

Движењата на атомите потребно е да ги именувате на следниот начин:

DesnoX - за придвижување на атомот X надесно (X може да биде H1, O или H2)
LevoX - за придвижување на атомот X налево (X може да биде H1, O или H2)
GoreX - за придвижување на атомот X нагоре (X може да биде H1, O или H2)
DoluX - за придвижување на атомот X надолу (X може да биде H1, O или H2)
Вашиот код треба да има само еден повик на функција за приказ на стандарден излез (print) со кој ќе ја вратите
секвенцата на движења која треба да се направи за да може атомите од почетната позиција да се доведат до бараната
позиција. Треба да примените неинформирано пребарување. Врз основа на тест примерите треба самите да определите кое
пребарување ќе го користите.

Sample input
6
3
5
8
1
3

Sample output
['DesnoO', 'GoreO', 'LevoH2', 'DoluH2', 'LevoO', 'DoluO', 'GoreH1', 'LevoH1']
"""

# Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje

# ______________________________________________________________________________________________
# Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite

import sys
import bisect

infinity = float('inf')  # sistemski definirana vrednost za beskonecnost


# ______________________________________________________________________________________________
# Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli

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)


# ______________________________________________________________________________________________
# Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
# Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
# na sekoj eden problem sto sakame da go resime


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


# ______________________________________________________________________________
# Definiranje na klasa za strukturata na jazel od prebaruvanje
# Klasata Node ne se nasleduva

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)


# ________________________________________________________________________________________________________
# Neinformirano prebaruvanje vo ramki na drvo
# Vo ramki na drvoto ne razresuvame jamki

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 depth_first_tree_search(problem):
    "Search the deepest nodes in the search tree first."
    return tree_search(problem, Stack())


# ________________________________________________________________________________________________________
# Neinformirano prebaruvanje vo ramki na graf
# Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi

def graph_search(problem, fringe):
    """Search through the successors of a problem to find a goal.
    The argument fringe should be an empty queue.
    If two paths reach a state, only use the best one."""
    closed = {}
    fringe.append(Node(problem.initial))
    while fringe:
        node = fringe.pop()
        if problem.goal_test(node.state):
            return node
        if node.state not in closed:
            closed[node.state] = True
            fringe.extend(node.expand(problem))
    return None


def breadth_first_graph_search(problem):
    "Search the shallowest nodes in the search tree first."
    return graph_search(problem, FIFOQueue())


def depth_first_graph_search(problem):
    "Search the deepest nodes in the search tree first."
    return graph_search(problem, Stack())


def uniform_cost_search(problem):
    "Search the nodes in the search tree with lowest cost first."
    return graph_search(problem, PriorityQueue(lambda a, b: a.path_cost < b.path_cost))


def depth_limited_search(problem, limit=50):
    "depth first search with limited depth"

    def recursive_dls(node, problem, limit):
        "helper function for depth limited"
        cutoff_occurred = False
        if problem.goal_test(node.state):
            return node
        elif node.depth == limit:
            return 'cutoff'
        else:
            for successor in node.expand(problem):
                result = recursive_dls(successor, problem, limit)
                if result == 'cutoff':
                    cutoff_occurred = True
                elif result != None:
                    return result
        if cutoff_occurred:
            return 'cutoff'
        else:
            return None

    # Body of depth_limited_search:
    return recursive_dls(Node(problem.initial), problem, limit)


def iterative_deepening_search(problem):
    for depth in range(sys.maxint):
        result = depth_limited_search(problem, depth)
        if result is not 'cutoff':
            return result


# _________________________________________________________________________________________________________
# PRIMER 1 : PROBLEM SO DVA SADA SO VODA
# OPIS: Dadeni se dva sada J0 i J1 so kapaciteti C0 i C1
# Na pocetok dvata sada se polni. Inicijalnata sostojba moze da se prosledi na pocetok
# Problemot e kako da se stigne do sostojba vo koja J0 ke ima G0 litri, a J1 ke ima G1 litri
# AKCII: 1. Da se isprazni bilo koj od sadovite
# 2. Da se prefrli tecnosta od eden sad vo drug so toa sto ne moze da se nadmine kapacitetot na sadovite
# Moze da ima i opcionalen tret vid na akcii 3. Napolni bilo koj od sadovite (studentite da ja implementiraat ovaa varijanta)
# ________________________________________________________________________________________________________

class WJ(Problem):
    """STATE: Torka od oblik (3,2) if jug J0 has 3 liters and J1 2 liters
    Opcionalno moze za nekoj od sadovite da se sretne i vrednost '*' sto znaci deka e nebitno kolku ima vo toj sad
    GOAL: Predefinirana sostojba do kade sakame da stigneme. Ako ne interesira samo eden sad za drugiot mozeme da stavime '*'
    PROBLEM: Se specificiraat kapacitetite na sadovite, pocetna sostojba i cel """

    def __init__(self, capacities=(5, 2), initial=(5, 0), goal=(0, 1)):
        self.capacities = capacities
        self.initial = initial
        self.goal = goal

    def goal_test(self, state):
        """ Vraka true ako sostojbata e celna """
        g = self.goal
        return (state[0] == g[0] or g[0] == '*') and \
               (state[1] == g[1] or g[1] == '*')

    def successor(self, J):
        """Vraka recnik od sledbenici na sostojbata"""
        successors = dict()
        J0, J1 = J
        (C0, C1) = self.capacities
        if J0 > 0:
            Jnew = 0, J1
            successors['dump jug 0'] = Jnew
        if J1 > 0:
            Jnew = J0, 0
            successors['dump jug 1'] = Jnew
        if J1 < C1 and J0 > 0:
            delta = min(J0, C1 - J1)
            Jnew = J0 - delta, J1 + delta
            successors['pour jug 0 into jug 1'] = Jnew
        if J0 < C0 and J1 > 0:
            delta = min(J1, C0 - J0)
            Jnew = J0 + delta, J1 - delta
            successors['pour jug 1 into jug 0'] = Jnew
        return successors

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

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


# So vaka definiraniot problem mozeme da gi koristime site neinformirani prebaruvanja
# Vo prodolzenie se dadeni mozni povici (vnimavajte za da moze da napravite povik mora da definirate problem)
#
#    WJInstance = WJ((5, 2), (5, 2), ('*', 1))
#    print WJInstance
#
#    answer1 = breadth_first_tree_search(WJInstance)
#    print answer1.solve()
#
#    answer2 = depth_first_tree_search(WJInstance) #vnimavajte na ovoj povik, moze da vleze vo beskonecna jamka
#    print answer2.solve()
#
#    answer3 = breadth_first_graph_search(WJInstance)
#    print answer3.solve()
#
#    answer4 = depth_first_graph_search(WJInstance)
#    print answer4.solve()
#
#    answer5 = depth_limited_search(WJInstance)
#    print answer5.solve()
#
#    answer6 = iterative_deepening_search(WJInstance)
#    print answer6.solve()



# Vasiot kod pisuvajte go pod ovoj komentar

prepreki = [(1, 4), (1, 6), (1, 8), (2, 3), (2, 9), (4, 2), (4, 7), (4, 8), (5, 5), (5, 7), (6, 1), (6, 2), (6, 4),
            (6, 7)]


def gore_atom_h1(a):
    h1 = a[0]
    while 0 < h1[0] < 8 and 0 < h1[1] < 10 and ((h1[0], h1[1]) not in prepreki) and (
            (h1[0], h1[1]) not in (a[1], a[2])):
        h1 = a[0]
        x = h1[0]
        x = x - 1
        a = (x, h1[1]), a[1], a[2]
    a_new = (h1[0] + 1, h1[1])  # +1 (a ne -1) poradi toa sto go vrakjame a[0] vo dozvolenata sostojba
    # a_new = a[0] - 1, a[1]
    return a_new


def dolu_atom_h1(a):
    h1 = a[0]
    while 0 < h1[0] < 8 and 0 < h1[1] < 10 and ((h1[0], h1[1]) not in prepreki) and (
            (h1[0], h1[1]) not in (a[1], a[2])):
        h1 = a[0]
        x = h1[0]
        x = x + 1
        a = (x, h1[1]), a[1], a[2]
    a_new = (h1[0] - 1, h1[1])
    return a_new


def levo_atom_h1(a):
    h1 = a[0]
    while 0 < h1[0] < 8 and 0 < h1[1] < 10 and ((h1[0], h1[1]) not in prepreki) and (
            (h1[0], h1[1]) not in (a[1], a[2])):
        h1 = a[0]
        y = h1[1]
        y = y - 1
        a = (h1[0], y), a[1], a[2]
    a_new = (h1[0], h1[1] + 1)
    return a_new


def desno_atom_h1(a):
    h1 = a[0]
    while 0 < h1[0] < 8 and 0 < h1[1] < 10 and ((h1[0], h1[1]) not in prepreki) and (
            (h1[0], h1[1]) not in (a[1], a[2])):
        h1 = a[0]
        y = h1[1]
        y = y + 1
        a = (h1[0], y), a[1], a[2]
    a_new = (h1[0], h1[1] - 1)
    return a_new


def gore_atom_o(a):
    o = a[1]
    while 0 < o[0] < 8 and 0 < o[1] < 10 and ((o[0], o[1]) not in prepreki) and (
            (o[0], o[1]) not in (a[0], a[2])):
        o = a[1]
        x = o[0]
        x = x - 1
        a = a[0], (x, o[1]), a[2]
    a_new = (o[0] + 1, o[1])
    return a_new


def dolu_atom_o(a):
    o = a[1]
    while 0 < o[0] < 8 and 0 < o[1] < 10 and ((o[0], o[1]) not in prepreki) and (
            (o[0], o[1]) not in (a[0], a[2])):
        o = a[1]
        x = o[0]
        x = x + 1
        a = a[0], (x, o[1]), a[2]
    a_new = (o[0] - 1, o[1])
    return a_new


def levo_atom_o(a):
    o = a[1]
    while 0 < o[0] < 8 and 0 < o[1] < 10 and ((o[0], o[1]) not in prepreki) and (
            (o[0], o[1]) not in (a[0], a[2])):
        o = a[1]
        y = o[1]
        y = y - 1
        a = a[0], (o[0], y), a[2]
    a_new = (o[0], o[1] + 1)
    return a_new


def desno_atom_o(a):
    o = a[1]
    while 0 < o[0] < 8 and 0 < o[1] < 10 and ((o[0], o[1]) not in prepreki) and (
            (o[0], o[1]) not in (a[0], a[2])):
        o = a[1]
        y = o[1]
        y = y + 1
        a = a[0], (o[0], y), a[2]
    a_new = (o[0], o[1] - 1)
    return a_new


def gore_atom_h2(a):
    h2 = a[2]
    while 0 < h2[0] < 8 and 0 < h2[1] < 10 and ((h2[0], h2[1]) not in prepreki) and (
            (h2[0], h2[1]) not in (a[0], a[1])):
        h2 = a[2]
        x = h2[0]
        x = x - 1
        a = a[0], a[1], (x, h2[1])
    a_new = (h2[0] + 1, h2[1])
    return a_new


def dolu_atom_h2(a):
    h2 = a[2]
    while 0 < h2[0] < 8 and 0 < h2[1] < 10 and ((h2[0], h2[1]) not in prepreki) and (
            (h2[0], h2[1]) not in (a[0], a[1])):
        h2 = a[2]
        x = h2[0]
        x = x + 1
        a = a[0], a[1], (x, h2[1])
    a_new = (h2[0] - 1, h2[1])
    return a_new


def levo_atom_h2(a):
    h2 = a[2]
    while 0 < h2[0] < 8 and 0 < h2[1] < 10 and ((h2[0], h2[1]) not in prepreki) and (
            (h2[0], h2[1]) not in (a[0], a[1])):
        h2 = a[2]
        y = h2[1]
        y = y - 1
        a = a[0], a[1], (h2[0], y)
    a_new = (h2[0], h2[1] + 1)
    return a_new


def desno_atom_h2(a):
    h2 = a[2]
    while 0 < h2[0] < 8 and 0 < h2[1] < 10 and ((h2[0], h2[1]) not in prepreki) and (
            (h2[0], h2[1]) not in (a[0], a[1])):
        h2 = a[2]
        y = h2[1]
        y = y + 1
        a = a[0], a[1], (h2[0], y)
    a_new = (h2[0], h2[1] - 1)
    return a_new


class Molekula(Problem):

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

    def goal_test(self, state):
        """ Vraka true ako sostojbata e celna """    # site treba da se vo ista kolona, vo redici edna ispod druga
        h1 = state[0]
        o = state[1]
        h2 = state[2]
        return h1[1] == o[1] and o[1] == h2[1] and h1[0] == o[0] - 1 and o[0] == h2[0] - 1

    def successor(self, state):
        """Vraka recnik od sledbenici na sostojbata"""
        successors = dict()

        h1 = state[0]
        o = state[1]
        h2 = state[2]

        #Gore h1
        h1_new = gore_atom_h1(state)
        state_new = (h1_new, o, h2)
        successors['GoreH1'] = state_new

        # Dolu h1
        h1_new = dolu_atom_h1(state)
        state_new = (h1_new, o, h2)
        successors['DoluH1'] = state_new

        # Levo h1
        h1_new = levo_atom_h1(state)
        state_new = (h1_new, o, h2)
        successors['LevoH1'] = state_new

        # Desno h1
        h1_new = desno_atom_h1(state)
        state_new = (h1_new, o, h2)
        successors['DesnoH1'] = state_new

        # Gore o
        o_new = gore_atom_o(state)
        state_new = (h1, o_new, h2)
        successors['GoreO'] = state_new

        # Dolu o
        o_new = dolu_atom_o(state)
        state_new = (h1, o_new, h2)
        successors['DoluO'] = state_new

        # Levo o
        o_new = levo_atom_o(state)
        state_new = (h1, o_new, h2)
        successors['LevoO'] = state_new

        # Desno o
        o_new = desno_atom_o(state)
        state_new = (h1, o_new, h2)
        successors['DesnoO'] = state_new

        # Gore h2
        h2_new = gore_atom_h2(state)
        state_new = (h1, o, h2_new)
        successors['GoreH2'] = state_new

        # Dolu h2
        h2_new = dolu_atom_h2(state)
        state_new = (h1, o, h2_new)
        successors['DoluH2'] = state_new

        # Levo h2
        h2_new = levo_atom_h2(state)
        state_new = (h1, o, h2_new)
        successors['LevoH2'] = state_new

        # Desno h2
        h2_new = desno_atom_h2(state)
        state_new = (h1, o, h2_new)
        successors['DesnoH2'] = state_new

        return successors

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

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


# Vcituvanje na vleznite argumenti za test primerite

H1AtomRedica = int(input())
H1AtomKolona = int(input())
OAtomRedica = int(input())
OAtomKolona = int(input())
H2AtomRedica = int(input())
H2AtomKolona = int(input())

MolekulaInstance = Molekula(((H1AtomRedica, H1AtomKolona), (OAtomRedica, OAtomKolona), (H2AtomRedica, H2AtomKolona)))

answer = breadth_first_graph_search(MolekulaInstance)
print(answer.solution())