• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # AI lab2 prob2 mrbearp  Apr 18th, 2019 (edited) 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import bisect
2.
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)
306.         return self.data.pop()
307.
308.     def __len__(self):
309.         return len(self.data)
310.
311.     def __contains__(self, item):
312.         return any(item == pair 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. import sys
324.
325.
326.
327. """
328. Uninformed tree search.
329. Within the tree we do not solve the loops.
330. """
331.
332.
333. def tree_search(problem, fringe):
334.     """Search through the successors of a problem to find a goal.
335.
336.    :param problem: given problem
337.    :param fringe:  empty queue
338.    :return: Node
339.    """
340.     fringe.append(Node(problem.initial))
341.     while fringe:
342.         node = fringe.pop()
343.         print(node.state)
344.         if problem.goal_test(node.state):
345.             return node
346.         fringe.extend(node.expand(problem))
347.     return None
348.
349.
350. def breadth_first_tree_search(problem):
351.     """Search the shallowest nodes in the search tree first.
352.
353.    :param problem: given problem
354.    :return: Node
355.    """
356.     return tree_search(problem, FIFOQueue())
357.
358.
359. def depth_first_tree_search(problem):
360.     """Search the deepest nodes in the search tree first.
361.
362.    :param problem: given problem
363.    :return: Node
364.    """
365.     return tree_search(problem, Stack())
366.
367.
368. """
369. Uninformed graph search
370. The main difference is that here we do not allow loops,
371. i.e. repetition of states
372. """
373.
374.
375. def graph_search(problem, fringe):
376.     """Search through the successors of a problem to find a goal.
377.     If two paths reach a state, only use the best one.
378.
379.    :param problem: given problem
380.    :param fringe: empty queue
381.    :return: Node
382.    """
383.     closed = set()
384.     fringe.append(Node(problem.initial))
385.     while fringe:
386.         node = fringe.pop()
387.         if problem.goal_test(node.state):
388.             return node
389.         if node.state not in closed:
390.             closed.add(node.state)
391.             fringe.extend(node.expand(problem))
392.     return None
393.
394.
395. def breadth_first_graph_search(problem):
396.     """Search the shallowest nodes in the search tree first.
397.
398.    :param problem: given problem
399.    :return: Node
400.    """
401.     return graph_search(problem, FIFOQueue())
402.
403.
404. def depth_first_graph_search(problem):
405.     """Search the deepest nodes in the search tree first.
406.
407.    :param problem: given problem
408.    :return: Node
409.    """
410.     return graph_search(problem, Stack())
411.
412.
413. def depth_limited_search(problem, limit=50):
414.     def recursive_dls(node, problem, limit):
415.         """Helper function for depth limited"""
416.         cutoff_occurred = False
417.         if problem.goal_test(node.state):
418.             return node
419.         elif node.depth == limit:
420.             return 'cutoff'
421.         else:
422.             for successor in node.expand(problem):
423.                 result = recursive_dls(successor, problem, limit)
424.                 if result == 'cutoff':
425.                     cutoff_occurred = True
426.                 elif result is not None:
427.                     return result
428.         if cutoff_occurred:
429.             return 'cutoff'
430.         return None
431.
432.     return recursive_dls(Node(problem.initial), problem, limit)
433.
434. from enum import Enum
435.
436.
437. class BlackWhiteProblem(Problem):
438.
439.     def __init__(self, initial, goal):
440.         super().__init__(initial, goal)
441.         self.initial = initial
442.         self.goal = goal
443.
444.     def goal_test(self, state):
445.         g = self.goal
446.         return g == state
447.
448.     def successor(self, state):
449.         successors = dict()
450.
451.         for i in range(0, state.__len__()):
452.             successors["x: " + str(i // 3) + ", y: " + str(i % 3)] = get_new_state(i, state)
453.
454.         return successors
455.
456.     def actions(self, state):
457.         return self.successor(state).keys()
458.
459.     def result(self, state, action):
460.         possible = self.successor(state)
461.         return possible[action]
462.
463.     def value(self):
464.         pass
465.
466.
467. def invert(num):
468.     if num == 1:
469.         num = 0
470.     else:
471.         num = 1
472.     return num
473.
474.
475. def get_new_state(pos, state):
476.     state_list = list(state)
477.
478.     state_list[pos] = invert(state_list[pos])
479.     size = n * n
480.
481.     if (pos + n) < size:
482.         state_list[pos + n] = invert(state_list[pos + n])
483.     if (pos - n) >= 0:
484.         state_list[pos - n] = invert(state_list[pos - n])
485.     if (pos + 1) < size and (pos % 3) != n - 1:
486.         state_list[pos + 1] = invert(state_list[pos + 1])
487.     if (pos - 1) >= 0 and (pos % 3) != 0:
488.         state_list[pos - 1] = invert(state_list[pos - 1])
489.
490.     return tuple(state_list)
491.
492.
493. if __name__ == '__main__':
494.     n = int(input())
495.     fields = list(map(int, input().split(',')))
496.     # solve the problem after this comment line
497.
498.     goal_state = []
499.     for i in range(0, n * n):
500.         goal_state.append(1)
501.     goal_state = tuple(goal_state)
502.
503.     initial_state = tuple(fields)
504.
505.     solution_space = BlackWhiteProblem(initial_state, goal_state)
506.     answer = breadth_first_graph_search(solution_space)
507.     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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top