Solution to closestSequence2().py

def create_matrix(len_a, len_b):
    matrix = [0] * (len_a+1)
    for i in range(len_a+1):
        matrix[i] = [0] * (len_b+1)
    return matrix

def get_sequence_indices(matrix):
    len_row = len(matrix)
    len_col = len(matrix[0])

    output = []

    rowi = len_row-1
    colj = len_col-1
    while colj > 0:
        if(matrix[rowi][colj] < matrix[rowi][colj-1]):
            output.append(colj)
            rowi -= 1
        else:
            colj -= 1

    return output[::-1]

def print_matrix(matrix):
    for row in matrix:
        print(row)
    print()

def closestSequence2(a, b):
    len_a = len(a) + 1
    len_b = len(b) + 1

    #just used for understanding the output
    delta_matrix = create_matrix(len(a), len(b))
    for rowi in range(1,len_a):
        for colj in range(1,len_b):
            delta_matrix[rowi][colj] = abs(a[rowi-1] - b[colj-1])

    print("delta matrix:")
    print_matrix(delta_matrix)

    #lets build the matrix
    matrix = create_matrix(len(a), len(b))

    #fill first row with 0
    for rowi in range(1,len_a):
        matrix[rowi][0] = 0

    #fill first column with 0
    for colj in range(1,len_b):
        matrix[0][colj] = 0

    #fill [1,0] with a copy of the value from [1,1]
    matrix[1][0]= abs(a[0] - b[0])

    #fill out the diagonal going [+1,+1] from {0,1]
    #this represents the result if you just chose the subsequence of values 0 to len(a)
    for i in range(2,min(len_a, len_b)):
        rowi = i
        colj = i-1
        row = rowi - 1
        col = colj
        start_diff = abs(a[row] - b[col])
        start_diag = matrix[rowi - 1][colj - 1]
        matrix[rowi][colj]= start_diff + start_diag

    for rowi in range(1,len_a):
        for colj in range(rowi,len_b):
            row = rowi - 1
            col = colj - 1

            left = matrix[rowi][colj-1]
            diag = matrix[rowi - 1][colj-1]

            diff = abs(a[row] - b[col])

            if (diff + diag < left): #if this value is lesser than the one to the left, it is optimal, go with it
                matrix[rowi][colj] = diff + diag
            else:   #if the value to the left is lesser, optimal index came earlier, stick with it
                matrix[rowi][colj] = left

    print("solution matrix")
    print_matrix(matrix)

    sequence_indices = get_sequence_indices(matrix)

    #output results
    print()
    print("a =", a)
    print("b =", b)

    print()
    print("subsequence indices")
    print([x - 1 for x in sequence_indices])

    print()
    print("subsequence of b that is the closest difference between sequences of a and b")
    for i in range(0,len(sequence_indices)):
        index = sequence_indices[i]
        print(b[index-1]," ", end="")

    print()
    print("difference of the subsequences: ")
    print(matrix[len(a)][len(b)])

    return matrix[len(a)][len(b)]

    #end

a = [1, 2, 6]
b = [0, 1, 3, 4, 3]

a1        = [1,    2, 1, 2,    1, 2]
b1     = [3, 0, 0, 3, 0, 3, 3, 0, 0]
delta  = [   1,    1, 1, 1,    1, 2]

closestSequence2(a1,b1)


#   OUTPUT
#
#   delta matrix:
#   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
#   [0, 2, 1, 1, 2, 1, 2, 2, 1, 1]
#   [0, 1, 2, 2, 1, 2, 1, 1, 2, 2]
#   [0, 2, 1, 1, 2, 1, 2, 2, 1, 1]
#   [0, 1, 2, 2, 1, 2, 1, 1, 2, 2]
#   [0, 2, 1, 1, 2, 1, 2, 2, 1, 1]
#   [0, 1, 2, 2, 1, 2, 1, 1, 2, 2]
#   
#   solution matrix
#   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
#   [2, 2, 1, 1, 1, 1, 1, 1, 1, 1]
#   [0, 4, 4, 3, 2, 2, 2, 2, 2, 2]
#   [0, 0, 5, 5, 5, 3, 3, 3, 3, 3]
#   [0, 0, 0, 6, 6, 6, 4, 4, 4, 4]
#   [0, 0, 0, 0, 7, 7, 7, 6, 5, 5]
#   [0, 0, 0, 0, 0, 8, 8, 8, 8, 7]
#   
#   
#   a = [1, 2, 1, 2, 1, 2]
#   b = [3, 0, 0, 3, 0, 3, 3, 0, 0]
#   
#   subsequence indices
#   [1, 3, 4, 5, 7, 8]
#   
#   subsequence of b that is the closest difference between sequences of a and b
#   0  3  0  3  0  0  
#   difference of the subsequences: 
#   7


#FINAL SOLUTION WITHOUT PRINT STATEMENTS
def create_matrix(len_a, len_b):
    matrix = [0] * (len_a+1)
    for i in range(len_a+1):
        matrix[i] = [0] * (len_b+1)
    return matrix

def closestSequence2(a, b):
    len_a = len(a) + 1
    len_b = len(b) + 1

    #lets build the matrix
    matrix = create_matrix(len(a), len(b))

    #fill first row with 0
    for rowi in range(1,len_a):
        matrix[rowi][0] = 0

    #fill first column with 0
    for colj in range(1,len_b):
        matrix[0][colj] = 0

    #fill [1,0] with a copy of the value from [1,1]
    matrix[1][0]= abs(a[0] - b[0])

    #fill out the diagonal going [+1,+1] from {0,1]
    #this represents the result if you just chose the subsequence of values 0 to len(a)
    for i in range(2,min(len_a, len_b)):
        rowi = i
        colj = i-1
        row = rowi - 1
        col = colj
        start_diff = abs(a[row] - b[col])
        start_diag = matrix[rowi - 1][colj - 1]
        matrix[rowi][colj]= start_diff + start_diag

    for rowi in range(1,len_a):
        for colj in range(rowi,len_b):
            row = rowi - 1
            col = colj - 1

            left = matrix[rowi][colj-1]
            diag = matrix[rowi - 1][colj-1]

            diff = abs(a[row] - b[col])

            if (diff + diag < left): #if this value is lesser than the one to the left, it is optimal, go with it
                matrix[rowi][colj] = diff + diag
            else:   #if the value to the left is lesser, optimal index came earlier, stick with it
                matrix[rowi][colj] = left

    return matrix[len(a)][len(b)]