Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- import bisect
- infinity = float('inf')
- 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)
- 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 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
- 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)
- 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())
- #koordinati na site prepreki vo shemata
- Obstacles = [(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)]
- #sostojba na nekoj atom ja definiram kako koordinati na site ostali atomi na primer H1x,H2x,Ox,Oy,H2x,H2y
- def upAtomH1(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- X=A[0] #the x coordinate of the atom is placed in the variable x
- X=X-1 #i reduce the x value because that is what happens when i move up in my coordinate system
- A=(X,A[1],A[2],A[3],A[4],A[5]) #vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew=(A[0]+1,A[1]) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- def downAtomH1(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- X=A[0] #the x coordinate of the atom is placed in the variable x
- X=X+1 #i reduce the x value because that is what happens when i move up in my coordinate system
- A=(X,A[1],A[2],A[3],A[4],A[5]) #vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew=(A[0]-1,A[1]) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- def leftAtomH1(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- Y=A[1] #the x coordinate of the atom is placed in the variable x
- Y=Y-1 #i reduce the x value because that is what happens when i move up in my coordinate system
- A=(A[0],Y,A[2],A[3],A[4],A[5]) #vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew=(A[0],A[1]+1) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- def rightAtomH1(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- Y = A[1] # the x coordinate of the atom is placed in the variable x
- Y = Y + 1 # i reduce the x value because that is what happens when i move up in my coordinate system
- A = (A[0], Y, A[2], A[3], A[4], A[5]) # vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew = (A[0], A[1] - 1) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- def upAtomO(A):
- tuple = ((A[0], A[1]), (A[4], A[5]))
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and # proveruvam dali mi iskacha od tablata
- ((A[2], A[3]) not in Obstacles) and # check wether i have landed on an obstacle
- ((A[2], A[3]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- X=A[3]
- X=X-1
- A=(A[0],A[1],X,A[3],A[4],A[5])
- Anew=(A[2]+1,A[3])
- return Anew
- def upAtomO(A):
- tuple = ((A[0], A[1]), (A[4], A[5]))
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and # proveruvam dali mi iskacha od tablata
- ((A[2], A[3]) not in Obstacles) and # check wether i have landed on an obstacle
- ((A[2], A[3]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- X=A[3]
- X=X-1
- A=(A[0],A[1],X,A[3],A[4],A[5])
- Anew=(A[2]+1,A[3])
- return Anew
- def downAtomO(A):
- tuple = ((A[0], A[1]), (A[4], A[5]))
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and # proveruvam dali mi iskacha od tablata
- ((A[2], A[3]) not in Obstacles) and # check wether i have landed on an obstacle
- ((A[2], A[3]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- X=A[3]
- X=X+1
- A=(A[0],A[1],X,A[3],A[4],A[5])
- Anew=(A[2]-1,A[3])
- return Anew
- def leftAtomO(A):
- tuple = ((A[0], A[1]), (A[4], A[5]))
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and # proveruvam dali mi iskacha od tablata
- ((A[2], A[3]) not in Obstacles) and # check wether i have landed on an obstacle
- ((A[2], A[3]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- Y=A[3]
- Y=Y-1
- A=(A[0],A[1],A[2],Y,A[4],A[5])
- Anew=(A[2],A[3]+1)
- return Anew
- def rightAtomO(A):
- tuple = ((A[0], A[1]), (A[4], A[5]))
- while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and # proveruvam dali mi iskacha od tablata
- ((A[2], A[3]) not in Obstacles) and # check wether i have landed on an obstacle
- ((A[2], A[3]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- Y=A[3]
- Y=Y+1
- A=(A[0],A[1],A[2],Y,A[4],A[5])
- Anew=(A[2],A[3]-1)
- return Anew
- def upAtomH2(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- X=A[0] #the x coordinate of the atom is placed in the variable x
- X=X-1 #i reduce the x value because that is what happens when i move up in my coordinate system
- A=(X,A[1],A[2],A[3],A[4],A[5]) #vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew=(A[0]+1,A[1]) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- def downAtomH2(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- X=A[0] #the x coordinate of the atom is placed in the variable x
- X=X+1 #i reduce the x value because that is what happens when i move up in my coordinate system
- A=(X,A[1],A[2],A[3],A[4],A[5]) #vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew=(A[0]-1,A[1]) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- def leftAtomH2(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- Y=A[1] #the x coordinate of the atom is placed in the variable x
- Y=Y-1 #i reduce the x value because that is what happens when i move up in my coordinate system
- A=(A[0],Y,A[2],A[3],A[4],A[5]) #vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew=(A[0],A[1]+1) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- def rightAtomH2(A):
- tuple = ((A[2],A[3]),(A[4],A[5]))
- while(A[0] > 0 and A[0] < 8 and A[1]> 0 and A[1]< 10 and #proveruvam dali mi iskacha od tablata
- ((A[0],A[1]) not in Obstacles) and #check wether i have landed on an obstacle
- ((A[0],A[1]) not in tuple)): # check wether i am in the same position as the other 2 atoms
- Y = A[1] # the x coordinate of the atom is placed in the variable x
- Y = Y + 1 # i reduce the x value because that is what happens when i move up in my coordinate system
- A = (A[0], Y, A[2], A[3], A[4], A[5]) # vo A ja smestuvam novata sostojba na atomot so smeneta x coordinate
- Anew = (A[0], A[1] - 1) #vo Anew stavam koordinati, po izvrshuvanje na while. za da zavrshi while moralo da stignam negde kaj sho ne e okej
- #zatoa mi sluzhi toa +1 za da se vratam edna poz nazad pred da napraam sranja za da iskocam od while
- #whileot ustvari e za neprekinato pushing vo edna nasoka
- return Anew
- class Molekula(Problem):
- def __init__(self,initial):
- self.initial=initial
- def goal_test(self,state):
- H1X = state[0]
- H1Y = state[1]
- OX = state[2]
- OY = state[3]
- H2X = state[4]
- H2Y = state[5]
- return(H1X == OX and OX == H2X and #proverka dali H1 i O se vo ista kolona posho za da se edni do drugi mora da se u ista kolona
- OY == H1Y +1 and #proverka dali i drugiot H2 atom e vo ista redica so ovie
- H2Y == OY+1) #dali se bash edni do drugi so rastojanie 0 megju sebe na sosedni kvadrati
- def successor(self,state):
- successors=dict() #definiram prazen rechnik
- H1 = state[0],state[1] #vo H1 stavam koordinati na H1 atomot shto gi dobivam od state
- O = state[2], state[3] # vo HO stavam koordinati na H1 atomot shto gi dobivam od state
- H2 = state[4], state[5] # vo H2 stavam koordinati na H1 atomot shto gi dobivam od state
- #podoly kako keyes vo dictionary gi staam iminjata na akciite a kako values gi staam states koi sledat od nekoja takva akcija
- #so sekoj nov state koj povikuva nekakva akcija od dict se generiraat novi possible states
- #zatoa na pocetokot successors sekogas se definira na prazen rechnik na pochetokot na funkcijava
- #GI DEFINIRAM SITE MOZHNI POTEZI I NIVNITE REZULTATI ZA H1 ATOM
- H1new = upAtomH1(state)
- Statenew= (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['GoreH1'] = Statenew
- H1new = downAtomH1(state)
- Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['DoleH1'] = Statenew
- H1new = leftAtomH1(state)
- Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['LevoH1'] = Statenew
- H1new = rightAtomH1(state)
- Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
- successors['DesnoH1'] = Statenew
- # GI DEFINIRAM SITE MOZHNI POTEZI I NIVNITE REZULTATI ZA H2 ATOM
- H2new = upAtomH2(state)
- Statenew = (H1[0],H1[1], O[0], O[1],H2new[0], H2new[1])
- successors['GoreH2'] = Statenew
- H2new = downAtomH2(state)
- Statenew = (H1[0],H1[1], O[0], O[1],H2new[0], H2new[1])
- successors['DoleH2'] = Statenew
- H2new = leftAtomH2(state)
- Statenew = (H1[0],H1[1], O[0], O[1],H2new[0], H2new[1])
- successors['LevoH2'] = Statenew
- H2new = rightAtomH2(state)
- Statenew = (H1[0],H1[1], O[0], O[1],H2new[0], H2new[1])
- successors['DesnoH2'] = Statenew
- # GI DEFINIRAM SITE MOZHNI POTEZI I NIVNITE REZULTATI ZA O ATOM
- Onew = upAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['GoreO'] = Statenew
- Onew = downAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['DoleO'] = Statenew
- Onew = leftAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['LevoO'] = Statenew
- Onew = rightAtomO(state)
- Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
- successors['DesnoO'] = Statenew
- return successors
- def actions(self, state):
- return self.successor(state).keys() #gi vrakjam site mozhni AKCII
- def result(self, state, action):
- possible = self.successor(state) #vrakjam koja sostojba e rezultat na dadena akcija pratena kako prarametar
- return possible[action]
- #Vcituvanje na vleznite argumenti za test primerite
- H1AtomRedica = int(input()) #atomot so link desno
- H1AtomKolona = int(input())
- OAtomRedica = int(input())
- OAtomKolona = int(input())
- H2AtomRedica = int(input()) #atomot so link levo
- H2AtomKolona = int(input())
- #Vasiot kod pisuvajte go pod ovoj komentar
- MolekulaInstance = Molekula((H1AtomRedica, H1AtomKolona, OAtomRedica, OAtomKolona, H2AtomRedica, H2AtomKolona))
- answer = breadth_first_graph_search(MolekulaInstance)
- print (answer.solution())
- import sys
- import bisect
- infinity = float('inf')
- 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)
- 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 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
- 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)
- 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 updateP1(P): #horisontal, to the left, start state: 2,2 and 2,3
- (X,Y,Nasoka) = P
- if(Y == 0 and Nasoka == 1) or (Y == 4 and Nasoka == -1): #ako sum doshla do nekoj od dzidovite sho me ogranichuvaat menjam nasoka
- Nasoka = Nasoka * (-1)
- Ynew = Y - Nasoka #na X mu se dodava/ odzema eden chekor zavisno od nasokata
- Pnew = (X, Ynew, Nasoka)
- return Pnew
- def updateP2(P): #diagonal, upward right, start state: 8,2 8,3 7,2 7,3
- (X, Y, Nasoka) = P
- if (X == 10 and Nasoka == -1) or (X == 6 and Nasoka == 1): # ako sum doshla do nekoj od dzidovite sho me ogranichuvaat menjam nasoka
- Nasoka = Nasoka * (-1)
- Xnew = X - Nasoka # na X mu se dodava/ odzema eden chekor zavisno od nasokata
- Ynew = Y + Nasoka
- Pnew = (Xnew, Ynew, Nasoka)
- return Pnew
- def updateP3(P): #vertical, down, 8,8 9,8
- (X,Y,Nasoka) = P
- if(X == 10 and Nasoka == 1) or (X == 6 and Nasoka == -1): #ako sum doshla do nekoj od dzidovite sho me ogranichuvaat menjam nasoka
- Nasoka = Nasoka * (-1)
- Xnew = X + Nasoka #na X mu se dodava/ odzema eden chekor zavisno od nasokata
- Pnew = (Xnew, Y, Nasoka)
- return Pnew
- class Istrazuvac(Problem):
- def __init__(self, initial, goal):
- self.initial = initial
- self.goal = goal
- def goal_test(self, state):
- g = self.goal
- return (state [0] == g[0] and state[1] == g[1])
- def successor(self,state):
- successors = dict()
- X = state[0]
- Y = state[1]
- P1 = (state[2], state[3], state[4])
- P2 = (state[5], state[6], state[7])
- P3 = (state[8], state[9], state[10])
- #ako x e pomalo od 10 mozam da odam nadolu
- if(X < 10):
- Xnew = X + 1
- Ynew = Y
- P1new = updateP1(P1)
- P2new = updateP2(P2)
- P3new = updateP3(P3)
- #obstacles se site koordinati kade bi se nashle preckite vo slednata iteracija
- obstacles = (P1new[0], P1new[1]), (P1new[0], P1new[1]+1), (P2new[0], P2new[1]), (P2new[0]-1, P2new[1]), (P2new[0], P2new[1]+1), (P2new[0]-1, P2new[1]+1), (P3new[0], P3new[1]), (P3new[0]+1, P3new[1])
- if( (Xnew, Ynew) not in obstacles):
- Statenew = (Xnew, Ynew, P1new[0], P1new[1], P1new[2], P2new[0],P2new[1], P2new[2],P3new[0], P3new[1], P3new[2])
- #vo statenew mi e novoto stanje posle mrdanje dole ako pomine ifot odnosno ovaa promena na sostojba nastanuva samo ako site constraints se zadovoleni
- successors['Dolu'] = Statenew
- #ako x e pogolemo od 0 mozham da odam nagore
- if (X > 0):
- Xnew = X - 1
- Ynew = Y
- P1new = updateP1(P1)
- P2new = updateP2(P2)
- P3new = updateP3(P3)
- # obstacles se site koordinati kade bi se nashle preckite vo slednata iteracija
- obstacles = (P1new[0], P1new[1]), (P1new[0], P1new[1] + 1), (P2new[0], P2new[1]), (P2new[0] - 1, P2new[1]), (P2new[0], P2new[1] + 1), (P2new[0] - 1, P2new[1] + 1), (P3new[0], P3new[1]), (P3new[0] + 1, P3new[1])
- if (((Xnew, Ynew) not in obstacles) and ((Y < 5) or (X > 5))):
- Statenew = (
- Xnew, Ynew, P1new[0], P1new[1], P1new[2], P2new[0], P2new[1], P2new[2], P3new[0], P3new[1], P3new[2])
- # vo statenew mi e novoto stanje posle mrdanje dole ako pomine ifot odnosno ovaa promena na sostojba nastanuva samo ako site constraints se zadovoleni
- successors['Gore'] = Statenew
- #ako y>0 mozham da odam vo levo
- if (Y > 0):
- Xnew = X
- Ynew = Y - 1
- P1new = updateP1(P1)
- P2new = updateP2(P2)
- P3new = updateP3(P3)
- # obstacles se site koordinati kade bi se nashle preckite vo slednata iteracija
- obstacles = (P1new[0], P1new[1]), (P1new[0], P1new[1] + 1), (P2new[0], P2new[1]), (P2new[0] - 1, P2new[1]), (P2new[0], P2new[1] + 1), (P2new[0] - 1, P2new[1] + 1), (P3new[0], P3new[1]), (P3new[0] + 1, P3new[1])
- if ((Xnew, Ynew) not in obstacles):
- Statenew = (
- Xnew, Ynew, P1new[0], P1new[1], P1new[2], P2new[0], P2new[1], P2new[2], P3new[0], P3new[1], P3new[2])
- # vo statenew mi e novoto stanje posle mrdanje dole ako pomine ifot odnosno ovaa promena na sostojba nastanuva samo ako site constraints se zadovoleni
- successors['Levo'] = Statenew
- # ako y<10 mozham da odam vo desno
- if (Y > 0):
- Xnew = X
- Ynew = Y + 1
- P1new = updateP1(P1)
- P2new = updateP2(P2)
- P3new = updateP3(P3)
- # obstacles se site koordinati kade bi se nashle preckite vo slednata iteracija
- obstacles = (P1new[0], P1new[1]), (P1new[0], P1new[1] + 1), (P2new[0], P2new[1]), (
- P2new[0] - 1, P2new[1]), (P2new[0], P2new[1] + 1), (P2new[0] - 1, P2new[1] + 1), (
- P3new[0], P3new[1]), (P3new[0] + 1, P3new[1])
- if (((Xnew, Ynew) not in obstacles) and ((X > 4) or (Y < 5))):
- Statenew = (Xnew, Ynew, P1new[0], P1new[1], P1new[2], P2new[0], P2new[1], P2new[2], P3new[0], P3new[1],
- P3new[2])
- # vo statenew mi e novoto stanje posle mrdanje dole ako pomine ifot odnosno ovaa promena na sostojba nastanuva samo ako site constraints se zadovoleni
- successors['Desno'] = Statenew
- return successors
- def actions(self,state):
- return self.successor(state).keys() #gi vrakjam site mozhni AKCII
- def result(self,state,action):
- possible = self.successor(state) #vrakjam koja sostojba e rezultat na dadena akcija pratena kako prarametar
- return possible[action]
- #Vcituvanje na vleznite argumenti za test primerite
- CoveceRedica = int(input())
- CoveceKolona = int(input())
- KukjaRedica = int(input())
- KukjaKolona = int(input())
- #Vasiot kod pisuvajte go pod ovoj komentar
- K = [KukjaRedica, KukjaKolona]
- IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona,2,1,1,7,3,1,9,8,1),K)
- answer = breadth_first_graph_search(IstrazuvacInstance)
- print (answer.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement