4_1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#You are given some matrix of ints and need to output a number\n",
    "#M_ij represents the peak number that \"room\" i can send to room j\n",
    "#If forall j M_ij = 0, then that is a goal room\n",
    "#You are told which rooms are the starting rooms, and they can emit their peak\n",
    "#output to each room.\n",
    "#The input of each room is just the sum of the emissions from each room going\n",
    "#to it\n",
    "#You need to maximize the total input to the goal rooms.\n",
    "\n",
    "#Rooms leading into the end room may emit to other rooms that lead to output rooms\n",
    "#themselves\n",
    "#But we only care about those rooms in so far as we have a peak \n",
    "    #IDEA: You have an image in your head RN of a series of chambers which connect\n",
    "    #downawrds to lower chambers with pipes. Each chamber has a store connected\n",
    "    #to its input and a bunch of gated channels leading to output pipes.\n",
    "    #The game is then: put some input into the initial chambers and let them\n",
    "    #funnel off all their water. Then when the chambers they're connected to \n",
    "    #notice no more water is coming in, they then emit. And so on.\n",
    "    #Maximize the collected amount of water at the end w/o having any water left\n",
    "    #in any of the input tanks.\n",
    "    \n",
    "    #Now, you were using this model to visualize things. And the visualization\n",
    "    #that led to the parent thought was \"what about chambers which output to the \n",
    "    #goal and to chambers which lead to the goal? Well, can't we just figure\n",
    "    #out the non-goal output's effective usefulness by checking how much the\n",
    "    #chamber it leads to outputs to the goal, recursively?\n",
    "    #And that was one visualization, which would be annoying to type down.\n",
    "    #Or perhaps to make into a native data representation.\n",
    "    \n",
    "    #But what if you could somehow automate that?\n",
    "        #IDEA: OR automate the process of coming up with visualizations and metaphors\n",
    "        #for pieces of code.\n",
    "    #Another visual I had was \"well, what if you have a chamber which leads to the \n",
    "    #goal and two of its inputs also lead to the goal?\n",
    "    \n",
    "    \n",
    "    #IDEA: What if you can just clump together chambers at the same level?\n",
    "        #When can you do this?\n",
    "        #For goal chambers\n",
    "        #For chambers with the same \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "def test_sum_room_inputs(test_function):\n",
    "    list_of_rooms_list=  [[[0,1,0,0],[0,0,1,1],[0,0,0,0],[0,0,0,0]], [[0,1,0,0],[0,0,1,1],[0,0,0,5],[0,0,0,0]]];\n",
    "    test_rooms = [0, 3];\n",
    "    ans = [0, 6]\n",
    "    for i in range(len(list_of_rooms_list)):\n",
    "        assert test_function(test_rooms[i], list_of_rooms_list[i]) == ans[i] \n",
    "\n",
    "def sum_room_inputs(room_index, rooms):\n",
    "    return sum([room[room_index] for room in rooms])\n",
    "test_sum_room_inputs(sum_room_inputs)\n",
    "\n",
    "def array_dims(array):\n",
    "    bool  = True\n",
    "    lens = []\n",
    "    ls = array\n",
    "    while bool:\n",
    "        try:\n",
    "            l = len(ls);\n",
    "            lens.append(l)\n",
    "            ls = ls[0]\n",
    "        except:\n",
    "            bool = False\n",
    "    return lens\n",
    "def like_array(array):\n",
    "    dims = array_dims(array);\n",
    "    len_dims = len(dims)\n",
    "    for i in range(len_dims):\n",
    "        if i ==0:\n",
    "            new_array = [0]*dims[len_dims -1 - i]\n",
    "        else:\n",
    "            new_array = [new_array]*dims[len_dims -1 - i]\n",
    "    return new_array\n",
    "\n",
    "def copy_matrix(matrix):\n",
    "    new_matrix = [];\n",
    "\n",
    "    for i in range(len(matrix)):\n",
    "        new_row = []\n",
    "        for j in range(len(matrix[0])):\n",
    "            new_row.append(matrix[i][j]);\n",
    "        new_matrix.append(new_row)\n",
    "    return new_matrix\n",
    "\n",
    "\n",
    "def copy_list(ls):\n",
    "    new_list = [];\n",
    "    for i in range(len(ls)):\n",
    "        new_list.append(ls[i])\n",
    "    return new_list\n",
    "element_of = lambda itm, ls: 1 if sum([(lambda x: 1 if x == itm else 0 ) (i) for i in ls]) else 0\n",
    "zero_out_end_rooms = lambda ends, rooms: [[ (lambda x: 0 if element_of(x, ends) else rooms[i][j])(i) for j in range(len(rooms[0]))  ] for i in range(len(rooms))]\n",
    "\n",
    "#So if start nodes are i,j,k,... we do row = [ sum(matrix[i])* element_of(i, start) for i in range(len(matrix))]; matr\n",
    "def add_start_node(starts,ends, M):\n",
    "    row = [sum(M[i])* element_of(i, starts) for i in range(len(M))];\n",
    "    new_matrix = copy_matrix(M)\n",
    "    new_matrix.insert(0, row);\n",
    "    \n",
    "    for i in range(len(new_matrix)):\n",
    "        new_matrix[i].insert(0,0)\n",
    "    new_starts = [];\n",
    "    for i in starts:\n",
    "        new_starts.append(i+1)\n",
    "    new_ends = [];\n",
    "    for end in ends:\n",
    "        new_ends.append(end+1)\n",
    "    return (0, new_ends, new_matrix)\n",
    "\n",
    "def add_end_node(ends, M):\n",
    "    new_matrix = copy_matrix(M)\n",
    "    for i in range(len(new_matrix)):\n",
    "        new_matrix[i].append(0)\n",
    "    for end in ends:\n",
    "        new_matrix[end][-1]+= sum_room_inputs(end, M)\n",
    "    new_matrix.append([0]*(len(M)+1))\n",
    "    return (len(new_matrix), new_matrix)\n",
    "\n",
    "#OK, so for matrix M[i][j] the vertices are the integers i\n",
    "get_vertices = lambda matrix: [i for i in range(len(matrix))]\n",
    "#Edges are the indicies i,j s.t. matrix[i][j]>0\n",
    "def get_edges(matrix):\n",
    "    e = [];\n",
    "    for i in range((len(matrix))):\n",
    "        for j in range(len(matrix)):\n",
    "            if matrix[i][j]>0:\n",
    "                e.append([i,j])\n",
    "    return e\n",
    "#test_edge = get_edges(test_m)\n",
    "\n",
    "def get_residual_capacity(graph, capacity, flow):\n",
    "    V, edges = graph;\n",
    "    len_vertices  = len(V)\n",
    "    c_f = [[0 for j in range(len_vertices)] for i in range(len_vertices)]\n",
    "    for i in edges:\n",
    "        u = i[0];\n",
    "        v = i[1];\n",
    "        c_f[u][v] = 1*capacity[u][v]- 1*flow[u][v];\n",
    "        c_f[v][u] = 1*flow[u][v]\n",
    "    return c_f\n",
    "\n",
    "def test_get_residual_graph_and_c_f(test_func):\n",
    "    graph =  ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 4], [5, 6], [6, 7]]) \n",
    "    capacity =  [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 2, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 6, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
    "    flow =  [[0, 14, 0, 0, 0, 0, 0, 0], [0, 0, 10, 4, 0, 0, 0, 0], [0, 0, 0, 0, 4, 6, 0, 0], [0, 0, 0, 0, 0, 4, 0, 0], [0, 0, 0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
    "    graph_f =  ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 3], [2, 3], [2, 5], [3, 5], [4, 6], [5, 4], [6, 7]]) \n",
    "    c_f_E_f =  [[0, 6, 0, 0, 0, 0, 0, 0], [14, 0, 0, 6, 0, 0, 0, 0], [0, 0, 0, 2, 0, 2, 0, 0], [0, 4, 0, 0, 0, 5, 0, 0], [0, 0, 0, 0, 0, 0, 6, 0], [0, 0, 6, 4, 6, 0, 0, 0], [0, 0, 0, 0, 4, 0, 0, 6], [0, 0, 0, 0, 0, 0, 14, 0]] \n",
    "    assert test_func(graph, capacity, flow) == (graph_f, c_f_E_f)\n",
    "test_get_residual_graph_and_c_f(get_residual_graph_and_c_f)\n",
    "\n",
    "def get_residual_graph_and_c_f(graph, capacity, flow):\n",
    "    V, E =(graph[0], graph[1])\n",
    "    vertices = copy_list(V);\n",
    "    c_f = get_residual_capacity((vertices, E), capacity, flow)\n",
    "    E_f = []\n",
    "    for u in range(len(V)):\n",
    "        for v in range(len(V)):\n",
    "            if c_f[u][v] >0 and element_of([u,v], E):\n",
    "                E_f.append([u,v])\n",
    "    c_f_E_f = get_residual_capacity((vertices, E_f), capacity, flow)\n",
    "    return ((vertices, E_f), c_f_E_f)\n",
    "\n",
    "\n",
    "def children(graph, u):\n",
    "    edges = graph[1];\n",
    "    childs = [];\n",
    "    for edge in edges:\n",
    "        if edge[0] == u:\n",
    "            childs.append(edge[1])\n",
    "    return childs\n",
    "def children_of_parents(graph, parents):\n",
    "    c = [];\n",
    "    for parent in parents:\n",
    "        c = c+ children(graph, parent)\n",
    "    return list(set(c))\n",
    "\n",
    "def distance(graph, s):\n",
    "    vertices, edges = graph\n",
    "    parents = [s];\n",
    "    Bool = True;\n",
    "    i = 0;\n",
    "    dists = [len(vertices)+1]*(len(vertices))\n",
    "    dists[0] = 0;\n",
    "    while Bool:\n",
    "        i+=1\n",
    "        children = children_of_parents(graph, parents)\n",
    "        if children == []:\n",
    "            Bool = False\n",
    "        for child in children:\n",
    "            dists[child] = min(dists[child], i)\n",
    "        parents = children\n",
    "        \n",
    "    return dists\n",
    "\n",
    "\n",
    "def test_get_level_graph_and_c_f(test_func ):\n",
    "    graph_f =  ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 4], [5, 6], [6, 7]]) \n",
    "    c_f_E_f = [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 2, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 6, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
    "    f_like = [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]\n",
    "    start = 0\n",
    "    graph_L = ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 6], [6, 7]])\n",
    "    c_f_E_L =  [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 0, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
    "\n",
    "    assert test_func(graph_f,c_f_E_f, f_like, start) == (graph_L, c_f_E_L)\n",
    "test_get_level_graph_and_c_f(get_level_graph_and_c_f)\n",
    "def get_level_graph_and_c_f(residual_graph, capacity, flow,s ):\n",
    "    start = s\n",
    "    V, E_f =(residual_graph[0], residual_graph[1])\n",
    "    vertices = copy_list(V);\n",
    "    E_L = [];\n",
    "    dists = distance(residual_graph, start)\n",
    "    for u in range(len(V)):\n",
    "        for v in range(len(V)):\n",
    "            if dists[v] == dists[u]+1 and element_of([u,v], E_f):\n",
    "                E_L.append([u,v])\n",
    "    c_f_E_L = get_residual_capacity((vertices, E_L), capacity, flow)\n",
    "    return ((vertices, E_L), c_f_E_L)\n",
    "\n",
    "def test_get_next_edge(test_func):\n",
    "    E_paths = [[0,1],[1,2],[1,3],[2,4],[3,4],[2,6]]\n",
    "    current_vertex = 1\n",
    "    assert test_func(current_vertex, E_paths) == [1,2]\n",
    "test_get_next_edge(get_next_edge)\n",
    "def get_next_edge(current_vertex, E_paths):\n",
    "    for edge in E_paths:\n",
    "        if edge[0]==current_vertex:\n",
    "            return edge\n",
    "    return None\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "def test_augment_flow_by_path(test_func):\n",
    "    path= [[0, 1], [1, 3], [3, 5], [5, 6], [6, 7]]\n",
    "    capacity =   [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 0, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]]\n",
    "\n",
    "    blocked_flow =  [[0, 10, 0, 0, 0, 0, 0, 0], [0, 0, 10, 0, 0, 0, 0, 0], [0, 0, 0, 0, 4, 6, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 0, 6, 0], [0, 0, 0, 0, 0, 0, 0, 10], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
    "    f = [[0, 14, 0, 0, 0, 0, 0, 0], [0, 0, 10, 4, 0, 0, 0, 0], [0, 0, 0, 0, 4, 6, 0, 0], [0, 0, 0, 0, 0, 4, 0, 0], [0, 0, 0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 0, 0, 0, 0]]\n",
    "    blocked_edge = [5, 6]\n",
    "    new_path = [[0, 1], [1, 3], [3, 5]]\n",
    "    test_func(path, blocked_flow, capacity) ==( f, blocked_edge, new_path)\n",
    "test_augment_flow_by_path(augment_flow_by_path)\n",
    "    \n",
    "def augment_flow_by_path(path, blocked_flow, capacity):\n",
    "    f = copy_matrix(blocked_flow)\n",
    "    new_path = []\n",
    "    capacity_along_path = min ([capacity[edge[0]][edge[1]]-f[edge[0]][edge[1]] for edge in path])\n",
    "\n",
    "    for edge in path:\n",
    "        f[edge[0]][edge[1]]+= capacity_along_path\n",
    "    \n",
    "    for edge in path:\n",
    "        u,v = edge\n",
    "        if f[u][v] == capacity[u][v]:\n",
    "            blocked_edge = edge\n",
    "            break\n",
    "        else:\n",
    "            new_path.append(edge)\n",
    "    return (f, blocked_edge, new_path)\n",
    "\n",
    "def test_find_blocking_flow(test_func):\n",
    "    graph =  ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 6], [6, 7]]) \n",
    "    flow =  [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
    "\n",
    "    capacity =  [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 0, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
    "    s = 0\n",
    "    t = 7\n",
    "    \n",
    "    assert test_func(graph,flow,capacity, s, t) == [[0, 14, 0, 0, 0, 0, 0, 0], [0, 0, 10, 4, 0, 0, 0, 0], [0, 0, 0, 0, 4, 6, 0, 0], [0, 0, 0, 0, 0, 4, 0, 0], [0, 0, 0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 0, 0, 0, 0]]\n",
    "\n",
    "\n",
    "def find_blocking_flow(graph, flow, capacity, s, t):\n",
    "    current_vertex = s\n",
    "    dists = distance(graph, s)\n",
    "    V = graph[0];\n",
    "    E_unblock = copy_matrix(graph[1])\n",
    "    blocked_flow = copy_matrix(flow)\n",
    "    current_path = []\n",
    "    while dists[-1] != len(dists)+1:\n",
    "        \n",
    "        next_edge = get_next_edge(current_vertex, E_unblock)\n",
    "        if next_edge == None:\n",
    "            E_unblock.remove(current_path[-1])\n",
    "            current_path.remove(current_path[-1])\n",
    "            if current_path ==[]:\n",
    "                current_vertex = s\n",
    "            else:\n",
    "                current_vertex = current_path[-1][1]\n",
    "        elif next_edge[1] == t:\n",
    "\n",
    "            current_path.append(next_edge)\n",
    "            blocked_flow, blocked_edge, current_path = augment_flow_by_path(current_path, blocked_flow, capacity)\n",
    "            current_vertex = blocked_edge[0]\n",
    "            E_unblock.remove(blocked_edge)\n",
    "\n",
    "        else:\n",
    "            current_vertex = next_edge[1]\n",
    "            current_path.append(next_edge)\n",
    "        dists = distance((V,E_unblock), s)\n",
    "    \n",
    "    return blocked_flow\n",
    "\n",
    "def test_solution(test_func):\n",
    "    starts, ends, matrix = [0],[5],[[0,10,10,0,0,0],[0,0,2,4,8,0],[0,0,0,0,9,0],[0,0,0,0,0,10],[0,0,0,6,0,10],[0,0,0,0,0,0]]\n",
    "    assert test_func(starts, ends, matrix)==19    \n",
    "\n",
    "def solution(starts, ends, matrix):\n",
    "    \n",
    "    mat = zero_out_end_rooms(ends, matrix)\n",
    "\n",
    "    start, ends, mat = add_start_node(starts, ends, mat)\n",
    "    end, mat = add_end_node(ends, mat)\n",
    "    V = get_vertices(mat)\n",
    "    E = get_edges(mat)\n",
    "    graph = (V,E)\n",
    "    flow = like_array(mat)\n",
    "    capacity = copy_matrix(mat)\n",
    "\n",
    "    D = 0\n",
    "    count = 0\n",
    "    while D< len(V)+1:\n",
    "        print(\"count is %s\" %count)\n",
    "        count+=1\n",
    "        print(\"graph is \\n %s \\n capacity is \\n %s \\n flow is \\n %s \\n\" %(graph, capacity, flow))\n",
    "        graph_f, c_f_E_f = get_residual_graph_and_c_f(graph, capacity, flow)\n",
    "        print(\"graph_f is \\n %s \\n c_f_E_f is \\n %s \\n \" %(graph_f, c_f_E_f))\n",
    "        f_like = like_array(flow)\n",
    "        \n",
    "        graph_L, c_f_E_L = get_level_graph_and_c_f(graph_f, c_f_E_f, copy_matrix(f_like), start)\n",
    "\n",
    "        D = distance(graph_L, 0)[end-1]\n",
    "        print(\"graph_L is \\n  %s c_f_E_L is \\n %s \\n    \"%(graph_L, c_f_E_L))\n",
    "        \n",
    "        blocking_flow = find_blocking_flow(graph_L, f_like, c_f_E_L, start,end-1)\n",
    "        flow = [ [ flow[i][j]+blocking_flow[i][j] for j in range(len(flow[0]))]for i in range(len(flow))  ]\n",
    "        \n",
    "    return sum([ i[-1] for i in flow ])\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "count is 0\n",
      "graph is \n",
      " ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 4], [5, 6], [6, 7]]) \n",
      " capacity is \n",
      " [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 2, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 6, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      " flow is \n",
      " [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      "\n",
      "graph_f is \n",
      " ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 4], [5, 6], [6, 7]]) \n",
      " c_f_E_f is \n",
      " [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 2, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 6, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      " \n",
      "graph_L is \n",
      "  ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 6], [6, 7]]) c_f_E_L is \n",
      " [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 0, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      "    \n",
      "count is 1\n",
      "graph is \n",
      " ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 4], [5, 6], [6, 7]]) \n",
      " capacity is \n",
      " [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 2, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 6, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      " flow is \n",
      " [[0, 14, 0, 0, 0, 0, 0, 0], [0, 0, 10, 4, 0, 0, 0, 0], [0, 0, 0, 0, 4, 6, 0, 0], [0, 0, 0, 0, 0, 4, 0, 0], [0, 0, 0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      "\n",
      "graph_f is \n",
      " ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 3], [2, 3], [2, 5], [3, 5], [4, 6], [5, 4], [6, 7]]) \n",
      " c_f_E_f is \n",
      " [[0, 6, 0, 0, 0, 0, 0, 0], [14, 0, 0, 6, 0, 0, 0, 0], [0, 0, 0, 2, 0, 2, 0, 0], [0, 4, 0, 0, 0, 5, 0, 0], [0, 0, 0, 0, 0, 0, 6, 0], [0, 0, 6, 4, 6, 0, 0, 0], [0, 0, 0, 0, 4, 0, 0, 6], [0, 0, 0, 0, 0, 0, 14, 0]] \n",
      " \n",
      "graph_L is \n",
      "  ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 3], [3, 5], [4, 6], [5, 4], [6, 7]]) c_f_E_L is \n",
      " [[0, 6, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 5, 0, 0], [0, 0, 0, 0, 0, 0, 6, 0], [0, 0, 0, 0, 6, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 6], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      "    \n",
      "count is 2\n",
      "graph is \n",
      " ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 5], [4, 6], [5, 4], [5, 6], [6, 7]]) \n",
      " capacity is \n",
      " [[0, 20, 0, 0, 0, 0, 0, 0], [0, 0, 10, 10, 0, 0, 0, 0], [0, 0, 0, 2, 4, 8, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 10, 0], [0, 0, 0, 0, 6, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      " flow is \n",
      " [[0, 19, 0, 0, 0, 0, 0, 0], [0, 0, 10, 9, 0, 0, 0, 0], [0, 0, 0, 0, 4, 6, 0, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 9, 0], [0, 0, 0, 0, 5, 0, 10, 0], [0, 0, 0, 0, 0, 0, 0, 19], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      "\n",
      "graph_f is \n",
      " ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 3], [2, 3], [2, 5], [4, 6], [5, 4], [6, 7]]) \n",
      " c_f_E_f is \n",
      " [[0, 1, 0, 0, 0, 0, 0, 0], [19, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 2, 0, 2, 0, 0], [0, 9, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 5, 1, 0], [0, 0, 6, 0, 1, 0, 0, 0], [0, 0, 0, 0, 9, 0, 0, 1], [0, 0, 0, 0, 0, 0, 19, 0]] \n",
      " \n",
      "graph_L is \n",
      "  ([0, 1, 2, 3, 4, 5, 6, 7], [[0, 1], [1, 3]]) c_f_E_L is \n",
      " [[0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]] \n",
      "    \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "19"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution([0],[5],[[0,10,10,0,0,0],[0,0,2,4,8,0],[0,0,0,0,9,0],[0,0,0,0,0,10],[0,0,0,6,0,10],[0,0,0,0,0,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Everything below is irrelevant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from copy import copy as copy\n",
    "#Assumption weak path equality :\n",
    "#\tEvery path to exit j from room i is as long as any other path.\n",
    "#Assumption path equality: \n",
    "#\tEvery path to an exit j and j' from room i have the same lengths. \n",
    "\n",
    "\n",
    "#Assumption start at start and end at end: There are no inputs into the start layer and the end layer\n",
    "#has no outputs. \n",
    "#We can enforce this by the following code\n",
    "def enforce_start_at_start_and_end_at_end(starts, ends, rooms):\n",
    "    new_rooms = rooms.copy()\n",
    "    for i in ends:\n",
    "        new_rooms[i] =[0]*len(new_rooms[i])\n",
    "    for i in starts:\n",
    "        for j in range(len(new_rooms)):\n",
    "            new_rooms[j][i] = 0\n",
    "    return new_rooms\n",
    "def test_enforce_start_at_start_and_end_at_end(test_function):\n",
    "    starts = [0];\n",
    "    ends = [3];\n",
    "    rooms = [[1,1,1,0], [1,0,3,0],[1,0,0,1],[1,0,0,1]]\n",
    "    ans = [[0, 1, 1, 0], [0, 0, 3, 0], [0, 0, 0, 1], [0, 0, 0, 0]]\n",
    "    assert test_function(starts, ends, rooms)\n",
    "test_enforce_start_at_start_and_end_at_end(enforce_start_at_start_and_end_at_end)\n",
    "\n",
    "#If we have path equality, then maybe things become trivial to solve. \n",
    "#\tSupposing this were true, then it would mean that we never have to worry about side channels going from room i to room j.\n",
    "#\tWe only have one set of paths that could do it, and all these paths are mutually exlusive? Or can be considered seperately \n",
    "#\tto one another? Or something? \n",
    "\n",
    "#\tBy this assumption, group together the starting layers. Then the layers that they feed into, and the ones that those feed \n",
    "#\tinto and so on.\n",
    "#\t\tTake in an array with the start layers at the beginning and the end layers at the end, with the end layers being [0]*n\n",
    "#\t\tSo we need a function that takes in the array and strips the goal layers.\n",
    "#\t\tAnother that re-arranges things so that the start and end layers are at the start and end. \n",
    "#\t\t\tIn order to do that, we need to reflect the swapped layers in the matrix values.\n",
    "#\t\t\tSo something that goes: take in the start arrays and make a new array with them at the beginning. Keep track of the \n",
    "#\t\t\tnew areas you've dispalced e.g. we have\n",
    "\n",
    "#\tWhat we really want is to have the input into all of the elements.\n",
    "#\tTo do that, we need the outputs of each layer in some array. \n",
    "def test_room_connects_to_X_rooms(test_function):\n",
    "    list_of_rooms =[ [0,0,0,1], [0,0,0,5], [0], [0,1,2]]\n",
    "    connections = [[3], [3], [], [1,2]]\n",
    "    for i in range(len(list_of_rooms)):\n",
    "        assert test_function(list_of_rooms[i]) == connections[i]\n",
    "\n",
    "def room_connects_to_X_rooms(room):\n",
    "    ls = [];\n",
    "    for i in range(len(room)):\n",
    "        if room[i] > 0:\n",
    "            ls.append(i)\n",
    "    return ls\n",
    "test_room_connects_to_X_rooms(room_connects_to_X_rooms)\n",
    "\n",
    "def test_room_connections(test_function):\n",
    "    list_of_rooms = [[0,1,1,0], [0,0,3,0],[0,0,0,1],[0,0,0,0]]\n",
    "    ans = [[1,2],[2],[3],[]]\n",
    "    assert test_function(list_of_rooms) == ans\n",
    "\n",
    "room_connections = lambda rooms: [room_connects_to_X_rooms(room) for room in rooms]\n",
    "test_room_connections(room_connections)\n",
    "#\t We are going to try and go through the rooms and limit their outputs by an upper bound of their inputs i.e.\n",
    "#\tsum_over_inputs_of_room_j(inputs_of_room_j[room_j])\n",
    "#\tWe can do the above via sum_room_inputs(room_index, rooms)\n",
    "\n",
    "def test_sum_room_inputs(test_function):\n",
    "    list_of_rooms_list=  [[[0,1,0,0],[0,0,1,1],[0,0,0,0],[0,0,0,0]], [[0,1,0,0],[0,0,1,1],[0,0,0,5],[0,0,0,0]]];\n",
    "    test_rooms = [0, 3];\n",
    "    ans = [0, 6]\n",
    "    for i in range(len(list_of_rooms_list)):\n",
    "        assert test_function(test_rooms[i], list_of_rooms_list[i]) == ans[i] \n",
    "\n",
    "def sum_room_inputs(room_index, rooms):\n",
    "    sum_inputs = 0;\n",
    "    for room in rooms:\n",
    "        sum_inputs += room[room_index];\n",
    "    return sum_inputs\n",
    "test_sum_room_inputs(sum_room_inputs)\n",
    "#\tNow, what we do is take in the starting rooms, find their outputs and for each output element calculate the inputs and \n",
    "#\tcap their outputs by their potential inputs.\n",
    "#\tThen we want to iterate through the outputs recursively and cap their outputs\n",
    "#\tUntil eventually we get to the case where all our outputs generate a list of ouputs that are type none. \n",
    "#\tThis is mutational, but we might be able to get a nice functional output out of this. \n",
    "#So, we could try doing something like \"get the capped outputs and after you have them, slap them onto some big array you have\"\n",
    "#But in order to do that faithfully, we need our outputs to not repeat and to have some indexing.\n",
    "\n",
    "#INCOMPLETE\n",
    "def cap_outputs_by_max_inputs_possible(layer, ends, rooms):\n",
    "    new_layer = []\n",
    "    inputs_to_new_layer = [];\n",
    "    for room_index in layer:\n",
    "        inputs_to_new_layer.append(sum_room_inputs(room_index, rooms))\n",
    "        \n",
    "    for room_index in layer:\n",
    "        new_layer += room_connects_to_X_rooms(rooms[room_index])\n",
    "    return inputs_to_new_layer\n",
    "    \n",
    "#This function takes the set of rooms, iterates through them and caps their outputs to each room they connect to by the total\n",
    "#outputs of the room they're conencting to.\n",
    "#ARGH, I got it wrong. You need to go through the rooms in reverse order. \n",
    "#Suppose you have six layers\n",
    "#[0 6 1 5 0 0]\n",
    "#[0 0 3 0 1 0]\n",
    "#[0 0 0 4 2 1]\n",
    "#[0 0 0 0 1 2]\n",
    "#[0 0 0 0 0 0]\n",
    "#[0 0 0 0 0 0]\n",
    "#Let layer 0 be the starting layer\n",
    "#Let 4,5 be the ending layer.\n",
    "#We can build up a DAG. We want to backwards traverse it, and visit only elements whose antecedants have been traversed\n",
    "#So come up with an algorithm for doing that I guess.\n",
    "#OK, so start with the ending layers [4,5]\n",
    "#Then generate the parents of [4,5]\n",
    "# 1,2,3 --> 4, 2,3 --> 5\n",
    "# So we have layers [1,2,3]\n",
    "#Now generate the layers that go into 1,2,3.\n",
    "#0--> 1, 0,1 --> 2  0,2 --> 3\n",
    "#The only element who's children have already been traversed \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def cap_inputs_by_max_outputs_possible(ends, rooms):    \n",
    "    \n",
    "    new_rooms = []\n",
    "    for room in rooms:\n",
    "        connected_indices = room_connects_to_X_rooms(room);\n",
    "        new_room = [0]*len(room)\n",
    "        for index in connected_indices:\n",
    "            next_room = rooms[index]\n",
    "            new_room[index] += (lambda output_of_next_room, output: output if output_of_next_room > output else output_of_next_room) (sum(next_room),room[index]) \n",
    "            new_room[index] += (lambda index: room[index] if sum( [index == end for end in ends]  ) else 0) (index)\n",
    "        new_rooms.append(new_room)\n",
    "    return new_rooms\n",
    "\n",
    "def test_cap_inputs_by_max_outputs_possible(test_function):\n",
    "    rooms = [[0, 10, 0],[0, 0, 2],[0,0,0]]\n",
    "    new_rooms = [[0, 2, 0], [0, 0, 2], [0, 0, 0]]\n",
    "    ends = [2]\n",
    "    assert new_rooms ==  test_function(ends, rooms)\n",
    "test_cap_inputs_by_max_outputs_possible(cap_inputs_by_max_outputs_possible)\n",
    "\n",
    "\n",
    "rooms = [[0,1,0,0],[0,0,1,1],[0,0,0,0],[0,0,0,0]]\n",
    "\n",
    "cap_outputs_by_max_inputs_possible([0], [2,3], rooms)\n",
    "\n",
    "#Also, you need to account for the fact that the total throughput at layers n must be lower than the total throughput at layers\n",
    "#n+1\n",
    "\n",
    "\n",
    "\n",
    "#How about this for an algorithm? \n",
    "#Suppose you have six  layers\n",
    "#[0 6 1 5 0 0]\n",
    "#[0 0 3 0 1 0]\n",
    "#[0 0 0 4 2 1]\n",
    "#[0 0 0 0 5 3]\n",
    "#[0 0 0 0 0 0]\n",
    "#[0 0 0 0 0 0]\n",
    "#Let layer 0 be the starting layer\n",
    "#Now what you want to do is max the outputs of layer 0.\n",
    "#Now we have the inputs as [0, 6, 1, 5, 0,0] i.e. we are outputting to layers [1,2,3]\n",
    "#Layer 1 is full an can max its outputs to layer 2 and 4\n",
    "#Layer 2 isn't maxed out and involves outputs to layer 3, 4 and 5. \n",
    "#Layer 3 isn't known to be maxed out either and involves output to layers 4 and 5.\n",
    "#We check if our output layers feed into one another. 1 --> 2 and 4, 2 --> 3,4,5, 3 --> 4,5\n",
    "#We check if any of our outputs are maxed out. These we can let flow through anyway because we've got no choice.\n",
    "#So drop off layer 1, and make it so our inputs are now\n",
    "# [0, 0, 4, 5, 1, 0] i.e. we are outputing to layers [2,3,4]\n",
    "#Layer 2 is not maxed out, neither is layer 3. Layer 4 infact is, and is a goal node. So we can drop layer four from \n",
    "#consideration BUT we attatch to total_output the value 1.\n",
    "#So we have\n",
    "#Now we have as inputs [0, 0, 4, 5, 0, 0] i.e. we are outputing to layers [2,3]\n",
    "#We have total_output = 1\n",
    "#Now we check if any of our layers have maxed out their inputs: answer, nope.\n",
    "#We also check if any of our layers can output to the goals.\n",
    "# 2 can output 4>3--> 3 total to the goals, three can output 8>5 --> 5 total.\n",
    "#So send as much as you can to the goals, add that to the total_ouput and remove the corresponding amounts from the \n",
    "#layer outputs, starting with the smallest\n",
    "#layer 2: [0 0 0 4 2 1] - > [0 0 0 4 0 0], input[2]-= 3, total_value += 3\n",
    "#layer 3: [0 0 0 0 5 3] - > [0 0 0 0 3 0], input[3]-= 5, total_value += 5\n",
    "#So our inputs are [0 0 4 0 0 0]\n",
    "#We check if any of our layers feed into one another. 2--> 3,4,5, 3--> 4,5\n",
    "#Layer 2 does feed into 3. \n",
    "#\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#This code passes the two visible tests.\n",
    "\n",
    "def bfs(matrix, source, destination):\n",
    "    traversed = [-1 for i in range(len(matrix))]\n",
    "    traversed[source] = source\n",
    "    queue = [source]\n",
    "    while len(queue) > 0:\n",
    "        top = queue.pop(0)\n",
    "        for i in range(len(matrix)):\n",
    "            if (matrix[top][i][1] - matrix[top][i][0]) != 0 and traversed[i] == -1:\n",
    "                if i == destination:\n",
    "                    # Get route\n",
    "                    traversed[destination] = top\n",
    "                    path = [destination]\n",
    "                    temp = destination\n",
    "                    while temp != source:\n",
    "                        temp = traversed[temp]\n",
    "                        path.append(temp)\n",
    "                    path.reverse()\n",
    "                    # Get flow value and update augmented graph\n",
    "                    temp = 1\n",
    "                    total = float(\"inf\")\n",
    "                    cur = source\n",
    "                    while temp != len(path):\n",
    "                        entry = matrix[cur][path[temp]]\n",
    "                        diff = abs(entry[1]) - entry[0]\n",
    "                        total = min(total, diff)\n",
    "                        cur = path[temp]\n",
    "                        temp += 1\n",
    "                    temp = 1\n",
    "                    cur = source\n",
    "                    while temp != len(path):\n",
    "                        entry = matrix[cur][path[temp]]\n",
    "                        if entry[1] < 0: # Already augmented need to flip\n",
    "                            entry[1] += total\n",
    "                        else:\n",
    "                            entry[0] += total\n",
    "                        entry = matrix[path[temp]][cur]\n",
    "                        if entry[1] <= 0: # Already augmented need to flip\n",
    "                            entry[1] -= total\n",
    "                        else:\n",
    "                            entry[0] += total\n",
    "                        cur = path[temp]\n",
    "                        temp += 1\n",
    "                    return True\n",
    "                else:\n",
    "                    traversed[i] = top\n",
    "                    queue.append(i)\n",
    "    return False\n",
    "\n",
    "def answer(entrances, exits, path):\n",
    "    max_val = sum(list(map(sum, path)))\n",
    "    aug = []\n",
    "    for i in range(len(path)):\n",
    "        aug.append([])\n",
    "        for j in range(len(path[i])):\n",
    "            aug[i].append([0, path[i][j]])\n",
    "        aug[i].append([0, 0])\n",
    "        if i in exits:\n",
    "            aug[i].append([0, max_val])\n",
    "        else:\n",
    "            aug[i].append([0, 0])\n",
    "    aug.append([])\n",
    "    aug.append([])\n",
    "    for i in range(len(path[0]) + 2):\n",
    "        if i in entrances:\n",
    "            aug[-2].append([0, max_val])\n",
    "        else:\n",
    "            aug[-2].append([0, 0])\n",
    "        aug[-1].append([0, 0])\n",
    "    while bfs(aug, len(aug)-2, len(aug)-1):\n",
    "        pass\n",
    "    total = 0\n",
    "    for i in range(len(aug)):\n",
    "        total += aug[-2][i][0]\n",
    "    return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "answer([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]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#This code passes the two visible tests.\n",
    "\n",
    "def bfs(matrix, source, destination):\n",
    "    len_matrix = len(matrix)\n",
    "    traversed = [-1]*len_matrix\n",
    "    traversed[source] = source\n",
    "    queue = [source]\n",
    "    while len(queue) > 0:\n",
    "        top = queue.pop(0)\n",
    "        for i in range(len(matrix)):\n",
    "            if (matrix[top][i][1] - matrix[top][i][0]) != 0 and traversed[i] == -1:\n",
    "                if i == destination:\n",
    "                    # Get route\n",
    "                    traversed[destination] = top\n",
    "                    path = [destination]\n",
    "                    temp = destination\n",
    "                    while temp != source:\n",
    "                        temp = traversed[temp]\n",
    "                        path.append(temp)\n",
    "                    path.reverse()\n",
    "                    # Get flow value and update augmented graph\n",
    "                    temp = 1\n",
    "                    total = float(\"inf\")\n",
    "                    cur = source\n",
    "                    while temp != len(path):\n",
    "                        entry = matrix[cur][path[temp]]\n",
    "                        diff = abs(entry[1]) - entry[0]\n",
    "                        total = min(total, diff)\n",
    "                        cur = path[temp]\n",
    "                        temp += 1\n",
    "                    temp = 1\n",
    "                    cur = source\n",
    "                    while temp != len(path):\n",
    "                        entry = matrix[cur][path[temp]]\n",
    "                        if entry[1] < 0: # Already augmented need to flip\n",
    "                            entry[1] += total\n",
    "                        else:\n",
    "                            entry[0] += total\n",
    "                        entry = matrix[path[temp]][cur]\n",
    "                        if entry[1] <= 0: # Already augmented need to flip\n",
    "                            entry[1] -= total\n",
    "                        else:\n",
    "                            entry[0] += total\n",
    "                        cur = path[temp]\n",
    "                        temp += 1\n",
    "                    return True\n",
    "                else:\n",
    "                    traversed[i] = top\n",
    "                    queue.append(i)\n",
    "    return False\n",
    "list_map = lambda f, ls: list(map(f, ls))\n",
    "\n",
    "def solution(entrances, exits, array):\n",
    "    max_val = sum(list_map(sum, array))\n",
    "    aug = []\n",
    "    for i in range(len(array)):\n",
    "        aug.append([])\n",
    "        for j in range(len(array[i])):\n",
    "            aug[i].append([0, array[i][j]])\n",
    "        aug[i].append([0, 0])\n",
    "        if i in exits:\n",
    "            aug[i].append([0, max_val])\n",
    "        else:\n",
    "            aug[i].append([0, 0])\n",
    "    aug.append([])\n",
    "    aug.append([])\n",
    "    for i in range(len(array[0]) + 2):\n",
    "        if i in entrances:\n",
    "            aug[-2].append([0, max_val])\n",
    "        else:\n",
    "            aug[-2].append([0, 0])\n",
    "        aug[-1].append([0, 0])\n",
    "    while bfs(aug, len(aug)-2, len(aug)-1):\n",
    "        pass\n",
    "    total = 0\n",
    "    for i in range(len(aug)):\n",
    "        total += aug[-2][i][0]\n",
    "    return total\n"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}