Google Foobar escape-pods Test Case N. 4 fails

Question

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)

Answer 1

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()