evitanasevska

[AI] Explorer

Sep 20th, 2020
698
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import sys
  2. import math
  3. import random
  4. import bisect
  5. from sys import maxsize as infinity
  6.  
  7. """
  8. Defining a class for the problem structure that we will solve with a search.
  9. The Problem class is an abstract class from which we make inheritance to define the basic
  10. characteristics of every problem we want to solve
  11. """
  12.  
  13.  
  14. class Problem:
  15.     def __init__(self, initial, goal=None):
  16.         self.initial = initial
  17.         self.goal = goal
  18.  
  19.     def successor(self, state):
  20.         """Given a state, return a dictionary of {action : state} pairs reachable
  21.        from this state. If there are many successors, consider an iterator
  22.        that yields the successors one at a time, rather than building them
  23.        all at once.
  24.  
  25.        :param state: given state
  26.        :return:  dictionary of {action : state} pairs reachable
  27.                  from this state
  28.        :rtype: dict
  29.        """
  30.         raise NotImplementedError
  31.  
  32.     def actions(self, state):
  33.         """Given a state, return a list of all actions possible
  34.        from that state
  35.  
  36.        :param state: given state
  37.        :return: list of actions
  38.        :rtype: list
  39.        """
  40.         raise NotImplementedError
  41.  
  42.     def result(self, state, action):
  43.         """Given a state and action, return the resulting state
  44.  
  45.        :param state: given state
  46.        :param action: given action
  47.        :return: resulting state
  48.        """
  49.         raise NotImplementedError
  50.  
  51.     def goal_test(self, state):
  52.         """Return True if the state is a goal. The default method compares
  53.        the state to self.goal, as specified in the constructor. Implement
  54.        this method if checking against a single self.goal is not enough.
  55.  
  56.        :param state: given state
  57.        :return: is the given state a goal state
  58.        :rtype: bool
  59.        """
  60.         return state == self.goal
  61.  
  62.     def path_cost(self, c, state1, action, state2):
  63.         """Return the cost of a solution path that arrives at state2 from state1
  64.        via action, assuming cost c to get up to state1. If the problem is such
  65.        that the path doesn't matter, this function will only look at state2.
  66.        If the path does matter, it will consider c and maybe state1 and action.
  67.        The default method costs 1 for every step in the path.
  68.  
  69.        :param c: cost of the path to get up to state1
  70.        :param state1: given current state
  71.        :param action: action that needs to be done
  72.        :param state2: state to arrive to
  73.        :return: cost of the path after executing the action
  74.        :rtype: float
  75.        """
  76.         return c + 1
  77.  
  78.     def value(self):
  79.         """For optimization problems, each state has a value.
  80.        Hill-climbing and related algorithms try to maximize this value.
  81.  
  82.        :return: state value
  83.        :rtype: float
  84.        """
  85.         raise NotImplementedError
  86.  
  87.  
  88. """
  89. Definition of the class for node structure of the search.
  90. The class Node is not inherited
  91. """
  92.  
  93.  
  94. class Node:
  95.     def __init__(self, state, parent=None, action=None, path_cost=0):
  96.         """Create node from the search tree,  obtained from the parent by
  97.        taking the action
  98.  
  99.        :param state: current state
  100.        :param parent: parent state
  101.        :param action: action
  102.        :param path_cost: path cost
  103.        """
  104.         self.state = state
  105.         self.parent = parent
  106.         self.action = action
  107.         self.path_cost = path_cost
  108.         self.depth = 0  # search depth
  109.         if parent:
  110.             self.depth = parent.depth + 1
  111.  
  112.     def __repr__(self):
  113.         return "<Node %s>" % (self.state,)
  114.  
  115.     def __lt__(self, node):
  116.         return self.state < node.state
  117.  
  118.     def expand(self, problem):
  119.         """List the nodes reachable in one step from this node.
  120.  
  121.        :param problem: given problem
  122.        :return: list of available nodes in one step
  123.        :rtype: list(Node)
  124.        """
  125.         return [self.child_node(problem, action)
  126.                 for action in problem.actions(self.state)]
  127.  
  128.     def child_node(self, problem, action):
  129.         """Return a child node from this node
  130.  
  131.        :param problem: given problem
  132.        :param action: given action
  133.        :return: available node  according to the given action
  134.        :rtype: Node
  135.        """
  136.         next_state = problem.result(self.state, action)
  137.         return Node(next_state, self, action,
  138.                     problem.path_cost(self.path_cost, self.state,
  139.                                       action, next_state))
  140.  
  141.     def solution(self):
  142.         """Return the sequence of actions to go from the root to this node.
  143.  
  144.        :return: sequence of actions
  145.        :rtype: list
  146.        """
  147.         return [node.action for node in self.path()[1:]]
  148.  
  149.     def solve(self):
  150.         """Return the sequence of states to go from the root to this node.
  151.  
  152.        :return: list of states
  153.        :rtype: list
  154.        """
  155.         return [node.state for node in self.path()[0:]]
  156.  
  157.     def path(self):
  158.         """Return a list of nodes forming the path from the root to this node.
  159.  
  160.        :return: list of states from the path
  161.        :rtype: list(Node)
  162.        """
  163.         x, result = self, []
  164.         while x:
  165.             result.append(x)
  166.             x = x.parent
  167.         result.reverse()
  168.         return result
  169.  
  170.     """We want the queue of nodes at breadth_first_search or
  171.    astar_search to not contain states-duplicates, so the nodes that
  172.    contain the same condition we treat as the same. [Problem: this can
  173.    not be desirable in other situations.]"""
  174.  
  175.     def __eq__(self, other):
  176.         return isinstance(other, Node) and self.state == other.state
  177.  
  178.     def __hash__(self):
  179.         return hash(self.state)
  180.  
  181.  
  182. """
  183. Definitions of helper structures for storing the list of generated, but not checked nodes
  184. """
  185.  
  186.  
  187. class Queue:
  188.     """Queue is an abstract class/interface. There are three types:
  189.        Stack(): Last In First Out Queue (stack).
  190.        FIFOQueue(): First In First Out Queue.
  191.        PriorityQueue(order, f): Queue in sorted order (default min-first).
  192.    """
  193.  
  194.     def __init__(self):
  195.         raise NotImplementedError
  196.  
  197.     def append(self, item):
  198.         """Adds the item into the queue
  199.  
  200.        :param item: given element
  201.        :return: None
  202.        """
  203.         raise NotImplementedError
  204.  
  205.     def extend(self, items):
  206.         """Adds the items into the queue
  207.  
  208.        :param items: given elements
  209.        :return: None
  210.        """
  211.         raise NotImplementedError
  212.  
  213.     def pop(self):
  214.         """Returns the first element of the queue
  215.  
  216.        :return: first element
  217.        """
  218.         raise NotImplementedError
  219.  
  220.     def __len__(self):
  221.         """Returns the number of elements in the queue
  222.  
  223.        :return: number of elements in the queue
  224.        :rtype: int
  225.        """
  226.         raise NotImplementedError
  227.  
  228.     def __contains__(self, item):
  229.         """Check if the queue contains the element item
  230.  
  231.        :param item: given element
  232.        :return: whether the queue contains the item
  233.        :rtype: bool
  234.        """
  235.         raise NotImplementedError
  236.  
  237.  
  238. class Stack(Queue):
  239.     """Last-In-First-Out Queue."""
  240.  
  241.     def __init__(self):
  242.         self.data = []
  243.  
  244.     def append(self, item):
  245.         self.data.append(item)
  246.  
  247.     def extend(self, items):
  248.         self.data.extend(items)
  249.  
  250.     def pop(self):
  251.         return self.data.pop()
  252.  
  253.     def __len__(self):
  254.         return len(self.data)
  255.  
  256.     def __contains__(self, item):
  257.         return item in self.data
  258.  
  259.  
  260. class FIFOQueue(Queue):
  261.     """First-In-First-Out Queue."""
  262.  
  263.     def __init__(self):
  264.         self.data = []
  265.  
  266.     def append(self, item):
  267.         self.data.append(item)
  268.  
  269.     def extend(self, items):
  270.         self.data.extend(items)
  271.  
  272.     def pop(self):
  273.         return self.data.pop(0)
  274.  
  275.     def __len__(self):
  276.         return len(self.data)
  277.  
  278.     def __contains__(self, item):
  279.         return item in self.data
  280.  
  281.  
  282. class PriorityQueue(Queue):
  283.     """A queue in which the minimum (or maximum) element is returned first
  284.     (as determined by f and order). This structure is used in
  285.     informed search"""
  286.  
  287.     def __init__(self, order=min, f=lambda x: x):
  288.         """
  289.        :param order: sorting function, if order is min, returns the element
  290.                      with minimal f (x); if the order is max, then returns the
  291.                      element with maximum f (x).
  292.        :param f: function f(x)
  293.        """
  294.         assert order in [min, max]
  295.         self.data = []
  296.         self.order = order
  297.         self.f = f
  298.  
  299.     def append(self, item):
  300.         bisect.insort_right(self.data, (self.f(item), item))
  301.  
  302.     def extend(self, items):
  303.         for item in items:
  304.             bisect.insort_right(self.data, (self.f(item), item))
  305.  
  306.     def pop(self):
  307.         if self.order == min:
  308.             return self.data.pop(0)[1]
  309.         return self.data.pop()[1]
  310.  
  311.     def __len__(self):
  312.         return len(self.data)
  313.  
  314.     def __contains__(self, item):
  315.         return any(item == pair[1] for pair in self.data)
  316.  
  317.     def __getitem__(self, key):
  318.         for _, item in self.data:
  319.             if item == key:
  320.                 return item
  321.  
  322.     def __delitem__(self, key):
  323.         for i, (value, item) in enumerate(self.data):
  324.             if item == key:
  325.                 self.data.pop(i)
  326.  
  327.  
  328. """
  329. Uninformed tree search.
  330. Within the tree we do not solve the loops.
  331. """
  332.  
  333.  
  334. def tree_search(problem, fringe):
  335.     """Search through the successors of a problem to find a goal.
  336.  
  337.    :param problem: given problem
  338.    :param fringe:  empty queue
  339.    :return: Node
  340.    """
  341.     fringe.append(Node(problem.initial))
  342.     while fringe:
  343.         node = fringe.pop()
  344.         print(node.state)
  345.         if problem.goal_test(node.state):
  346.             return node
  347.         fringe.extend(node.expand(problem))
  348.     return None
  349.  
  350.  
  351. def breadth_first_tree_search(problem):
  352.     """Search the shallowest nodes in the search tree first.
  353.  
  354.    :param problem: given problem
  355.    :return: Node
  356.    """
  357.     return tree_search(problem, FIFOQueue())
  358.  
  359.  
  360. def depth_first_tree_search(problem):
  361.     """Search the deepest nodes in the search tree first.
  362.  
  363.    :param problem: given problem
  364.    :return: Node
  365.    """
  366.     return tree_search(problem, Stack())
  367.  
  368.  
  369. """
  370. Uninformed graph search
  371. The main difference is that here we do not allow loops,
  372. i.e. repetition of states
  373. """
  374.  
  375.  
  376. def graph_search(problem, fringe):
  377.     """Search through the successors of a problem to find a goal.
  378.     If two paths reach a state, only use the best one.
  379.  
  380.    :param problem: given problem
  381.    :param fringe: empty queue
  382.    :return: Node
  383.    """
  384.     closed = set()
  385.     fringe.append(Node(problem.initial))
  386.     while fringe:
  387.         node = fringe.pop()
  388.         if problem.goal_test(node.state):
  389.             return node
  390.         if node.state not in closed:
  391.             closed.add(node.state)
  392.             fringe.extend(node.expand(problem))
  393.     return None
  394.  
  395.  
  396. def breadth_first_graph_search(problem):
  397.     """Search the shallowest nodes in the search tree first.
  398.  
  399.    :param problem: given problem
  400.    :return: Node
  401.    """
  402.     return graph_search(problem, FIFOQueue())
  403.  
  404.  
  405. def depth_first_graph_search(problem):
  406.     """Search the deepest nodes in the search tree first.
  407.  
  408.    :param problem: given problem
  409.    :return: Node
  410.    """
  411.     return graph_search(problem, Stack())
  412.  
  413.  
  414. def depth_limited_search(problem, limit=50):
  415.     def recursive_dls(node, problem, limit):
  416.         """Helper function for depth limited"""
  417.         cutoff_occurred = False
  418.         if problem.goal_test(node.state):
  419.             return node
  420.         elif node.depth == limit:
  421.             return 'cutoff'
  422.         else:
  423.             for successor in node.expand(problem):
  424.                 result = recursive_dls(successor, problem, limit)
  425.                 if result == 'cutoff':
  426.                     cutoff_occurred = True
  427.                 elif result is not None:
  428.                     return result
  429.         if cutoff_occurred:
  430.             return 'cutoff'
  431.         return None
  432.  
  433.     return recursive_dls(Node(problem.initial), problem, limit)
  434.  
  435.  
  436. def iterative_deepening_search(problem):
  437.     for depth in range(sys.maxsize):
  438.         result = depth_limited_search(problem, depth)
  439.         if result is not 'cutoff':
  440.             return result
  441.  
  442.  
  443. def uniform_cost_search(problem):
  444.     """Search the nodes in the search tree with lowest cost first."""
  445.     return graph_search(problem, PriorityQueue(min, lambda a: a.path_cost))
  446.  
  447.  
  448. """
  449. Informed graph search.
  450. """
  451.  
  452.  
  453. def memoize(fn, slot=None):
  454.     """ Store the calculated value for any arguments list. If a
  455.    slot is specified, store the result in that slot in the first
  456.    argument. If slot is false, store the results in a dictionary.
  457.  
  458.    :param fn: given function
  459.    :param slot: name of the attribute for saving the function results
  460.    :return: modified function for storing the results
  461.    """
  462.     if slot:
  463.         def memoized_fn(obj, *args):
  464.             if hasattr(obj, slot):
  465.                 return getattr(obj, slot)
  466.             else:
  467.                 val = fn(obj, *args)
  468.                 setattr(obj, slot, val)
  469.                 return val
  470.     else:
  471.         def memoized_fn(*args):
  472.             if args not in memoized_fn.cache:
  473.                 memoized_fn.cache[args] = fn(*args)
  474.             return memoized_fn.cache[args]
  475.  
  476.         memoized_fn.cache = {}
  477.     return memoized_fn
  478.  
  479.  
  480. def best_first_graph_search(problem, f):
  481.     """The idea of Best First Search is to use an evaluation function
  482.    to decide which adjacent is most promising and then explore.
  483.  
  484.    :param problem: given problem
  485.    :param f: given heuristic function
  486.    :return: Node or None
  487.    """
  488.     f = memoize(f, 'f')
  489.     node = Node(problem.initial)
  490.     if problem.goal_test(node.state):
  491.         return node
  492.     frontier = PriorityQueue(min, f)
  493.     frontier.append(node)
  494.     explored = set()
  495.     while frontier:
  496.         node = frontier.pop()
  497.         if problem.goal_test(node.state):
  498.             return node
  499.         explored.add(node.state)
  500.         for child in node.expand(problem):
  501.             if child.state not in explored and child not in frontier:
  502.                 frontier.append(child)
  503.             elif child in frontier:
  504.                 incumbent = frontier[child]
  505.                 if f(child) < f(incumbent):
  506.                     del frontier[incumbent]
  507.                     frontier.append(child)
  508.     return None
  509.  
  510.  
  511. def greedy_best_first_graph_search(problem, h=None):
  512.     """ Greedy best-first search is implemented with f(n) = h(n).
  513.  
  514.    :param problem: given problem
  515.    :param h: given heuristic function
  516.    :return: Node or None
  517.    """
  518.     h = memoize(h or problem.h, 'h')
  519.     return best_first_graph_search(problem, h)
  520.  
  521.  
  522. def astar_search(problem, h=None):
  523.     """ A* search is best-first graph search where f(n) = g(n) + h(n).
  524.  
  525.    :param problem: given problem
  526.    :param h: given heuristic function
  527.    :return: Node or None
  528.    """
  529.     h = memoize(h or problem.h, 'h')
  530.     return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  531.  
  532.  
  533. def recursive_best_first_search(problem, h=None):
  534.     """ Recursive best first search - limits recursion by
  535.    keeping track of the f-value of the best alternative
  536.    path from any ancestor node (one step look-ahead).
  537.  
  538.    :param problem: given problem
  539.    :param h: given heuristic function
  540.    :return: Node or None
  541.    """
  542.     h = memoize(h or problem.h, 'h')
  543.  
  544.     def RBFS(problem, node, flimit):
  545.         if problem.goal_test(node.state):
  546.             return node, 0  # (the second value is not important)
  547.         successors = node.expand(problem)
  548.         if len(successors) == 0:
  549.             return None, infinity
  550.         for s in successors:
  551.             s.f = max(s.path_cost + h(s), node.f)
  552.         while True:
  553.             # Sort them according to the lowest f value
  554.             successors.sort(key=lambda x: x.f)
  555.             best = successors[0]
  556.             if best.f > flimit:
  557.                 return None, best.f
  558.             if len(successors) > 1:
  559.                 alternative = successors[1].f
  560.             else:
  561.                 alternative = infinity
  562.             result, best.f = RBFS(problem, best, min(flimit, alternative))
  563.             if result is not None:
  564.                 return result, best.f
  565.  
  566.     node = Node(problem.initial)
  567.     node.f = h(node)
  568.     result, bestf = RBFS(problem, node, infinity)
  569.     return result
  570.  
  571.  
  572. """
  573. Finite graph search.
  574. """
  575.  
  576.  
  577. def distance(a, b):
  578.     """The distance between two (x, y) points."""
  579.     return math.hypot((a[0] - b[0]), (a[1] - b[1]))
  580.  
  581.  
  582. class Graph:
  583.     """A graph connects nodes (verticies) by edges (links).  Each edge can also
  584.    have a length associated with it.  The constructor call is something like:
  585.        g = Graph({'A': {'B': 1, 'C': 2})
  586.    this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from
  587.    A to B,  and an edge of length 2 from A to C.  You can also do:
  588.        g = Graph({'A': {'B': 1, 'C': 2}, directed=False)
  589.    This makes an undirected graph, so inverse links are also added. The graph
  590.    stays undirected; if you add more links with g.connect('B', 'C', 3), then
  591.    inverse link is also added.  You can use g.nodes() to get a list of nodes,
  592.    g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the
  593.    length of the link from A to B.  'Lengths' can actually be any object at
  594.    all, and nodes can be any hashable object."""
  595.  
  596.     def __init__(self, dictionary=None, directed=True):
  597.         self.dict = dictionary or {}
  598.         self.directed = directed
  599.         if not directed:
  600.             self.make_undirected()
  601.         else:
  602.             # add empty edges dictionary for those nodes that do not
  603.             # have edges and are not included in the dictionary as keys
  604.             nodes_no_edges = list({y for x in self.dict.values()
  605.                                    for y in x if y not in self.dict})
  606.             for node in nodes_no_edges:
  607.                 self.dict[node] = {}
  608.  
  609.     def make_undirected(self):
  610.         """Make a digraph into an undirected graph by adding symmetric edges."""
  611.         for a in list(self.dict.keys()):
  612.             for (b, dist) in self.dict[a].items():
  613.                 self.connect1(b, a, dist)
  614.  
  615.     def connect(self, node_a, node_b, distance_val=1):
  616.         """Add a link from node_a and node_b of given distance_val, and also add the inverse
  617.        link if the graph is undirected."""
  618.         self.connect1(node_a, node_b, distance_val)
  619.         if not self.directed:
  620.             self.connect1(node_b, node_a, distance_val)
  621.  
  622.     def connect1(self, node_a, node_b, distance_val):
  623.         """Add a link from node_a to node_b of given distance_val, in one direction only."""
  624.         self.dict.setdefault(node_a, {})[node_b] = distance_val
  625.  
  626.     def get(self, a, b=None):
  627.         """Return a link distance or a dict of {node: distance} entries.
  628.        .get(a,b) returns the distance or None;
  629.        .get(a) returns a dict of {node: distance} entries, possibly {}."""
  630.         links = self.dict.get(a)
  631.         if b is None:
  632.             return links
  633.         else:
  634.             return links.get(b)
  635.  
  636.     def nodes(self):
  637.         """Return a list of nodes in the graph."""
  638.         return list(self.dict.keys())
  639.  
  640.  
  641. def UndirectedGraph(dictionary=None):
  642.     """Build a Graph where every edge (including future ones) goes both ways."""
  643.     return Graph(dictionary=dictionary, directed=False)
  644.  
  645.  
  646. def RandomGraph(nodes=list(range(10)), min_links=2, width=400, height=300,
  647.                 curvature=lambda: random.uniform(1.1, 1.5)):
  648.     """Construct a random graph, with the specified nodes, and random links.
  649.    The nodes are laid out randomly on a (width x height) rectangle.
  650.    Then each node is connected to the min_links nearest neighbors.
  651.    Because inverse links are added, some nodes will have more connections.
  652.    The distance between nodes is the hypotenuse times curvature(),
  653.    where curvature() defaults to a random number between 1.1 and 1.5."""
  654.     g = UndirectedGraph()
  655.     g.locations = {}
  656.     # Build the cities
  657.     for node in nodes:
  658.         g.locations[node] = (random.randrange(width), random.randrange(height))
  659.     # Build roads from each city to at least min_links nearest neighbors.
  660.     for i in range(min_links):
  661.         for node in nodes:
  662.             if len(g.get(node)) < min_links:
  663.                 here = g.locations[node]
  664.  
  665.                 def distance_to_node(n):
  666.                     if n is node or g.get(node, n):
  667.                         return math.inf
  668.                     return distance(g.locations[n], here)
  669.  
  670.                 neighbor = nodes.index(min(nodes, key=distance_to_node))
  671.                 d = distance(g.locations[neighbor], here) * curvature()
  672.                 g.connect(node, neighbor, int(d))
  673.     return g
  674.  
  675.  
  676. class GraphProblem(Problem):
  677.     """The problem of searching a graph from one node to another."""
  678.  
  679.     def __init__(self, initial, goal, graph):
  680.         super().__init__(initial, goal)
  681.         self.graph = graph
  682.  
  683.     def actions(self, state):
  684.         """The actions at a graph node are just its neighbors."""
  685.         return list(self.graph.get(state).keys())
  686.  
  687.     def result(self, state, action):
  688.         """The result of going to a neighbor is just that neighbor."""
  689.         return action
  690.  
  691.     def path_cost(self, c, state1, action, state2):
  692.         return c + (self.graph.get(state1, state2) or math.inf)
  693.  
  694.     def h(self, node):
  695.         """h function is straight-line distance from a node's state to goal."""
  696.         locs = getattr(self.graph, 'locations', None)
  697.         if locs:
  698.             return int(distance(locs[node.state], locs[self.goal]))
  699.         else:
  700.             return math.inf
  701.  
  702. def update_obs(position):
  703.     x = position[0]
  704.     y = position[1]
  705.     n = position[2]
  706.  
  707.     if(y == 1 and n == -1) or (y == 6 and n == 1):
  708.         n = n * (-1)
  709.     y = y + n
  710.     position = (x,y,n)
  711.     return position
  712.  
  713. class Explorer(Problem):
  714.     def __init__(self, initial, goal):
  715.         self.initial = initial
  716.         self.goal = goal
  717.  
  718.     def successor(self, state):
  719.         successors = dict()
  720.  
  721.         x = state[0]
  722.         y = state[1]
  723.  
  724.         obs1 = (state[2],state[3],state[4])
  725.         obs2 = (state[5],state[6],state[7])
  726.  
  727.         #Move obs
  728.         obs1 = update_obs(obs1)
  729.         obs2 = update_obs(obs2)
  730.         obs = [(obs1[0],obs1[1]),(obs2[0],obs2[1])]
  731.  
  732.         #Right -> x+1,y until x=8
  733.         if x < 8 and (x+1,y) not in obs:
  734.             state_new = (x+1,y,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
  735.             successors['Right'] = state_new
  736.  
  737.         #Left -> x-1,y until x=1
  738.         if x > 1 and (x-1,y) not in obs:
  739.             state_new = (x-1,y,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
  740.             successors['Left'] = state_new
  741.  
  742.         #Up  -> x,y+1 until y=6
  743.         if y < 6 and (x,y+1) not in obs:
  744.             state_new = (x,y+1,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
  745.             successors['Up'] = state_new
  746.  
  747.         #Down -> x,y-1 until x=1
  748.         if y > 1 and (x,y-1) not in obs:
  749.             state_new = (x,y-1,obs1[0],obs1[1],obs1[2],obs2[0],obs2[1],obs2[2])
  750.             successors['Down'] = state_new
  751.  
  752.         return successors
  753.  
  754.     def actions(self, state):
  755.         return self.successor(state).keys()
  756.  
  757.     def result(self, state, action):
  758.         possible = self.successor(state)
  759.         return possible[action]
  760.  
  761.     def goal_test(self, state):
  762.         position = (state[0],state[1])
  763.         return position == self.goal
  764.  
  765. man_x = int(input())
  766. man_y = int(input())
  767.  
  768. house_x = int(input())
  769. house_y = int(input())
  770.  
  771. initial = (man_x,man_y,3,6,-1,6,1,1)
  772. goal = (house_x,house_y)
  773.  
  774.  
  775. explorer = Explorer(initial,goal)
  776.  
  777. result = breadth_first_graph_search(explorer).solution()
  778. print(result)
  779. solution = breadth_first_graph_search(explorer).solve()
  780. print(solution)
  781.  
  782.  
  783.  
RAW Paste Data