#!env python
# Find Minimum Edit Distance of two strings, and show alignment
# 0440949 Andreas van Cranenburgh
# 9660208 Ricus Smid

def mineditdistance(source, target):
	def substcost():
		if a == b: return 0 
		else: return 2
	def mintuple(list):
		smallest = list[0]
		for a in list:
			if a[0] < smallest[0]:
				smallest = a
		return smallest

	#initialize distance matrix
	distance = [[(0, ' ')for a in target+' '] for b in source+' ']
	for i, row in enumerate(distance): row[0] = (i, 'I')
	for j in range(len(distance[0])): distance[0][j] = (j, 'D')
	distance[0][0] = (0, 'S')
	
	#populate distance matrix
	for i, a in list(enumerate('#'+source))[1:]:
		for j, b in list(enumerate('#'+target))[1:]:
				insc = (distance[i-1][j][0] + 1, 'I')
				substc = (distance[i-1][j-1][0] + substcost(), 'S')
				delc = (distance[i][j-1][0] + 1, 'D')
				distance[i][j] = mintuple((substc, insc, delc))					
	return distance

def align(source, target, matrix):
	#return alignment, showing insertions and deletions as '*'
	i, j = len(source), len(target)
	newsource, newtarget = [], []
	while i > 0 or j > 0:
		if matrix[i][j][1] == 'S':
			i -= 1
			j -= 1
			newsource.append(source[i])
			newtarget.append(target[j])
		elif matrix[i][j][1] == 'I':
			i -= 1
			newsource.append(source[i])
			newtarget.append('*')
		elif matrix[i][j][1] == 'D':
			j -= 1
			newsource.append('*')
			newtarget.append(target[j])
		else:
			print 'unexpected symbol'	
	source, target = "".join(reversed(newsource)), "".join(reversed(newtarget))
	return source, target

source = "spelling issues"
target = "speling isjoes"
matrix = mineditdistance(source, target)

#print the whole distance matrix
for a in reversed(matrix): 
	for b, c in a: print '%02u%s' % (b, c),
	print

print "edit distance: ", matrix[-1][-1][0]	#last element

#show alignment
source, target = align(source, target, matrix)
print source
print target