Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import bisect
- import sys
- import math
- import random
- from sys import maxsize as infinity
- """
- Defining a class for the problem structure that we will solve with a search.
- The Problem class is an abstract class from which we make inheritance to define the basic
- characteristics of every problem we want to solve
- """
- class Problem:
- def __init__(self, initial, goal=None):
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- """Given a state, return a dictionary of {action : state} pairs reachable
- from this state. If there are many successors, consider an iterator
- that yields the successors one at a time, rather than building them
- all at once.
- :param state: given state
- :return: dictionary of {action : state} pairs reachable
- from this state
- :rtype: dict
- """
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible
- from that state
- :param state: given state
- :return: list of actions
- :rtype: list
- """
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the resulting state
- :param state: given state
- :param action: given action
- :return: resulting state
- """
- raise NotImplementedError
- def goal_test(self, state):
- """Return True if the state is a goal. The default method compares
- the state to self.goal, as specified in the constructor. Implement
- this method if checking against a single self.goal is not enough.
- :param state: given state
- :return: is the given state a goal state
- :rtype: bool
- """
- return state == self.goal
- def path_cost(self, c, state1, action, state2):
- """Return the cost of a solution path that arrives at state2 from state1
- via action, assuming cost c to get up to state1. If the problem is such
- that the path doesn't matter, this function will only look at state2.
- If the path does matter, it will consider c and maybe state1 and action.
- The default method costs 1 for every step in the path.
- :param c: cost of the path to get up to state1
- :param state1: given current state
- :param action: action that needs to be done
- :param state2: state to arrive to
- :return: cost of the path after executing the action
- :rtype: float
- """
- return c + 1
- def value(self):
- """For optimization problems, each state has a value.
- Hill-climbing and related algorithms try to maximize this value.
- :return: state value
- :rtype: float
- """
- raise NotImplementedError
- """
- Definition of the class for node structure of the search.
- The class Node is not inherited
- """
- class Node:
- def __init__(self, state, parent=None, action=None, path_cost=0):
- """Create node from the search tree, obtained from the parent by
- taking the action
- :param state: current state
- :param parent: parent state
- :param action: action
- :param path_cost: path cost
- """
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0 # search depth
- if parent:
- self.depth = parent.depth + 1
- def __repr__(self):
- return "<Node %s>" % (self.state,)
- def __lt__(self, node):
- return self.state < node.state
- def expand(self, problem):
- """List the nodes reachable in one step from this node.
- :param problem: given problem
- :return: list of available nodes in one step
- :rtype: list(Node)
- """
- return [self.child_node(problem, action)
- for action in problem.actions(self.state)]
- def child_node(self, problem, action):
- """Return a child node from this node
- :param problem: given problem
- :param action: given action
- :return: available node according to the given action
- :rtype: Node
- """
- next_state = problem.result(self.state, action)
- return Node(next_state, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next_state))
- def solution(self):
- """Return the sequence of actions to go from the root to this node.
- :return: sequence of actions
- :rtype: list
- """
- return [node.action for node in self.path()[1:]]
- def solve(self):
- """Return the sequence of states to go from the root to this node.
- :return: list of states
- :rtype: list
- """
- return [node.state for node in self.path()[0:]]
- def path(self):
- """Return a list of nodes forming the path from the root to this node.
- :return: list of states from the path
- :rtype: list(Node)
- """
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- result.reverse()
- return result
- """We want the queue of nodes at breadth_first_search or
- astar_search to not contain states-duplicates, so the nodes that
- contain the same condition we treat as the same. [Problem: this can
- not be desirable in other situations.]"""
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- """
- Definitions of helper structures for storing the list of generated, but not checked nodes
- """
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): Last In First Out Queue (stack).
- FIFOQueue(): First In First Out Queue.
- PriorityQueue(order, f): QQueue in sorted order (default min-first).
- """
- def __init__(self):
- raise NotImplementedError
- def append(self, item):
- """Adds the item into the queue
- :param item: given element
- :return: None
- """
- raise NotImplementedError
- def extend(self, items):
- """Adds the items into the queue
- :param items: given elements
- :return: None
- """
- raise NotImplementedError
- def pop(self):
- """Returns the first element of the queue
- :return: first element
- """
- raise NotImplementedError
- def __len__(self):
- """Returns the number of elements in the queue
- :return: number of elements in the queue
- :rtype: int
- """
- raise NotImplementedError
- def __contains__(self, item):
- """Check if the queue contains the element item
- :param item: given element
- :return: whether the queue contains the item
- :rtype: bool
- """
- raise NotImplementedError
- class Stack(Queue):
- """Last-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop()
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class FIFOQueue(Queue):
- """First-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop(0)
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element is returned first
- (as determined by f and order). This structure is used in
- informed search"""
- def __init__(self, order=min, f=lambda x: x):
- """
- :param order: sorting function, if order is min, returns the element
- with minimal f (x); if the order is max, then returns the
- element with maximum f (x).
- :param f: function f(x)
- """
- assert order in [min, max]
- self.data = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort_right(self.data, (self.f(item), item))
- def extend(self, items):
- for item in items:
- bisect.insort_right(self.data, (self.f(item), item))
- def pop(self):
- if self.order == min:
- return self.data.pop(0)[1]
- return self.data.pop()[1]
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.data)
- def __getitem__(self, key):
- for _, item in self.data:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.data):
- if item == key:
- self.data.pop(i)
- """
- Defining a class for the problem structure that we will solve with a search.
- The Problem class is an abstract class from which we make inheritance to define the basic
- characteristics of every problem we want to solve
- """
- class Problem:
- def __init__(self, initial, goal=None):
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- """Given a state, return a dictionary of {action : state} pairs reachable
- from this state. If there are many successors, consider an iterator
- that yields the successors one at a time, rather than building them
- all at once.
- :param state: given state
- :return: dictionary of {action : state} pairs reachable
- from this state
- :rtype: dict
- """
- raise NotImplementedError
- def actions(self, state):
- """Given a state, return a list of all actions possible
- from that state
- :param state: given state
- :return: list of actions
- :rtype: list
- """
- raise NotImplementedError
- def result(self, state, action):
- """Given a state and action, return the resulting state
- :param state: given state
- :param action: given action
- :return: resulting state
- """
- raise NotImplementedError
- def goal_test(self, state):
- """Return True if the state is a goal. The default method compares
- the state to self.goal, as specified in the constructor. Implement
- this method if checking against a single self.goal is not enough.
- :param state: given state
- :return: is the given state a goal state
- :rtype: bool
- """
- return state == self.goal
- def path_cost(self, c, state1, action, state2):
- """Return the cost of a solution path that arrives at state2 from state1
- via action, assuming cost c to get up to state1. If the problem is such
- that the path doesn't matter, this function will only look at state2.
- If the path does matter, it will consider c and maybe state1 and action.
- The default method costs 1 for every step in the path.
- :param c: cost of the path to get up to state1
- :param state1: given current state
- :param action: action that needs to be done
- :param state2: state to arrive to
- :return: cost of the path after executing the action
- :rtype: float
- """
- return c + 1
- def value(self):
- """For optimization problems, each state has a value.
- Hill-climbing and related algorithms try to maximize this value.
- :return: state value
- :rtype: float
- """
- raise NotImplementedError
- """
- Definition of the class for node structure of the search.
- The class Node is not inherited
- """
- class Node:
- def __init__(self, state, parent=None, action=None, path_cost=0):
- """Create node from the search tree, obtained from the parent by
- taking the action
- :param state: current state
- :param parent: parent state
- :param action: action
- :param path_cost: path cost
- """
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0 # search depth
- if parent:
- self.depth = parent.depth + 1
- def __repr__(self):
- return "<Node %s>" % (self.state,)
- def __lt__(self, node):
- return self.state < node.state
- def expand(self, problem):
- """List the nodes reachable in one step from this node.
- :param problem: given problem
- :return: list of available nodes in one step
- :rtype: list(Node)
- """
- return [self.child_node(problem, action)
- for action in problem.actions(self.state)]
- def child_node(self, problem, action):
- """Return a child node from this node
- :param problem: given problem
- :param action: given action
- :return: available node according to the given action
- :rtype: Node
- """
- next_state = problem.result(self.state, action)
- return Node(next_state, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next_state))
- def solution(self):
- """Return the sequence of actions to go from the root to this node.
- :return: sequence of actions
- :rtype: list
- """
- return [node.action for node in self.path()[1:]]
- def solve(self):
- """Return the sequence of states to go from the root to this node.
- :return: list of states
- :rtype: list
- """
- return [node.state for node in self.path()[0:]]
- def path(self):
- """Return a list of nodes forming the path from the root to this node.
- :return: list of states from the path
- :rtype: list(Node)
- """
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- result.reverse()
- return result
- """We want the queue of nodes at breadth_first_search or
- astar_search to not contain states-duplicates, so the nodes that
- contain the same condition we treat as the same. [Problem: this can
- not be desirable in other situations.]"""
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- """
- Definitions of helper structures for storing the list of generated, but not checked nodes
- """
- class Queue:
- """Queue is an abstract class/interface. There are three types:
- Stack(): Last In First Out Queue (stack).
- FIFOQueue(): First In First Out Queue.
- PriorityQueue(order, f): Queue in sorted order (default min-first).
- """
- def __init__(self):
- raise NotImplementedError
- def append(self, item):
- """Adds the item into the queue
- :param item: given element
- :return: None
- """
- raise NotImplementedError
- def extend(self, items):
- """Adds the items into the queue
- :param items: given elements
- :return: None
- """
- raise NotImplementedError
- def pop(self):
- """Returns the first element of the queue
- :return: first element
- """
- raise NotImplementedError
- def __len__(self):
- """Returns the number of elements in the queue
- :return: number of elements in the queue
- :rtype: int
- """
- raise NotImplementedError
- def __contains__(self, item):
- """Check if the queue contains the element item
- :param item: given element
- :return: whether the queue contains the item
- :rtype: bool
- """
- raise NotImplementedError
- class Stack(Queue):
- """Last-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop()
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class FIFOQueue(Queue):
- """First-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop(0)
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class PriorityQueue(Queue):
- """A queue in which the minimum (or maximum) element is returned first
- (as determined by f and order). This structure is used in
- informed search"""
- def __init__(self, order=min, f=lambda x: x):
- """
- :param order: sorting function, if order is min, returns the element
- with minimal f (x); if the order is max, then returns the
- element with maximum f (x).
- :param f: function f(x)
- """
- assert order in [min, max]
- self.data = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort_right(self.data, (self.f(item), item))
- def extend(self, items):
- for item in items:
- bisect.insort_right(self.data, (self.f(item), item))
- def pop(self):
- if self.order == min:
- return self.data.pop(0)[1]
- return self.data.pop()[1]
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.data)
- def __getitem__(self, key):
- for _, item in self.data:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.data):
- if item == key:
- self.data.pop(i)
- """
- Uninformed tree search.
- Within the tree we do not solve the loops.
- """
- def tree_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- :param problem: given problem
- :param fringe: empty queue
- :return: Node
- """
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- print(node.state)
- if problem.goal_test(node.state):
- return node
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_tree_search(problem):
- """Search the shallowest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return tree_search(problem, FIFOQueue())
- def depth_first_tree_search(problem):
- """Search the deepest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return tree_search(problem, Stack())
- """
- Uninformed graph search
- The main difference is that here we do not allow loops,
- i.e. repetition of states
- """
- def graph_search(problem, fringe):
- """Search through the successors of a problem to find a goal.
- If two paths reach a state, only use the best one.
- :param problem: given problem
- :param fringe: empty queue
- :return: Node
- """
- closed = set()
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- if problem.goal_test(node.state):
- return node
- if node.state not in closed:
- closed.add(node.state)
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_graph_search(problem):
- """Search the shallowest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return graph_search(problem, FIFOQueue())
- def depth_first_graph_search(problem):
- """Search the deepest nodes in the search tree first.
- :param problem: given problem
- :return: Node
- """
- return graph_search(problem, Stack())
- def depth_limited_search(problem, limit=50):
- def recursive_dls(node, problem, limit):
- """Helper function for depth limited"""
- cutoff_occurred = False
- if problem.goal_test(node.state):
- return node
- elif node.depth == limit:
- return 'cutoff'
- else:
- for successor in node.expand(problem):
- result = recursive_dls(successor, problem, limit)
- if result == 'cutoff':
- cutoff_occurred = True
- elif result is not None:
- return result
- if cutoff_occurred:
- return 'cutoff'
- return None
- return recursive_dls(Node(problem.initial), problem, limit)
- def iterative_deepening_search(problem):
- for depth in range(sys.maxsize):
- result = depth_limited_search(problem, depth)
- if result is not 'cutoff':
- return result
- def uniform_cost_search(problem):
- """Search the nodes in the search tree with lowest cost first."""
- return graph_search(problem, PriorityQueue(min, lambda a: a.path_cost))
- """
- Informed graph search.
- """
- def memoize(fn, slot=None):
- """ Store the calculated value for any arguments list. If a
- slot is specified, store the result in that slot in the first
- argument. If slot is false, store the results in a dictionary.
- :param fn: given function
- :param slot: name of the attribute for saving the function results
- :return: modified function for storing the results
- """
- if slot:
- def memoized_fn(obj, *args):
- if hasattr(obj, slot):
- return getattr(obj, slot)
- else:
- val = fn(obj, *args)
- setattr(obj, slot, val)
- return val
- else:
- def memoized_fn(*args):
- if args not in memoized_fn.cache:
- memoized_fn.cache[args] = fn(*args)
- return memoized_fn.cache[args]
- memoized_fn.cache = {}
- return memoized_fn
- def best_first_graph_search(problem, f):
- """The idea of Best First Search is to use an evaluation function
- to decide which adjacent is most promising and then explore.
- :param problem: given problem
- :param f: given heuristic function
- :return: Node or None
- """
- f = memoize(f, 'f')
- node = Node(problem.initial)
- if problem.goal_test(node.state):
- return node
- frontier = PriorityQueue(min, f)
- frontier.append(node)
- explored = set()
- while frontier:
- node = frontier.pop()
- if problem.goal_test(node.state):
- return node
- explored.add(node.state)
- for child in node.expand(problem):
- if child.state not in explored and child not in frontier:
- frontier.append(child)
- elif child in frontier:
- incumbent = frontier[child]
- if f(child) < f(incumbent):
- del frontier[incumbent]
- frontier.append(child)
- return None
- def greedy_best_first_graph_search(problem, h=None):
- """ Greedy best-first search is implemented with f(n) = h(n).
- :param problem: given problem
- :param h: given heuristic function
- :return: Node or None
- """
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, h)
- def astar_search(problem, h=None):
- """ A* search is best-first graph search where f(n) = g(n) + h(n).
- :param problem: given problem
- :param h: given heuristic function
- :return: Node or None
- """
- h = memoize(h or problem.h, 'h')
- return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
- # ===========
- class GraphExplorer(Problem):
- def __init__(self, initial, goal=None):
- super().__init__(initial, goal)
- def successor(self, state):
- succesors = dict()
- player_position = state[0]
- star1 = state[1]
- star2 = state[2]
- edges = state[3]
- #Levo
- new_maze = self.moveFigure("Levo", state);
- if new_maze != None: succesors['Levo'] = new_maze
- #Desno
- new_maze = self.moveFigure("Desno", state);
- if new_maze != None: succesors['Desno'] = new_maze
- #Gore
- new_maze = self.moveFigure("Gore", state);
- if new_maze != None: succesors['Gore'] = new_maze
- #Dolu
- new_maze = self.moveFigure("Dolu", state);
- if new_maze != None: succesors['Dolu'] = new_maze
- #DoluDesno
- new_maze = self.moveFigure("DoluDesno", state);
- if new_maze != None: succesors['DoluDesno'] = new_maze
- #GoreLevo
- new_maze = self.moveFigure("GoreLevo", state);
- if new_maze != None: succesors['GoreLevo'] = new_maze
- return succesors
- def goal_test(self, state):
- star1 = state[1]
- star2 = state[2]
- return star1 == -1 and star2 == -1
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- return self.successor(state)[action]
- def moveFigure(self, direction, state):
- availableMovements = movements[state[0]]
- oldPosition, newPosition = state[0], None
- new_maze = None
- star1, star2 = state[1], state[2]
- edgeList = list(state[3])
- for movement in availableMovements:
- if movement[1] != direction: continue
- else:
- edge = oldPosition, movement[0]
- reverseEdge = movement[0], oldPosition
- if edge not in edgeList and reverseEdge not in edgeList: return None
- if edge in edgeList:
- edgeList.remove(edge)
- if reverseEdge in edgeList:
- edgeList.remove(reverseEdge)
- newPosition = movement[0]
- if newPosition == star1:
- star1 = -1
- if newPosition == star2:
- star2 = -1
- new_maze = (newPosition, star1, star2, tuple(edgeList))
- return new_maze
- movements = {
- 1: ((2, "Desno"), (5, "Dolu")), 2: ((1, "Levo"), (6, "Dolu")), 3: ((4, "Desno"), (7, "Dolu")),
- 4: ((3, "Levo"), (8, "Dolu")), 5: ((1, "Gore"), (6, "Desno")),
- 6: ((2, "Gore"), (5, "Levo"), (7, "Desno"), (10, "Dolu"), (11, "DoluDesno")),
- 7: ((3, "Gore"), (6, "Levo"), (8, "Desno"), (11, "Dolu")), 8: ((4, "Gore"), (7, "Levo")),
- 9: ((10, "Desno"), (13, "Dolu")), 10: ((6, "Gore"), (9, "Levo"), (11, "Desno"), (14, "Dolu")),
- 11: ((7, "Gore"), (10, "Levo"), (12, "Desno"), (15, "Dolu"), (6, "GoreLevo")),
- 12: ((11, "Levo"), (16, "Dolu")), 13: ((14, "Desno"), (9, "Gore")), 14: ((13, "Levo"), (10, "Gore")),
- 15: ((16, "Desno"), (11, "Gore")), 16: ((15, "Levo"), (12, "Gore"))
- }
- if __name__ == '__main__':
- player_position = int(input())
- s1_position = int(input())
- s2_position = int(input())
- edges = (
- (1,2), (3,4), (5,6), (6,7), (7,8), (9,10), (10,11), (11,12), (13,14), (15,16),
- (1,5), (9,13), (2,6), (6,10), (10,14), (3,7), (7,11), (11,15), (4,8), (12,16), (6,11)
- )
- problem = GraphExplorer((player_position, s1_position, s2_position, edges))
- solution = breadth_first_graph_search(problem)
- print(solution.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement