• API
• FAQ
• Tools
• Archive
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.
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:
59.             fringe.extend(node.expand(problem))
60.     return None
61.
62.
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)
410.         return self.data.pop()
411.
412.     def __len__(self):
413.         return len(self.data)
414.
415.     def __contains__(self, item):
416.         return any(item == pair 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))