I am on 4th level of the google foobar challenge. And I am facing issues in the question. I have tried my solution on the provided test cases but the grade checker of google shows that my code is wrong for those test cases as well. Can anybody help me? Where exactly am I wrong?
Problem
Escape Pods
Given the starting room numbers of the groups of bunnies, the room numbers of the escape pods, and how many bunnies can fit through at a time in each direction of every corridor in between, figure out how many bunnies can safely make it to the escape pods at a time at peak.
Write a function solution(entrances, exits, path) that takes an array of integers denoting where the groups of gathered bunnies are, an array of integers denoting where the escape pods are located, and an array of an array of integers of the corridors, returning the total number of bunnies that can get through at each time step as an int. The entrances and exits are disjoint and thus will never overlap. The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step. There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.
For example, if you have:
entrances = [0, 1]
exits = [4, 5]
path =
[
[0, 0, 4, 6, 0, 0], # Room 0: Bunnies
[0, 0, 5, 2, 0, 0], # Room 1: Bunnies
[0, 0, 0, 0, 4, 4], # Room 2: Intermediate room
[0, 0, 0, 0, 6, 6], # Room 3: Intermediate room
[0, 0, 0, 0, 0, 0], # Room 4: Escape pods
[0, 0, 0, 0, 0, 0], # Room 5: Escape pods
]
Then in each time step, the following might happen: 0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3 1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3 2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5 3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5
So, in total, 16 bunnies could make it to the escape pods at 4 and 5 at each time step. (Note that in this example, room 3 could have sent any variation of 8 bunnies to 4 and 5, such as 2/6 and 6/6, but the final solution remains the same.)
Test cases
Your code should pass the following test cases. Note that it may also be run against hidden test cases not shown here.
-- Python cases -- Input:
solution.solution([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]])
Output:
6
Input:
solution.solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])
Output:
16
My Solution
def get_new_path(entrances,exits,path):
for p in path:
p.insert(0, 0)
p.append(0)
new_length = len(path[0])
path.insert(0,[0]* new_length)
path.append([0]* new_length)
for e in entrances:
path[0][e+1] = 2e+6
for e in exits:
path[e+1][new_length-1] = 2e+6
return path
def get_route(stack, open, path):
next = stack[-1]
list_of_nexts = [i for i,val in enumerate(path[next]) if ( i not in open and val != 0)]
for i in list_of_nexts:
open.add(i)
if len(path)-1 in list_of_nexts:
stack.append(len(path)-1)
return stack
for i in list_of_nexts:
new_stack = stack.copy()
new_stack.append(i)
r = get_route(new_stack, open, path)
if r == -1: continue
else: return r
return -1
def solution(entrances, exits, path):
path = get_new_path(entrances, exits, path)
flow = 0
while True:
stack = [0]
open = set()
open.add(0)
route = get_route(stack, open, path)
if(route == -1):
return flow
else:
f = min([path[route[i-1]][route[i]] for i in range(1,len(route))])
for i in range(2,len(route)-1):
temp = path[route[i-1]][route[i]]
path[route[i-1]][route[i]] = temp - f
path[route[i]][route[i-1]] += f
flow += f
return flow
print(solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]))