Я решаю проблему Google Foobar - Escape pods на уровне 4, и я столкнулся с проблемой в тестовом примере N.4, который никогда не проходит! У меня всего два дня до крайнего срока, и я не могу понять, в чем проблема с моим кодом в этом случае. Есть ли кто-нибудь, кто может взглянуть или может предоставить мне несколько тестовых примеров, в которых мой код не работает? Вот вопрос:
Спасательные капсулы
Вы взорвали устройство судного дня LAMBCHOP и вырвали кроликов из тюрьмы Лямбда - и теперь вам нужно сбежать с космической станции как можно быстрее и организованнее! Все кролики собрались в разных местах по всей станции, и им нужно пробраться к, казалось бы, бесконечному количеству спасательных капсул, расположенных в других частях станции. Вам нужно провести многочисленных кроликов через различные комнаты к спасательным капсулам. К сожалению, коридоры между комнатами не могут вместить столько кроликов одновременно. Более того, размеры многих коридоров были изменены, чтобы в них мог поместиться БАРНЯЦ, поэтому они различаются по количеству кроликов, которые могут проходить по ним одновременно.
Зная начальные номера комнат групп кроликов, номера комнат спасательных капсул и сколько кроликов может пройти одновременно в каждом направлении каждого коридора между ними, выясните, сколько кроликов может безопасно добраться до побега. капсул за раз на пике.
Напишите решение функции (входы, выходы, путь), которая принимает массив целых чисел, обозначающих, где находятся группы собравшихся кроликов, массив целых чисел, обозначающих, где расположены спасательные капсулы, и массив массивов целых чисел коридоров, возвращая общее количество кроликов, которые могут пройти на каждом временном шаге, как целое число. Входы и выходы не пересекаются и поэтому никогда не перекрываются. Элемент пути 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 кроликов могли добраться до спасательных капсул по 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)
