Solution for foobor 4-2

bunnyEscape.py

from itertools import permutations, groupby
width = 0
def solution(times, time_limit):
	global width
	width = len(times)
	numBunnies = width - 2
	full = [i for i in range(width)]
	fullBunnies = full[:-2]
	fullBunniesIndex = [i+1 for i in fullBunnies]
	if(negativeCycles(times)):
		return fullBunnies

	shortestRoutes = findShortestPaths(times)
	bunnyOptions = []
	for x in range(numBunnies):
		for i in permutations(fullBunniesIndex, numBunnies - x):
			bunnyOptions.append(i)

	for option in bunnyOptions:
		if(pathPossible(option, shortestRoutes, time_limit)):
			option = list(option)
			option.sort()
			option = [i-1 for i in option]
			return option

def iterate(search, times, min):
	tempSearch = [[] for x in range(width)]
	for row in range(width):
		if(search[row]):
			for route in range(len(search[row])):
				for x in range(width):
					tempTime = search[row][route][1] - pathFrom(row, x, times)
					if((not row == x) and tempTime >= min):
						t = (search[row][route][0] + [x], tempTime)
						tempSearch[x].append(t)
	for x in range(width):
		tempSearch[x].sort()
		tempSearch[x] = list(t for t,_ in groupby(tempSearch[x]))
	print((tempSearch[width-1]))
	return tempSearch
def findShortestPaths(times):
	possible = []
	for x in range(width):
		possible+=[x]
	shortestRoutes = []
	for x in range(width):
		shortestRoutes.append([])
		for y in range(width):
			shortestRoutes[x].append(0)
	c = list(permutations(possible, 2))
	for i in c:
		shortestRoutes[i[0]][i[1]] = shortest(i[0], i[1], times)
	return shortestRoutes

def shortest(a, b, times):
	bestTimes = []
	for t in range(width):
		if(t == a):
			bestTimes.append(0)
		else:
			bestTimes.append(999)
	lastChange = 0
	while lastChange<50:
		lastChange += 1
		for x in range(len(bestTimes)):
			for y in range(len(bestTimes)):
				if(not x == y):
					if(pathFrom(x,y,times) + bestTimes[x] < bestTimes[y]):
						bestTimes[y] = pathFrom(x,y,times) + bestTimes[x]
						#lastChange = 0
	return bestTimes[b]

def negativeCycles(times):
	for x in range(width):
		if(shortest(x,x,times) < 0):
			return True
	return False

def pathFrom(a,b,times):
	return times[a][b]

def pathPossible(stops, times, time_limit):
	time = pathFrom(0, stops[0], times) + pathFrom(stops[-1], len(times)-1, times)
	for i in range(len(stops)-1):
		time += pathFrom(stops[i], stops[i+1], times)
	return time <= time_limit




print("Starting:")
test1 = [[0, 2, 2, 2, -1],
		[9, 0, 2, 2, -1],
		[9, 3, 0, 2, -1],
		[9, 3, 2, 0, -1],
		[9, 3, 2, 2, 0]]
test2 = [[0, 1, 1, 1, 1 ],
		[1, 0, 1, 1, 1 ],
		[1, 1, 0, 1, 1 ],
		[1, 1, 1, 0, 1 ],
		[1, 1, 1, 1, 0]]
test3 = [[0, -1, 1, 1, 1 ],
		[1, 0, 1, 1, 1 ],
		[-3, 1, 0, 1, 1 ],
		[1, 1, 1, 0, 1 ],
		[1, 1, 1, 1, 0]]
print(solution(test1, 1))
print(solution(test2, 3))
print(solution(test3, 3))