def direct_sum_decompose(U_basis, V_basis, w):
    '''
    input:  A list of Vecs, U_basis, containing a basis for a vector space, U.
    A list of Vecs, V_basis, containing a basis for a vector space, V.
    A Vec, w, that belongs to the direct sum of these spaces.
    output: A pair, (u, v), such that u+v=w and u is an element of U and
    v is an element of V.
    
    >>> U_basis = [Vec({0, 1, 2, 3, 4, 5},{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec({0, 1, 2, 3, 4, 5},{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec({0, 1, 2, 3, 4, 5},{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
    >>> V_basis = [Vec({0, 1, 2, 3, 4, 5},{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec({0, 1, 2, 3, 4, 5},{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
    >>> w = Vec({0, 1, 2, 3, 4, 5},{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
    >>> direct_sum_decompose(U_basis, V_basis, w) == (Vec({0, 1, 2, 3, 4, 5},{0: 2.0, 1: 4.999999999999972, 2: 0.0, 3: 0.0, 4: 1.0, 5: 0.0}), Vec({0, 1, 2, 3, 4, 5},{0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0, 5: 0.0}))
    True
    '''
    from hw4 import vec2rep
    U = coldict2mat(U_basis)
    V = coldict2mat(V_basis)
    sum = U_basis + V_basis
    sol_w = vec2rep(sum,w)
    lenU = len(U_basis)
    wu = list2vec ([ v for i, v in sol_w.f.items () if i <  lenU ])
    wv = list2vec ([ v for i, v in sol_w.f.items () if i >= lenU ])
    u = U*wu
    v = V*wv
    return (u,v)

def selectRandom():
    vecs =[(a0,b0)]
    for x in range(4):
        a = list2vec([randGF2() for x in range(6)])
        b = list2vec([randGF2() for x in range(6)])
        vecs.append((a,b))
    return vecs

def direct_sum_decompose(U_basis, V_basis, w):
    '''
    input:  A list of Vecs, U_basis, containing a basis for a vector space, U.
    A list of Vecs, V_basis, containing a basis for a vector space, V.
    A Vec, w, that belongs to the direct sum of these spaces.
    output: A pair, (u, v), such that u+v=w and u is an element of U and
    v is an element of V.

    >>> U_basis = [Vec({0, 1, 2, 3, 4, 5},{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec({0, 1, 2, 3, 4, 5},{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec({0, 1, 2, 3, 4, 5},{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
    >>> V_basis = [Vec({0, 1, 2, 3, 4, 5},{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec({0, 1, 2, 3, 4, 5},{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
    >>> w = Vec({0, 1, 2, 3, 4, 5},{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
    >>> direct_sum_decompose(U_basis, V_basis, w) == (Vec({0, 1, 2, 3, 4, 5},{0: 2.0, 1: 4.999999999999972, 2: 0.0, 3: 0.0, 4: 1.0, 5: 0.0}), Vec({0, 1, 2, 3, 4, 5},{0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0, 5: 0.0}))
    True
    '''
    #W_basis = U_basis + V_basis
    #rep_w = vec2rep(W_basis, w)

    #U = set(range(len(U_basis)))
    #rep_u = Vec(U,{u:rep_w[u] for u in U})
    #u = coldict2mat(U_basis)*rep_u

    #V = set(range(len(U_basis), len(rep_w.D)))
    #rep_v = Vec(V,{v:rep_w[v] for v in V})
    #v = coldict2mat(V_basis)*rep_v
    T  = U_basis + V_basis
    x  = vec2rep(T, w)
    rep= list(x.f.values())
    u1 = list2vec(rep[0:len(U_basis)])
    v1 = list2vec(rep[len(U_basis):len(T)])
    u  = rep2vec(u1,U_basis)
    v  = rep2vec(v1,V_basis)
    return (u,v)

def growSec():
	from independence import is_independent
	from itertools import combinations
	proven = [(a0,b0)]
	found = False
	while not found:
		t = [(list2vec([randGF2() for i in range(6)]),list2vec([randGF2() for i in range(6)])) for j in range(2)]
		vecs = proven + t
		if all(is_independent(list(sum(x,()))) for x in combinations(vecs,3)):
			found = True
			proven += t
	
	found1 = False
	while not found1:
		t1 = [(list2vec([randGF2() for i in range(6)]),list2vec([randGF2() for i in range(6)])) for j in range(2)]
		vecs1 = proven + t1
		if all(is_independent(list(sum(x,()))) for x in combinations(vecs1,3)): 
			found1 = True
			proven += t1
	
	return proven		
	
			
	
			
	
		
	
		
	
		

def choose_secret_vector(s,t):
    uFound = False
    u = list2vec([0,0,0,0,0,0])
    while not uFound:
        u = list2vec([randGF2() for i in range(6)])
        if a0*u == s and b0*u == t:
            uFound = True
    return u

def choose_secret_vector(s,t):
    #GF2 field elements s and t
    # output: a random 6 vector u such that a*u = s and b*u = t
    u = list2vec([randGF2() for x in range(6)])
    while a0 * u != s or b0 * u != t:
        u = list2vec([randGF2() for x in range(6)])

    return u

def bin2vect(n):
    num = bin(n)
    bin_list = [ one if x == '1' else 0 for x in num[2:]]
    if len(bin_list) < 6:
        new_lst = [0] * (6 - len(bin_list))
        new_lst.extend(bin_list)
        return list2vec(new_lst)
    return list2vec(bin_list)

def direct_sum_decompose(U_basis, V_basis, w):
    UV = coldict2mat(U_basis+V_basis)    
    U = coldict2mat(U_basis)    
    V = coldict2mat(V_basis)    
    W = solve(UV,w)    
    Wu = list2vec([v for i, v in W.f.items() if i < len(U_basis)])    
    Wv = list2vec([v for i, v in W.f.items() if i >= len(U_basis)])    
    u = U * Wu    
    v = V * Wv   
    return (u,v)

def test_rowlist2echelon():
  v1 = list2vec([0,2,3,4,5])
  v2 = list2vec([0,0,0,0,5])
  v3 = list2vec([1,2,3,4,5])
  v4 = list2vec([0,0,0,4,5])

  rowlist = [v1,v2,v3,v4]

  A = rowlist2echelon(rowlist)
  print(A)

def choose_tokens(a, b):
    tokens = [a, b]
    for _ in range(1000000):
        token_A = list2vec([randGF2() for _ in range(len(a0.D))])
        token_B = list2vec([randGF2() for _ in range(len(a0.D))])
        if is_token_pair_suitable(tokens, [token_A, token_B]):
            tokens = tokens + [token_A, token_B]
        if len(tokens) == 10:
            return tokens
    raise Exception("Unable to pick tokens")

def direct_sum_decompose(U_basis, V_basis, w):
    '''
    Input:
        - U_basis: a list of Vecs forming a basis for a vector space U
        - V_basis: a list of Vecs forming a basis for a vector space V
        - w: a Vec in the direct sum of U and V
    Output:
        - a pair (u, v) such that u + v = w, u is in U, v is in V
    Example:

        >>> D = {0,1,2,3,4,5}
        >>> U_basis = [Vec(D,{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec(D,{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec(D,{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
        >>> V_basis = [Vec(D,{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec(D,{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
        >>> w = Vec(D,{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
        >>> (u, v) = direct_sum_decompose(U_basis, V_basis, w)
        >>> (u + v - w).is_almost_zero()
        True
        >>> U_matrix = coldict2mat(U_basis)
        >>> V_matrix = coldict2mat(V_basis)
        >>> (u - U_matrix*solve(U_matrix, u)).is_almost_zero()
        True
        >>> (v - V_matrix*solve(V_matrix, v)).is_almost_zero()
        True
        >>> ww = Vec(D,{0: 2, 1: 5, 2: 51, 4: 1, 5: 7})
        >>> (u, v) = direct_sum_decompose(U_basis, V_basis, ww)
        >>> (u + v - ww).is_almost_zero()
        True
        >>> (u - U_matrix*solve(U_matrix, u)).is_almost_zero()
        True
        >>> (v - V_matrix*solve(V_matrix, v)).is_almost_zero()
        True
        >>> U_basis == [Vec(D,{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec(D,{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec(D,{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
        True
        >>> V_basis == [Vec(D,{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec(D,{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
        True
        >>> w == Vec(D,{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
        True
    '''

    UV_basis = U_basis + V_basis
    uv_w = basis.vec2rep(UV_basis,w)

    uv_values = list(uv_w.f.values())

    udims = len(U_basis)

    ux = list2vec(uv_values[:udims])
    vy = list2vec(uv_values[udims:])


    u = basis.rep2vec(ux, U_basis)
    v = basis.rep2vec(vy, V_basis)

    return (u,v)

def task2():

    row = [(a0, b0)] + [
        (list2vec([randGF2() for i in range(6)]), list2vec([randGF2() for i in range(6)])) for j in range(4)
    ]

    while not all(is_independent(list(sum(x, ()))) for x in combinations(row, 3)):
        row = [(a0, b0)] + [
            (list2vec([randGF2() for i in range(6)]), list2vec([randGF2() for i in range(6)])) for j in range(4)
        ]

    return row

def direct_sum_decompose(U_basis, V_basis, w):
    '''
    Input:
        - U_basis: a list of Vecs forming a basis for a vector space U
        - V_basis: a list of Vecs forming a basis for a vector space V
        - w: a Vec in the direct sum of U and V
    Output:
        - a pair (u, v) such that u + v = w, u is in U, v is in V
    Example:

        >>> D = {0,1,2,3,4,5}
        >>> U_basis = [Vec(D,{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec(D,{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec(D,{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
        >>> V_basis = [Vec(D,{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec(D,{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
        >>> w = Vec(D,{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
        >>> (u, v) = direct_sum_decompose(U_basis, V_basis, w)
        >>> (u + v - w).is_almost_zero()
        True
        >>> U_matrix = coldict2mat(U_basis)
        >>> V_matrix = coldict2mat(V_basis)
        >>> (u - U_matrix*solve(U_matrix, u)).is_almost_zero()
        True
        >>> (v - V_matrix*solve(V_matrix, v)).is_almost_zero()
        True
        >>> ww = Vec(D,{0: 2, 1: 5, 2: 51, 4: 1, 5: 7})
        >>> (u, v) = direct_sum_decompose(U_basis, V_basis, ww)
        >>> (u + v - ww).is_almost_zero()
        True
        >>> (u - U_matrix*solve(U_matrix, u)).is_almost_zero()
        True
        >>> (v - V_matrix*solve(V_matrix, v)).is_almost_zero()
        True
        >>> U_basis == [Vec(D,{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec(D,{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec(D,{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
        True
        >>> V_basis == [Vec(D,{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec(D,{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
        True
        >>> w == Vec(D,{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
        True
    '''
    U_V_basis = list(U_basis)
    U_V_basis.extend(V_basis)
    w_coordinates = vec2rep(U_V_basis, w)
    w_u_coord = list()
    w_v_coord = list()
    for n in range(len(U_V_basis)):
        if n < len(U_basis):
            w_u_coord.append(w_coordinates[n])
        else:
            w_v_coord.append(w_coordinates[n])

    u = rep2vec(list2vec(w_u_coord), U_basis)
    v = rep2vec(list2vec(w_v_coord), V_basis)
    return (u, v)

def pick_known_vectors(a, b):
    all = [ (a,b),None,None,None,None ]
    while True:
        for i in range(1,5):
            all[i] = (list2vec([ randGF2() for i in range(6) ]),
                      list2vec([ randGF2() for i in range(6) ]))
        ok = True
        for x,y,z in combinations(range(5), 3):
            L = [ all[x][0], all[x][1], all[y][0], all[y][1], all[z][0], all[z][1] ]
            if not is_independent(L):
                ok = False
                break
        if ok:
            return all

def helper():
    L0 = []
    while True:
        a1 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        b1 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        a2 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        b2 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        if is_independent ([a0, b0, a1, b1, a2, b2]) == True:
            break
        L0 = [a0, b0, a1, b1, a2, b2]
    while True:
        a3 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        b3 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        L1 = [a0, b0, a1, b1, a3, b3]
        L2 = [a0, b0, a2, b2, a3, b3]
        L3 = [a1, b1, a2, b2, a3, b3]
        if is_independent (L1) == True and is_independent (L2) == True and is_independent (L3) == True:
                break           
    while True:
        a4 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        b4 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
        L4 = [a0, b0, a1, b1, a4, b4]
        L5 = [a0, b0, a2, b2, a4, b4]
        L6 = [a1, b1, a2, b2, a4, b4]
        L7 = [a0, b0, a3, b3, a4, b4]
        L8 = [a1, b1, a3, b3, a4, b4]
        L9 = [a2, b2, a3, b3, a4, b4]
        if is_independent (L4) == True and is_independent (L5) == True and is_independent (L6) == True and is_independent (L7) == True and is_independent (L8) == True and is_independent (L9) == True:
            break
    return a0, b0, a1, b1, a2, b2, a3, b3, a4, b4

def random_select():
    while True:
     a1 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     b1 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     a2 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     b2 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     a3 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     b3 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     a4 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     b4 = list2vec([randGF2(),randGF2(),randGF2(),randGF2(),randGF2(),randGF2()])
     l1 = [a0,a1,a2,b0,b1,b2]
     l2 = [a0,a1,a3,b0,b1,b3]
     l3 = [a0,a1,a4,b0,b1,b4]
     l4 = [a0,a2,a3,b0,b2,b3]
     l5 = [a0,a2,a4,b0,b2,b4]
     l6 = [a0,a3,a4,b0,b3,b4]
     l7 = [a1,a2,a3,b1,b2,b3]
     l8 = [a1,a2,a4,b1,b2,b4]
     l9 = [a1,a3,a4,b1,b3,b4]
     l10 =[a2,a3,a4,b2,b3,b4]
     t1 = my_is_independent(l1);
     t2 = my_is_independent(l2);
     t3 = my_is_independent(l3);
     t4 = my_is_independent(l4);
     t5 = my_is_independent(l5);
     t6 = my_is_independent(l6);
     t7 = my_is_independent(l7);
     t8 = my_is_independent(l8);
     t9 = my_is_independent(l9);
     t10 = my_is_independent(l10);
     if t1 == True and t2 == True and t3 == True and t4 == True and t5 == True  and t6 == True and t7 == True and t8 ==True and t9 == True and t10 == True:
      return [a1,b1,a2,b2,a3,b3,a4,b4]

def direct_sum_decompose(U_basis, V_basis, w):
    """
    Input:
        - U_basis: a list of Vecs forming a basis for a vector space U
        - V_basis: a list of Vecs forming a basis for a vector space V
        - w: a Vec in the direct sum of U and V
    Output:
        - a pair (u, v) such that u + v = w, u is in U, v is in V
    Example:

        >>> D = {0,1,2,3,4,5}
        >>> U_basis = [Vec(D,{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec(D,{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec(D,{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
        >>> V_basis = [Vec(D,{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec(D,{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
        >>> w = Vec(D,{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
        >>> (u, v) = direct_sum_decompose(U_basis, V_basis, w)
        >>> (u + v - w).is_almost_zero()
        True
        >>> U_matrix = coldict2mat(U_basis)
        >>> V_matrix = coldict2mat(V_basis)
        >>> (u - U_matrix*solve(U_matrix, u)).is_almost_zero()
        True
        >>> (v - V_matrix*solve(V_matrix, v)).is_almost_zero()
        True
        >>> ww = Vec(D,{0: 2, 1: 5, 2: 51, 4: 1, 5: 7})
        >>> (u, v) = direct_sum_decompose(U_basis, V_basis, ww)
        >>> (u + v - ww).is_almost_zero()
        True
        >>> (u - U_matrix*solve(U_matrix, u)).is_almost_zero()
        True
        >>> (v - V_matrix*solve(V_matrix, v)).is_almost_zero()
        True
        >>> U_basis == [Vec(D,{0: 2, 1: 1, 2: 0, 3: 0, 4: 6, 5: 0}), Vec(D,{0: 11, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0}), Vec(D,{0: 3, 1: 1.5, 2: 0, 3: 0, 4: 7.5, 5: 0})]
        True
        >>> V_basis == [Vec(D,{0: 0, 1: 0, 2: 7, 3: 0, 4: 0, 5: 1}), Vec(D,{0: 0, 1: 0, 2: 15, 3: 0, 4: 0, 5: 2})]
        True
        >>> w == Vec(D,{0: 2, 1: 5, 2: 0, 3: 0, 4: 1, 5: 0})
        True
    """
    UV_basis = U_basis + V_basis
    UV_matrix = coldict2mat(UV_basis)
    U_matrix = coldict2mat(U_basis)
    V_matrix = coldict2mat(V_basis)
    x = solve(UV_matrix, w)
    list_x = list(x.f.values())
    # print(list_x)
    u = U_matrix * list2vec(list_x[0 : len(U_matrix.D[1])])
    v = V_matrix * list2vec(list_x[len(U_matrix.D[1]) :])
    return (u, v)

def choose_secret_vector(s,t):
    while True:
        secret = [ randGF2() for i in range(6) ]
        secret = list2vec(secret)
        print(secret)
        if a0 * secret == s and b0 * secret == t:
            return secret

def find_average_similarity(sen, sen_set, voting_dict):
    """
    Input: the name of a senator, a set of senator names, and a voting dictionary.
    Output: the average dot-product between sen and those in sen_set.
    Example:
        >>> vd = {'Klein': [1,1,1], 'Fox-Epstein': [1,-1,0], 'Ravella': [-1,0,0]}
        >>> find_average_similarity('Klein', {'Fox-Epstein','Ravella'}, vd)
        -0.5
    """
    from vecutil import list2vec
    _sum = 0
    vec0 = list2vec(voting_dict[sen])
    for sen_name in sen_set:
        vec1 = list2vec(voting_dict[sen_name])
        _sum += vec0 * vec1
    return _sum/len(sen_set)

def find_triangular_matrix_inverse(A):
    """
    Supporting GF2 is not required.

    Input:
        - A: an upper triangular Mat with nonzero diagonal elements
    Output:
        - Mat that is the inverse of A
    
    Example:
        >>> A = listlist2mat([[1, .5, .2, 4],[0, 1, .3, .9],[0,0,1,.1],[0,0,0,1]])
        >>> find_triangular_matrix_inverse(A) == Mat(({0, 1, 2, 3}, {0, 1, 2, 3}), {(0, 1): -0.5, (1, 2): -0.3, (3, 2): 0.0, (0, 0): 1.0, (3, 3): 1.0, (3, 0): 0.0, (3, 1): 0.0, (2, 1): 0.0, (0, 2): -0.05000000000000002, (2, 0): 0.0, (1, 3): -0.87, (2, 3): -0.1, (2, 2): 1.0, (1, 0): 0.0, (0, 3): -3.545, (1, 1): 1.0})
        True
    """
    res = []
    # print(A)
    n = len(A.D[0])
    row_vecs = mat2rowdict(A)
    rowlist = list(row_vecs.values())
    # print(rowlist)

    for i in range(n):
        b = list2vec([0] * i + [1] + [0] * (n - i - 1))
        x = triangular_solve(rowlist, list(A.D[0]), b)
        res.append(x)

    # print(coldict2mat(res))
    return coldict2mat(res)