project1

import matplotlib.pyplot as plt
import time
import numpy as np
import sympy
from sympy import S, symbols
import random
from math import floor

def randomArray(totalNumbers,min,max):
    array = []
    while totalNumbers > 0:
        array.append(random.randrange(min,max))
        totalNumbers -= 1
    return array

def regressionCurve(x,y):
    # calculate polynomial
    p = np.polyfit(x, y, 3)
    f = np.poly1d(p)

    # calculate new x's and y's
    x_new = np.linspace(x[0], x[-1], 50)
    y_new = f(x_new)

    x = symbols("x")
    poly = sum(S("{:6.5f}".format(v))*x**i for i, v in enumerate(p[::-1]))
    eq_latex = sympy.printing.latex(poly)
    
    plt.plot(x_new, y_new, label="${}$".format(eq_latex))
    plt.legend(fontsize="small")
    plt.show()

def enumeration(array):
    max = None
    to_return = (max, 0, 0)
    for i in range(0, len(array) + 1):
        for j in range(0, i):
            currentSum = 0
            for k in range(j, i):
                currentSum += array[k]
                if (max is None) or (currentSum > max):
                    max = currentSum
                    to_return = (max, j, k)	
    return to_return

def betterEnumeration(array):
    max = None
    to_return = (max, 0, 0)
    for i in range(1, len(array) + 1):
        currentSum = 0
        for j in range(i, len(array) + 1):
            currentSum += array[j - 1]
            if (max is None) or (currentSum > max):
                max = currentSum		
                to_return = (max, i-1, j-1)    
    return to_return

def divideConquer(A, i, j):
    if i == j:
        return (A[i], i, j)
    else:
        mid = int(floor((i+j)/2))
        left = divideConquer(A, i, mid)
        right = divideConquer(A, mid+1, j)
        across = crossmid(A, i, j, mid)
        if left[0] >= right[0] and left[0] >= across[0]:
            return left
        elif right[0] >= left[0] and right[0] >= across[0]:
            return right
        else:
            return across
   	 
def crossmid(A, i, j, mid):
    arraysum = 0
    max_left = float("-inf")
    index_left = mid
    for k in reversed(range(i, mid+1)):
        arraysum+=A[k]
        if max_left < arraysum:
            max_left = arraysum
            index_left = k
    arraysum = 0
    max_right = float("-inf")
    index_right = mid+1
    for k in range(mid+1, j+1):
        arraysum += A[k]
        if max_right < arraysum:
            max_right = arraysum
            index_right = k
    return (max_left + max_right, index_left, index_right)

def linearTime(array):
    max = None
    to_return = (max, 0, 0)
    maxNew = 0
    maxStartIndexNew = -1
    for i in range(len(array)):
        value = maxNew + array[i]
        if value > 0:
            if maxNew == 0:
                maxStartIndexNew = i
            maxNew = value
        else:
            maxNew = 0
        if max == None or maxNew > max:
            max = maxNew
            to_return = (max, maxStartIndexNew, i)
    return to_return

def chartEnumeration():
    nValues = [10,25,50,100,250,500,1000]
    avgExecTimes = []
    for n in nValues: # For each n value
        totals = []
        sum = 0
        avgExecTime = 0
        for i in range(0,10): # Create and test 10 random arrays
            executionTimes = []
            array = randomArray(n,0,10)
            t1 = time.clock()
            enumeration(array)
            t2 = time.clock()
            total = t2-t1
            totals.append(total)
            executionTimes.append(total)
            print("Time elapsed(n=" + str(n) + "): " + str(total))
        for t in totals: # Find avg running time for each n's 10 executions
            sum += t
        avgExecTime = sum/10
        avgExecTimes.append(avgExecTime)
        print("Avg execution time: " + str(avgExecTime))

    # Chart execution times
    plt.plot(nValues,avgExecTimes)
    plt.ylabel('Seconds')
    plt.xlabel('n')
    plt.show()

    # Chart curve that fits
    x = np.array(nValues)
    y = np.array(avgExecTimes)
    regressionCurve(x,y)
            
chartEnumeration()