def QR_solve(A, b):
    '''
    Input:
        - A: a Mat
        - b: a Vec
    Output:
        - vector x that minimizes norm(b - A*x)
    Example:
        >>> domain = ({'a','b','c'},{'A','B'})
        >>> A = Mat(domain,{('a','A'):-1, ('a','B'):2,('b','A'):5, ('b','B'):3,('c','A'):1,('c','B'):-2})
        >>> Q, R = QR.factor(A)
        >>> b = Vec(domain[0], {'a': 1, 'b': -1})
        >>> x = QR_solve(A, b)
        >>> result = A.transpose()*(b-A*x)
        >>> result * result < 1E-10
        True
    '''
    from triangular import triangular_solve
    from QR import factor
    from matutil import mat2rowdict
    
    Q,R = factor(A)
    rowlist = [mat2rowdict(R)[v] for v in mat2rowdict(R)]
    label_list = sorted(A.D[1], key = repr)
    
    return triangular_solve(rowlist, label_list, b*Q)

def find_triangular_matrix_inverse(A): 
		'''
		input: An upper triangular Mat, A, with nonzero diagonal elements
		output: Inverse of A
		>>> 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
		'''
		(v,k)=(list(mat2rowdict(A).values()),list(mat2rowdict(A).keys()))
		return coldict2mat([triangular_solve(v,k,Vec(A.D[1], {e:1})) for e in A.D[1]])

def dot_prod_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    return Mat(
        (A.D[0], B.D[1]),
        {
            (row, col): matutil.mat2rowdict(A)[row] * matutil.mat2coldict(B)[col]
            for row in matutil.mat2rowdict(A)
            for col in matutil.mat2coldict(B)
        },
    )

def find_triangular_matrix_inverse(A): 
    '''
    input: An upper triangular Mat, A, with nonzero diagonal elements
    output: Inverse of A
    >>> 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
    '''
    cols = []
    i = identity(A.D[0], 1)
    i_cols = mat2coldict(i)
    for k in A.D[0]:
        cols.append( triangular_solve([ mat2rowdict(A)[k] for k in mat2rowdict(A) ], list(range(len(A.D[0]))), i_cols[k]) )
    return coldict2mat(cols)

def QR_solve(A, b):
    '''
    Input:
        - A: a Mat
        - b: a Vec
    Output:
        - vector x that minimizes norm(b - A*x)
    Example:
        >>> domain = ({'a','b','c'},{'A','B'})
        >>> A = Mat(domain,{('a','A'):-1, ('a','B'):2,('b','A'):5, ('b','B'):3,('c','A'):1,('c','B'):-2})
        >>> Q, R = QR.factor(A)
        >>> b = Vec(domain[0], {'a': 1, 'b': -1})
        >>> x = QR_solve(A, b)
        >>> result = A.transpose()*(b-A*x)
        >>> result * result < 1E-10
        True
    '''
    Q,R = factor(A)
    return triangular_solve(mat2rowdict(R),list(A.D[1]), Q.transpose()*b)

# test
#domain = ({'a','b','c'},{'A','B'})
#A = Mat(domain,{('a','A'):-1, ('a','B'):2,('b','A'):5, ('b','B'):3,('c','A'):1,('c','B'):-2})
#Q, R = factor(A)
#b = Vec(domain[0], {'a': 1, 'b': -1})
#x = QR_solve(A, b)
#result = A.transpose()*(b-A*x)
#print(result * result < 1E-10)

def dot_product_mat_vec_mult(M, v):
    assert M.D[1] == v.D
    result = Vec(M.D[0], {c: 0 for c in M.D[0]})
    rows = mat2rowdict(M)
    for k in M.D[0]:
        result.f[k] = rows[k] * v
    return result

def lin_comb_vec_mat_mult(v, M):
    assert v.D == M.D[0]
    result = Vec(M.D[1], {r: 0 for r in M.D[1]})
    rows = mat2rowdict(M)
    for k, value in v.f.items():
        result = result + value * rows[k]
    return result

def dot_product_mat_vec_mult(M, v):
    assert(M.D[1] == v.D)
    res = Vec(M.D[0], {})
    dct = matutil.mat2rowdict(M)
    for k,n in dct.items():
        res[k] = n * v
    return res

def lin_comb_vec_mat_mult(v, M):
    assert(v.D == M.D[0])
    res = Vec(M.D[1], {})
    dct = matutil.mat2rowdict(M)
    for k in v.D:
        res = res + v[k]*dct[k]
    return res

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 find_triangular_matrix_inverse(A):
    """
    input: An upper triangular Mat, A, with nonzero diagonal elements
    output: Inverse of A
    >>> 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
    """
    cd = list()
    label_list = list(mat2rowdict(A).keys())
    rowlist = list(mat2rowdict(A).values())
    for j in label_list:
        c = triangular_solve(rowlist, label_list, list2vec([1 if i == j else 0 for i in label_list]))
        cd.append(c)

    return coldict2mat(cd)

def find_triangular_matrix_inverse(A):
    """
    input: An upper triangular Mat, A, with nonzero diagonal elements
    output: Inverse of A
    >>> 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
    """
    I_col_dict = {i: Vec(A.D[0], {i: 1}) for i in A.D[1]}
    # def triangular_solve(rowlist, label_list, b):
    rowlist = list()
    label_list = list()
    from matutil import mat2rowdict

    rowdict = mat2rowdict(A)
    for key in rowdict.keys():
        label_list.append(key)
        rowlist.append(rowdict[key])

    B_coldict = dict()
    from triangular import triangular_solve

    for key in label_list:
        B_coldict[key] = triangular_solve(rowlist, label_list, I_col_dict[key])
    return coldict2mat(B_coldict)

def QR_solve(A, b):
    '''
    Input:
        - A: a Mat
        - b: a Vec
    Output:
        - vector x that minimizes norm(b - A*x)
    Example:
        >>> domain = ({'a','b','c'},{'A','B'})
        >>> A = Mat(domain,{('a','A'):-1, ('a','B'):2,('b','A'):5, ('b','B'):3,('c','A'):1,('c','B'):-2})
        >>> Q, R = QR.factor(A)
        >>> b = Vec(domain[0], {'a': 1, 'b': -1})
        >>> x = QR_solve(A, b)
        >>> result = A.transpose()*(b-A*x)
        >>> result * result < 1E-10
        True
    '''
    from QR import factor
    from triangular import triangular_solve
    from mat import transpose
    from matutil import mat2rowdict
    Q, R = factor(A)
    qT = Q.transpose()
    c = qT*b
    rows = [rowVec for index,rowVec in mat2rowdict(R).items()]
    colLabels = sorted(A.D[1], key=repr)
    x_hat = triangular_solve(rows,colLabels,c)
    return x_hat

def dot_prod_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    import vec, matutil
    A_dict = matutil.mat2rowdict(A)
    B_dict = matutil.mat2coldict(B)
    dp = {(i,j): A_dict[i]*B_dict[j] for j in B_dict.keys() for i in A_dict.keys()}
    return Mat((set(A_dict.keys()), set(B_dict.keys())), dp)

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
    '''
    I = {i:Vec(A.D[0],{i:1}) for i in A.D[1]}
    rl = list()
    ll = list()
    cd = dict()
    rd = mat2rowdict(A)
    for k,i in rd.items():
        ll.append(k)
        rl.append(rd[k])
    for k in ll:
        cd[k]= triangular_solve(rl,ll,I[k])
    return coldict2mat(cd)

def lin_comb_vec_mat_mult(v, M):
    assert(v.D == M.D[0])
    vc= matutil.mat2rowdict(M)
    nvc= {c: v[c] * vc[c] for c in v.D}
    snvc= {r: sum([nvc[c][r] for c in v.D]) for r in M.D[1]}
    return Vec(set(snvc.keys()), snvc)
    pass

def QR_solve(A, b):
    '''
    Input:
        - A: a Mat
        - b: a Vec
    Output:
        - vector x that minimizes norm(b - A*x)
    Example:
        >>> domain = ({'a','b','c'},{'A','B'})
        >>> A = Mat(domain,{('a','A'):-1, ('a','B'):2,('b','A'):5, ('b','B'):3,('c','A'):1,('c','B'):-2})
        >>> Q, R = QR.factor(A)
        >>> b = Vec(domain[0], {'a': 1, 'b': -1})
        >>> x = QR_solve(A, b)
        >>> result = A.transpose()*(b-A*x)
        >>> result * result < 1E-10
        True
    '''
    from triangular import triangular_solve
    from QR import factor
    from dictutil import dict2list
    from vecutil import vec2list

    Q,R = factor(A)
    b = Q.transpose()*b
    rowdict = mat2rowdict(R)
    rowlist = dict2list(rowdict, list(rowdict.keys()))
    x = triangular_solve(rowlist, list(rowlist[0].D), vec2list(b))
    return x

def lin_comb_vec_mat_mult(v, M):
    assert v.D == M.D[0]
    import matutil
    from matutil import mat2rowdict

    mat2row = mat2rowdict(M)
    return sum([getitem(v, key) * mat2row[key] for key in v.D])

def QR_solve(A, b):
    '''
    Input:
        - A: a Mat with linearly independent columns
        - b: a Vec whose domain equals the set of row-labels of A
    Output:
        - vector x that minimizes norm(b - A*x)
    Note: This procedure uses the procedure QR_factor, which in turn uses dict2list and list2dict.
           You wrote these procedures long back in python_lab.  Make sure the completed python_lab.py
           is in your matrix directory.
    Example:
        >>> domain = ({'a','b','c'},{'A','B'})
        >>> A = Mat(domain,{('a','A'):-1, ('a','B'):2,('b','A'):5, ('b','B'):3,('c','A'):1,('c','B'):-2})
        >>> Q, R = QR_factor(A)
        >>> b = Vec(domain[0], {'a': 1, 'b': -1})
        >>> x = QR_solve(A, b)
        >>> result = A.transpose()*(b-A*x)
        >>> result.is_almost_zero()
        True
    '''
    Q, R = QR_factor(A)
    R_rows = mat2rowdict(R)
    R_rows = [R_rows[r] for r in
              sorted(R_rows.keys(), key=repr)]
    return triangular_solve(R_rows,
                            sorted(A.D[1],key=repr),
                            Q.transpose()*b)

def least_squares(Q, R, b):
    R_rows = mat2rowdict(R)
    R_rows = [R_rows[r] for r in
              sorted(R_rows.keys(), key=repr)]
    return triangular_solve(R_rows,
                            sorted(R.D[1],key=repr),
                            Q.transpose()*b)