SHARE
TWEET

Untitled

a guest Apr 19th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #podvizni prepreki
  2.  
  3. import sys
  4. import bisect
  5.  
  6. infinity = float('inf')  # sistemski definirana vrednost za beskonecnost
  7.  
  8.  
  9. # ______________________________________________________________________________________________
  10. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  11.  
  12. class Queue:
  13.     """Queue is an abstract class/interface. There are three types:
  14.         Stack(): A Last In First Out Queue.
  15.         FIFOQueue(): A First In First Out Queue.
  16.         PriorityQueue(order, f): Queue in sorted order (default min-first).
  17.     Each type supports the following methods and functions:
  18.         q.append(item)  -- add an item to the queue
  19.         q.extend(items) -- equivalent to: for item in items: q.append(item)
  20.         q.pop()         -- return the top item from the queue
  21.         len(q)          -- number of items in q (also q.__len())
  22.         item in q       -- does q contain item?
  23.     Note that isinstance(Stack(), Queue) is false, because we implement stacks
  24.     as lists.  If Python ever gets interfaces, Queue will be an interface."""
  25.  
  26.     def __init__(self):
  27.         raise NotImplementedError
  28.  
  29.     def extend(self, items):
  30.         for item in items:
  31.             self.append(item)
  32.  
  33.  
  34. def Stack():
  35.     """A Last-In-First-Out Queue."""
  36.     return []
  37.  
  38.  
  39. class FIFOQueue(Queue):
  40.     """A First-In-First-Out Queue."""
  41.  
  42.     def __init__(self):
  43.         self.A = []
  44.         self.start = 0
  45.  
  46.     def append(self, item):
  47.         self.A.append(item)
  48.  
  49.     def __len__(self):
  50.         return len(self.A) - self.start
  51.  
  52.     def extend(self, items):
  53.         self.A.extend(items)
  54.  
  55.     def pop(self):
  56.         e = self.A[self.start]
  57.         self.start += 1
  58.         if self.start > 5 and self.start > len(self.A) / 2:
  59.             self.A = self.A[self.start:]
  60.             self.start = 0
  61.         return e
  62.  
  63.     def __contains__(self, item):
  64.         return item in self.A[self.start:]
  65.  
  66.  
  67. class PriorityQueue(Queue):
  68.     """A queue in which the minimum (or maximum) element (as determined by f and
  69.     order) is returned first. If order is min, the item with minimum f(x) is
  70.     returned first; if order is max, then it is the item with maximum f(x).
  71.     Also supports dict-like lookup. This structure will be most useful in informed searches"""
  72.  
  73.     def __init__(self, order=min, f=lambda x: x):
  74.         self.A = []
  75.         self.order = order
  76.         self.f = f
  77.  
  78.     def append(self, item):
  79.         bisect.insort(self.A, (self.f(item), item))
  80.  
  81.     def __len__(self):
  82.         return len(self.A)
  83.  
  84.     def pop(self):
  85.         if self.order == min:
  86.             return self.A.pop(0)[1]
  87.         else:
  88.             return self.A.pop()[1]
  89.  
  90.     def __contains__(self, item):
  91.         return any(item == pair[1] for pair in self.A)
  92.  
  93.     def __getitem__(self, key):
  94.         for _, item in self.A:
  95.             if item == key:
  96.                 return item
  97.  
  98.     def __delitem__(self, key):
  99.         for i, (value, item) in enumerate(self.A):
  100.             if item == key:
  101.                 self.A.pop(i)
  102.  
  103.  
  104. # ______________________________________________________________________________________________
  105. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  106. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  107. # na sekoj eden problem sto sakame da go resime
  108.  
  109.  
  110. class Problem:
  111.     """The abstract class for a formal problem.  You should subclass this and
  112.     implement the method successor, and possibly __init__, goal_test, and
  113.     path_cost. Then you will create instances of your subclass and solve them
  114.     with the various search functions."""
  115.  
  116.     def __init__(self, initial, goal=None):
  117.         """The constructor specifies the initial state, and possibly a goal
  118.         state, if there is a unique goal.  Your subclass's constructor can add
  119.         other arguments."""
  120.         self.initial = initial
  121.         self.goal = goal
  122.  
  123.     def successor(self, state):
  124.         """Given a state, return a dictionary of {action : state} pairs reachable
  125.         from this state. If there are many successors, consider an iterator
  126.         that yields the successors one at a time, rather than building them
  127.         all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  128.         raise NotImplementedError
  129.  
  130.     def actions(self, state):
  131.         """Given a state, return a list of all actions possible from that state"""
  132.         raise NotImplementedError
  133.  
  134.     def result(self, state, action):
  135.         """Given a state and action, return the resulting state"""
  136.         raise NotImplementedError
  137.  
  138.     def goal_test(self, state):
  139.         """Return True if the state is a goal. The default method compares the
  140.         state to self.goal, as specified in the constructor. Implement this
  141.         method if checking against a single self.goal is not enough."""
  142.         return state == self.goal
  143.  
  144.     def path_cost(self, c, state1, action, state2):
  145.         """Return the cost of a solution path that arrives at state2 from
  146.         state1 via action, assuming cost c to get up to state1. If the problem
  147.         is such that the path doesn't matter, this function will only look at
  148.         state2.  If the path does matter, it will consider c and maybe state1
  149.         and action. The default method costs 1 for every step in the path."""
  150.         return c + 1
  151.  
  152.     def value(self):
  153.         """For optimization problems, each state has a value.  Hill-climbing
  154.         and related algorithms try to maximize this value."""
  155.         raise NotImplementedError
  156.  
  157.  
  158. # ______________________________________________________________________________
  159. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  160. # Klasata Node ne se nasleduva
  161.  
  162. class Node:
  163.     """A node in a search tree. Contains a pointer to the parent (the node
  164.     that this is a successor of) and to the actual state for this node. Note
  165.     that if a state is arrived at by two paths, then there are two nodes with
  166.     the same state.  Also includes the action that got us to this state, and
  167.     the total path_cost (also known as g) to reach the node.  Other functions
  168.     may add an f and h value; see best_first_graph_search and astar_search for
  169.     an explanation of how the f and h values are handled. You will not need to
  170.     subclass this class."""
  171.  
  172.     def __init__(self, state, parent=None, action=None, path_cost=0):
  173.         "Create a search tree Node, derived from a parent by an action."
  174.         self.state = state
  175.         self.parent = parent
  176.         self.action = action
  177.         self.path_cost = path_cost
  178.         self.depth = 0
  179.         if parent:
  180.             self.depth = parent.depth + 1
  181.  
  182.     def __repr__(self):
  183.         return "<Node %s>" % (self.state,)
  184.  
  185.     def __lt__(self, node):
  186.         return self.state < node.state
  187.  
  188.     def expand(self, problem):
  189.         "List the nodes reachable in one step from this node."
  190.         return [self.child_node(problem, action)
  191.                 for action in problem.actions(self.state)]
  192.  
  193.     def child_node(self, problem, action):
  194.         "Return a child node from this node"
  195.         next = problem.result(self.state, action)
  196.         return Node(next, self, action,
  197.                     problem.path_cost(self.path_cost, self.state,
  198.                                       action, next))
  199.  
  200.     def solution(self):
  201.         "Return the sequence of actions to go from the root to this node."
  202.         return [node.action for node in self.path()[1:]]
  203.  
  204.     def solve(self):
  205.         "Return the sequence of states to go from the root to this node."
  206.         return [node.state for node in self.path()[0:]]
  207.  
  208.     def path(self):
  209.         "Return a list of nodes forming the path from the root to this node."
  210.         x, result = self, []
  211.         while x:
  212.             result.append(x)
  213.             x = x.parent
  214.         return list(reversed(result))
  215.  
  216.     # We want for a queue of nodes in breadth_first_search or
  217.     # astar_search to have no duplicated states, so we treat nodes
  218.     # with the same state as equal. [Problem: this may not be what you
  219.     # want in other contexts.]
  220.  
  221.     def __eq__(self, other):
  222.         return isinstance(other, Node) and self.state == other.state
  223.  
  224.     def __hash__(self):
  225.         return hash(self.state)
  226.  
  227.  
  228. # ________________________________________________________________________________________________________
  229. # Pomosna funkcija za informirani prebaruvanja
  230. # So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
  231.  
  232. def memoize(fn, slot=None):
  233.     """Memoize fn: make it remember the computed value for any argument list.
  234.     If slot is specified, store result in that slot of first argument.
  235.     If slot is false, store results in a dictionary."""
  236.     if slot:
  237.         def memoized_fn(obj, *args):
  238.             if hasattr(obj, slot):
  239.                 return getattr(obj, slot)
  240.             else:
  241.                 val = fn(obj, *args)
  242.                 setattr(obj, slot, val)
  243.                 return val
  244.     else:
  245.         def memoized_fn(*args):
  246.             if not memoized_fn.cache.has_key(args):
  247.                 memoized_fn.cache[args] = fn(*args)
  248.             return memoized_fn.cache[args]
  249.  
  250.         memoized_fn.cache = {}
  251.     return memoized_fn
  252.  
  253.  
  254. # ________________________________________________________________________________________________________
  255. # Informirano prebaruvanje vo ramki na graf
  256.  
  257. def best_first_graph_search(problem, f):
  258.     """Search the nodes with the lowest f scores first.
  259.     You specify the function f(node) that you want to minimize; for example,
  260.     if f is a heuristic estimate to the goal, then we have greedy best
  261.     first search; if f is node.depth then we have breadth-first search.
  262.     There is a subtlety: the line "f = memoize(f, 'f')" means that the f
  263.     values will be cached on the nodes as they are computed. So after doing
  264.     a best first search you can examine the f values of the path returned."""
  265.  
  266.     f = memoize(f, 'f')
  267.     node = Node(problem.initial)
  268.     if problem.goal_test(node.state):
  269.         return node
  270.     frontier = PriorityQueue(min, f)
  271.     frontier.append(node)
  272.     explored = set()
  273.     while frontier:
  274.         node = frontier.pop()
  275.         if problem.goal_test(node.state):
  276.             return node
  277.         explored.add(node.state)
  278.         for child in node.expand(problem):
  279.             if child.state not in explored and child not in frontier:
  280.                 frontier.append(child)
  281.             elif child in frontier:
  282.                 incumbent = frontier[child]
  283.                 if f(child) < f(incumbent):
  284.                     del frontier[incumbent]
  285.                     frontier.append(child)
  286.     return None
  287.  
  288.  
  289. def greedy_best_first_graph_search(problem, h=None):
  290.     "Greedy best-first search is accomplished by specifying f(n) = h(n)"
  291.     h = memoize(h or problem.h, 'h')
  292.     return best_first_graph_search(problem, h)
  293.  
  294.  
  295. def astar_search(problem, h=None):
  296.     "A* search is best-first graph search with f(n) = g(n)+h(n)."
  297.     h = memoize(h or problem.h, 'h')
  298.     return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  299.  
  300.  
  301. # ________________________________________________________________________________________________________
  302. # Dopolnitelni prebaruvanja
  303. # Recursive_best_first_search e implementiran
  304. # Kako zadaca za studentite da gi implementiraat SMA* i IDA*
  305.  
  306. def recursive_best_first_search(problem, h=None):
  307.     h = memoize(h or problem.h, 'h')
  308.  
  309.     def RBFS(problem, node, flimit):
  310.         if problem.goal_test(node.state):
  311.             return node, 0  # (The second value is immaterial)
  312.         successors = node.expand(problem)
  313.         if len(successors) == 0:
  314.             return None, infinity
  315.         for s in successors:
  316.             s.f = max(s.path_cost + h(s), node.f)
  317.         while True:
  318.             # Order by lowest f value
  319.             successors.sort(key=lambda x: x.f)
  320.             best = successors[0]
  321.             if best.f > flimit:
  322.                 return None, best.f
  323.             if len(successors) > 1:
  324.                 alternative = successors[1].f
  325.             else:
  326.                 alternative = infinity
  327.             result, best.f = RBFS(problem, best, min(flimit, alternative))
  328.             if result is not None:
  329.                 return result, best.f
  330.  
  331.     node = Node(problem.initial)
  332.     node.f = h(node)
  333.     result, bestf = RBFS(problem, node, infinity)
  334.     return result
  335.  
  336.  
  337. # _________________________________________________________________________________________________________
  338. # PRIMER 2 : PROBLEM NA SLOZUVALKA
  339. # OPIS: Dadena e slozuvalka 3x3 na koja ima polinja so brojki od 1 do 8 i edno prazno pole
  340. # Praznoto pole e obelezano so *. Eden primer na slozuvalka e daden vo prodolzenie:
  341. #  -------------
  342. #  | * | 3 | 2 |
  343. #  |---|---|---|
  344. #  | 4 | 1 | 5 |
  345. #  |---|---|---|
  346. #  | 6 | 7 | 8 |
  347. #  -------------
  348. # Problemot e kako da se stigne do nekoja pocetna raspredelba na polinjata do nekoja posakuvana, na primer do:
  349. #  -------------
  350. #  | * | 1 | 2 |
  351. #  |---|---|---|
  352. #  | 3 | 4 | 5 |
  353. #  |---|---|---|
  354. #  | 6 | 7 | 8 |
  355. #  -------------
  356. # AKCII: Akciite ke gi gledame kako dvizenje na praznoto pole, pa mozni akcii se : gore, dole, levo i desno.
  357. # Pri definiranjeto na akciite mora da se vnimava dali akciite voopsto mozat da se prevzemat vo dadenata slozuvalka
  358. # STATE: Sostojbata ke ja definirame kako string koj ke ima 9 karakteri (po eden za sekoe brojce plus za *)
  359. # pri sto stringot ke se popolnuva so izminuvanje na slozuvalkata od prviot kon tretiot red, od levo kon desno.
  360. # Na primer sostojbata za pocetnata slozuvalka e: '*32415678'
  361. # Sostojbata za finalnata slozuvalka e: '*12345678'
  362. # ________________________________________________________________________________________________________
  363. #
  364.  
  365. default_goal = '*12345678'  # predefinirana cel
  366.  
  367.  
  368. # Ke definirame 3 klasi za problemot
  369. # Prvata klasa nema implementirano nikakva hevristika
  370.  
  371. class P8(Problem):
  372.     name = 'No Heuristic'
  373.  
  374.     def __init__(self, goal=default_goal, initial=None, N=20):
  375.         self.goal = goal
  376.         self.initial = initial
  377.  
  378.     def successor(self, state):
  379.         return successor8(state)
  380.  
  381.     def actions(self, state):
  382.         return self.successor(state).keys()
  383.  
  384.     def h(self, node):
  385.         """Heuristic for 8 puzzle: returns 0"""
  386.         return 0
  387.  
  388.     def result(self, state, action):
  389.         possible = self.successor(state)
  390.         return possible[action]
  391.  
  392.  
  393. # Slednite klasi ke nasleduvaat od prethodnata bez hevristika so toa sto ovde ke ja definirame i hevristikata
  394.  
  395. class P8_h1(P8):
  396.     """ Slozuvalka so hevristika
  397.     HEVRISTIKA: Brojot na polinja koi ne se na vistinskoto mesto"""
  398.  
  399.     name = 'Out of Place Heuristic'
  400.  
  401.     def h(self, node):
  402.         """Funkcija koja ja presmetuva hevristikata,
  403.         t.e. razlikata pomegu nekoj tekoven jazel od prebaruvanjeto i celniot jazel"""
  404.         matches = 0
  405.         for (t1, t2) in zip(node.state, self.goal):
  406.             # zip funkcijata od dve listi na vlez pravi edna lista od parovi (torki)
  407.             # primer: zip(['a','b','c'],[1,2,3]) == [('a',1),('b',2),('c',3)]
  408.             # zip('abc','123') == [('a','1'),('b','2'),('c','3')]
  409.             if t1 != t2:
  410.                 matches = + 1
  411.         return matches
  412.  
  413.  
  414. class P8_h2(P8):
  415.     """ Slozuvalka so hevristika
  416.     HEVRISTIKA: Menheten rastojanie do celna sostojba"""
  417.  
  418.     name = 'Manhattan Distance Heuristic (MHD)'
  419.  
  420.     def h(self, node):
  421.         """Funkcija koja ja presmetuva hevristikata,
  422.         t.e. Menheten rastojanieto pomegu nekoj tekoven jazel od prebaruvanjeto i celniot jazel, pri sto
  423.         Menheten rastojanieto megu jazlite e zbir od Menheten rastojanijata pomegu istite broevi vo dvata jazli"""
  424.         sum = 0
  425.         for c in '12345678':
  426.             sum = + mhd(node.state.index(c), self.goal.index(c))  # pomosna funkcija definirana vo prodolzenie
  427.         return sum
  428.  
  429.  
  430. # Za da mozeme da go definirame rastojanieto treba da definirame koordinaten sistem
  431. # Pozetokot na koordinatniot sistem e postaven vo gorniot lev agol na slozuvalkata
  432. # Definirame recnik za koordinatite na sekoe pole od slozuvalkata
  433. coordinates = {0: (0, 0), 1: (1, 0), 2: (2, 0),
  434.                3: (0, 1), 4: (1, 1), 5: (2, 1),
  435.                6: (0, 2), 7: (1, 2), 8: (2, 2)}
  436.  
  437.  
  438. # Funkcija koja presmetuva Menheten rastojanie za slozuvalkata
  439. # Na vlez dobiva dva celi broja koi odgovaraat na dve polinja na koi se naogaat broevite za koi treba da presmetame rastojanie
  440. def mhd(n, m):
  441.     x1, y1 = coordinates[n]
  442.     x2, y2 = coordinates[m]
  443.     return abs(x1 - x2) + abs(y1 - y2)
  444.  
  445.  
  446. def successor8(S):
  447.     """Pomosna funkcija koja generira recnik za sledbenicite na daden jazel"""
  448.  
  449.     blank = S.index('*')  # kade se naoga praznoto pole
  450.  
  451.     succs = {}
  452.  
  453.     # GORE: Ako praznoto pole ne e vo prviot red, togas vo sostojbata napravi swap
  454.     # na praznoto pole so brojceto koe se naoga na poleto nad nego
  455.     if blank > 2:
  456.         swap = blank - 3
  457.         succs['GORE'] = S[0:swap] + '*' + S[swap + 1:blank] + S[swap] + S[blank + 1:]
  458.  
  459.     # DOLE: Ako praznoto pole ne e vo posledniot red, togas vo sostojbata napravi swap
  460.     # na praznoto pole so brojceto koe se naoga na poleto pod nego
  461.     if blank < 6:
  462.         swap = blank + 3
  463.         succs['DOLE'] = S[0:blank] + S[swap] + S[blank + 1:swap] + '*' + S[swap + 1:]
  464.  
  465.     # LEVO: Ako praznoto pole ne e vo prvata kolona, togas vo sostojbata napravi swap
  466.     # na praznoto pole so brojceto koe se naoga na poleto levo od nego
  467.     if blank % 3 > 0:
  468.         swap = blank - 1
  469.         succs['LEVO'] = S[0:swap] + '*' + S[swap] + S[blank + 1:]
  470.  
  471.     # DESNO: Ako praznoto pole ne e vo poslednata kolona, togas vo sostojbata napravi swap
  472.     # na praznoto pole so brojceto koe se naoga na poleto desno od nego
  473.     if blank % 3 < 2:
  474.         swap = blank + 1
  475.         succs['DESNO'] = S[0:blank] + S[swap] + '*' + S[swap + 1:]
  476.  
  477.     return succs
  478.  
  479.  
  480. # So vaka definiraniot problem mozeme da gi koristime site informirani, no i neinformirani prebaruvanja
  481. # Vo prodolzenie se dadeni mozni povici (vnimavajte za da moze da napravite povik mora da definirate problem)
  482. #
  483. #    s='*32415678'
  484. #    p1=P8(initial=s)
  485. #    p2=P8_h1(initial=s)
  486. #    p3=P8_h2(initial=s)
  487. #
  488. #    answer1 = greedy_best_first_graph_search(p1)
  489. #    print answer1.solve()
  490. #
  491. #    answer2 = greedy_best_first_graph_search(p2)
  492. #    print answer2.solve()
  493. #
  494. #    answer3 = greedy_best_first_graph_search(p3)
  495. #    print answer3.solve()
  496. #
  497. #    answer4 = astar_search(p1)
  498. #    print answer4.solve()
  499. #
  500. #    answer5 = astar_search(p2)
  501. #    print answer5.solve()
  502. #
  503. #    answer6 = astar_search(p3)
  504. #    print answer6.solve()
  505. #
  506. #    answer7 = recursive_best_first_search(p1)
  507. #    print answer7.solve()
  508. #
  509. #    answer8 = recursive_best_first_search(p2)
  510. #    print answer8.solve()
  511. #
  512. #    answer9 = recursive_best_first_search(p3)
  513. #    print answer9.solve()
  514. def updateP1(P1):
  515.     x = P1[0]
  516.     y = P1[1]
  517.     n = P1[2]
  518.     if (y == 4 and n == 1):
  519.         n = n * (-1)
  520.     if (y == 0 and n == -1):
  521.         n = n * (-1)
  522.     ynew = y + n
  523.     return (x, ynew, n)
  524.  
  525.  
  526. def updateP2(P2):
  527.     x = P2[0]
  528.     y = P2[1]
  529.     n = P2[2]
  530.     if (x == 5 and y == 4 and n == 1):
  531.         n = n * (-1)
  532.     if (y == 0 and x == 9 and n == -1):
  533.         n = n * (-1)
  534.     xnew = x - n
  535.     ynew = y + n
  536.     return (xnew, ynew, n)
  537.  
  538.  
  539. def updateP3(P3):
  540.     x = P3[0]
  541.     y = P3[1]
  542.     n = P3[2]
  543.     if (x == 5 and n == -1):
  544.         n = n * (-1)
  545.     if (x == 9 and n == 1):
  546.         n = n * (-1)
  547.     xnew = x + n
  548.     return (xnew, y, n)
  549.  
  550.  
  551. def isValid(x, y, P1, P2, P3):
  552.     t = 1
  553.     if (x == P1[0] and y == P1[1]) or (x == P1[0] and y == P1[1] + 1):
  554.         t = 0
  555.     if (x == P2[0] and y == P2[1]) or (x == P2[0] and y == P2[1] + 1) or (x == P2[0] + 1 and y == P2[1]) or (
  556.             x == P2[0] + 1 and y == P2[1] + 1):
  557.         t = 0
  558.     if (x == P3[0] and y == P3[1]) or (x == P3[0] + 1 and y == P3[1]):
  559.         t = 0
  560.     return t
  561.  
  562.  
  563. class Istrazuvac(Problem):
  564.     def __init__(self, initial, goal):
  565.         self.initial = initial
  566.         self.goal = goal
  567.  
  568.     def successor(self, state):
  569.         successors = dict()
  570.         X = state[0]
  571.         Y = state[1]
  572.         P1 = state[2]
  573.         P2 = state[3]
  574.         P3 = state[4]
  575.         P1new = updateP1(P1)
  576.         P2new = updateP2(P2)
  577.         P3new = updateP3(P3)
  578.  
  579.         # Levo
  580.         if Y - 1 >= 0:
  581.             Ynew = Y - 1
  582.             Xnew = X
  583.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  584.                 successors['Levo'] = (Xnew, Ynew, P1new, P2new, P3new)
  585.         # Desno
  586.         if X < 5 and Y < 5:
  587.             Ynew = Y + 1
  588.             Xnew = X
  589.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  590.                 successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  591.         elif X >= 5 and Y < 10:
  592.             Xnew = X
  593.             Ynew = Y + 1
  594.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  595.                 successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  596.         # Dolu
  597.         if X < 10:
  598.             Xnew = X + 1
  599.             Ynew = Y
  600.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  601.                 successors['Dolu'] = (Xnew, Ynew, P1new, P2new, P3new)
  602.         # Gore
  603.         if Y >= 6 and X > 5:
  604.             Xnew = X - 1
  605.             Ynew = Y
  606.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  607.                 successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  608.         elif Y < 6 and X > 0:
  609.             Xnew = X - 1
  610.             Ynew = Y
  611.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  612.                 successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  613.         return successors
  614.  
  615.     def actions(self, state):
  616.         return self.successor(state).keys()
  617.  
  618.     def result(self, state, action):
  619.         possible = self.successor(state)
  620.         return possible[action]
  621.  
  622.     def goal_test(self, state):
  623.         g = self.goal
  624.         return (state[0] == g[0] and state[1] == g[1])
  625.  
  626.     def h(self, node):
  627.         rez = abs(node.state[0] - self.goal[0]) + abs(node.state[1] - self.goal[1])
  628.         return rez
  629.  
  630.  
  631. # Vcituvanje na vleznite argumenti za test primerite
  632.  
  633. CoveceRedica = input()
  634. CoveceKolona = input()
  635. KukaRedica = input()
  636. KukaKolona = input()
  637.  
  638. # Vasiot kod pisuvajte go pod ovoj komentar
  639.  
  640. # prepreka 1 ima lev kvadrat na 2,2 odi levo (-1) na pocetok, prepreka 2 ima goren lev kvadrat na 2,7 odi gore desno (1)
  641. # prepreka 3 ima gore kvadrat na 8,7 odi nagore na pocetok(-1)
  642. IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona, (2, 2, -1), (7, 2, 1), (7, 8, 1)),
  643.                                 (KukaRedica, KukaKolona))
  644.  
  645. answer = astar_search(IstrazuvacInstance).solution()
  646. print(answer)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top