import numpy as np


def f1(x):
    return -5 * x ** 5 + 4 * x ** 4 - 12 * x ** 3 + 11 * x ** 2 - 2 * x + 1


def f_1(x):
    return -25 * x ** 4 + 16 * x ** 3 - 36 * x ** 2 + 22 * x - 2


def o1(x):
    return f1(x), f_1(x)


def f2(x):
    return -np.log(x - 2) ** 2 + np.log(10 - x) ** 2 - x ** 0.2


def f_2(x):
    return -0.2 / x ** 0.8 - 2 * np.log(10 - x) / (10 - x) - 2 * np.log(x - 2) / (x - 2)


def o2(x):
    return f2(x), f_2(x)


def f3(x):
    return -3 * x * np.sin(0.75 * x) + np.exp(-2 * x)


def f_3(x):
    return -2 * np.exp(-2 * x) - 3*np.sin(x * 0.75) - 9./4 * x * np.cos(x * 0.75)


def o3(x):
    return f3(x), f_3(x)


def f4(x):
    return np.exp(3 * x) + 5 * np.exp(-2 * x)


def f_4(x):
    return 3 * np.exp(3 * x) - 10 * np.exp(-2 * x)


def o4(x):
    return f4(x), f_4(x)


def f5(x):
    return 0.2 * x * np.log(x) + (x - 2.3) ** 2


def f_5(x):
    return 0.2 * np.log(x) + 0.2 + 2 * (x - 2.3)


def o5(x):
    return f5(x), f_5(x)


def min_golden(func, a, b, tol=1e-5, max_iter=500, disp=False, trace=False):
    hist = {'x': [], 'f': [], 'n_evals': []}
    K = (5 ** 0.5 - 1) / 2
    I = np.zeros(max_iter + 2)
    I[0] = b - a
    I[1] = K * I[0]
    x_2, x_1 = a + I[1], b - I[1]
    f_1, f_2 = func(x_1), func(x_2)
    hist['n_evals'].append(2)
    for i in range(1, max_iter + 1):
        I[i + 1] = K * I[i]
        if f_1 >= f_2:
            if disp:
                print("{0} iteration, interval's length = {1}, function's min = {2}".format(*(i, I[i], f_2)))
            hist['x'].append(x_2)
            hist['f'].append(f_2)
            a, x_1 = x_1, x_2
            x_2 = a + I[i + 1]
            f_1, f_2 = f_2, func(x_2)
            hist['n_evals'].append(hist['n_evals'][-1] + 1)
        else:
            if disp:
                print("{0} iteration, interval's length = {1}, function's min = {2}".format(*(i, I[i], f_1)))
            hist['x'].append(x_1)
            hist['f'].append(f_1)
            x_2, b = x_1, x_2
            x_1 = b - I[i + 1]
            f_1, f_2 = func(x_1), f_1
            hist['n_evals'].append(hist['n_evals'][-1] + 1)
        if I[i + 1] < tol:
            return get_result(hist, 0, trace)
    return get_result(hist, 1, trace)


def min_parabolic(func, a, b, tol=1e-5, max_iter=500, disp=False, trace=False):
    hist = {'x': [], 'f': [], 'n_evals': []}
    x1, x2, x3 = a, (a + b) / 2., b
    f1, f2, f3 = func(x1), func(x2), func(x3)
    hist['n_evals'].append(3)
    I = np.zeros(max_iter + 2)
    I[0] = x3 - x1
    for i in range(1, max_iter + 1):
        num, den = get_min_parabolas(f1, f2, f3, x1, x2, x3)
        if abs(den) > 0:
            u = x2 - num / den
        else:
            return get_result(hist, 0, trace)
        f_u = func(u)
        hist['n_evals'].append(hist['n_evals'][-1] + 1)
        if f2 <= f_u:
            if x2 < u:
                x3, f3 = u, f_u
            else:
                x1, f1 = u, f_u
            hist['x'].append(x2)
            hist['f'].append(f2)
        else:
            if x2 < u:
                x1, x2 = x2, u
                f1, f2 = f2, f_u
            else:
                x2, f2, x3, f3 = u, f_u, x2, f2
            hist['x'].append(u)
            hist['f'].append(f_u)
        I[i] = x3 - x1
        if disp:
            print("{0} iteration, interval's length = {1}, function's min = {2}".format(*(i, I[i], hist['f'][-1])))
        if I[i] < tol:
            return get_result(hist, 0, trace)
    return get_result(hist, 1, trace)


def get_min_parabolas(f1, f2, f3, x1, x2, x3):
    num = (x2 - x1) ** 2 * (f2 - f3) - (x2 - x3) ** 2 * (f2 - f1)
    den = 2 * (x2 - x1) * (f2 - f3) - 2 * (x2 - x3) * (f2 - f1)

    return num, den


def check_for_inequal(v, x, w, tol):
    return abs(v - x) > tol and abs(x - w) > tol and abs(v - w) > tol


def min_brent(func, a, b, tol=1e-5, max_iter=500, disp=False, trace=False):
    hist = {'x': [], 'f': [], 'n_evals': []}
    a, c = a, b
    K = (3 - 5 ** 0.5) / 2
    x = w = v = a + K * (c - a)
    fx = fw = fv = func(x)
    hist['n_evals'].append(1)
    d = e = c - a
    I = np.zeros(max_iter + 2)
    I[0] = c - a
    u = 0
    for i in range(max_iter):
        g, e = e, d
        t = tol * abs(x) + tol / 10.
        if abs(x - (a + c) / 2) + (c - a) / 2 <= 2 * tol:
            return get_result(hist, 0, trace)
        parabolic_flag = True
        num, den = get_min_parabolas(fv, fx, fw, v, x, w)
        if abs(den) > 0 and check_for_inequal(v, x, w, tol) and check_for_inequal(fx, fv, fw, tol)\
                and a <= x + num / den <= c and abs(num / den) < g / 2.:
            u = x - num / den
            if u - a < 2 * t or c - u < 2 * t:
                u = x - np.sign(x - (a + c) / 2) * t
        else:
            parabolic_flag = False
        if not parabolic_flag:
            if x < (a + c) / 2:
                u = x + K * (c - x)
                e = c - x
            else:
                u = x - K * (x - a)
                e = x - a
        if abs(x - u) < t * 10 ** -5:
            u = x + np.sign(u - x) * t
        d = abs(u - x)
        fu = func(u)
        hist['n_evals'].append(hist['n_evals'][-1] + 1)
        if fu <= fx:
            if u >= x:
                a = x
            else:
                c = x
            v, w, x, fv, fw, fx = w, x, u, fw, fx, fu
        else:
            if u >= x:
                c = u
            else:
                a = u
            if fu <= fw or abs(x - w) <= 10 ** -10:
                v, w, fv, fw = w, u, fw, fu
            elif fu <= fv or abs(v - x) <= 10 ** -10 or abs(v - w) <= 10 ** -10:
                v, fv = u, fu
        hist['x'].append(x)
        hist['f'].append(fx)
        if disp:
            if parabolic_flag:
                print("{0} iteration, interval's length = {1}, function's min = {2}, parabolic".format(*(i + 1, I[i], hist['f'][-1])))
            else:
                print("{0} iteration, interval's length = {1}, function's min = {2}, golden".format(*(i + 1, I[i], hist['f'][-1])))
        I[i + 1] = c - a
    return get_result(hist, 1, trace)


def get_min_parabolas_der(f_1, f_2, x1, x2):
    a = (f_1 - f_2) / 2. / (x1 - x2)
    b = (f_1 * x2 - f_2 * x1) / (x2 - x1)
    return -b / 2. / a


def min_brent_der(func, a, b, tol=1e-5, max_iter=500, disp=False, trace=False):
    hist = {'x': [], 'f': [], 'n_evals': []}
    a, c = a, b
    x = w = v = (a + c) / 2
    fx, f_x = func(x)
    fw, fv, f_w, f_v = fx, fx, f_x, f_x
    hist['n_evals'].append(1)
    d = e = c - a
    I = np.zeros(max_iter + 2)
    I[0] = c - a
    for i in range(1, max_iter + 1):
        g, e, = e, d
        if abs(x - (a + c) / 2) + (c - a) / 2 <= 2 * (tol * abs(x) + tol / 10.):
            return get_result(hist, 0, trace)
        flag1 = flag2 = False
        if abs(x - w) > tol and abs(f_x - f_w) > tol:
            u1 = get_min_parabolas_der(f_x, f_w, x, w)
            if a <= u1 <= c and (u1 - x) * f_x <= 0 and abs(u1 - x) < g / 2.:
                flag1 = True
        if abs(x - v) > tol and abs(f_x - f_v) > tol:
            u2 = get_min_parabolas_der(f_x, f_v, x, v)
            if a <= u2 <= c and (u2 - x) * f_x <= 0 and abs(u2 - x) < g / 2.:
                flag2 = True
        if flag1 or flag2:
            if flag1 and flag2:
                if abs(u1 - x) < abs(u2 - x):
                    u = u1
                else:
                    u = u2
            else:
                if flag1:
                    u = u1
                else:
                    u = u2
        else:
            if f_x > 0:
                u, e = (a + x) / 2., x - a
            else:
                u, e = (x + c) / 2., c - x
        if abs(u - x) < tol * 10 ** -5:
            u = x + np.sign(u - x) * tol
        d = abs(x - u)
        fu, f_u = func(u)
        hist['n_evals'].append(hist['n_evals'][-1] + 1)
        if fu <= fx:
            if u >= x:
                a = x
            else:
                c = x
            v, w, x, fv, fw, fx, f_v, f_w, f_x = w, x, u, fw, fx, fu, f_w, f_x, f_u
        else:
            if u >= x:
                c = u
            else:
                a = u
            if fu <= fw or abs(w - x) < tol * 10 ** -5:
                v, w, fv, fw, f_v, f_w = w, u, fw, fu, f_w, f_u
            elif fu <= fv or abs(v - x) < tol * 10 ** -5 or abs(v - w) < tol * 10 ** -5:
                v, fv, f_v = u, fu, f_u
        hist['x'].append(x)
        hist['f'].append(fx)
        if disp:
            if flag1 or flag2:
                print("{0} iteration, interval's length = {1}, function's min = {2}, parabolic".format(*(i, I[i - 1], hist['f'][-1])))
            else:
                print("{0} iteration, interval's length = {1}, function's min = {2}, bisection".format(*(i, I[i - 1], hist['f'][-1])))
        I[i] = c - a
    return get_result(hist, 1, trace)


def get_min_cubic_der(f1, f2, f_1, f_2, x1, x2):
    z = 3 * (f1 - f2) / (x2 - x1) + f_1 + f_2
    if x1 < x2:
        w = (z ** 2 - f_1 * f_2) ** 0.5
    else:
        w = -(z ** 2 - f_1 * f_2) ** 0.5
    M = (f_2 + w - z) / (f_2 - f_1 + 2 * w)
    if M < 0:
        return x2
    elif M > 1:
        return x1
    else:
        return x2 - M * (x2 - x1)


def min_cubic(func, a, b, tol=1e-5, max_iter=500, disp=False, trace=False):
    hist = {'x': [], 'f': [], 'n_evals': []}
    x1, x2 = a, b
    f1, f_1 = func(x1)
    f2, f_2 = func(x2)
    hist['n_evals'].append(3)
    I = np.zeros(max_iter + 2)
    I[0] = x2 - x1
    for i in range(1, max_iter + 1):
        if I[i - 1] < tol:
            return get_result(hist, 0, trace)
        u = get_min_cubic_der(f1, f2, f_1, f_2, x1, x2)
        fu, f_u = func(u)
        hist['n_evals'].append(hist['n_evals'][-1] + 1)
        if f_u > 0:
            x2, f2, f_2 = u, fu, f_u
        else:
            x1, f1, f_1 = u, fu, f_u
        if f1 < f2:
            hist['x'].append(x1)
            hist['f'].append(f1)
        else:
            hist['x'].append(x2)
            hist['f'].append(f2)
        if disp:
            print("{0} iteration, interval's length = {1}, function's min = {2}".format(*(i, I[i - 1], hist['f'][-1])))
        I[i] = x2 - x1
        if abs(f_u) < tol:
            return get_result(hist, 0, trace)
    return get_result(hist, 1, trace)


def get_result(hist, status, trace):
    if trace:
        return hist['x'][-1], hist['f'][-1], status, {'x': np.array(hist['x']),
                                                      'f': np.array(hist['f']),
                                                      'n_evals': np.array(hist['n_evals'][1:])}
    else:
        return hist['x'][-1], hist['f'][-1], status