+/foobar
google programming puzzles
git clone https://git.julia.blue/+/foobar
2e1d345
master
1#!/usr/bin/python2.7 2from pprint import pprint 3from collections import deque 4 5dest ,cap ,flow = range (3 ) 6 7 8def bfs (graph ): 9visited = [False ]* len (graph ) 10q = deque ([[- 1 ]]) 11while len (q ): 12p = q .popleft () 13for i in graph [p [- 1 ]]:# for all nodes adjacent to last in path 14if i [dest ]== - 2 :# check if made it to exit 15return p + [- 2 ] 16if visited [i [dest ]]:# skip if already visited 17continue 18# otherwise add as new path 19visited [i [dest ]]= True 20q .append (p [:]+ [i [dest ]]) 21return None 22 23 24def minpath (graph ): 25path = bfs (graph ) 26if not path : 27return None ,None 28small = 2000000 29for i in range (len (path )- 2 ): 30small = min (small ,filter (lambda x :x [0 ]is path [i + 1 ],graph [path [i ]])[0 ][1 ]) 31return path ,small 32 33 34def augmenting_path (graph ): 35aug = {i : []for i in graph .keys ()} 36for node in graph : 37for edge in graph [node ]: 38if edge [flow ]< edge [cap ]: 39aug [node ].append ([edge [dest ],edge [cap ]- edge [flow ]]) 40if edge [flow ]> 0 : 41aug [edge [dest ]].append ([node ,edge [flow ]]) 42return aug 43 44 45def path_index (edges ,n ): 46for i in enumerate (edges ): 47if i [1 ][dest ]== n : 48return i [0 ] 49return None 50 51 52def augment (graph ,path ,n ): 53for i in range (len (path )- 1 ): 54start ,end = path [i ],path [i + 1 ] 55temp = path_index (graph [start ],end ) 56if temp is None :# if it was a backwards path 57temp = path_index (graph [end ],start ) 58graph [end ][temp ][flow ]-= n 59else : 60graph [start ][temp ][flow ]+= n 61 62 63def answer (entrances ,exits ,path ): 64capflow = {} 65# use -1 as sentinal for entrances (-2 will be exit) 66capflow [- 1 ]= [[i ,2000000 ,0 ]for i in entrances ] 67capflow [- 2 ]= [] 68for i in range (len (path )): 69if i in exits : 70capflow [i ]= [[- 2 ,2000000 ,0 ]] 71else : 72capflow [i ]= [ 73 [j ,path [i ][j ],0 ]for j in range (len (path [i ]))if path [i ][j ]!= 0 74 ] 75while True : 76# pprint(capflow) 77aug = augmenting_path (capflow ) 78# pprint(aug) 79path ,n = minpath (aug ) 80# pprint(path) 81if not path : 82break 83if augment (capflow ,path ,n ): 84break 85return 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 116answer (entrances ,exits ,path )