Google Foobar escape-pods 测试用例 N.4 失败
Google Foobar escape-pods Test Case N. 4 fails
我正在解决第 4 级的 Google Foobar - Escape pods 问题，我在测试用例 N.4 上遇到了一个问题，但从未通过！
离截止日期只有两天了，我无法弄清楚我的代码在这种情况下有什么问题。有没有人可以看一下或者可以为我提供一些我的代码失败的测试用例？
这是问题：
逃脱Pods
你已经炸毁了 LAMBCHOP 世界末日装置并将兔子从 Lambda 的监狱中解救出来 - 现在你需要尽快并尽可能有序地逃离 space 空间站！兔子们都聚集在整个空间站的不同位置，需要前往空间站其他地方看似无穷无尽的逃生通道 pods。你需要让无数的兔子穿过各个房间才能逃脱pods。不幸的是，房间之间的走廊一次只能容纳这么多兔子。更重要的是，许多走廊的大小都经过调整以容纳 LAMBCHOP，因此一次可以移动的兔子数量有所不同。
给定兔子组的起始房间号，逃生的房间号pods，以及中间每条走廊的每个方向一次可以通过多少只兔子，计算出如何许多兔子可以在高峰期一次安全地逃生pods。
写一个函数 solution(entrances, exits, path)，它接受一个整数数组，表示聚集的兔子组的位置，一个整数数组，表示逃生 pods 所在的位置，以及一个数组走廊的整数数组，以 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 只兔子可以在每个时间步的第 4 和第 5 处逃脱 pods。 （请注意，在此示例中，房间 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)
希望您可以使用此代码来帮助跟踪代码中的问题。
免责声明：我没有写解决方案（只有单元测试），只是用它来完成挑战，看看最后发生了什么。
祝你好运！
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()
我正在解决第 4 级的 Google Foobar - Escape pods 问题，我在测试用例 N.4 上遇到了一个问题，但从未通过！ 离截止日期只有两天了，我无法弄清楚我的代码在这种情况下有什么问题。有没有人可以看一下或者可以为我提供一些我的代码失败的测试用例？ 这是问题：
逃脱Pods
你已经炸毁了 LAMBCHOP 世界末日装置并将兔子从 Lambda 的监狱中解救出来 - 现在你需要尽快并尽可能有序地逃离 space 空间站！兔子们都聚集在整个空间站的不同位置，需要前往空间站其他地方看似无穷无尽的逃生通道 pods。你需要让无数的兔子穿过各个房间才能逃脱pods。不幸的是，房间之间的走廊一次只能容纳这么多兔子。更重要的是，许多走廊的大小都经过调整以容纳 LAMBCHOP，因此一次可以移动的兔子数量有所不同。
给定兔子组的起始房间号，逃生的房间号pods，以及中间每条走廊的每个方向一次可以通过多少只兔子，计算出如何许多兔子可以在高峰期一次安全地逃生pods。
写一个函数 solution(entrances, exits, path)，它接受一个整数数组，表示聚集的兔子组的位置，一个整数数组，表示逃生 pods 所在的位置，以及一个数组走廊的整数数组，以 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 只兔子可以在每个时间步的第 4 和第 5 处逃脱 pods。 （请注意，在此示例中，房间 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)
希望您可以使用此代码来帮助跟踪代码中的问题。
免责声明：我没有写解决方案（只有单元测试），只是用它来完成挑战，看看最后发生了什么。
祝你好运！
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()