import numpy as np
import itertools
np.random.seed(42)

def preprocess(X, y):
    """
    Perform mean normalization on the features and divide the true labels by
    the range of the column. 

    Input:
    - X: Inputs  (n features over m instances).
    - y: True labels.

    Returns a two vales:
    - X: The mean normalized inputs.
    - y: The scaled labels.
    """
    
    
    ###########################################################################
    # TODO: Implement the normalization function.                             #
    ###########################################################################
    
    
    X = (X - np.mean(X, axis=0)) / (np.max(X, axis=0) - np.min(X, axis=0))
    y = (y - np.mean(y)) / (np.max(y) - np.min(y))
    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
    return X, y

def compute_cost(X, y, theta):
    """
    Computes the average squared difference between an observation’s actual and
    predicted values for linear regression.  

    Input:
    - X: Inputs  (n features over m instances).
    - y: True labels (1 value over m instances).
    - theta: The parameters (weights) of the model being learned.

    Returns a single value:
    - J: the cost associated with the current set of parameters (single number).
    """
    
    J = 0  # Use J for the cost.
    ###########################################################################
    # TODO: Implement the MSE cost function.                                  #
    ###########################################################################
#     hypothesis = np.dot(X, theta)
#     diff = np.subtract(hypothesis,y)
#     J = np.sum(np.power(diff, 2)) / (2 * len(y))
    return np.sum(np.square(np.dot(X, theta) - y)) / ( 2 * len(y) )
#     ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
 #   return J

def gradient_descent(X, y, theta, alpha, num_iters):
    """
    Learn the parameters of the model using gradient descent. Gradient descent
    is an optimization algorithm used to minimize some (loss) function by 
    iteratively moving in the direction of steepest descent as defined by the
    negative of the gradient. We use gradient descent to update the parameters
    (weights) of our model.

    Input:
    - X: Inputs  (n features over m instances).
    - y: True labels (1 value over m instances).
    - theta: The parameters (weights) of the model being learned.
    - alpha: The learning rate of your model.
    - num_iters: The number of updates performed.

    Returns two values:
    - theta: The learned parameters of your model.
    - J_history: the loss value for every iteration.
    """                                                  
    
    J_history = [] # Use a python list to save cost in every iteration
    ###########################################################################
    # TODO: Implement the gradient descent optimization algorithm.            #
    ###########################################################################
    for i in range(num_iters):
        J_history.append(compute_cost(X, y, theta))
        theta = theta - ((np.dot(X.T, (np.dot(X, theta) - y))) * (alpha / len(y)))                                                                    
    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
    return theta, J_history

def pinv(X, y):
    """
    Calculate the optimal values of the parameters using the pseudoinverse
    approach as you saw in class.

    Input:
    - X: Inputs  (n features over m instances).
    - y: True labels (1 value over m instances).

    Returns two values:
    - theta: The optimal parameters of your model.

    ########## DO NOT USE numpy.pinv ##############
    """
    ###########################################################################
    # TODO: Implement the pseudoinverse algorithm.                            #
    ###########################################################################
    pinv = np.dot(np.linalg.inv(np.dot(X.T, X)), X.T)
    pinv_theta = np.dot(pinv, y)
    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
    return pinv_theta

def efficient_gradient_descent(X, y, theta, alpha, num_iters):
    """
    Learn the parameters of your model, but stop the learning process once
    the improvement of the loss value is smaller than 1e-8. This function is
    very similar to the gradient descent function you already implemented.

    Input:
    - X: Inputs  (n features over m instances).
    - y: True labels (1 value over m instances).
    - theta: The parameters (weights) of the model being learned.
    - alpha: The learning rate of your model.
    - num_iters: The number of updates performed.

    Returns two values:
    - theta: The learned parameters of your model.
    - J_history: the loss value for every iteration.
    """
    
    J_history = [] # Use a python list to save cost in every iteration
    ###########################################################################
    # TODO: Implement the gradient descent optimization algorithm.            #
    ###########################################################################
    prev_j = 0
    for i in range(num_iters):
        j = compute_cost(X, y, theta)
        J_history.append(j)
        # same as abs, looking for performance upgrades
        if np.abs(j - prev_j) < 1e-8:
            return theta, J_history
        theta = theta - ((np.dot(X.T, (np.dot(X, theta) - y))) * (alpha / len(y)))
        prev_j = j
    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
    return theta, J_history
    
    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################

def find_best_alpha(X, y, iterations):
    """
    Iterate over provided values of alpha and maintain a python dictionary 
    with alpha as the key and the final loss as the value.

    Input:
    - X: a dataframe that contains all relevant features.

    Returns:
    - alpha_dict: A python dictionary that hold the loss value after training 
    for every value of alpha.
    """
    
    alphas = [0.00001, 0.00003, 0.0001, 0.0003, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1, 2, 3]
    alpha_dict = {}
    ###########################################################################
    # TODO: Implement the function.                                           #
    ###########################################################################
    theta = np.random.random(size=2)
    alpha_dict = {alpha: efficient_gradient_descent(X, y, theta,alpha, iterations)[1][-1] for alpha in alphas}

    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
    return alpha_dict

def generate_triplets(X):
    """
    generate all possible sets of three features out of all relevant features
    available from the given dataset X. You might want to use the itertools
    python library.

    Input:
    - X: a dataframe that contains all relevant features.

    Returns:
    - A python list containing all feature triplets.
    """
    
    triplets = []
    ###########################################################################
    # TODO: Implement the function.                                           #
    ###########################################################################
    triplets = list(itertools.combinations(X, 3))
    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
    return triplets

def find_best_triplet(df, triplets, alpha, num_iter):
    """
    Iterate over all possible triplets and find the triplet that best 
    minimizes the cost function. For better performance, you should use the 
    efficient implementation of gradient descent. You should first preprocess
    the data and obtain a array containing the columns corresponding to the
    triplet. Don't forget the bias trick.

    Input:
    - df: A dataframe that contains the data
    - triplets: a list of three strings representing three features in X.
    - alpha: The value of the best alpha previously found.
    - num_iters: The number of updates performed.

    Returns:
    - The best triplet as a python list holding the best triplet as strings.
    """
    best_triplet = None
    min_J = float('inf')
    ###########################################################################
    # TODO: Implement the function.                                           #
    ###########################################################################
    for triplet in triplets:
        X = np.array(df[list(triplet)])
        y = np.array(df.get('price'))
        X, y = preprocess(X,y)
        ones = np.ones(np.size(X,0)).reshape(-1,1)
        X = np.hstack((ones, X))
        mock_theta = np.ones(np.size(X,1))
        current_j = efficient_gradient_descent(X, y, mock_theta, alpha, num_iter)[1][-1]
        if (current_j < min_J):
            min_J = current_j
            best_triplet = triplet
        
    ###########################################################################
    #                             END OF YOUR CODE                            #
    ###########################################################################
    return best_triplet

