# Python module for calculating the newton polynom from given points
#                _ _   _               _
# __      ___ __(_) |_| |_ ___ _ __   | |__  _   _
# \ \ /\ / / '__| | __| __/ _ \ '_ \  | '_ \| | | |
#  \ V  V /| |  | | |_| ||  __/ | | | | |_) | |_| |
#   \_/\_/ |_|  |_|\__|\__\___|_| |_| |_.__/ \__, |
#                                            |___/
#  ____                  __     __               _
# / ___|_   _____ _ __   \ \   / /__   __ _  ___| |
# \___ \ \ / / _ \ '_ \   \ \ / / _ \ / _` |/ _ \ |
#  ___) \ V /  __/ | | |   \ V / (_) | (_| |  __/ |
# |____/ \_/ \___|_| |_|    \_/ \___/ \__, |\___|_|
#                                     |___/
# Licensed under the GPLv2 License, Version 2.0 (the "License");
# Copyright (c) Sven Vogel

def combine_n(points):
    k = len(points)

    if k == 1:
        return points[0][1]
    elif k == 2:
        return (points[1][1] - points[0][1]) / (points[1][0] - points[0][0])
    else:
        return (combine_n(points[1:k]) - combine_n(points[0:(k - 1)])) / (points[k - 1][0] - points[0][0])


# returns a polynom that will intersect all supplied points as long as
# the number of points is bigger than 1
def newton_polynom(points):
    polynom = ""
    for x in range(1, len(points)):

        if x == 1:
            polynom += '{r0:.2f} + '.format(r0=points[0][1])
        else:
            polynom += ' + '

        polynom += "{r:.2f}".format(r=combine_n(points[0:(x + 1)]))

        for y in range(x):
            polynom += " * (x - {value:.2f})".format(value=points[y][0])

    return polynom


def test():
    points = [[-1, 5], [2, -1], [3, -1], [4, 5], [8, 9]]
    print("newton polynom: ", newton_polynom(points))