import sys sys.setrecursionlimit(50000) corral = {(5,5), (6,5), (7,5), (7,6), (5,7), (6,7), (7,7)} target = (6,6) def manhattan_heuristic(x1: int, y1: int, x2: int, y2: int): return abs(x1 - x2) + abs(y1 - y2) #This method returns all the potential moves the robot can do given an x, y, and bull position def get_robo_moves(x, y, bull): moves = [] for n1, n2 in [(0,0), (0,-1), (0,1), (1,0), (1, -1), (1,1), (-1, -1), (-1, 0), (-1, 1)]: x2, y2, robo = x+n1, y+n2, (x+n1, y+n2) if robo not in corral and 0 <= x2 <= 13 and 0 <= y2 <= 13 and robo != bull: moves.append(robo) return moves #This method returns all the potential moves the bull can go given an x, y, and the robot position def get_bull_moves(x, y, robot, d): moves = [] rx, ry = robot #This boolean will indicated whether we are in the 5x5 radius five = False if abs(x - rx) <=2 and abs(y - ry) <= 2: five = True for n1, n2 in [(0,1), (0, -1), (1,0), (-1, 0)]: x2, y2, bull = x+n1, y+n2, (x+n1, y+n2) if bull not in corral and 0 <= x2 <= 13 and 0 <= y2 <= 13 and bull != robot: if not five and not (manhattan_heuristic(rx, ry, x2, y2) > d): moves.append((robot, bull)) return moves def compute_t_star(robot, bull, stored, visit): #This is the base case if bull == target: stored[(robot, bull)] = 0 return stored[(robot, bull)] #If already stored if stored[(robot, bull)] < 10**6: return stored[(robot, bull)] #The x and y of the robot and bull r1, r2 = robot b1, b2 = bull #This loop will go through all the robot moves and get the potential bull moves for new_robot in get_robo_moves(r1, r2, bull): potential_moves = [] new_r1, new_r2 = new_robot d = manhattan_heuristic(new_r1, new_r2, b1, b2) #This is for the case where the robot and bull are next to each other and the bull skips its turn if robot != new_robot and d == 1: potential_moves.append((new_robot, bull)) else: potential_moves.extend(get_bull_moves(b1, b2, new_robot, d)) #Now that we have all the new states (potential moves), we can compute the t's t = 0 for nr, nb in potential_moves: pml = len(potential_moves) #Check if its already in visit, and if not add and recurse if (nr, nb) not in visit: visit.add((nr, nb)) compute_t_star(nr, nb, stored, visit) stored[(robot, bull)] = min(stored[(nr, nb)] + 1, stored[(robot, bull)]) t += stored[(nr, nb)] if potential_moves: #This is just the formula from 1.3 stored[(robot, bull)] = min((t/ pml) + 1, stored[(robot, bull)]) return stored[(robot, bull)]

from collections import defaultdict stored = defaultdict(lambda: float('inf')) stored[((6,6), (5,6))] = 10**6 visited = set([((0,0), (12,12)), ((6,6), (5,6))]) print(compute_t_star((0,0), (12,12), stored, visited))