def exchange(S, A, z):
    '''
    Input:
        - S: a list of vectors, as instances of your Vec class
        - A: a list of vectors, each of which are in S, with len(A) < len(S)
        - z: an instance of Vec such that A+[z] is linearly independent
    Output: a vector w in S but not in A such that Span S = Span ({z} U S - {w})
    Example:
        >>> S = [list2vec(v) for v in [[0,0,5,3],[2,0,1,3],[0,0,1,0],[1,2,3,4]]]
        >>> A = [list2vec(v) for v in [[0,0,5,3],[2,0,1,3]]]
        >>> z = list2vec([0,2,1,1])
        >>> exchange(S, A, z) == Vec({0, 1, 2, 3},{0: 0, 1: 0, 2: 1, 3: 0})
        True
    '''
    
    T=list()
    for e in S:
        if e not in A:
            T.append(e)
    U = superset_basis(A, S)
    for w in T:
        U.remove(w)
        mat = rowdict2mat(U)
        s = solve(mat,z)
        if z*s ==0:
            return w

def vM_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    from matutil import mat2rowdict, rowdict2mat

    a = mat2rowdict(A)
    m = rowdict2mat({k: v * B for (k, v) in a.items()})
    return m

def grayscale():
    '''
    Input: None
    Output: 3x3 greyscale matrix.
    '''
    labels = {'r', 'g', 'b'}
    return rowdict2mat({ i : Vec(labels, {'r' : 77/256, 'g' : 151/256, 'b' : 28/256} ) for i in labels })

def read_training_data(fname, D=None):
    """Given a file in appropriate format, and given a set D of features,
    returns the pair (A, b) consisting of 
    a P-by-D matrix A and a P-vector b,
    where P is a set of patient identification integers (IDs).

    For each patient ID p,
      - row p of A is the D-vector describing patient p's tissue sample,
      - entry p of b is +1 if patient p's tissue is malignant, and -1 if it is benign.

    The set D of features must be a subset of the features in the data (see text).
    """
    file = open(fname)
    params = ["radius", "texture", "perimeter","area","smoothness","compactness","concavity","concave points","symmetry","fractal dimension"];
    stats = ["(mean)", "(stderr)", "(worst)"]
    feature_labels = set([y+x for x in stats for y in params])
    feature_map = {params[i]+stats[j]:j*len(params)+i for i in range(len(params)) for j in range(len(stats))}
    if D is None: D = feature_labels
    feature_vectors = {}
    patient_diagnoses = {}
    for line in file:
        row = line.split(",")
        patient_ID = int(row[0])
        patient_diagnoses[patient_ID] = -1 if row[1]=='B' else +1
        feature_vectors[patient_ID] = Vec(D, {f:float(row[feature_map[f]+2]) for f in D})
    return rowdict2mat(feature_vectors), Vec(set(patient_diagnoses.keys()), patient_diagnoses)

def grayscale():
    '''
    Input: None
    Output: 3x3 greyscale matrix.
    '''
    labels = {'r','g','b'}
    row = Vec(labels,{'r':77/256, 'g':151/256, 'b':28/256})
    return(rowdict2mat({'r':row,'g':row,'b':row}))

def vM_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    import matutil
    from matutil import mat2rowdict
    from matutil import rowdict2mat

    mat2row_A = mat2rowdict(A)
    return rowdict2mat({key: v * B for (key, v) in zip(mat2row_A.keys(), mat2row_A.values())})

def vM_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    from matutil import mat2rowdict
    from matutil import rowdict2mat
    rows = mat2rowdict(A)
    for row,rowVec in rows.items():
    	rows[row] = rowVec*B
    return rowdict2mat(rows)

def make_matrix(feature_vectors, diagnoses, features):
    ids = feature_vectors.keys()

    # main constraints
    rows = {i: main_constraint(i, feature_vectors[i], diagnoses[i], features) for i in ids}
    # nonnegativity constraints
    rows.update({-i: Vec(A_COLS, {i: 1}) for i in ids})
    return rowdict2mat(rows)

def vM_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    output = {}
    from matutil import mat2rowdict
    from matutil import rowdict2mat
    A_row = mat2rowdict(A)
    for i in A.D[0]:
        output[i] = A_row[i] * B
    return rowdict2mat(output)

def vM_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]

    row_dict = matutil.mat2rowdict(A)

    foo_dict = {}
    for key, val in row_dict.items():
        foo_dict[key] = val * B

    return matutil.rowdict2mat(foo_dict)

def getL():
    xarray = [(358, 36), (329, 597), (592, 157), (580, 483)]
    warray = [(0,0), (0,1), (1,0), (1,1)]
    pairlist = [make_equations(x1,x2,w1,w2) for (x1,x2),(w1,w2) in zip(xarray, warray)]
    mymap = {}
    for i in range(len(pairlist)):
        mymap[2*i]=pairlist[i][0]
        mymap[2*i+1]=pairlist[i][1]
    mymap[8]=w
    return rowdict2mat(mymap)

def vM_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    v = mat2rowdict(A)
    l=[]
    d={}
    for (i,j) in v.items():
        s = j*B
        l.append(s)
        for e in l:
            d[i]=e
    return rowdict2mat(d)        

def grayscale():
    '''
    Input: None
    Output: 3x3 greyscale matrix.

    >>> grayscale() * Vec({'r','g','b'},{'r':1}) == Vec({'r','g','b'},{'r':77/256,'g':77/256,'b':77/256})
    True
    >>> grayscale() * Vec({'r','g','b'},{'b':2}) == Vec({'r','g','b'},{'r':56/256,'g':56/256,'b':56/256})
    True
    '''
    return rowdict2mat({colour:Vec({'r','g','b'},{ 'r': 77/256, 'g': 151/256, 'b': 28/256}) for colour in {'r','g','b'}})

def find_a_b(fname):
    data = read_vectors(fname)

    a_row_d = set(range(2))
    a_rows, b = [], Vec(set(range(len(data))), {})
    for i, v in enumerate(data):
        a_rows.append(Vec(a_row_d, {0: v['age'], 1:1}))
        b[i] = v['height']

    coeffs = QR_solve(rowdict2mat(a_rows), b)
    return (coeffs[0], coeffs[1])

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
		'''
		M = rowdict2mat(U_basis+V_basis)
		solution=solve(M.transpose(),w)
		zero=[zero_vec(U_basis[0].D)]
		uvec=solution*rowdict2mat(U_basis+zero*len(V_basis))
		vvec=solution*rowdict2mat(zero*len(U_basis)+V_basis)
		return (uvec,vvec)

def matrix_matrix_mul(A, B):
    "Returns the product of A and B"
    assert A.D[1] == B.D[0]
    from matutil import mat2rowdict, rowdict2mat

    row_vecs = mat2rowdict(A)
    row_dict = {}
    for row in A.D[0]:
        row_dict[row] = (vector_matrix_mul(row_vecs[row], B))
    matrix_product = rowdict2mat(row_dict)

    return matrix_product

def vM_mat_mat_mult(A, B):
    """
    >>> A = Mat(({0,1,2}, {0,1,2}), {(1,1):4, (0,0):0, (1,2):1, (1,0):5, (0,1):3, (0,2):2})
    >>> B = Mat(({0,1,2}, {0,1,2}), {(1,0):5, (2,1):3, (1,1):2, (2,0):0, (0,0):1, (0,1):4})
    >>> vM_mat_mat_mult(A,B) == Mat(({0,1,2}, {0,1,2}), {(0,0):15, (0,1):12, (1,0):25, (1,1):31})
    True
    >>> C = Mat(({0,1,2}, {'a','b'}), {(0,'a'):4, (0,'b'):-3, (1,'a'):1, (2,'a'):1, (2,'b'):-2})
    >>> D = Mat(({'a','b'}, {'x','y'}), {('a','x'):3, ('a','y'):-2, ('b','x'):4, ('b','y'):-1})
    >>> vM_mat_mat_mult(C,D) == Mat(({0,1,2}, {'x','y'}), {(0,'y'):-5, (1,'x'):3, (1,'y'):-2, (2,'x'):-5})
    True
    """
    assert A.D[1] == B.D[0]
    return rowdict2mat({x: row * B for x, row in mat2rowdict(A).items()})

def find_non_trivial_div(N):
    pr_lst = primes(10000)
    roots, rowlist = find_candidates(N, pr_lst)
    M = echelon.transformation_rows(rowlist, sorted(pr_lst, reverse=True))
    A = rowdict2mat(rowlist)
    for v in reversed(M):
        if not is_zero_vec(v*A):
            raise Exception("Unable to find non-trivial div")
        a, b = find_a_and_b(v, roots, N)
        div_candidate = gcd(a - b, N)
        if div_candidate != 1:
            return div_candidate
    raise Exception("Unable to find non-trivial div")

def lin_comb_mat_vec_mult(M, v):
    assert(M.D[1] == v.D)
    temp = {}
    from matutil import mat2coldict
    from matutil import rowdict2mat
    M_col = mat2coldict(M)
    for i in M.D[1]:
        temp[i] = v[i]*M_col[i]
    temp = rowdict2mat(temp)
    output = Vec(temp.D[1],{})
    for i in output.D:
        for j in temp.D[0]:
            output[i] = output[i] + temp[j,i]
    return output

def lin_comb_vec_mat_mult(v, M):
    assert(v.D == M.D[0])
    temp = {}
    from matutil import mat2rowdict
    from matutil import rowdict2mat
    M_row = mat2rowdict(M)
    for i in M.D[0]:
        temp[i] = v[i]*M_row[i]
    temp = rowdict2mat(temp)
    output = Vec(temp.D[1],{})
    for i in output.D:
        for j in temp.D[0]:
            output[i] = output[i] + temp[j,i]
    return output