Google Foobar escape-pods Test Case N. 4 fails
I am solving the Google Foobar - Escape pods problem on level 4, and I faced a problem on test case N.4 which never passes! I've got only two days till the deadline and cannot figure out what is the problem with my code on that case. Is there anyone who can take a look or can provide me with some test cases in which my code fails? Here is the question:
Escape Pods
You've blown up the LAMBCHOP doomsday device and broken the bunnies out of Lambda's prison - and now you need to escape from the space station as quickly and as orderly as possible! The bunnies have all gathered in various locations throughout the station, and need to make their way towards the seemingly endless amount of escape pods positioned in other parts of the station. You need to get the numerous bunnies through the various rooms to the escape pods. Unfortunately, the corridors between the rooms can only fit so many bunnies at a time. What's more, many of the corridors were resized to accommodate the LAMBCHOP, so they vary in how many bunnies can move through them at a time.
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.)
here is my code:
class Edge:
def __init__(self, destination, capacity):
self.destination = destination
self.capacity = capacity
self.remaining = capacity
class Node:
def __init__(self, name, level=0, edges=None):
self.name = name
self.level = level
if edges is None:
self.edges = []
def add_edge(self, destination, weight):
self.edges.append(Edge(destination, weight))
def get_children(self):
res = []
for edge in self.edges:
res.append(edge.destination)
return res
def __str__(self):
res = str(self.name) + " ({})".format(str(self.level))
for edge in self.edges:
res = res + " --> {} ({})".format(str(edge.destination), str(edge.remaining))
return res
class Graph:
nodes = []
flow = []
permanent_dead_ends = []
levels = []
def __init__(self, entrances, exits, matrix):
self.entrances = entrances
self.exits = exits
self.matrix = matrix
for i in range(0, len(self.matrix)):
self.nodes.append(Node(i))
def create(self):
for i in range(0, len(self.matrix)):
if self.nodes[i].name in self.exits:
continue
for j in range(0, len(self.matrix[i])):
if self.matrix[i][j] != 0:
self.nodes[i].add_edge(j, self.matrix[i][j])
def bfs(self):
queue = self.entrances[:]
seen = self.entrances[:]
level = 0
self.levels = [-1] * len(self.matrix)
for entrance in self.entrances:
self.nodes[entrance].level = level
self.levels[entrance] = level
while len(queue) > 0:
to_remove = []
i = queue.pop(0)
level = self.nodes[i].level + 1
for edge in self.nodes[i].edges:
if edge.destination in self.permanent_dead_ends:
to_remove.append(edge) # pruning permanent dead ends
elif edge.remaining > 0:
if edge.destination not in seen:
self.nodes[edge.destination].level = self.levels[edge.destination] = level
queue.append(edge.destination)
seen.append(edge.destination)
else:
to_remove.append(edge)
for edge in to_remove:
self.nodes[i].edges.remove(edge)
#for node in self.nodes:
#print(node)
if self.is_finished():
return False
return True
def is_finished(self):
for ex in self.exits:
if self.levels[ex] != -1:
return False
return True
def choose_next_node(self, candidates, dead_ends):
for i in candidates:
previous_level = self.nodes[i].level
for edge in self.nodes[i].edges:
if (edge.remaining > 0) \
and (previous_level < self.nodes[edge.destination].level)\
and (edge.destination not in dead_ends):
return i, edge, edge.remaining
return None, None, None
def dfs(self):
path = []
capacities = []
edges = []
dead_ends = self.permanent_dead_ends[:]
entr = self.entrances[:]
current_node, edge, capacity = self.choose_next_node(entr, dead_ends)
next_node = None
if edge is not None:
next_node = edge.destination
edges.append(edge)
path.append(current_node)
if next_node in self.exits:
path.append(next_node)
capacities.append(capacity)
else:
return
while next_node not in self.exits and len(path) > 0:
if next_node != path[-1]:
path.append(next_node)
capacities.append(capacity)
current_node, edge, capacity = self.choose_next_node([next_node], dead_ends)
if edge is not None:
next_node = edge.destination
edges.append(edge)
if next_node in self.exits:
path.append(next_node)
capacities.append(capacity)
else:
#print("dead-end reached: {}".format(path))
if len(path) > 1:
dead_ends.append(path[-1])
path = path[:-1]
edges = edges[:-1]
next_node = path[-1]
capacities = capacities[:-1]
else:
entr.remove(path[0])
path = []
capacities = []
current_node, edge, capacity = self.choose_next_node(entr, dead_ends)
next_node = None
if edge is not None:
next_node = edge.destination
edges.append(edge)
path.append(current_node)
if next_node in self.exits:
path.append(next_node)
capacities.append(capacity)
else:
return
if len(path) < 1:
#print("no path found!")
return False
capacity = min(capacities)
#print("capacity: {}".format(capacity))
self.flow.append(capacity)
#print("path: {}".format(path))
i = 0
for edge in edges:
edge.remaining -= capacity
if edge.remaining == 0:
self.nodes[path[i]].edges.remove(edge)
if len(self.nodes[path[i]].edges) < 1:
self.permanent_dead_ends.append(self.nodes[path[i]].name)
#print("added permanent dead end: {}".format(self.nodes[path[i]].name))
i += 1
#for node in self.nodes:
#print(node)
return False
def solution(entrances, exits, matrix):
graph = Graph(entrances, exits, matrix)
graph.create()
while graph.bfs():
#print("another BFS!")
graph.dfs()
#print("flow is: {}".format(graph.flow))
return sum(graph.flow)
Hopefully you can use this code to help trace what is wrong with your code.
Disclaimer: I did not write the solution (only the unittests) and only used it to complete the challenge to see what happened at the end.
Good luck!
import unittest
def solution(entrances, exits, path):
# First, it's important to realize that this is a multiple sources, multiple
# sinks problem where we have to find the max flow. This problem builds off
# of the single source, single sink problem. To get the max flow for the
# latter problem, you create a residual graph and then find an augmenting
# path through the residual graph using DFS, updating the residual graph
# based on the augmenting path found. So long as there is an augmenting path
# through the residual graph, you can increase the flow.
#
# We can extend this solution to multiple sources and multiple sinks. If
# an augmenting path can be found starting at ***any*** source and ending
# at ***any*** sink, you can increase the flow.
# The residual graph starts out being the same as the graph given to us.
residual = path[:]
# How many bunnies can make it to the escape pods at each time step?
numBunnies = 0
# To determine whether the number of bunnies we found is the max flow, we
# have to have a tracker that would determine whether we were able to find
# an augmented path
prevNumBunnies = -1
while prevNumBunnies != numBunnies:
# Set the tracker here. If an augmented path is found, numBunnies will
# change.
prevNumBunnies = numBunnies
# Check all paths starting at each available entrance
for j in entrances:
# Visited graph - which nodes have been visited?
visited = []
# The augmented path, implemented as a stack. The stack will add a
# node if the node is connected to at least one other unvisited
# node. The node on the top of the stack will be popped otherwise.
path = []
# Start the path at an entrance
node = j
while 1:
# Keep track of whether or not we have found an unvisited node
# connected to our current node of interest
findUnvisited = False
# Also keep track of visited nodes
visited.append(node)
# To speed up program, use a greedy algorithm. At each node,
# only travel to a connected unvisited node that would allow
# the maximum number of bunnies to travel through.
maximum = 0
index = 0
# Check all adjacent nodes for the one that would allow the
# maximum number of bunnies to travel through
for i in range(len(residual[node])):
if residual[node][i] > maximum and i not in visited:
maximum = residual[node][i]
index = i
findUnvisited = True
# Go to the node that would allow the most number of bunnies
# in the corridor
if findUnvisited:
path.append(node)
node = index
# If there are no unvisited nodes connected to this entrance,
# check the paths connecting to another entrance.
elif not path:
break
# If there are no unvisited nodes connected, backtrace in the
# augmented path.
else:
node = path.pop()
# If we find an end node, update the residual graph depending
# on the augmented path. To speed up the program, get the
# maximum number of bunnies that could go through the corridor
# by finding the bottleneck corridor in the augmenting path
# (the corridor that would allow the least number of bunnies to
# go through. Use that to update numBunnies
if node in exits:
path.append(node)
minimum = 2000000
for j in range(len(path) - 1):
if residual[path[j]][path[j + 1]] < minimum:
minimum = residual[path[j]][path[j + 1]]
numBunnies += minimum
for j in range(len(path) - 2):
residual[path[j]][path[j + 1]] -= minimum
residual[path[j + 1]][path[j]] += minimum
residual[path[len(path) - 2]][path[len(path) - 1]] -= minimum
break
# Return number of bunnies
return numBunnies
ents = [0, 1]
exts = [4, 5]
pth = [
[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
]
ans = 16
ents2 = [0]
exts2 = [3]
pth2 = [
[0, 7, 0, 0],
[0, 0, 6, 0],
[0, 0, 0, 8],
[9, 0, 0, 0]
]
ans2 = 6
print(solution(ents2, exts2, pth2))
class TestEscapePods(unittest.TestCase):
def test1(self):
self.assertEqual(solution(ents, exts, pth), ans)
def test2(self):
self.assertEqual(solution(ents2, exts2, pth2), ans2)
unittest.main()