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))

KernelInterrupted: Execution interrupted by the Jupyter kernel.