import numpy as np
from scipy.optimize import minimize
import scipy



m = 10 #m parameter from paper

def lamb(j, cs):
    return 1/m * sum(cs[i] for i in range(1, j))

    
#Computes f_j(alphas, alphat) in time O(m^2)
def fj(j, cs, l):
    part1 = 1-np.exp(-lamb(j, cs))
    part2 = 0
    for k in range(j, m+1):
        part2 += np.exp(-lamb(k, cs)) * (1-np.exp(-cs[k]/m)) * l/cs[k]
    return part1+part2


def evaluate_competitive_ratio(cs):
    for i in range(1, len(cs)):
        if cs[i]<cs[i-1]:
            raise Exception("Values are not increasing")
    
    competitive_ratio = 1-np.exp(-1/m * float(sum(cs)) )
    competitive_ratio = min(sum([np.exp(-lamb(k, cs)) * (1-np.exp(-cs[k]/m))/cs[k]  for k in range(1, m+1)]), competitive_ratio)

    for j in range(2, m+1): 
        alphat_bounds = [(cs[j-1],cs[j])]
        x0 = (cs[j-1]+cs[j])/2.0
        
        res = minimize(lambda l: fj(j, cs, l[0])/(1-np.exp(-l[0])), 
                       x0=x0, 
                       bounds=alphat_bounds)
        """As a sanity check, make sure res.fun <= a few values in the middle to make sure minimization worked"""
        for xx in np.linspace(alphat_bounds[0][0], alphat_bounds[0][1], 1000):
            assert res.fun <= fj(j, cs, xx)/(1-np.exp(-xx)), (alphat_bounds, xx, res)
        
        competitive_ratio = min(competitive_ratio, res.fun)
    return competitive_ratio
    
cs = [0.        , 0.07077646, 0.2268947 , 0.42146915, 0.60679691,
       0.8570195 , 1.17239753, 1.51036256, 1.9258193 , 2.88381902,
       3.97363258]
c = evaluate_competitive_ratio(cs)
print(c)