Foobar: Escape Pods

0286

You’ve blown up the LAMBCHOP doomsday device and relieved the bunnies of their work duries — 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.)

Languages

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases

Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

Input:
solution.solution([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]])
Output:
6

Input:
solution.solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])
Output:
16 

<span>from</span> <span>collections</span> <span>import</span> <span>deque</span>
<span>CORRIDOR_CAPACITY</span> <span>=</span> <span>2000001</span>
<span># Great ref: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm </span><span>class</span> <span>EscapePods</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>entrances</span><span>,</span> <span>exits</span><span>,</span> <span>path</span><span>):</span>
        <span>n</span> <span>=</span> <span>len</span><span>(</span><span>path</span><span>)</span>
        <span>m</span> <span>=</span> <span>n</span> <span>+</span> <span>2</span>
        <span># graph[0] is the new single source s </span>        <span># graph[-1] is the new single sink t </span>        <span>self</span><span>.</span><span>graph</span> <span>=</span> <span>[]</span>
        <span>self</span><span>.</span><span>size</span> <span>=</span> <span>m</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>m</span><span>):</span>
            <span>self</span><span>.</span><span>graph</span><span>.</span><span>append</span><span>([</span><span>0</span><span>]</span> <span>*</span> <span>m</span><span>)</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
            <span>for</span> <span>j</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
                <span>self</span><span>.</span><span>graph</span><span>[</span><span>i</span><span>+</span><span>1</span><span>][</span><span>j</span><span>+</span><span>1</span><span>]</span> <span>=</span> <span>path</span><span>[</span><span>i</span><span>][</span><span>j</span><span>]</span>
        <span>for</span> <span>num</span> <span>in</span> <span>entrances</span><span>:</span>
            <span>self</span><span>.</span><span>graph</span><span>[</span><span>0</span><span>][</span><span>num</span> <span>+</span> <span>1</span><span>]</span> <span>=</span> <span>CORRIDOR_CAPACITY</span>
        <span>for</span> <span>num</span> <span>in</span> <span>exits</span><span>:</span>
            <span>self</span><span>.</span><span>graph</span><span>[</span><span>num</span> <span>+</span> <span>1</span><span>][</span><span>m</span> <span>-</span> <span>1</span><span>]</span> <span>=</span> <span>CORRIDOR_CAPACITY</span>
    <span>def</span> <span>bfs</span><span>(</span><span>self</span><span>):</span>
        <span>parents</span> <span>=</span> <span>[</span><span>-</span><span>1</span><span>]</span> <span>*</span> <span>self</span><span>.</span><span>size</span>
        <span>queue</span> <span>=</span> <span>deque</span><span>()</span>
        <span>queue</span><span>.</span><span>append</span><span>(</span><span>0</span><span>)</span>
        <span>while</span> <span>queue</span> <span>and</span> <span>parents</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
            <span>u</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
            <span>for</span> <span>v</span> <span>in</span> <span>range</span><span>(</span><span>self</span><span>.</span><span>size</span><span>):</span>
                <span>if</span> <span>self</span><span>.</span><span>graph</span><span>[</span><span>u</span><span>][</span><span>v</span><span>]</span> <span>></span> <span>0</span> <span>and</span> <span>parents</span><span>[</span><span>v</span><span>]</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
                    <span>queue</span><span>.</span><span>append</span><span>(</span><span>v</span><span>)</span>
                    <span>parents</span><span>[</span><span>v</span><span>]</span> <span>=</span> <span>u</span>
        <span>path</span> <span>=</span> <span>[]</span>
        <span>u</span> <span>=</span> <span>parents</span><span>[</span><span>-</span><span>1</span><span>]</span>
        <span>while</span> <span>u</span> <span>!=</span> <span>0</span><span>:</span>
            <span>if</span> <span>u</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
                <span>return</span> <span>None</span>
            <span>path</span><span>.</span><span>append</span><span>(</span><span>u</span><span>)</span>
            <span>u</span> <span>=</span> <span>parents</span><span>[</span><span>u</span><span>]</span>
        <span>path</span><span>.</span><span>reverse</span><span>()</span>
        <span>return</span> <span>path</span>
    <span>def</span> <span>solve</span><span>(</span><span>self</span><span>):</span>
        <span>max_flow</span> <span>=</span> <span>0</span>
        <span>path</span> <span>=</span> <span>self</span><span>.</span><span>bfs</span><span>()</span>
        <span>while</span> <span>path</span><span>:</span>
            <span>cap</span> <span>=</span> <span>CORRIDOR_CAPACITY</span>
            <span>u</span> <span>=</span> <span>0</span>
            <span>for</span> <span>v</span> <span>in</span> <span>path</span><span>:</span>
                <span>cap</span> <span>=</span> <span>min</span><span>(</span><span>cap</span><span>,</span> <span>self</span><span>.</span><span>graph</span><span>[</span><span>u</span><span>][</span><span>v</span><span>])</span>
                <span>u</span> <span>=</span> <span>v</span>
            <span>max_flow</span> <span>+=</span> <span>cap</span>
            <span>u</span> <span>=</span> <span>0</span>
            <span>for</span> <span>v</span> <span>in</span> <span>path</span><span>:</span>
                <span>self</span><span>.</span><span>graph</span><span>[</span><span>u</span><span>][</span><span>v</span><span>]</span> <span>-=</span> <span>cap</span>
                <span>self</span><span>.</span><span>graph</span><span>[</span><span>v</span><span>][</span><span>u</span><span>]</span> <span>+=</span> <span>cap</span>
                <span>u</span> <span>=</span> <span>v</span>
            <span>path</span> <span>=</span> <span>self</span><span>.</span><span>bfs</span><span>()</span>
        <span>return</span> <span>max_flow</span>
<span>def</span> <span>solution</span><span>(</span><span>entrances</span><span>,</span> <span>exits</span><span>,</span> <span>path</span><span>):</span>
    <span>escape_pods</span> <span>=</span> <span>EscapePods</span><span>(</span><span>entrances</span><span>,</span> <span>exits</span><span>,</span> <span>path</span><span>)</span>
    <span>res</span> <span>=</span> <span>escape_pods</span><span>.</span><span>solve</span><span>()</span>
    <span>return</span> <span>res</span>
<span>from</span> <span>collections</span> <span>import</span> <span>deque</span>
<span>CORRIDOR_CAPACITY</span> <span>=</span> <span>2000001</span>


<span># Great ref: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm </span><span>class</span> <span>EscapePods</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>entrances</span><span>,</span> <span>exits</span><span>,</span> <span>path</span><span>):</span>
        <span>n</span> <span>=</span> <span>len</span><span>(</span><span>path</span><span>)</span>
        <span>m</span> <span>=</span> <span>n</span> <span>+</span> <span>2</span>

        <span># graph[0] is the new single source s </span>        <span># graph[-1] is the new single sink t </span>        <span>self</span><span>.</span><span>graph</span> <span>=</span> <span>[]</span>
        <span>self</span><span>.</span><span>size</span> <span>=</span> <span>m</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>m</span><span>):</span>
            <span>self</span><span>.</span><span>graph</span><span>.</span><span>append</span><span>([</span><span>0</span><span>]</span> <span>*</span> <span>m</span><span>)</span>

        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
            <span>for</span> <span>j</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
                <span>self</span><span>.</span><span>graph</span><span>[</span><span>i</span><span>+</span><span>1</span><span>][</span><span>j</span><span>+</span><span>1</span><span>]</span> <span>=</span> <span>path</span><span>[</span><span>i</span><span>][</span><span>j</span><span>]</span>

        <span>for</span> <span>num</span> <span>in</span> <span>entrances</span><span>:</span>
            <span>self</span><span>.</span><span>graph</span><span>[</span><span>0</span><span>][</span><span>num</span> <span>+</span> <span>1</span><span>]</span> <span>=</span> <span>CORRIDOR_CAPACITY</span>

        <span>for</span> <span>num</span> <span>in</span> <span>exits</span><span>:</span>
            <span>self</span><span>.</span><span>graph</span><span>[</span><span>num</span> <span>+</span> <span>1</span><span>][</span><span>m</span> <span>-</span> <span>1</span><span>]</span> <span>=</span> <span>CORRIDOR_CAPACITY</span>

    <span>def</span> <span>bfs</span><span>(</span><span>self</span><span>):</span>
        <span>parents</span> <span>=</span> <span>[</span><span>-</span><span>1</span><span>]</span> <span>*</span> <span>self</span><span>.</span><span>size</span>
        <span>queue</span> <span>=</span> <span>deque</span><span>()</span>
        <span>queue</span><span>.</span><span>append</span><span>(</span><span>0</span><span>)</span>
        <span>while</span> <span>queue</span> <span>and</span> <span>parents</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
            <span>u</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
            <span>for</span> <span>v</span> <span>in</span> <span>range</span><span>(</span><span>self</span><span>.</span><span>size</span><span>):</span>
                <span>if</span> <span>self</span><span>.</span><span>graph</span><span>[</span><span>u</span><span>][</span><span>v</span><span>]</span> <span>></span> <span>0</span> <span>and</span> <span>parents</span><span>[</span><span>v</span><span>]</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
                    <span>queue</span><span>.</span><span>append</span><span>(</span><span>v</span><span>)</span>
                    <span>parents</span><span>[</span><span>v</span><span>]</span> <span>=</span> <span>u</span>
        <span>path</span> <span>=</span> <span>[]</span>
        <span>u</span> <span>=</span> <span>parents</span><span>[</span><span>-</span><span>1</span><span>]</span>
        <span>while</span> <span>u</span> <span>!=</span> <span>0</span><span>:</span>
            <span>if</span> <span>u</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
                <span>return</span> <span>None</span>
            <span>path</span><span>.</span><span>append</span><span>(</span><span>u</span><span>)</span>
            <span>u</span> <span>=</span> <span>parents</span><span>[</span><span>u</span><span>]</span>
        <span>path</span><span>.</span><span>reverse</span><span>()</span>
        <span>return</span> <span>path</span>

    <span>def</span> <span>solve</span><span>(</span><span>self</span><span>):</span>
        <span>max_flow</span> <span>=</span> <span>0</span>
        <span>path</span> <span>=</span> <span>self</span><span>.</span><span>bfs</span><span>()</span>

        <span>while</span> <span>path</span><span>:</span>
            <span>cap</span> <span>=</span> <span>CORRIDOR_CAPACITY</span>
            <span>u</span> <span>=</span> <span>0</span>
            <span>for</span> <span>v</span> <span>in</span> <span>path</span><span>:</span>
                <span>cap</span> <span>=</span> <span>min</span><span>(</span><span>cap</span><span>,</span> <span>self</span><span>.</span><span>graph</span><span>[</span><span>u</span><span>][</span><span>v</span><span>])</span>
                <span>u</span> <span>=</span> <span>v</span>
            <span>max_flow</span> <span>+=</span> <span>cap</span>
            <span>u</span> <span>=</span> <span>0</span>
            <span>for</span> <span>v</span> <span>in</span> <span>path</span><span>:</span>
                <span>self</span><span>.</span><span>graph</span><span>[</span><span>u</span><span>][</span><span>v</span><span>]</span> <span>-=</span> <span>cap</span>
                <span>self</span><span>.</span><span>graph</span><span>[</span><span>v</span><span>][</span><span>u</span><span>]</span> <span>+=</span> <span>cap</span>
                <span>u</span> <span>=</span> <span>v</span>
            <span>path</span> <span>=</span> <span>self</span><span>.</span><span>bfs</span><span>()</span>
        <span>return</span> <span>max_flow</span>


<span>def</span> <span>solution</span><span>(</span><span>entrances</span><span>,</span> <span>exits</span><span>,</span> <span>path</span><span>):</span>
    <span>escape_pods</span> <span>=</span> <span>EscapePods</span><span>(</span><span>entrances</span><span>,</span> <span>exits</span><span>,</span> <span>path</span><span>)</span>
    <span>res</span> <span>=</span> <span>escape_pods</span><span>.</span><span>solve</span><span>()</span>
    <span>return</span> <span>res</span>
from collections import deque
CORRIDOR_CAPACITY = 2000001


# Great ref: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm class EscapePods:
    def __init__(self, entrances, exits, path):
        n = len(path)
        m = n + 2

        # graph[0] is the new single source s         # graph[-1] is the new single sink t         self.graph = []
        self.size = m
        for i in range(m):
            self.graph.append([0] * m)

        for i in range(n):
            for j in range(n):
                self.graph[i+1][j+1] = path[i][j]

        for num in entrances:
            self.graph[0][num + 1] = CORRIDOR_CAPACITY

        for num in exits:
            self.graph[num + 1][m - 1] = CORRIDOR_CAPACITY

    def bfs(self):
        parents = [-1] * self.size
        queue = deque()
        queue.append(0)
        while queue and parents[-1] == -1:
            u = queue.popleft()
            for v in range(self.size):
                if self.graph[u][v] > 0 and parents[v] == -1:
                    queue.append(v)
                    parents[v] = u
        path = []
        u = parents[-1]
        while u != 0:
            if u == -1:
                return None
            path.append(u)
            u = parents[u]
        path.reverse()
        return path

    def solve(self):
        max_flow = 0
        path = self.bfs()

        while path:
            cap = CORRIDOR_CAPACITY
            u = 0
            for v in path:
                cap = min(cap, self.graph[u][v])
                u = v
            max_flow += cap
            u = 0
            for v in path:
                self.graph[u][v] -= cap
                self.graph[v][u] += cap
                u = v
            path = self.bfs()
        return max_flow


def solution(entrances, exits, path):
    escape_pods = EscapePods(entrances, exits, path)
    res = escape_pods.solve()
    return res

Enter fullscreen mode Exit fullscreen mode

原文链接：Foobar: Escape Pods

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Python（EN）
# python# google# foobar# maxflow
喜欢就支持一下吧
点赞6 分享
Sometimes, we are not waiting for somebody or something. We are waiting to be changed as time goes by.
有时候，我们并不是在等什么人或什么事。我们只是在静待岁月改变自己
kity的头像-拾光赋
相关推荐
评论 抢沙发

请登录后发表评论

    暂无评论内容

kity的头像-拾光赋
今日剩余 6.8%
本周剩余 86.7%
本月剩余 45.4%
本年剩余 79.2%
最近评论
Vito的头像-拾光赋

Vito5个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋5个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
Sometimes, we are not waiting for somebody or something. We are waiting to be changed as time goes by.
有时候，我们并不是在等什么人或什么事。我们只是在静待岁月改变自己