Advertisement
mitkonikov

Untitled

Mar 16th, 2023
468
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 12.78 KB | None | 0 0
  1. import bisect
  2. from copy import deepcopy
  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. dx = [0, 1, 0, -1]
  11. dy = [1, 0, -1, 0]
  12. op = [2, 3, 0, 1]
  13.  
  14. class Problem:
  15.     def __init__(self, initial, goal=None):
  16.         # [red, green, snake]
  17.         self.initial = initial
  18.         self.goal = goal
  19.  
  20.     def valid(self, x, y):
  21.         return (x >= 0 and x < 10 and y >= 0 and y < 10)
  22.  
  23.     def go(self, S, dir):
  24.         state = [None, None, None]
  25.         state[0] = list(S[0])
  26.         state[1] = list(S[1])
  27.         state[2] = list(S[2])
  28.         current = state[2][-1]
  29.         nx = current[0] + dx[dir]
  30.         ny = current[1] + dy[dir]
  31.         if not self.valid(nx, ny):
  32.             return None
  33.  
  34.         red_ahead = False
  35.         for apple in state[0]:
  36.             if apple[0] == nx and apple[1] == ny:
  37.                 red_ahead = True
  38.                 break
  39.  
  40.         if red_ahead:
  41.             return None
  42.  
  43.         green_ahead = False
  44.         for i in range(len(state[1])):
  45.             if state[1][i][0] == nx and state[1][i][1] == ny:
  46.                 green_ahead = True
  47.                 state[1].pop(i)
  48.                 break
  49.  
  50.         # remove the tail
  51.         if not green_ahead:
  52.             state[2].pop(0)
  53.  
  54.         # add the head
  55.         state[2].append((nx, ny))
  56.  
  57.         state[0] = tuple(state[0])
  58.         state[1] = tuple(state[1])
  59.         state[2] = tuple(state[2])
  60.         return tuple(state)
  61.  
  62.     def successor(self, state):
  63.         """Given a state, return a dictionary of {action : state} pairs reachable
  64.        from this state. If there are many successors, consider an iterator
  65.        that yields the successors one at a time, rather than building them
  66.        all at once.
  67.  
  68.        :param state: given state
  69.        :return:  dictionary of {action : state} pairs reachable
  70.                  from this state
  71.        :rtype: dict
  72.        """
  73.  
  74.         successors = {}
  75.  
  76.         red, green, snake = deepcopy(state)
  77.  
  78.         dir_coming_from = 0
  79.         for dir in range(4):
  80.             nx = snake[-1][0] + dx[dir]
  81.             ny = snake[-1][1] + dy[dir]
  82.             if nx == snake[-2][0] and ny == snake[-2][1]:
  83.                 dir_coming_from = dir
  84.                 break
  85.        
  86.         # pravo e op[dir_coming_from]
  87.         # levo e op[dir_coming_from] - 1
  88.         # desno e op[dir_coming_from] + 1
  89.  
  90.         ahead = self.go(state, op[dir_coming_from])
  91.         if ahead is not None:
  92.             successors['ProdolzhiPravo'] = ahead
  93.        
  94.         right = self.go(state, (op[dir_coming_from] + 1) % 4)
  95.         if right is not None:
  96.             successors['SvrtiDesno'] = right
  97.        
  98.         left = self.go(state, (op[dir_coming_from] - 1 + 4) % 4)
  99.         if left is not None:
  100.             successors['SvrtiLevo'] = left
  101.  
  102.         return successors
  103.  
  104.     def actions(self, state):
  105.         """Given a state, return a list of all actions possible
  106.        from that state
  107.  
  108.        :param state: given state
  109.        :return: list of actions
  110.        :rtype: list
  111.        """
  112.         return self.successor(state).keys()
  113.  
  114.     def result(self, state, action):
  115.         """Given a state and action, return the resulting state
  116.  
  117.        :param state: given state
  118.        :param action: given action
  119.        :return: resulting state
  120.        """
  121.         return self.successor(state)[action]
  122.  
  123.     def goal_test(self, state):
  124.         """Return True if the state is a goal. The default method compares
  125.        the state to self.goal, as specified in the constructor. Implement
  126.        this method if checking against a single self.goal is not enough.
  127.  
  128.        :param state: given state
  129.        :return: is the given state a goal state
  130.        :rtype: bool
  131.        """
  132.         # all green apples are eaten
  133.         return len(state[1]) == 0
  134.  
  135.     def path_cost(self, c, state1, action, state2):
  136.         """Return the cost of a solution path that arrives at state2 from state1
  137.        via action, assuming cost c to get up to state1. If the problem is such
  138.        that the path doesn't matter, this function will only look at state2.
  139.        If the path does matter, it will consider c and maybe state1 and action.
  140.        The default method costs 1 for every step in the path.
  141.  
  142.        :param c: cost of the path to get up to state1
  143.        :param state1: given current state
  144.        :param action: action that needs to be done
  145.        :param state2: state to arrive to
  146.        :return: cost of the path after executing the action
  147.        :rtype: float
  148.        """
  149.         return c + 1
  150.  
  151.     def value(self):
  152.         """For optimization problems, each state has a value.
  153.        Hill-climbing and related algorithms try to maximize this value.
  154.  
  155.        :return: state value
  156.        :rtype: float
  157.        """
  158.         return -len(self.initial[1])
  159.  
  160.  
  161. """
  162. Definition of the class for node structure of the search.
  163. The class Node is not inherited
  164. """
  165.  
  166.  
  167. class Node:
  168.     def __init__(self, state, parent=None, action=None, path_cost=0):
  169.         """Create node from the search tree,  obtained from the parent by
  170.        taking the action
  171.  
  172.        :param state: current state
  173.        :param parent: parent state
  174.        :param action: action
  175.        :param path_cost: path cost
  176.        """
  177.         self.state = state
  178.         self.parent = parent
  179.         self.action = action
  180.         self.path_cost = path_cost
  181.         self.depth = 0  # search depth
  182.         if parent:
  183.             self.depth = parent.depth + 1
  184.  
  185.     def __repr__(self):
  186.         return "<Node %s>" % (self.state,)
  187.  
  188.     def __lt__(self, node):
  189.         return self.state < node.state
  190.  
  191.     def expand(self, problem):
  192.         """List the nodes reachable in one step from this node.
  193.  
  194.        :param problem: given problem
  195.        :return: list of available nodes in one step
  196.        :rtype: list(Node)
  197.        """
  198.         return [self.child_node(problem, action)
  199.                 for action in problem.actions(self.state)]
  200.  
  201.     def child_node(self, problem, action):
  202.         """Return a child node from this node
  203.  
  204.        :param problem: given problem
  205.        :param action: given action
  206.        :return: available node  according to the given action
  207.        :rtype: Node
  208.        """
  209.         next_state = problem.result(self.state, action)
  210.         return Node(next_state, self, action,
  211.                     problem.path_cost(self.path_cost, self.state,
  212.                                       action, next_state))
  213.  
  214.     def solution(self):
  215.         """Return the sequence of actions to go from the root to this node.
  216.  
  217.        :return: sequence of actions
  218.        :rtype: list
  219.        """
  220.         return [node.action for node in self.path()[1:]]
  221.  
  222.     def solve(self):
  223.         """Return the sequence of states to go from the root to this node.
  224.  
  225.        :return: list of states
  226.        :rtype: list
  227.        """
  228.         return [node.state for node in self.path()[0:]]
  229.  
  230.     def path(self):
  231.         """Return a list of nodes forming the path from the root to this node.
  232.  
  233.        :return: list of states from the path
  234.        :rtype: list(Node)
  235.        """
  236.         x, result = self, []
  237.         while x:
  238.             result.append(x)
  239.             x = x.parent
  240.         result.reverse()
  241.         return result
  242.  
  243.     """We want the queue of nodes at breadth_first_search or
  244.    astar_search to not contain states-duplicates, so the nodes that
  245.    contain the same condition we treat as the same. [Problem: this can
  246.    not be desirable in other situations.]"""
  247.  
  248.     def __eq__(self, other):
  249.         return isinstance(other, Node) and self.state == other.state
  250.  
  251.     def __hash__(self):
  252.         return hash(self.state)
  253.  
  254.  
  255. """
  256. Definitions of helper structures for storing the list of generated, but not checked nodes
  257. """
  258.  
  259.  
  260. class Queue:
  261.     """Queue is an abstract class/interface. There are three types:
  262.        Stack(): Last In First Out Queue (stack).
  263.        FIFOQueue(): First In First Out Queue.
  264.        PriorityQueue(order, f): Queue in sorted order (default min-first).
  265.    """
  266.  
  267.     def __init__(self):
  268.         raise NotImplementedError
  269.  
  270.     def append(self, item):
  271.         """Adds the item into the queue
  272.  
  273.        :param item: given element
  274.        :return: None
  275.        """
  276.         raise NotImplementedError
  277.  
  278.     def extend(self, items):
  279.         """Adds the items into the queue
  280.  
  281.        :param items: given elements
  282.        :return: None
  283.        """
  284.         raise NotImplementedError
  285.  
  286.     def pop(self):
  287.         """Returns the first element of the queue
  288.  
  289.        :return: first element
  290.        """
  291.         raise NotImplementedError
  292.  
  293.     def __len__(self):
  294.         """Returns the number of elements in the queue
  295.  
  296.        :return: number of elements in the queue
  297.        :rtype: int
  298.        """
  299.         raise NotImplementedError
  300.  
  301.     def __contains__(self, item):
  302.         """Check if the queue contains the element item
  303.  
  304.        :param item: given element
  305.        :return: whether the queue contains the item
  306.        :rtype: bool
  307.        """
  308.         raise NotImplementedError
  309.  
  310.  
  311. class Stack(Queue):
  312.     """Last-In-First-Out Queue."""
  313.  
  314.     def __init__(self):
  315.         self.data = []
  316.  
  317.     def append(self, item):
  318.         self.data.append(item)
  319.  
  320.     def extend(self, items):
  321.         self.data.extend(items)
  322.  
  323.     def pop(self):
  324.         return self.data.pop()
  325.  
  326.     def __len__(self):
  327.         return len(self.data)
  328.  
  329.     def __contains__(self, item):
  330.         return item in self.data
  331.  
  332.  
  333. class FIFOQueue(Queue):
  334.     """First-In-First-Out Queue."""
  335.  
  336.     def __init__(self):
  337.         self.data = []
  338.  
  339.     def append(self, item):
  340.         self.data.append(item)
  341.  
  342.     def extend(self, items):
  343.         self.data.extend(items)
  344.  
  345.     def pop(self):
  346.         return self.data.pop(0)
  347.  
  348.     def __len__(self):
  349.         return len(self.data)
  350.  
  351.     def __contains__(self, item):
  352.         return item in self.data
  353.  
  354.  
  355. class PriorityQueue(Queue):
  356.     """A queue in which the minimum (or maximum) element is returned first
  357.     (as determined by f and order). This structure is used in
  358.     informed search"""
  359.  
  360.     def __init__(self, order=min, f=lambda x: x):
  361.         """
  362.        :param order: sorting function, if order is min, returns the element
  363.                      with minimal f (x); if the order is max, then returns the
  364.                      element with maximum f (x).
  365.        :param f: function f(x)
  366.        """
  367.         assert order in [min, max]
  368.         self.data = []
  369.         self.order = order
  370.         self.f = f
  371.  
  372.     def append(self, item):
  373.         bisect.insort_right(self.data, (self.f(item), item))
  374.  
  375.     def extend(self, items):
  376.         for item in items:
  377.             bisect.insort_right(self.data, (self.f(item), item))
  378.  
  379.     def pop(self):
  380.         if self.order == min:
  381.             return self.data.pop(0)[1]
  382.         return self.data.pop()[1]
  383.  
  384.     def __len__(self):
  385.         return len(self.data)
  386.  
  387.     def __contains__(self, item):
  388.         return any(item == pair[1] for pair in self.data)
  389.  
  390.     def __getitem__(self, key):
  391.         for _, item in self.data:
  392.             if item == key:
  393.                 return item
  394.  
  395.     def __delitem__(self, key):
  396.         for i, (value, item) in enumerate(self.data):
  397.             if item == key:
  398.                 self.data.pop(i)
  399.  
  400.  
  401. """
  402. Uninformed graph search
  403. The main difference is that here we do not allow loops,
  404. i.e. repetition of states
  405. """
  406.  
  407.  
  408. def graph_search(problem, fringe):
  409.     """Search through the successors of a problem to find a goal.
  410.      If two paths reach a state, only use the best one.
  411.  
  412.    :param problem: given problem
  413.    :param fringe: empty queue
  414.    :return: Node
  415.    """
  416.     closed = {}
  417.     fringe.append(Node(problem.initial))
  418.     while fringe:
  419.         node = fringe.pop()
  420.         if problem.goal_test(node.state):
  421.             return node
  422.         if node.state not in closed:
  423.             closed[node.state] = True
  424.             fringe.extend(node.expand(problem))
  425.     return None
  426.  
  427.  
  428. def breadth_first_graph_search(problem) -> Node:
  429.     """Search the shallowest nodes in the search tree first.
  430.  
  431.    :param problem: given problem
  432.    :return: Node
  433.    """
  434.     return graph_search(problem, FIFOQueue())
  435.  
  436.  
  437. if __name__ == '__main__':
  438.     green_apples = int(input())
  439.     green = []
  440.     for i in range(green_apples):
  441.         green.append(tuple(map(int, input().split(','))))
  442.    
  443.     red_apples = int(input())
  444.     red = []
  445.     for i in range(red_apples):
  446.         red.append(tuple(map(int, input().split(','))))
  447.    
  448.     snake = ((0, 9), (0, 8), (0, 7))
  449.     initial_state = (tuple(red), tuple(green), snake)
  450.     state = Problem(initial_state)
  451.  
  452.     sol = breadth_first_graph_search(state)
  453.     print(sol.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement