"""
Algorithm for calculating the most cost-efficient sequence for converting one string
into another.
The only allowed operations are
---Copy character with cost cC
---Replace character with cost cR
---Delete character with cost cD
---Insert character with cost cI
"""


def compute_transform_tables(X, Y, cC, cR, cD, cI):
 X = list(X)
 Y = list(Y)
 m = len(X)
 n = len(Y)

 costs = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
 ops = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

 for i in range(1, m + 1):
 costs[i][0] = i * cD
 ops[i][0] = "D%c" % X[i - 1]

 for i in range(1, n + 1):
 costs[0][i] = i * cI
 ops[0][i] = "I%c" % Y[i - 1]

 for i in range(1, m + 1):
 for j in range(1, n + 1):
 if X[i - 1] == Y[j - 1]:
 costs[i][j] = costs[i - 1][j - 1] + cC
 ops[i][j] = "C%c" % X[i - 1]
 else:
 costs[i][j] = costs[i - 1][j - 1] + cR
 ops[i][j] = "R%c" % X[i - 1] + str(Y[j - 1])

 if costs[i - 1][j] + cD < costs[i][j]:
 costs[i][j] = costs[i - 1][j] + cD
 ops[i][j] = "D%c" % X[i - 1]

 if costs[i][j - 1] + cI < costs[i][j]:
 costs[i][j] = costs[i][j - 1] + cI
 ops[i][j] = "I%c" % Y[j - 1]

 return costs, ops


def assemble_transformation(ops, i, j):
 if i == 0 and j == 0:
 seq = []
 return seq
 else:
 if ops[i][j][0] == "C" or ops[i][j][0] == "R":
 seq = assemble_transformation(ops, i - 1, j - 1)
 seq.append(ops[i][j])
 return seq
 elif ops[i][j][0] == "D":
 seq = assemble_transformation(ops, i - 1, j)
 seq.append(ops[i][j])
 return seq
 else:
 seq = assemble_transformation(ops, i, j - 1)
 seq.append(ops[i][j])
 return seq


if __name__ == "__main__":
 _, operations = compute_transform_tables("Python", "Algorithms", -1, 1, 2, 2)

 m = len(operations)
 n = len(operations[0])
 sequence = assemble_transformation(operations, m - 1, n - 1)

 string = list("Python")
 i = 0
 cost = 0

 with open("min_cost.txt", "w") as file:
 for op in sequence:
 print("".join(string))

 if op[0] == "C":
 file.write("%-16s" % "Copy %c" % op[1])
 file.write("\t\t\t" + "".join(string))
 file.write("\r\n")

 cost -= 1
 elif op[0] == "R":
 string[i] = op[2]

 file.write("%-16s" % ("Replace %c" % op[1] + " with " + str(op[2])))
 file.write("\t\t" + "".join(string))
 file.write("\r\n")

 cost += 1
 elif op[0] == "D":
 string.pop(i)

 file.write("%-16s" % "Delete %c" % op[1])
 file.write("\t\t\t" + "".join(string))
 file.write("\r\n")

 cost += 2
 else:
 string.insert(i, op[1])

 file.write("%-16s" % "Insert %c" % op[1])
 file.write("\t\t\t" + "".join(string))
 file.write("\r\n")

 cost += 2

 i += 1

 print("".join(string))
 print("Cost: ", cost)

 file.write("\r\nMinimum cost: " + str(cost))