+/foobar

google programming puzzles

git clone https://git.julia.blue/+/foobar

Joseph RyanI made it2e1d345

master
2.9 KiB116 linesraw
1#!/usr/bin/python2.7
2from pprint import pprint
3from collections import deque
4
5dest, cap, flow = range(3)
6
7
8def bfs(graph):
9    visited = [False] * len(graph)
10    q = deque([[-1]])
11    while len(q):
12        p = q.popleft()
13        for i in graph[p[-1]]:  # for all nodes adjacent to last in path
14            if i[dest] == -2:  # check if made it to exit
15                return p + [-2]
16            if visited[i[dest]]:  # skip if already visited
17                continue
18            # otherwise add as new path
19            visited[i[dest]] = True
20            q.append(p[:] + [i[dest]])
21    return None
22
23
24def minpath(graph):
25    path = bfs(graph)
26    if not path:
27        return None, None
28    small = 2000000
29    for i in range(len(path) - 2):
30        small = min(small, filter(lambda x: x[0] is path[i + 1], graph[path[i]])[0][1])
31    return path, small
32
33
34def augmenting_path(graph):
35    aug = {i: [] for i in graph.keys()}
36    for node in graph:
37        for edge in graph[node]:
38            if edge[flow] < edge[cap]:
39                aug[node].append([edge[dest], edge[cap] - edge[flow]])
40            if edge[flow] > 0:
41                aug[edge[dest]].append([node, edge[flow]])
42    return aug
43
44
45def path_index(edges, n):
46    for i in enumerate(edges):
47        if i[1][dest] == n:
48            return i[0]
49    return None
50
51
52def augment(graph, path, n):
53    for i in range(len(path) - 1):
54        start, end = path[i], path[i + 1]
55        temp = path_index(graph[start], end)
56        if temp is None: # if it was a backwards path
57            temp = path_index(graph[end], start)
58            graph[end][temp][flow] -= n
59        else:
60            graph[start][temp][flow] += n
61
62
63def answer(entrances, exits, path):
64    capflow = {}
65    # use -1 as sentinal for entrances (-2 will be exit)
66    capflow[-1] = [[i, 2000000, 0] for i in entrances]
67    capflow[-2] = []
68    for i in range(len(path)):
69        if i in exits:
70            capflow[i] = [[-2, 2000000, 0]]
71        else:
72            capflow[i] = [
73                [j, path[i][j], 0] for j in range(len(path[i])) if path[i][j] != 0
74            ]
75    while True:
76        # pprint(capflow)
77        aug = augmenting_path(capflow)
78        # pprint(aug)
79        path, n = minpath(aug)
80        # pprint(path)
81        if not path:
82            break
83        if augment(capflow, path, n):
84            break
85    return sum(capflow[i][0][flow] for i in exits)
86
87
88entrances = [0, 1]
89exits = [4, 5]
90path = [
91    [0, 3, 7, 0, 0, 0],
92    [3, 0, 0, 2, 0, 0],
93    [0, 0, 0, 2, 1, 0],
94    [0, 0, 3, 0, 0, 4],
95    [1, 0, 2, 2, 0, 0],
96    [0, 1, 2, 2, 0, 0],
97]
98
99# entrances = [0]
100# exits = [3]
101# path = [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]
102# 6
103
104# entrances = [0, 1]
105# exits = [4, 5]
106# path = [
107#     [0, 0, 4, 6, 0, 0],
108#     [0, 0, 5, 2, 0, 0],
109#     [0, 0, 0, 0, 4, 4],
110#     [0, 0, 0, 0, 6, 6],
111#     [0, 0, 0, 0, 0, 0],
112#     [0, 0, 0, 0, 0, 0],
113# ]
114# 16
115
116print answer(entrances, exits, path)