3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ I don't understand the rules of the problem. Can you link to the original problem description? \$\endgroup\$ – Gareth Rees Nov 11 '16 at 11:07
  • \$\begingroup\$ @Gareth Rees ,I can't link to the original problem cause you need to be invited to get in the website :( , however i edited the post to add a detailed example i hope it helps \$\endgroup\$ – Ouail Bendidi Nov 11 '16 at 12:09
  • \$\begingroup\$ If you can't link to the problem, can you copy the whole problem description? \$\endgroup\$ – Gareth Rees Nov 11 '16 at 12:15
  • \$\begingroup\$ @GarethRees here's the full problem ! \$\endgroup\$ – Ouail Bendidi Nov 11 '16 at 12:32
  • \$\begingroup\$ I have rolled back Rev 6 → 5. Please see What to do when someone answers. \$\endgroup\$ – 200_success Nov 13 '16 at 4:43
1
\$\begingroup\$

The problem description says:

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.

However, if I make a problem instance with this property:

problem = [ 
    [0, 2, -2],  # 0 = Start
    [9, 0, -2],  # 1 = prisoner 0
    [9, 1,  0],  # 2 = exit door
]

then when I try it I get a stack overflow:

>>> answer(problem, 0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr146426.py", line 20, in answer
    res=find_path(times,0,n-1,time_limit)
  File "cr146426.py", line 15, in find_path
    newpath = find_path(times, i, end,time-times[start][i], path)
  [... many lines omitted ...]
  File "cr146426.py", line 13, in find_path
    for i in range(n):
RecursionError: maximum recursion depth exceeded in comparison

So it looks to me as though the code in the post does not solve the problem.

\$\endgroup\$
  • \$\begingroup\$ I'm thinking of adding a new function that will detect all loops that can add time to the path, and which loops they are for example ?to then use this info to find all the prisoners that i can get ? if there's no such loop , it should work fine i presume .... \$\endgroup\$ – Ouail Bendidi Nov 11 '16 at 16:01
  • \$\begingroup\$ I edited the function now , to solve the 'walk in circle' problem , using the Floyd Warshall Algorithm, I think it solves the problem now ? \$\endgroup\$ – Ouail Bendidi Nov 13 '16 at 1:33
  • \$\begingroup\$ @OuailBendli: If you've fixed the problem, then post a new question with the revised code. \$\endgroup\$ – Gareth Rees Nov 13 '16 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.