Advertisement
Guest User

Untitled

a guest
Jun 16th, 2019
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 19.64 KB | None | 0 0
  1. import bisect
  2. import sys
  3.  
  4. """
  5. Defining a class for the problem structure that we will solve with a search.
  6. The Problem class is an abstract class from which we make inheritance to define the basic
  7. characteristics of every problem we want to solve
  8. """
  9.  
  10.  
  11. class Problem:
  12. def __init__(self, initial, goal=None):
  13. self.initial = initial
  14. self.goal = goal
  15.  
  16. def successor(self, state):
  17. """Given a state, return a dictionary of {action : state} pairs reachable
  18. from this state. If there are many successors, consider an iterator
  19. that yields the successors one at a time, rather than building them
  20. all at once.
  21.  
  22. :param state: given state
  23. :return: dictionary of {action : state} pairs reachable
  24. from this state
  25. :rtype: dict
  26. """
  27. raise NotImplementedError
  28.  
  29. def actions(self, state):
  30. """Given a state, return a list of all actions possible
  31. from that state
  32.  
  33. :param state: given state
  34. :return: list of actions
  35. :rtype: list
  36. """
  37. raise NotImplementedError
  38.  
  39. def result(self, state, action):
  40. """Given a state and action, return the resulting state
  41.  
  42. :param state: given state
  43. :param action: given action
  44. :return: resulting state
  45. """
  46. raise NotImplementedError
  47.  
  48. def goal_test(self, state):
  49. """Return True if the state is a goal. The default method compares
  50. the state to self.goal, as specified in the constructor. Implement
  51. this method if checking against a single self.goal is not enough.
  52.  
  53. :param state: given state
  54. :return: is the given state a goal state
  55. :rtype: bool
  56. """
  57. return state == self.goal
  58.  
  59. def path_cost(self, c, state1, action, state2):
  60. """Return the cost of a solution path that arrives at state2 from state1
  61. via action, assuming cost c to get up to state1. If the problem is such
  62. that the path doesn't matter, this function will only look at state2. 
  63. If the path does matter, it will consider c and maybe state1 and action.
  64. The default method costs 1 for every step in the path.
  65.  
  66. :param c: cost of the path to get up to state1
  67. :param state1: given current state
  68. :param action: action that needs to be done
  69. :param state2: state to arrive to
  70. :return: cost of the path after executing the action
  71. :rtype: float
  72. """
  73. return c + 1
  74.  
  75. def value(self):
  76. """For optimization problems, each state has a value.
  77. Hill-climbing and related algorithms try to maximize this value.
  78.  
  79. :return: state value
  80. :rtype: float
  81. """
  82. raise NotImplementedError
  83.  
  84.  
  85. """
  86. Definition of the class for node structure of the search.
  87. The class Node is not inherited
  88. """
  89.  
  90.  
  91. class Node:
  92. def __init__(self, state, parent=None, action=None, path_cost=0):
  93. """Create node from the search tree, obtained from the parent by
  94. taking the action
  95.  
  96. :param state: current state
  97. :param parent: parent state
  98. :param action: action
  99. :param path_cost: path cost
  100. """
  101. self.state = state
  102. self.parent = parent
  103. self.action = action
  104. self.path_cost = path_cost
  105. self.depth = 0 # search depth
  106. if parent:
  107. self.depth = parent.depth + 1
  108.  
  109. def __repr__(self):
  110. return "<Node %s>" % (self.state,)
  111.  
  112. def __lt__(self, node):
  113. return self.state < node.state
  114.  
  115. def expand(self, problem):
  116. """List the nodes reachable in one step from this node.
  117.  
  118. :param problem: given problem
  119. :return: list of available nodes in one step
  120. :rtype: list(Node)
  121. """
  122. return [self.child_node(problem, action)
  123. for action in problem.actions(self.state)]
  124.  
  125. def child_node(self, problem, action):
  126. """Return a child node from this node
  127.  
  128. :param problem: given problem
  129. :param action: given action
  130. :return: available node according to the given action
  131. :rtype: Node
  132. """
  133. next_state = problem.result(self.state, action)
  134. return Node(next_state, self, action,
  135. problem.path_cost(self.path_cost, self.state,
  136. action, next_state))
  137.  
  138. def solution(self):
  139. """Return the sequence of actions to go from the root to this node.
  140.  
  141. :return: sequence of actions
  142. :rtype: list
  143. """
  144. return [node.action for node in self.path()[1:]]
  145.  
  146. def solve(self):
  147. """Return the sequence of states to go from the root to this node.
  148.  
  149. :return: list of states
  150. :rtype: list
  151. """
  152. return [node.state for node in self.path()[0:]]
  153.  
  154. def path(self):
  155. """Return a list of nodes forming the path from the root to this node.
  156.  
  157. :return: list of states from the path
  158. :rtype: list(Node)
  159. """
  160. x, result = self, []
  161. while x:
  162. result.append(x)
  163. x = x.parent
  164. result.reverse()
  165. return result
  166.  
  167. """We want the queue of nodes at breadth_first_search or
  168.     astar_search to not contain states-duplicates, so the nodes that
  169.     contain the same condition we treat as the same. [Problem: this can
  170.     not be desirable in other situations.]"""
  171.  
  172. def __eq__(self, other):
  173. return isinstance(other, Node) and self.state == other.state
  174.  
  175. def __hash__(self):
  176. return hash(self.state)
  177.  
  178.  
  179. """
  180. Definitions of helper structures for storing the list of generated, but not checked nodes
  181. """
  182.  
  183.  
  184. class Queue:
  185. """Queue is an abstract class/interface. There are three types:
  186.         Stack(): Last In First Out Queue (stack).
  187.         FIFOQueue(): First In First Out Queue.
  188.         PriorityQueue(order, f): QQueue in sorted order (default min-first).
  189.     """
  190.  
  191. def __init__(self):
  192. raise NotImplementedError
  193.  
  194. def append(self, item):
  195. """Adds the item into the queue
  196.  
  197. :param item: given element
  198. :return: None
  199. """
  200. raise NotImplementedError
  201.  
  202. def extend(self, items):
  203. """Adds the items into the queue
  204.  
  205. :param items: given elements
  206. :return: None
  207. """
  208. raise NotImplementedError
  209.  
  210. def pop(self):
  211. """Returns the first element of the queue
  212.  
  213. :return: first element
  214. """
  215. raise NotImplementedError
  216.  
  217. def __len__(self):
  218. """Returns the number of elements in the queue
  219.  
  220. :return: number of elements in the queue
  221. :rtype: int
  222. """
  223. raise NotImplementedError
  224.  
  225. def __contains__(self, item):
  226. """Check if the queue contains the element item
  227.  
  228. :param item: given element
  229. :return: whether the queue contains the item
  230. :rtype: bool
  231. """
  232. raise NotImplementedError
  233.  
  234.  
  235. class Stack(Queue):
  236. """Last-In-First-Out Queue."""
  237.  
  238. def __init__(self):
  239. self.data = []
  240.  
  241. def append(self, item):
  242. self.data.append(item)
  243.  
  244. def extend(self, items):
  245. self.data.extend(items)
  246.  
  247. def pop(self):
  248. return self.data.pop()
  249.  
  250. def __len__(self):
  251. return len(self.data)
  252.  
  253. def __contains__(self, item):
  254. return item in self.data
  255.  
  256.  
  257. class FIFOQueue(Queue):
  258. """First-In-First-Out Queue."""
  259.  
  260. def __init__(self):
  261. self.data = []
  262.  
  263. def append(self, item):
  264. self.data.append(item)
  265.  
  266. def extend(self, items):
  267. self.data.extend(items)
  268.  
  269. def pop(self):
  270. return self.data.pop(0)
  271.  
  272. def __len__(self):
  273. return len(self.data)
  274.  
  275. def __contains__(self, item):
  276. return item in self.data
  277.  
  278.  
  279. class PriorityQueue(Queue):
  280. """A queue in which the minimum (or maximum) element is returned first
  281.      (as determined by f and order). This structure is used in
  282.      informed search"""
  283.  
  284. def __init__(self, order=min, f=lambda x: x):
  285. """
  286. :param order: sorting function, if order is min, returns the element
  287.                       with minimal f (x); if the order is max, then returns the
  288. element with maximum f (x).
  289. :param f: function f(x)
  290. """
  291. assert order in [min, max]
  292. self.data = []
  293. self.order = order
  294. self.f = f
  295.  
  296. def append(self, item):
  297. bisect.insort_right(self.data, (self.f(item), item))
  298.  
  299. def extend(self, items):
  300. for item in items:
  301. bisect.insort_right(self.data, (self.f(item), item))
  302.  
  303. def pop(self):
  304. if self.order == min:
  305. return self.data.pop(0)[1]
  306. return self.data.pop()[1]
  307.  
  308. def __len__(self):
  309. return len(self.data)
  310.  
  311. def __contains__(self, item):
  312. return any(item == pair[1] for pair in self.data)
  313.  
  314. def __getitem__(self, key):
  315. for _, item in self.data:
  316. if item == key:
  317. return item
  318.  
  319. def __delitem__(self, key):
  320. for i, (value, item) in enumerate(self.data):
  321. if item == key:
  322. self.data.pop(i)
  323.  
  324. """
  325. Uninformed tree search.
  326. Within the tree we do not solve the loops.
  327. """
  328.  
  329.  
  330. def tree_search(problem, fringe):
  331. """Search through the successors of a problem to find a goal.
  332.  
  333. :param problem: given problem
  334. :param fringe: empty queue
  335. :return: Node
  336. """
  337. fringe.append(Node(problem.initial))
  338. while fringe:
  339. node = fringe.pop()
  340. print(node.state)
  341. if problem.goal_test(node.state):
  342. return node
  343. fringe.extend(node.expand(problem))
  344. return None
  345.  
  346.  
  347. def breadth_first_tree_search(problem):
  348. """Search the shallowest nodes in the search tree first.
  349.  
  350. :param problem: given problem
  351. :return: Node
  352. """
  353. return tree_search(problem, FIFOQueue())
  354.  
  355.  
  356. def depth_first_tree_search(problem):
  357. """Search the deepest nodes in the search tree first.
  358.  
  359. :param problem: given problem
  360. :return: Node
  361. """
  362. return tree_search(problem, Stack())
  363.  
  364.  
  365. """
  366. Uninformed graph search
  367. The main difference is that here we do not allow loops,
  368. i.e. repetition of states
  369. """
  370.  
  371.  
  372. def graph_search(problem, fringe):
  373. """Search through the successors of a problem to find a goal.
  374.     If two paths reach a state, only use the best one.
  375.  
  376. :param problem: given problem
  377. :param fringe: empty queue
  378. :return: Node
  379. """
  380. closed = set()
  381. fringe.append(Node(problem.initial))
  382. while fringe:
  383. node = fringe.pop()
  384. if problem.goal_test(node.state):
  385. return node
  386. if node.state not in closed:
  387. closed.add(node.state)
  388. fringe.extend(node.expand(problem))
  389. return None
  390.  
  391.  
  392. def breadth_first_graph_search(problem):
  393. """Search the shallowest nodes in the search tree first.
  394.  
  395. :param problem: given problem
  396. :return: Node
  397. """
  398. return graph_search(problem, FIFOQueue())
  399.  
  400.  
  401. def depth_first_graph_search(problem):
  402. """Search the deepest nodes in the search tree first.
  403.  
  404. :param problem: given problem
  405. :return: Node
  406. """
  407. return graph_search(problem, Stack())
  408.  
  409.  
  410. def depth_limited_search(problem, limit=50):
  411. def recursive_dls(node, problem, limit):
  412. """Helper function for depth limited"""
  413. cutoff_occurred = False
  414. if problem.goal_test(node.state):
  415. return node
  416. elif node.depth == limit:
  417. return 'cutoff'
  418. else:
  419. for successor in node.expand(problem):
  420. result = recursive_dls(successor, problem, limit)
  421. if result == 'cutoff':
  422. cutoff_occurred = True
  423. elif result is not None:
  424. return result
  425. if cutoff_occurred:
  426. return 'cutoff'
  427. return None
  428.  
  429. return recursive_dls(Node(problem.initial), problem, limit)
  430.  
  431.  
  432. def iterative_deepening_search(problem):
  433. for depth in range(sys.maxsize):
  434. result = depth_limited_search(problem, depth)
  435. if result is not 'cutoff':
  436. return result
  437.  
  438.  
  439. def uniform_cost_search(problem):
  440. """Search the nodes in the search tree with lowest cost first."""
  441. return graph_search(problem, PriorityQueue(min, lambda a: a.path_cost))
  442. class BoxWorld (Problem):
  443.  
  444. def __init__(self, initial):
  445. self.initial = initial
  446.  
  447. def actions(self, state):
  448. return self.successor(state).keys()
  449.  
  450. def result(self, state, action):
  451. return self.successor(state)[action]
  452.  
  453. def goal_test(self, state):
  454. if (state[1] == (2,3) or state[1] == (2,5) or state[1] == (2,7)) and (
  455. state[2] == (2,3) or state[2] == (2,5) or state[2] == (2,7)) and (
  456. state[3] == (2,3) or state[3] == (2,5) or state[3] == (2,7)):
  457. return True
  458. else:
  459. return False
  460.  
  461. def moveFigureUp (self,figure):
  462. x = figure [0]
  463. y = figure [1]
  464. return (x-1,y)
  465. def moveFigureDown (self,figure):
  466. x = figure [0]
  467. y = figure [1]
  468. return (x+1,y)
  469. def moveFigureLeft (self,figure):
  470. x = figure [0]
  471. y = figure [1]
  472. return (x,y-1)
  473. def moveFigureRight (self,figure):
  474. x = figure [0]
  475. y = figure [1]
  476. return (x,y+1)
  477.  
  478. def moveBoxUp (self,box):
  479. x = box [0]
  480. y = box [1]
  481. return (x-1,y)
  482. def moveBoxDown (self,box):
  483. x = box [0]
  484. y = box [1]
  485. return (x+1,y)
  486. def moveBoxLeft (self,box):
  487. x = box [0]
  488. y = box [1]
  489. return (x,y-1)
  490. def moveBoxRight (self,box):
  491. x = box [0]
  492. y = box [1]
  493. return (x,y+1)
  494.  
  495. def isValid(self, covek, box1, box2, box3):
  496. if covek[0] < 0 or covek[0] > 7:
  497. return False
  498. if covek[1] < 0 or covek[1] > 9:
  499. return False
  500. if box1[0] == 0 or box1[0] == 7:
  501. return False
  502. if box1[1] == 0 or box1[1] == 9:
  503. return False
  504. if box2[0] == 0 or box2[0] == 7:
  505. return False
  506. if box2[1] == 0 or box2[1] == 9:
  507. return False
  508. if box3[0] == 0 or box3[0] == 7:
  509. return False
  510. if box3[1] == 0 or box3[1] == 9:
  511. return False
  512. if box1 == box2 or box1 == box3 or box2 == box3 or covek == box1 or covek == box2 or covek == box3:
  513. return False
  514. return True
  515.  
  516. def successor(self, state):
  517. successors = dict ()
  518. figura = state[0]
  519. box1 = state[1]
  520. box2 = state[2]
  521. box3 = state[3]
  522. box1X = box1[0]
  523. box2X = box2[0]
  524. box3X = box3[0]
  525. box1Y = box1[1]
  526. box2Y = box2[1]
  527. box3Y = box3[1]
  528. covekX=figura[0]
  529. covekY=figura[1]
  530.  
  531. if covekX - box1X == 1 and covekY == box1Y:
  532. newFigura = self.moveFigureUp(figura)
  533. newBox1 = self.moveBoxUp(box1)
  534. if (self.isValid(newFigura,newBox1,box2,box3)):
  535. successors ['GoreCK'] = (newFigura,newBox1,box2,box3)
  536.  
  537. if box1X - covekX == 1 and covekY == box1Y:
  538. newFigura = self.moveFigureDown(figura)
  539. newBox1 = self.moveBoxDown(box1)
  540. if (self.isValid(newFigura, newBox1, box2, box3)):
  541. successors['DoluCK'] = (newFigura, newBox1, box2, box3)
  542.  
  543. if covekY - box1Y == 1 and covekX == box1X:
  544. newFigura = self.moveFigureLeft(figura)
  545. newBox1 = self.moveBoxLeft(box1)
  546. if (self.isValid(newFigura, newBox1, box2, box3)):
  547. successors['LevoCK'] = (newFigura, newBox1, box2, box3)
  548.  
  549. if box1Y - covekY == 1 and covekX == box1X:
  550. newFigura = self.moveFigureRight(figura)
  551. newBox1 = self.moveBoxRight(box1)
  552. if (self.isValid(newFigura, newBox1, box2, box3)):
  553. successors['DesnoCK'] = (newFigura, newBox1, box2, box3)
  554.  
  555. if covekX - box2X == 1 and covekY == box2Y:
  556. newFigura = self.moveFigureUp(figura)
  557. newBox2 = self.moveBoxUp(box2)
  558. if (self.isValid(newFigura, box1, newBox2, box3)):
  559. successors['GoreCK'] = (newFigura, box1, newBox2, box3)
  560.  
  561. if box2X - covekX == 1 and covekY == box2Y:
  562. newFigura = self.moveFigureDown(figura)
  563. newBox2 = self.moveBoxDown(box2)
  564. if (self.isValid(newFigura, box1, newBox2, box3)):
  565. successors['DoluCK'] = (newFigura, box1, newBox2, box3)
  566.  
  567. if covekY - box2Y == 1 and covekX == box2X:
  568. newFigura = self.moveFigureLeft(figura)
  569. newBox2 = self.moveBoxLeft(box2)
  570. if (self.isValid(newFigura, box1, newBox2, box3)):
  571. successors['LevoCK'] = (newFigura, box1, newBox2, box3)
  572.  
  573. if box2Y - covekY == 1 and covekX == box2X:
  574. newFigura = self.moveFigureRight(figura)
  575. newBox2 = self.moveBoxRight(box2)
  576. if (self.isValid(newFigura, box1, newBox2, box3)):
  577. successors['DesnoCK'] = (newFigura, box1, newBox2, box3)
  578.  
  579. if covekX - box3X == 1 and covekY == box3Y:
  580. newFigura = self.moveFigureUp(figura)
  581. newBox3 = self.moveBoxUp(box3)
  582. if (self.isValid(newFigura, box1, box2, newBox3)):
  583. successors['GoreCK'] = (newFigura, box1, box2, newBox3)
  584.  
  585. if box3X - covekX == 1 and covekY == box3Y:
  586. newFigura = self.moveFigureDown(figura)
  587. newBox3 = self.moveBoxDown(box3)
  588. if (self.isValid(newFigura, box1, box2, newBox3)):
  589. successors['DoluCK'] = (newFigura, box1, box2, newBox3)
  590.  
  591. if covekY - box3Y == 1 and covekX == box3X:
  592. newFigura = self.moveFigureLeft(figura)
  593. newBox3 = self.moveBoxLeft(box3)
  594. if (self.isValid(newFigura, box1, box2, newBox3)):
  595. successors['LevoCK'] = (newFigura, box1, box2, newBox3)
  596.  
  597. if box3Y - covekY == 1 and covekX == box3X:
  598. newFigura = self.moveFigureRight(figura)
  599. newBox3 = self.moveBoxRight(box3)
  600. if (self.isValid(newFigura, box1, box2, newBox3)):
  601. successors['DesnoCK'] = (newFigura, box1, box2, newBox3)
  602.  
  603. newFigura = self.moveFigureUp(figura)
  604. if (self.isValid(figura,box1,box2,box3)):
  605. successors['GoreC'] = (newFigura, box1, box2, box3)
  606.  
  607. newFigura = self.moveFigureDown(figura)
  608. if (self.isValid(figura, box1, box2, box3)):
  609. successors['DoluC'] = (newFigura, box1, box2, box3)
  610.  
  611. newFigura = self.moveFigureLeft(figura)
  612. if (self.isValid(figura, box1, box2, box3)):
  613. successors['LevoC'] = (newFigura, box1, box2, box3)
  614.  
  615. newFigura = self.moveFigureRight(figura)
  616. if (self.isValid(figura, box1, box2, box3)):
  617. successors['DesnoC'] = (newFigura, box1, box2, box3)
  618. return successors
  619.  
  620.  
  621.  
  622.  
  623.  
  624. if __name__ == '__main__':
  625. man_row = int(input())
  626. man_column = int(input())
  627. b1_row = int(input())
  628. b1_column = int(input())
  629. b2_row = int(input())
  630. b2_column = int(input())
  631. b3_row = int(input())
  632. b3_column = int(input())
  633. Man = (man_row,man_column)
  634. Box1 = (b1_row,b1_column)
  635. Box2 = (b2_row,b2_column)
  636. Box3 = (b3_row,b3_column)
  637. Dot1 = (2,3)
  638. Dot2 = (2,5)
  639. Dot3 = (2,7)
  640. initalState = (Man,Box1,Box2,Box3,Dot1,Dot2,Dot3)
  641. # print (state[1])
  642. problem = BoxWorld (initalState)
  643. answer = uniform_cost_search(problem)
  644. print (answer.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement