def polynom(k):
    A = np.matrix(np.ones(len(x_train))).T
    for i in range(1, k + 1):
        l = [j**i for j in x_train]
        A = np.concatenate((np.matrix(l).T, A), axis=1)
    ps = np.linalg.inv(A.transpose() * A) * (A.transpose()) * (np.matrix(y_train).T)
    ps = np.squeeze(np.asarray(ps))
    return ps

def polynom_y(k):
    ps = polynom(k)
    answer = [0 for i in range(len(x_train))]
    for i in range(len(x_train)):
        for j in range(k + 1):
            answer[i] += (x_train[i] ** j) * ps[len(ps) - j - 1]
    return answer

def polynom_plot(k, x, y):
    xy = []
    for i in range(len(x_train)):
        xy.append([x[i], y[i]])
    plt.plot(*zip(*xy), marker='o', color='r', ls='')
    YD = polynom_y(k)
    plt.plot(x, YD)
    plt.show()

def polynom_formule(k):
    ps = polynom(k)
    answer = ''
    for i in range(len(ps) - 1):
        answer += '(' + str(ps[i]) + ')' + 'x^' + str(len(ps) - i - 1) + ' + '
    answer += str(ps[-1])
    print(answer)

def f(k, x, y):
    ps = polynom(k)
    answer = [0 for i in range(len(x))]
    for i in range(len(x)):
        for j in range(k + 1):
            answer[i] += (x[i] ** j) * ps[len(ps) - j - 1]
    ps = answer
    answer = 0
    for i in range(len(ps)):
        answer += (ps[i] - y[i])**2
    return answer / len(ps)