#!/usr/bin/python def printListOfList(l): """Just a nicer print method""" print("{") for row in l: print(row) print("}") def compute(left, top): """Use dynamic programming wow!""" horiz_pen = [] vert_pen = [] diag_pen = [] arrow = [] final = [] # Initialze left border for l in range(len(left)+1): final.append([]) final[l].append(-2*l) # Initialize top border for t in range(len(top)+1): if t != 0: final[0].append(-2*t) print('Initialized State:') printListOfList(final) # Work from the top down for l in range(len(left)): #Penalty lists start empty. We must create an empty list in preparation for the following for loop horiz_pen.append([]) vert_pen.append([]) diag_pen.append([]) arrow.append([]) #Work from the left to the right for t in range(len(top)): match_point = 1 if left[l] == top[t] else -1 horiz_pen[l].append(final[l][t+1] -2) vert_pen[l].append(final[l+1][t] -2) diag_pen[l].append(final[l][t] + match_point) mscore = max(horiz_pen[l][t], vert_pen[l][t], diag_pen[l][t]) if mscore == horiz_pen[l][t]: arrow[l].append('h') elif mscore == vert_pen[l][t]: arrow[l].append('v') elif mscore == diag_pen[l][t]: arrow[l].append('d') else: raise Exception('bad') final[l+1].append(mscore) print('horiz_pen') printListOfList(horiz_pen) print('vert_pen') printListOfList(vert_pen) print('diag_pen') printListOfList(diag_pen) print('final') printListOfList(final) print('arrow') printListOfList(arrow) if __name__ == '__main__': compute('CGATCG', 'CAAGAC')
Standard input is empty
Initialized State: { [0, -2, -4, -6, -8, -10, -12] [-2] [-4] [-6] [-8] [-10] [-12] } horiz_pen { [-4, -6, -8, -10, -12, -14] [-1, -3, -5, -7, -9, -11] [-3, -2, -4, -4, -6, -8] [-5, -2, -1, -3, -3, -5] [-7, -4, -3, -2, -4, -4] [-9, -6, -5, -4, -3, -3] } vert_pen { [-4, -1, -3, -5, -7, -9] [-6, -3, -2, -4, -4, -6] [-8, -5, -2, -1, -3, -3] [-10, -7, -4, -3, -2, -4] [-12, -9, -6, -5, -4, -3] [-14, -11, -8, -7, -4, -5] } diag_pen { [1, -3, -5, -7, -9, -9] [-3, 0, -2, -2, -6, -8] [-5, 0, 1, -3, -1, -5] [-7, -4, -1, 0, -2, -2] [-7, -6, -3, -2, -1, -1] [-11, -8, -5, -2, -3, -2] } final { [0, -2, -4, -6, -8, -10, -12] [-2, 1, -1, -3, -5, -7, -9] [-4, -1, 0, -2, -2, -4, -6] [-6, -3, 0, 1, -1, -1, -3] [-8, -5, -2, -1, 0, -2, -2] [-10, -7, -4, -3, -2, -1, -1] [-12, -9, -6, -5, -2, -3, -2] } arrow { ['d', 'v', 'v', 'v', 'v', 'v'] ['h', 'd', 'v', 'd', 'v', 'v'] ['h', 'd', 'd', 'v', 'd', 'v'] ['h', 'h', 'h', 'd', 'v', 'd'] ['h', 'h', 'h', 'h', 'd', 'd'] ['h', 'h', 'h', 'd', 'h', 'd'] }