1+ from __future__ import print_function
2+
3+ try :
4+ xrange #Python 2
5+ except NameError :
6+ xrange = range #Python 3
7+
8+ def compute_transform_tables (X , Y , cC , cR , cD , cI ):
9+ '''
10+ Algorithm for calculating the most cost-efficient sequence for converting one string into another.
11+ The only allowed operations are
12+ ---Copy character with cost cC
13+ ---Replace character with cost cR
14+ ---Delete character with cost cD
15+ ---Insert character with cost cI
16+ '''
17+ X = list (X )
18+ Y = list (Y )
19+ m = len (X )
20+ n = len (Y )
21+
22+ costs = [[0 for _ in xrange (n + 1 )] for _ in xrange (m + 1 )]
23+ ops = [[0 for _ in xrange (n + 1 )] for _ in xrange (m + 1 )]
24+
25+ for i in xrange (1 , m + 1 ):
26+ costs [i ][0 ] = i * cD
27+ ops [i ][0 ] = 'D%c' % X [i - 1 ]
28+
29+ for i in xrange (1 , n + 1 ):
30+ costs [0 ][i ] = i * cI
31+ ops [0 ][i ] = 'I%c' % Y [i - 1 ]
32+
33+ for i in xrange (1 , m + 1 ):
34+ for j in xrange (1 , n + 1 ):
35+ if X [i - 1 ] == Y [j - 1 ]:
36+ costs [i ][j ] = costs [i - 1 ][j - 1 ] + cC
37+ ops [i ][j ] = 'C%c' % X [i - 1 ]
38+ else :
39+ costs [i ][j ] = costs [i - 1 ][j - 1 ] + cR
40+ ops [i ][j ] = 'R%c' % X [i - 1 ] + str (Y [j - 1 ])
41+
42+ if costs [i - 1 ][j ] + cD < costs [i ][j ]:
43+ costs [i ][j ] = costs [i - 1 ][j ] + cD
44+ ops [i ][j ] = 'D%c' % X [i - 1 ]
45+
46+ if costs [i ][j - 1 ] + cI < costs [i ][j ]:
47+ costs [i ][j ] = costs [i ][j - 1 ] + cI
48+ ops [i ][j ] = 'I%c' % Y [j - 1 ]
49+
50+ return costs , ops
51+
52+ def assemble_transformation (ops , i , j ):
53+ if i == 0 and j == 0 :
54+ seq = []
55+ return seq
56+ else :
57+ if ops [i ][j ][0 ] == 'C' or ops [i ][j ][0 ] == 'R' :
58+ seq = assemble_transformation (ops , i - 1 , j - 1 )
59+ seq .append (ops [i ][j ])
60+ return seq
61+ elif ops [i ][j ][0 ] == 'D' :
62+ seq = assemble_transformation (ops , i - 1 , j )
63+ seq .append (ops [i ][j ])
64+ return seq
65+ else :
66+ seq = assemble_transformation (ops , i , j - 1 )
67+ seq .append (ops [i ][j ])
68+ return seq
69+
70+ if __name__ == '__main__' :
71+ from time import sleep
72+ _ , operations = compute_transform_tables ('Python' , 'Algorithms' , - 1 , 1 , 2 , 2 )
73+
74+ m = len (operations )
75+ n = len (operations [0 ])
76+ sequence = assemble_transformation (operations , m - 1 , n - 1 )
77+
78+ file = open ('min_cost.txt' , 'w' )
79+
80+ string = list ('Python' )
81+ i = 0
82+ cost = 0
83+ for op in sequence :
84+ print '' .join (string )
85+ if op [0 ] == 'C' :
86+ file .write ('%-16s' % 'Copy %c' % op [1 ])
87+ file .write ('\t \t \t ' + '' .join (string ))
88+ file .write ('\r \n ' )
89+
90+ i += 1
91+ cost -= 1
92+ elif op [0 ] == 'R' :
93+ string [i ] = op [2 ]
94+
95+ file .write ('%-16s' % ('Replace %c' % op [1 ] + ' with ' + str (op [2 ])))
96+ file .write ('\t \t ' + '' .join (string ))
97+ file .write ('\r \n ' )
98+
99+ i += 1
100+ cost += 1
101+ elif op [0 ] == 'D' :
102+ string .pop (i )
103+
104+ file .write ('%-16s' % 'Delete %c' % op [1 ])
105+ file .write ('\t \t \t ' + '' .join (string ))
106+ file .write ('\r \n ' )
107+
108+ i += 1
109+ cost += 2
110+ else :
111+ string .insert (i , op [1 ])
112+
113+ file .write ('%-16s' % 'Insert %c' % op [1 ])
114+ file .write ('\t \t \t ' + '' .join (string ))
115+ file .write ('\r \n ' )
116+
117+ i += 1
118+ cost += 2
119+
120+ print '' .join (string )
121+ print 'Cost: ' , cost
122+
123+ file .write ('\r \n Minimum cost: ' + str (cost ))
124+ file .close ()
0 commit comments