def disp(op,i,j):
    global output
    if i==0 and j==0:
        return
    if op[i][j]=="C" or op[i][j]=="R":
        k=i-1
        r=j-1
    elif op[i][j]=="T":
        k=i-2
        r=j-2
    elif op[i][j]=="D":
        k=i-1
        r=j
    elif op[i][j]=="I":
        k=i
        r=j-1
    elif op[i][j]=="K":
        k=temp[i][j]
        r=j
    disp(op,k,r)
    output.write(str(op[i][j])+"\n")
    
def main(x1,y1):
    global temp
    m=len(x1)
    n=len(y1)
    cost=[1]*6
    c=[]
    op=[]
    for i in range(20):
        c.append([0]*20)
    for i in range(20):
        op.append([None]*20)
    x=[None]*(m+1)
    y=[None]*(n+1)
    for i in range(1,m+1):
        x[i]=x1[i-1]
    for j in range(1,n+1):
        y[j]=y1[j-1] 
    c[0][0]=0
    op[0][0]="N"
    for i in range(1,m+1):
        c[i][0]=i*cost[0]
        op[i][0]="D"
    for j in range(1,n+1):
        c[0][j]=j*cost[1]
        op[0][j]="I"
    
    for i in range(1,m+1):
        for j in range(1,n+1):
            c[i][j]=9999
            if x[i]==y[j]:
                c[i][j]=c[i-1][j-1]+cost[2]
                op[i][j]="C"
            if x[i]!=y[j] and c[i-1][j-1]+cost[3]<c[i][j]:
                c[i][j]=c[i-1][j-1]+cost[3]
                op[i][j]="R"
            if (i>=2 and j>=2) and (x[i]==y[j-1] and x[i-1]==y[j]) and (c[i-2][j-2]+cost[4]<c[i][j]):
                c[i][j]=c[i-2][j-2]+cost[4]
                op[i][j]="T"
            if c[i-1][j]+cost[0]<c[i][j]:
                c[i][j]=c[i-1][j]+cost[0]
                op[i][j]="D"
            if c[i][j-1]+cost[1]<c[i][j]:
                c[i][j]=c[i][j-1]+cost[1]
                op[i][j]="I"
    for i in range(m):
        if c[i][n]+cost[5]<c[m][n]:
            c[m][n]=c[i][n]+cost[5]
            op[m][n]="K"
            temp[m][n]=i
    for i in range(m+1):
        for j in range(n+1):
            output.write(str(c[i][j])+","+str(op[i][j])+" ")
        output.write("\n")
    output.write("Transformation followed is: \n")
    disp(op,m,n)

input=open("in17_3.txt","r+")
output=open("out_23_17_3.txt","w+")
temp=[]
for i in range(20):
    temp.append([0]*20)
count=0
x1=[]
y1=[]
x2=[]
y2=[]
x3=[]
y3=[]
x4=[]
y4=[]
x5=[]
y5=[]
for row in input:
    if count==0:
        for i in row:
            x1.append(i)
    elif count==1:
        for i in row:
            y1.append(i)
    elif count==2:
        for i in row:
            x2.append(i)
    elif count==3:
        for i in row:
            y2.append(i)
    elif count==4:
        for i in row:
            x3.append(i)
    elif count==5:
        for i in row:
            y3.append(i)
    elif count==6:
        for i in row:
            x4.append(i)
    elif count==7:
        for i in row:
            y4.append(i)
    elif count==8:
        for i in row:
            x5.append(i)
    elif count==9:
        for i in row:
            y5.append(i)
    
    count+=1
output.write("SString: "+str(x1)+"\n")
output.write("TString: "+str(y1)+"\n")
main(x1,y1)
output.write("SString: "+str(x2)+"\n")
output.write("TString: "+str(y2)+"\n")
main(x2,y2)
output.write("SString: "+str(x3)+"\n")
output.write("TString: "+str(y3)+"\n")
main(x3,y3)
output.write("S string: "+str(x4)+"\n")
output.write("TString: "+str(y4)+"\n")
main(x4,y4)
output.write("SString: "+str(x5)+"\n")
output.write("Tstring: "+str(y5)+"\n")
main(x5,y5)
output.close()