SHARE
TWEET

[AI] Lab 2 - Black and White

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