def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for a user by performing least-squares linear regression using feature_fn
    on the items in restaurants. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(restaurant) for restaurant in restaurants]
    ys = [reviews_by_user[restaurant_name(restaurant)] for restaurant in restaurants]

    # BEGIN Question 7
    def sum(s1, s2):
        result = 0
        for a,b in zip(s1, s2):
            result += (a - mean(s1))*(b - mean(s2))
        return result

    S_xx = sum(xs,xs)
    S_yy = sum(ys, ys)
    S_xy = sum(xs, ys)

    b = S_xy/S_xx
    a = mean(ys) - b * mean(xs)
    r_squared = (S_xy*S_xy)/(S_xx*S_yy)
    # END Question 7
    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for a user by performing least-squares linear regression using feature_fn
    on the items in restaurants. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]

    x_avg, y_avg = mean(xs), mean(ys)
    Sxx, Syy = sum([(x-x_avg)**2 for x in xs]), sum([(y-y_avg)**2 for y in ys])
    x_y_pairs = zip(xs,ys)
    Sxy = sum([(pair[0]-x_avg)*(pair[1]-y_avg) for pair in x_y_pairs])

    b, r_squared = Sxy/Sxx, Sxy**2/(Sxx*Syy) 
    a = y_avg - b*x_avg

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

 def test_mean(self):
     """
     Test calculating arithmetic mean.
     """
     self.assertEqual(0, utils.mean([]))
     self.assertEqual(2.5, utils.mean([5, 0]))
     self.assertAlmostEqual(1.914213, utils.mean([8**0.5, 1]), places=5)

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for a user by performing least-squares linear regression using feature_fn
    on the items in restaurants. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]

    # BEGIN Question 7
    "*** REPLACE THIS LINE ***"
    mean_xs = mean(xs)
    mean_ys = mean(ys)
    list_x = [x - mean_xs for x in xs]
    list_y = [y - mean_ys for y in ys]
    sxx = sum( map(lambda x: x * x, list_x) )
    syy = sum( map(lambda y: y * y, list_y) )
    sxy = sum([a * b for a,b in zip (list_x, list_y)])

    b = sxy / sxx
    a = mean_ys - b * mean_xs
    r_squared =  (sxy ** 2) / (sxx * syy)
    # END Question 7

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for a user by performing least-squares linear regression using feature_fn
    on the items in restaurants. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}
    #print (reviews_by_user)

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]
    joined_list = zip(xs, ys)
    # BEGIN Question 7
    meanx = mean(xs)
    meany = mean(ys)
    sxx = sum([(x-meanx)**2 for x in xs])
    syy = sum([(y-meany)**2 for y in ys])
    sxy = sum([(xy[0]-meanx)*(xy[1]-meany) for xy in joined_list])

    b = sxy/ sxx
    a = meany - b * meanx
    r_squared = sxy**2 / (sxx * syy)
    # END Question 7

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_centroid(restaurants):
    """Return the centroid of the locations of RESTAURANTS."""
    "*** YOUR CODE HERE ***"
    locations = [restaurant_location(restaurant) for restaurant in restaurants]
    latitude = [location[0] for location in locations]
    longitude = [location[1] for location in locations]
    return [mean(latitude), mean(longitude)]

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for USER by performing least-squares linear regression using FEATURE_FN
    on the items in RESTAURANTS. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]
    
    mean_x = mean(xs)
    mean_y = mean(ys)

    sxx = sum([pow((feature_fn(r) - mean_x), 2) for r in restaurants])
    syy = sum([(pow((e - mean_y), 2)) for e in ys])
    lst_x = [(feature_fn(r) - mean_x) for r in restaurants] 
    lst_y = [(r - mean_y) for r in ys]
    sxy = sum([lst_x[i] * lst_y[i] for i in range(len(restaurants))])
    b = (sxy)/(sxx)
    a = (mean_y) - (b * mean_x) 
    r_squared = ((sxy)**2)/(sxx * syy)
    
    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for a user by performing least-squares linear regression using feature_fn
    on the items in restaurants. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]

    # BEGIN Question 7
    "*** REPLACE THIS LINE ***"
    # b, a, r_squared = 0, 0, 0  # REPLACE THIS LINE WITH YOUR SOLUTION
    mean_x = mean(xs)
    mean_y = mean(ys)
    xys = zip(xs, ys)
    sxx = sum([(x-mean_x) * (x-mean_x) for x in xs])
    syy = sum([(y-mean_y) * (y-mean_y) for y in ys])
    sxy = sum([(x-mean_x) * (y-mean_y) for x, y in xys])
    b = sxy / sxx
    a = mean_y - b * mean_x
    r_squared = sxy * sxy / (sxx * syy)
    # END Question 7

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def parametrize_approx(site,eta=1,tol=10**-2,mono=True,iterations=100000):
    L = len(sites[0])
    mono_fs = [lambda site,i=i,b=b:site[i]==b for i in range(L) for b in bases]
    di_fs = [lambda site,i=i,b1=b1,b2=b2:(site[i]==b1 and site[i+1]==b2)
             for i in range(L-1)
             for b1 in bases
             for b2 in bases]
    if mono:
        fs = mono_fs
    else:
        fs = di_fs
    ys = [mean(f(site) for site in sites) for f in fs]
    lambs = [1 for y in ys]
    err = 1
    while err > tol:
        site_chain = sample_dist(fs,lambs,iterations=iterations)
        yhats = [mean(fi(site) for site in site_chain)
                 for fi in fs]
        lambs_new = [lamb + (yhat - y)*eta for lamb,y,yhat in zip(lambs,ys,yhats)]
        for y,yhat,lamb,lamb_new in zip(ys,yhats,lambs,lambs_new):
            print y,"vs.",yhat,":",lamb,"->",lamb_new
        err = sum((y-yhat)**2 for y,yhat in zip(ys,yhats))
        print "err:",err
        lambs = lambs_new
    return lambs

def find_centroid(restaurants):
    """Return the centroid of the locations of RESTAURANTS."""
    "*** YOUR CODE HERE ***"
    list_locations = [restaurant_location(restaurant) for restaurant in restaurants]
    list_lat = [x[0] for x in list_locations]
    list_long = [y[1] for y in list_locations]
    return [mean(list_lat), mean(list_long)]

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for `user` by performing least-squares linear regression using `feature_fn`
    on the items in `restaurants`. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]

    # BEGIN Question 7
    "*** REPLACE THIS LINE ***"
    x_mean = mean(xs)
    y_mean = mean(ys)
    s_xx = sum([pow(x-x_mean,2) for x in xs])
    s_yy = sum([pow(y-y_mean,2) for y in ys])
    s_xy = sum([(x-x_mean)*(y-y_mean) for x,y in zip(xs,ys)])
    b, a, r_squared = s_xy/s_xx, y_mean - (s_xy/s_xx)*x_mean, (pow(s_xy,2))/(s_xx*s_yy)  # REPLACE THIS LINE WITH YOUR SOLUTION
    # END Question 7

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_centroid(restaurants):
    """Return the centroid of the locations of RESTAURANTS."""
    "*** YOUR CODE HERE ***"
    location_list=[restaurant_location(i) for i in restaurants]
    latitude=mean([i[0] for i in location_list])
    longitude=mean([i[1] for i in location_list])
    return [latitude,longitude]

def plot_results_dict_gini_qq(results_dict,filename=None):
    bios = []
    maxents = []
    uniforms = []
    for i,k in enumerate(results_dict):
        g1,g2,tf = k.split("_")
        genome = g1 + "_" + g2
        bio_motif = extract_tfdf_sites(genome,tf)
        bio_ic = motif_ic(bio_motif)
        bio_gini = motif_gini(bio_motif)
        d = results_dict[k]
        bios.append(bio_gini)
        maxents.append(mean(d['maxent']['motif_gini']))
        uniforms.append(mean(d['uniform']['motif_gini']))
    plt.scatter(bios,maxents,label='ME')
    plt.scatter(bios,uniforms,label='TURS',color='g')
    minval = min(bios+maxents+uniforms)
    maxval = max(bios+maxents+uniforms)
    plt.plot([minval,maxval],[minval,maxval],linestyle='--')
    plt.xlabel("Observed Gini Coefficient")
    plt.ylabel("Mean Sampled Gini Coefficient")
    plt.legend(loc='upper left')
    print "bio vs maxent:",pearsonr(bios,maxents)
    print "bio vs uniform:",pearsonr(bios,uniforms)
    maybesave(filename)

def evo_sim_experiment(filename=None):
    """compare bio motifs to on-off evosims"""
    tfdf = extract_motif_object_from_tfdf()
    bio_motifs = [getattr(tfdf,tf) for tf in tfdf.tfs]
    evosims = [spoof_motif(motif,num_motifs=100,Ne_tol=10**-4)
               for motif in tqdm(bio_motifs)]
    evo_ics = [mean(map(motif_ic,sm)) for sm in tqdm(evosims)]
    evo_ginis = [mean(map(motif_gini,sm)) for sm in tqdm(evosims)]
    evo_mis = [mean(map(total_motif_mi,sm)) for sm in tqdm(evosims)]
    plt.subplot(1,3,1)
    scatter(map(motif_ic,bio_motifs),evo_ics)
    plt.title("Motif IC (bits)")
    plt.xlabel("Biological Value")
    plt.ylabel("Simulated Value")
    plt.subplot(1,3,2)
    scatter(map(motif_gini,bio_motifs),
            evo_ginis)
    plt.title("Motif Gini Coefficient")
    plt.xlabel("Biological Value")
    plt.ylabel("Simulated Value")
    plt.subplot(1,3,3)
    scatter(map(total_motif_mi,bio_motifs),
            evo_mis)
    plt.xlabel("Biological Value")
    plt.ylabel("Simulated Value")
    plt.title("Pairwise Motif MI (bits)")
    plt.loglog()
    plt.tight_layout()
    plt.savefig(filename)
    return evosims

def experiment3(trials=10):
    mu = -10
    Ne = 5
    L = 10
    sigma = 1
    codes = [sample_code(L, sigma) for i in range(trials)]
    pssms = [sample_matrix(L, sigma) for i in range(trials)]
    sites = [random_site(L) for i in xrange(10000)]
    apw_site_sigmas = [sd([score(code,site) for site in sites]) for code in codes]
    linear_site_sigmas = [sd([score_seq(pssm,site) for site in sites]) for pssm in pssms]
    def apw_phat(code, site):
        ep = score(code, site)
        return 1/(1+exp(ep-mu))**(Ne-1)
    def apw_occ(code, site):
        ep = score(code, site)
        return 1/(1+exp(ep-mu))
    def linear_phat(pssm, site):
        ep = score_seq(pssm, site)
        return 1/(1+exp(ep-mu))**(Ne-1)
    def linear_occ(pssm, site):
        ep = score_seq(pssm, site)
        return 1/(1+exp(ep-mu))
    apw_mean_fits = [exp(mean(map(log10, mh(lambda s:apw_phat(code, s), proposal=mutate_site, x0=random_site(L),
                                          capture_state = lambda s:apw_occ(code, s))[1:])))
                         for code in tqdm(codes)]
    linear_mean_fits = [exp(mean(map(log10, mh(lambda s:linear_phat(pssm, s), proposal=mutate_site, x0=random_site(L),
                                             capture_state = lambda s:linear_occ(pssm, s))[1:])))
                        for pssm in tqdm(pssms)]
    plt.scatter(apw_site_sigmas, apw_mean_fits, label='apw')
    plt.scatter(linear_site_sigmas, linear_mean_fits, color='g',label='linear')
    plt.semilogy()
    plt.legend(loc='lower right')

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for a user by performing least-squares linear regression using feature_fn
    on the items in restaurants. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]

    # BEGIN Question 7
    xx, yy, sxy = [elem - mean(xs) for elem in xs], [elem - mean(ys) for elem in ys], 0
    # computes the standard deviations of x and y
    sxx, syy = sum(x**2 for x in xx), sum(y**2 for y in yy)
    for a, b in zip(xx, yy):
        sxy += a*b
    
    # finds a and b to solve for predictor function
    b = sxy/sxx
    a = mean(ys) - b*mean(xs)
    r_squared = sxy**2/(sxx*syy)
    # END Question 7

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for a user by performing least-squares linear regression using feature_fn
    on the items in restaurants. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]

    # BEGIN Question 7
    ave_xs = mean(xs)
    ave_ys = mean(ys)
    s_xx = sum([(x - ave_xs) ** 2 for x in xs])
    s_yy = sum([(y - ave_ys) ** 2 for y in ys])
    s_xy = sum([(x - ave_xs) * (y - ave_ys) for x, y in zip(xs, ys)])
    b, r_squared = s_xy / s_xx, s_xy ** 2 / (s_xx * s_yy)
    a = ave_ys - b * ave_xs
    # END Question 7

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for USER by performing least-squares linear regression using FEATURE_FN
    on the items in RESTAURANTS. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]
    mean_xs = mean(xs)
    mean_ys = mean(ys)

    s_xx = sum([pow(x - mean_xs, 2) for x in xs])
    s_yy = sum([pow(y - mean_ys, 2) for y in ys])
    s_xy = sum([mul(z[0], z[1]) for z in zip([x - mean_xs for x in xs], [y - mean_ys for y in ys])])

    b = s_xy / s_xx
    a = mean_ys - b * mean_xs
    r_squared = pow(s_xy, 2) / mul(s_xx, s_yy)

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared

def find_centroid(cluster):
    """Return the centroid of the locations of the restaurants in cluster."""
    locations = [restaurant_location(x) for x in cluster]
    lat = [x[0] for x in locations]
    lon = [x[1] for x in locations]
    centroid = [mean(lat), mean(lon)]
    return centroid

def find_predictor(user, restaurants, feature_fn):
    """Return a rating predictor (a function from restaurants to ratings),
    for USER by performing least-squares linear regression using FEATURE_FN
    on the items in RESTAURANTS. Also, return the R^2 value of this model.

    Arguments:
    user -- A user
    restaurants -- A sequence of restaurants
    feature_fn -- A function that takes a restaurant and returns a number
    """
    reviews_by_user = {review_restaurant_name(review): review_rating(review)
                       for review in user_reviews(user).values()}

    xs = [feature_fn(r) for r in restaurants]
    ys = [reviews_by_user[restaurant_name(r)] for r in restaurants]

    "*** YOUR CODE HERE ***"
    b, a, r_squared = 0, 0, 0  # REPLACE THIS LINE WITH YOUR SOLUTION
    

    mean_x = mean(xs) 
    mean_y = mean(ys)
    s_xx = sum([pow(x-mean_x,2) for x in xs]) 
    s_yy = sum([pow(y-mean_y,2) for y in ys]) 
    xy_pair = zip(xs,ys)
    s_xy = sum([(pair[0]-mean_x)*(pair[1]-mean_y) for pair in xy_pair]) 
    b = s_xy/s_xx 
    a = mean_y-b*mean_x
    r_squared = pow(s_xy,2)/(s_xx*s_yy)

    def predictor(restaurant):
        return b * feature_fn(restaurant) + a

    return predictor, r_squared