I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python:
You and your rescued prisoners need to get out of this collapsing death trap - and fast! Unfortunately, some of the prisonners have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The exit doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many prisoners as you can and get through the exit doors before they close.
The time it takes to move from your starting point to all of the prisoners and to the exit door will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first prisoner, second prisoner, ..., last prisoner, and the exit door in that order. The order of the rows follows the same pattern (start, each prisoner, exit door). The prisoners can jump into your arms, so picking them up is instantaneous, and arriving at the exit door at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any prisoner you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the exit door doesn't mean you have to immediately leave - you can move to and from the exit door to pick up additional prisoners if time permits.
In addition to spending time traveling between prisoners, some paths interact with security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the exit doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the doors to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.
Write a function of the form answer(times, time_limit) to calculate the most prisoners you can pick up and which prisoners they are, while still escaping through the exit doors before they close for good. If there are multiple sets of prisoners of the same number, return the set of prisoners with the lowest prisoner IDs (as indexes) in sorted order. The prisoners are represented as a sorted list by prisoner ID, with the first prisoner being 0. There are at most 5 prisoners, and time_limit is a non-negative integer that is at most 999.
The function that I wrote is:
def answer(times,time_limit):
mindic=min(min(times))
n=len(times)
def find_path(times, start, end,time, path=[]):
if start != 0 and start != end :
if start-1 in path:
pass
else:
path = path + [start-1]
if start == end and time-min(times[start][0:len(times[start])-1]) < mindic:
return path
best=None
for i in range(n):
if time-times[start][i] >= mindic and times[start][i] != 0 :
newpath = find_path(times, i, end,time-times[start][i], path)
if newpath != None :
if not best or len(newpath) > len(best):
best=newpath
return best
res=find_path(times,0,n-1,time_limit)
return res
Calling the function will be something like this:
answer([[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]],3)
and the answer for the above example is:
[0, 1]
It will only be able to save the prisoners with index 0 and index 1.
Running the function with '%% timeit 10' gives the following:
1000 loops, best of 3: 163 µs per loop
Is there any way to reduce the time?
EDIT1: here's an example, hope it helps understanding the problem,
in the case of:
[
[0, 2, 2, 2, -1], # 0 = Start
[9, 0, 2, 2, -1], # 1 = prisoner 0
[9, 3, 0, 2, -1], # 2 = prisoner 1
[9, 3, 2, 0, -1], # 3 = prisoner 2
[9, 3, 2, 2, 0], # 4 = exit door
]
and a time limit of 1, the five inner array rows designate the starting point, prisoner 0, prisoner 1, prisoner 2, and the exit door respectively. You could take the path:
Start End Delta Time Status
- 0 - 1 exit door initially open
0 4 -1 2
4 2 2 0
2 4 -1 1
4 3 2 -1 exit door closes
3 4 -1 0 exit door reopens; you and the saved persons exit
With this solution, you would pick up prisoner 1 and 2. This is the best combination for this case, so the answer is [1, 2].
so generally it should: be something like this :
Inputs:
(int) times = [[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]]
(int) time_limit = 3
Output:
(int list) [0, 1]
Inputs:
(int) times = [[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]]
(int) time_limit = 1
Output:
(int list) [1, 2]
