Your task is to build a model^(1) which can predict y-coordinate.
You can pass tests if predicted y-coordinates are inside error margin.

You will receive train set which should be used to build a model. 
After you build a model tests will call function ```predict``` and pass x to it. 

Error is going to be calculated with RMSE.


Side note: Points in test cases are from different polynomials (up to 5th degree).



Easier version: Data mining #1


Blocked libraries: sklearn, pandas, tensorflow, numpy, scipy

Explanation
[1] A mining model is created by applying an algorithm to data, but it is more than an algorithm or a metadata container: it is a set of data, statistics, and patterns that can be applied to new data to generate predictions and make inferences about relationships.

Difficulty: interview

Starter code:

def __init__(self, train_set):
	

Solutions:
from functools import reduce

class Datamining:

    def __init__(self, train_set):
        self.p = train_set[:5]
    
    def lagrange_interp(self, x):
        return sum(reduce(lambda p,n: p*n, [(x-xi)/(xj-xi) for (i,(xi,yi)) in enumerate(self.p) if j!=i], yj) for (j,(xj,yj)) in enumerate(self.p))
    
    def predict(self, x):
        return self.lagrange_interp(x)

# Matrix access functions
row = lambda m, r: m[r]
col = lambda m, c: [r[c] for r in m]

# Matrix row functions
row_mul = lambda m, r, coeff: [[v * coeff for v in row] if rr == r else row for rr, row in enumerate(m)]
row_add = lambda m, r1, r2, coeff=1: [[v1 + v2 * coeff for v1, v2 in zip(row, m[r2])] if rr == r1 else row for rr, row in enumerate(m)]

class Datamining:

    def __init__(self, train_set):
        """
        Given the training set build a set of polynomial regression coefficients
        Up to a maximum of degree 10.
        Yay for linear algebra!
        """
        N = len(train_set)
        P = N - 1
        P = min(10, P)
        xs, ys = [t[0] for t in train_set], [t[1] for t in train_set]
        
        # Build powers of xs[i]
        m = [[sum(xs[i] ** (p1 + p2) for i in range(N)) for p2 in range(P)] for p1 in range(P)]
        # Create augmented matrix with expected coefficients column
        r = [sum(ys[i] * xs[i] ** p for i in range(N)) for p in range(P)]
        m = [m[i] + [r[i]] for i in range(P)]
        
        # Perform Gaussian reduction
        for r in range(P):
            # Make current diagonal equal 1
            if m[r][r] == 0:
                # Oops this diagonal is zeo, so add another row
                vs = col(m, r)
                for rr, v in enumerate(vs):
                    if rr > r and v != 0:
                        break
                m = row_add(m, r, rr, 1/m[rr][r])
            else:
                # Multiply to get to value 1
                m = row_mul(m, r, 1/m[r][r])
            
            # Use current row to zero out other rows on same column
            for cr in range(P):
                if cr != r:
                    f = m[cr][r]
                    if f != 0:
                        m = row_add(m, cr, r, -f)

        self.coeffs = col(m, -1)
        print(("coeffs: {}".format([round(c, 4) for c in self.coeffs])))
        
    def predict(self, x):
        """Use calculated coefficients to predict next y given x"""
        return sum(c * (x ** p) for p, c in enumerate(self.coeffs))


def reduced_echelon_form(matrix):
    matrix = matrix[::]
    if not matrix: return
    lead = 0
    row_count = len(matrix)
    column_count = len(matrix[0])
    for r in range(row_count):
        if lead >= column_count:
            return matrix
        i = r
        while matrix[i][lead] == 0:
            i += 1
            if i == row_count:
                i = r
                lead += 1
                if column_count == lead:
                    return matrix
        matrix[i], matrix[r] = matrix[r], matrix[i]
        lv = matrix[r][lead]
        matrix[r] = [mrx / float(lv) for mrx in matrix[r]]
        for i in range(row_count):
            if i != r:
                lv = matrix[i][lead]
                matrix[i] = [iv - lv * rv for rv, iv in zip(matrix[r], matrix[i])]
        lead += 1

    return matrix

class Poly:
    def __init__(self, k, coef, lambda_=[1]):
        vector = [(_[1], e)for e, _ in enumerate( zip(range(0, k+1), coef) )]  # _[1]:coef
        self.poly = vector
        self.lambda_ = lambda_

    def eval_poly(self, x):
        return sum(l* pe[0]*x**pe[1] for pe, l in zip(self.poly, self.lambda_))

    def _to_string(self):
        s = ""
        for p, e in self.poly[::-1]:
            s += "{}{}x^{}" . format("+" if p>=0 else "", p, e)
        s = s.strip("+")
        return s

class Datamining:

    def __init__(self, train_set):
        self.train = train_set
        self.copy = train_set[::]
        self._learn()

    def _mse(self, corr, pred):
        s = [(c - p) ** 2 for c, p in zip(corr, pred)]
        return sum(s) / len(s)

    def frange(self, start, end, step):
        while start < end:
            yield start
            start += step

    def _learn(self):
        from random import shuffle
        train_perc = 0.65
        iterations = 18
        best = set()
        deg = 0
        lmbds = self.frange(0.7, 1.3, 0.1)
        degrees = range(2,6)
        for l in lmbds:
            for d in degrees:
                for iter in range(iterations):
                    # make matrix
                    # required deg+1 points
                    m = []
                    tmp = []
                    for p in self.train[:deg+1+d]:
                        x = p[0]
                        y = p[1]
                        tmp = [x**e for e in range(deg+1+d)]
                        tmp.append(y)
                        m.append(tmp)

                    # reduced form
                    mtx = reduced_echelon_form(m)
                    coef = [r[-1] for r in mtx]

                    shuffle(self.copy)

                    ntrain = int(len(self.copy)*train_perc)
                    train = self.copy[:ntrain]
                    test = self.copy[ntrain:]

                    poly = Poly(deg+d, coef, lambda_=[l for _ in range(deg+d)])
                    model = poly.eval_poly

                    predicted = [model(p[0]) for p in test]
                    correct = [p[1] for p in test]

                    best.add( (self._mse(predicted, correct), poly) )

        _, poly = min(best, key=lambda x: x[0])
        self.model = poly.eval_poly

    def predict(self, x):
        return self.model(x)

from functools import reduce

class Datamining:
    def __init__(self, train_set):
        self.s = train_set[:6]

    def predict(self, x):
        f = lambda j, x, xj: [(x - xi) / (xj - xi) for (i, (xi,yi)) in enumerate(self.s) if j != i]
        return sum(
            reduce(lambda s, n: s * n, f (j,x,xj), yj) for (j, (xj,yj)) in enumerate(self.s))

from functools import reduce

class Datamining:
    def __init__(self, train_set):
        self.s = train_set[:6]

    def predict(self, x):
        # Lagrange interpolating polynomial
        return sum(
            reduce(lambda s, n: s * n, [(x - xi) / (xj - xi) for (i, (xi,yi)) in enumerate(self.s) if j != i], yj) for
            (j, (xj,yj)) in enumerate(self.s))

def matrix_multiply(A,B):
    rowsA = len(A)
    colsA = len(A[0])
    rowsB = len(B)
    colsB = len(B[0])
    if colsA != rowsB:
        print('Number of A columns must equal number of B rows.')
        return
    C = [[0],
         [0],
         [0],
         [0],
         [0]]
    for i in range(rowsA):
        for j in range(colsB):
            total = 0
            for ii in range(colsA):
                total += A[i][ii] * B[ii][j]
            C[i][j] = total
    return C

def invert_matrix(A, tol=None):
    n = len(A)
    AM = A
    I = [[1,0,0,0,0],
          [0,1,0,0,0],
          [0,0,1,0,0],
          [0,0,0,1,0],
          [0,0,0,0,1]]
    IM = [[1,0,0,0,0],
          [0,1,0,0,0],
          [0,0,1,0,0],
          [0,0,0,1,0],
          [0,0,0,0,1]]
    indices = list(range(n))
    for fd in range(n):
        fdScaler = 1.0 / AM[fd][fd]
        for j in range(n):
            AM[fd][j] *= fdScaler
            IM[fd][j] *= fdScaler
        for i in indices[0:fd] + indices[fd+1:]: 
            crScaler = AM[i][fd]
            for j in range(n): 
                AM[i][j] = AM[i][j] - crScaler * AM[fd][j]
                IM[i][j] = IM[i][j] - crScaler * IM[fd][j]
    return IM

mean = lambda x: sum(x)/len(x)

class Datamining:

    def __init__(self, train_set):
        A = []
        v = []
        for k in range(5):
            v.append( [mean([y * x**k for x,y in train_set])] )
            A.append( [mean([x**(j+k) for x,y in train_set]) for j in range(5)] )
        B = invert_matrix(A)
        self.coefs = matrix_multiply(B,v)

    def predict(self, x):
        return sum([ a[0] * x**i for i,a in enumerate(self.coefs)])


class Datamining:

    def __init__(self, train_set):
        self.X = [s[0] for s in train_set[:6]]
        self.Y = [s[1] for s in train_set[:6]]
        

    def predict(self, x):
        y = 0
        for j in range(len(self.X)):
            Lj, xj = 1, self.X[j]
            for k in range(len(self.X)):
                xk = self.X[k]
                if xk != xj:
                    Lj *= (x-xk)/(xj-xk)
            y += Lj * self.Y[j]
        
        
        
        
        return y


from statistics import mean, pvariance
from copy import deepcopy

def matrix_transpose(m):
    return [list(i) for i in zip(*m)]
    
def matrix_matrix_multiply(a, b):
    n, p, m = len(a), len(b), len(b[0])
    c = [[0] * m for i in range(n)]
    
    for i in range(n):
        for j in range(m):
            for k in range(p):
                c[i][j] += a[i][k] * b[k][j]
                
    return c

def matrix_vector_multiply(a, b):
    n, p = len(a), len(b)
    c = [0] * n
    
    for i in range(n):
        for k in range(p):
            c[i] += a[i][k] * b[k]
            
    return c
    
# Very crude Gaussian elimination, little regard to performance or accuracy.
def matrix_solve(x, y):
    n, u, v = len(x), deepcopy(x), deepcopy(y)

    for i in range(n - 1):
        for j in range(i + 1, n):
            k = u[j][i] / u[i][i]
            u[j] = [a - k * b for a, b in zip(u[j], u[i])]
            v[j] = v[j] - k * v[i]

    for i in reversed(range(n)):
        v[i] = (v[i] - sum([v[j] * u[i][j] for j in range(i + 1, n)])) / u[i][i]

    return v
    
def features(x):
    return [1, x, x ** 2, x ** 3, x ** 4, x ** 5]
    
class Datamining:
    def __init__(self, train_set):
        x, y = zip(*train_set)
        
        design = [features(i) for i in x]
        t_design = matrix_transpose(design)
        
        cov = matrix_matrix_multiply(t_design, design)
         
        self.beta_hat = matrix_solve(cov, matrix_vector_multiply(t_design, y))

    def predict(self, x):
        z = features(x)
        
        return sum([a * b for a, b in zip(z, self.beta_hat)])


# https://integratedmlai.com/matrixinverse/
def identity_matrix(n):
    """
    Creates and returns an identity matrix.
        :param n: the square size of the matrix
        :returns: a square identity matrix
    """
    I = zeros_matrix(n, n)
    for i in range(n):
        I[i][i] = 1.0

    return I

def invert_matrix(A, tol=None):
    """
    Returns the inverse of the passed in matrix.
        :param A: The matrix to be inversed

        :return: The inverse of the matrix A
    """
    n = len(A)
    AM = copy_matrix(A)
    I = identity_matrix(n)
    IM = copy_matrix(I)

    # Section 3: Perform row operations
    indices = list(range(n)) # to allow flexible row referencing ***
    for fd in range(n): # fd stands for focus diagonal
        fdScaler = 1.0 / AM[fd][fd]
        # FIRST: scale fd row with fd inverse.
        for j in range(n): # Use j to indicate column looping.
            AM[fd][j] *= fdScaler
            IM[fd][j] *= fdScaler
        # SECOND: operate on all rows except fd row as follows:
        for i in indices[0:fd] + indices[fd+1:]:
            # *** skip row with fd in it.
            crScaler = AM[i][fd] # cr stands for "current row".
            for j in range(n):
                # cr - crScaler * fdRow, but one element at a time.
                AM[i][j] = AM[i][j] - crScaler * AM[fd][j]
                IM[i][j] = IM[i][j] - crScaler * IM[fd][j]
    return IM


def zeros_matrix(rows, cols):
    A = []
    for i in range(rows):
        A.append([])
        for j in range(cols):
            A[-1].append(0.0)
    return A

def copy_matrix(M):
    rows = len(M)
    cols = len(M[0])

    MC = zeros_matrix(rows, cols)

    for i in range(rows):
        for j in range(rows):
            MC[i][j] = M[i][j]

    return MC

def matrix_multiply(A,B):
    rowsA = len(A)
    colsA = len(A[0])

    rowsB = len(B)
    colsB = len(B[0])

    if colsA != rowsB:
        print('Number of A columns must equal number of B rows.')
        return

    C = zeros_matrix(rowsA, colsB)

    for i in range(rowsA):
        for j in range(colsB):
            total = 0
            for ii in range(colsA):
                total += A[i][ii] * B[ii][j]
            C[i][j] = total

    return C

def transposeMatrix(m):
    return list(map(list,list(zip(*m))))

class Datamining:
    def __init__(self, train_set, n=6):
        self.data = train_set
        self.n = n
        self.m = len(self.data)
        self.fit()

    def fit(self):
        X, ys = [], []
        for x, y in self.data:
            X.append([x ** i for i in range(self.n)])
            ys.append([y])
        Xt = transposeMatrix(X)
        iv = invert_matrix(matrix_multiply(Xt, X))
        R = matrix_multiply(iv, Xt)
        self.weights = matrix_multiply(R, ys)

    def predict(self, x):
        xs = [[x ** i for i in range(self.n)]]
        return matrix_multiply(xs, self.weights)[0][0]


def minv(mat):
    N=len(mat)
    for i in range(N):
        extra=[0]*N
        extra[i]=1
        mat[i].extend(extra)
    for i in range(N):
        for j in range(N):
            if i==j:continue
            mul=mat[j][i]/mat[i][i]
            for k in range(N*2):
                mat[j][k]-=mul*mat[i][k]
    for i in range(N):
        div=mat[i][i]
        for j in range(2*N):
            mat[i][j]/=div
    for i in range(N):
        del mat[i][:N]
    return mat


class Datamining:
    def __init__(self, train_set):
        self.N=len(train_set)
        if self.N<6: 
            return
        self.Xt=[[],[],[],[],[],[]]
        self.y=[]
        
        for i in train_set:
            for k in range(6):
                self.Xt[k].append(i[0]**k)
            self.y.append(i[1])
        
        self.XtX = [[0]*6 for i in range(6)]
        for i in range(6):
            for j in range(6):
                self.XtX[i][j]=sum(self.Xt[i][k]*self.Xt[j][k] for k in range(self.N))
        self.XtY = [0]*6
        for i in range(6):
            self.XtY[i] = sum(self.Xt[i][k]*self.y[k] for k in range(self.N))
        
        self.XtX1=minv(self.XtX)
        self.b=[0]*6
        for i in range(6):
            self.b[i] = sum(self.XtX1[i][k]*self.XtY[k] for k in range(6))
        

    def predict(self, x):
        if self.N==5: return 5
        return sum(self.b[i]*x**i for i in range(6))