smooth_gradient_descent.py

# https://classroom.udacity.com/courses/cs373/lessons/48743150/concepts/487471330923
# -----------
# User Instructions
#
# Define a function smooth that takes a path as its input
# (with optional parameters for weight_data, weight_smooth,
# and tolerance) and returns a smooth path. The first and 
# last points should remain unchanged.
#
# Smoothing should be implemented by iteratively updating
# each entry in newpath until some desired level of accuracy
# is reached. The update should be done according to the
# gradient descent equations given in the instructor's note
# below (the equations given in the video are not quite 
# correct).
# -----------

from copy import deepcopy

# thank you to EnTerr for posting this on our discussion forum
def printpaths(path,newpath):
    for old,new in zip(path,newpath):
        print '['+ ', '.join('%.3f'%x for x in old) + \
               '] -> ['+ ', '.join('%.3f'%x for x in new) +']'

# Don't modify path inside your function.
path = [[0, 0],
        [0, 1],
        [0, 2],
        [1, 2],
        [2, 2],
        [3, 2],
        [4, 2],
        [4, 3],
        [4, 4]]

def get_min(path, newpath, alpha=1):
    min_v = 0
    for p,np in zip(path,newpath):
        px,py=p
        npx,npy=np
        min_v += (px-npx)**2 + (py-npy)**2
    
    for i in range(len(newpath)):
        if i > 0:
            min_v += alpha * ((newpath[i][0]-newpath[i-1][0])**2 + (newpath[i][1]-newpath[i-1][1])**2)
    
    return min_v
    
def diff(path, newpath):
    min_v = 0
    for p,np in zip(path,newpath):
        px,py=p
        npx,npy=np
        min_v += (px-npx)**2 + (py-npy)**2
    return min_v

def smooth(path, weight_data = 0.5, weight_smooth = 0.1, tolerance = 0.000001):

    # Make a deep copy of path into newpath
    newpath = deepcopy(path)

    #######################
    ### ENTER CODE HERE ###
    #######################
    last_min = get_min(path, newpath)
    cnt = 0
    done = False
    while not done:
        last_newpath = deepcopy(newpath)
        
        for i in range(len(newpath)):
            if i>0 and i< len(newpath)-1:
                nxl, nyl = newpath[i-1]
                nxr, nyr = newpath[i+1]
                nx,ny = newpath[i]
                x,y = path[i]
                newpath[i][0] = nx + weight_data * (x-nx) + weight_smooth * (nxl + nxr - 2*nx) 
                newpath[i][1] = ny + weight_data * (y-ny) + weight_smooth * (nyl + nyr - 2*ny)
    
        
        new_min = diff(last_newpath, newpath)
        if abs(new_min - last_min) < tolerance:
            done = True
        last_min = new_min
        #print last_min
       
    
    return newpath # Leave this line for the grader!

printpaths(path,smooth(path))