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: MEDIUM_HARD
Tags: Mathematics

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)


row = lambda m, r: m[r]
col = lambda m, c: [r[c] for r in m]
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):
		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])
		m = [[sum((xs[i] ** (p1 + p2) for i in range(N))) for p2 in range(P)] for p1 in range(P)]
		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)]
		for r in range(P):
			if m[r][r] == 0:
				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:
				m = row_mul(m, r, 1 / m[r][r])
			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):
		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))]
		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):
					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)
					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)))


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

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)])


def identity_matrix(n):
	I = zeros_matrix(n, n)
	for i in range(n):
		I[i][i] = 1.0
	return I

def invert_matrix(A, tol=None):
	n = len(A)
	AM = copy_matrix(A)
	I = identity_matrix(n)
	IM = copy_matrix(I)
	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

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)))