Я решаю проблему с Google Foobar — Escape pods на уровне 4, и я столкнулся с проблемой в тестовом примере N.4, который никогда не проходит! У меня осталось всего два дня до крайнего срока, и я не могу понять, в чем проблема с моим кодом в этом случае. Есть ли кто-нибудь, кто может взглянуть или может предоставить мне несколько тестовых примеров, в которых мой код терпит неудачу? Вот вопрос:

Escape-модули

Вы взорвали устройство LAMBCHOP doomsday и вызволили кроликов из тюрьмы Лямбды — и теперь вам нужно сбежать с космической станции как можно быстрее и организованнее! Все кролики собрались в разных местах по всей станции, и им нужно пробраться к, казалось бы, бесконечному количеству спасательных капсул, расположенных в других частях станции. Вам нужно провести множество кроликов через различные комнаты к спасательным капсулам. К сожалению, в коридорах между комнатами одновременно может поместиться не так много кроликов. Более того, многие коридоры были изменены для размещения баранины, поэтому они различаются в зависимости от того, сколько кроликов может перемещаться по ним одновременно.

Учитывая начальные номера комнат для групп кроликов, номера комнат в спасательных капсулах и количество кроликов, которые могут пройти одновременно в каждом направлении каждого промежуточного коридора, выясните, сколько кроликов могут безопасно добраться до спасательных капсул одновременно на пике.

Напишите функциональное решение (входы, выходы, путь), которое принимает массив целых чисел, обозначающих, где находятся группы собранных кроликов, массив целых чисел, обозначающих, где расположены спасательные капсулы, и массив массива целых чисел коридоров, возвращающий общее количество кроликов, которые могут пройтина каждом временном шаге как int. Входы и выходы не пересекаются и, следовательно, никогда не будут перекрываться. Элемент пути path[A] [B] = C описывает, что коридор, идущий от A до B, может вместить C кроликов на каждом временном шаге. Одновременно может поместиться не более 50 комнат, соединенных коридорами, и не более 2000000 кроликов.

 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
]
 

Затем на каждом временном шаге может произойти следующее:
0 отправляет 4/4 кроликов на 2 и 6/6 кроликов на 3
1 отправляет 4/5 кроликов на 2 и 2/2 кроликов на 3
2 отправляет 4/4 кроликов на 4 и 4/4 кроликов на 5
3 отправляет 4/6 кроликов на 4 и 4/6 кроликов на 5

Таким образом, в общей сложности 16 кроликов могут попасть в escape-модули на 4 и 5 на каждом временном шаге. (Обратите внимание, что в этом примере комната 3 могла отправить любой вариант из 8 кроликов на 4 и 5, например 2/6 и 6/6, но окончательное решение остается прежним.)

вот мой код:

 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)
 

Надеюсь, вы можете использовать этот код, чтобы помочь отследить, что не так с вашим кодом.

Отказ от ответственности: я не писал решение (только unittests) и использовал его только для завершения задачи, чтобы посмотреть, что произошло в конце.

Удачи!

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