#!/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')
 

IyEvdXNyL2Jpbi9weXRob24KCgpkZWYgcHJpbnRMaXN0T2ZMaXN0KGwpOgogICAgIiIiSnVzdCBhIG5pY2VyIHByaW50IG1ldGhvZCIiIgogICAgcHJpbnQoInsiKQogICAgZm9yIHJvdyBpbiBsOgogICAgICAgIHByaW50KHJvdykKICAgIHByaW50KCJ9IikKCmRlZiBjb21wdXRlKGxlZnQsIHRvcCk6CiAgICAiIiJVc2UgZHluYW1pYyBwcm9ncmFtbWluZyB3b3chIiIiCiAgICBob3Jpel9wZW4gPSBbXQogICAgdmVydF9wZW4gPSBbXQogICAgZGlhZ19wZW4gPSBbXQogICAgYXJyb3cgPSBbXQogICAgZmluYWwgPSBbXQoKICAgICMgSW5pdGlhbHplIGxlZnQgYm9yZGVyCiAgICBmb3IgbCBpbiByYW5nZShsZW4obGVmdCkrMSk6CiAgICAgICAgZmluYWwuYXBwZW5kKFtdKQogICAgICAgIGZpbmFsW2xdLmFwcGVuZCgtMipsKQoKICAgICMgSW5pdGlhbGl6ZSB0b3AgYm9yZGVyCiAgICBmb3IgdCBpbiByYW5nZShsZW4odG9wKSsxKToKICAgICAgICBpZiB0ICE9IDA6CiAgICAgICAgICAgIGZpbmFsWzBdLmFwcGVuZCgtMip0KQoKICAgIHByaW50KCdJbml0aWFsaXplZCBTdGF0ZTonKQogICAgcHJpbnRMaXN0T2ZMaXN0KGZpbmFsKQoKICAgICMgV29yayBmcm9tIHRoZSB0b3AgZG93bgogICAgZm9yIGwgaW4gcmFuZ2UobGVuKGxlZnQpKToKCiAgICAgICAgI1BlbmFsdHkgbGlzdHMgc3RhcnQgZW1wdHkuIFdlIG11c3QgY3JlYXRlIGFuIGVtcHR5IGxpc3QgaW4gcHJlcGFyYXRpb24gZm9yIHRoZSBmb2xsb3dpbmcgZm9yIGxvb3AKICAgICAgICBob3Jpel9wZW4uYXBwZW5kKFtdKQogICAgICAgIHZlcnRfcGVuLmFwcGVuZChbXSkKICAgICAgICBkaWFnX3Blbi5hcHBlbmQoW10pCiAgICAgICAgYXJyb3cuYXBwZW5kKFtdKQoKICAgICAgICAjV29yayBmcm9tIHRoZSBsZWZ0IHRvIHRoZSByaWdodAogICAgICAgIGZvciB0IGluIHJhbmdlKGxlbih0b3ApKToKICAgICAgICAgICAgCiAgICAgICAgICAgIG1hdGNoX3BvaW50ID0gMSBpZiBsZWZ0W2xdID09IHRvcFt0XSBlbHNlIC0xCiAgICAgICAgICAgIAogICAgICAgICAgICBob3Jpel9wZW5bbF0uYXBwZW5kKGZpbmFsW2xdW3QrMV0gLTIpCiAgICAgICAgICAgIHZlcnRfcGVuW2xdLmFwcGVuZChmaW5hbFtsKzFdW3RdIC0yKQogICAgICAgICAgICBkaWFnX3BlbltsXS5hcHBlbmQoZmluYWxbbF1bdF0gKyBtYXRjaF9wb2ludCkKCiAgICAgICAgICAgIG1zY29yZSA9IG1heChob3Jpel9wZW5bbF1bdF0sIHZlcnRfcGVuW2xdW3RdLCBkaWFnX3BlbltsXVt0XSkKICAgICAgICAgICAgaWYgbXNjb3JlID09IGhvcml6X3BlbltsXVt0XToKICAgICAgICAgICAgICAgIGFycm93W2xdLmFwcGVuZCgnaCcpCiAgICAgICAgICAgIGVsaWYgbXNjb3JlID09IHZlcnRfcGVuW2xdW3RdOgogICAgICAgICAgICAgICAgYXJyb3dbbF0uYXBwZW5kKCd2JykKICAgICAgICAgICAgZWxpZiBtc2NvcmUgPT0gZGlhZ19wZW5bbF1bdF06CiAgICAgICAgICAgICAgICBhcnJvd1tsXS5hcHBlbmQoJ2QnKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcmFpc2UgRXhjZXB0aW9uKCdiYWQnKQoKICAgICAgICAgICAgZmluYWxbbCsxXS5hcHBlbmQobXNjb3JlKQoKICAgIHByaW50KCdob3Jpel9wZW4nKQogICAgcHJpbnRMaXN0T2ZMaXN0KGhvcml6X3BlbikKICAgIHByaW50KCd2ZXJ0X3BlbicpCiAgICBwcmludExpc3RPZkxpc3QodmVydF9wZW4pCiAgICBwcmludCgnZGlhZ19wZW4nKQogICAgcHJpbnRMaXN0T2ZMaXN0KGRpYWdfcGVuKQogICAgcHJpbnQoJ2ZpbmFsJykKICAgIHByaW50TGlzdE9mTGlzdChmaW5hbCkKICAgIHByaW50KCdhcnJvdycpCiAgICBwcmludExpc3RPZkxpc3QoYXJyb3cpCgppZiBfX25hbWVfXyA9PSAnX19tYWluX18nOgogICAgY29tcHV0ZSgnQ0dBVENHJywgJ0NBQUdBQycpCg==