Part four of Levenshtein Distance

lev_part_four.go

package main
import "fmt"

// PART FOUR: in which we get the min value for delete, insert, substitute and set value in Vector, return significant Vector value.

func MinInt(a ...int) int {
  min := int(^uint(0) >> 1)
	for _, i := range a {
		if i < min {
			min = i
		}
	}
	return min
}

func LevenshteinThree(s1, s2 string) int {
	m := len(s1)
	n := len(s2)
	width := n - 1
	vcell := make([]int, m * n)
	fmt.Println("initial",vcell)

	// cells for i of m(s1)
	for i := 1; i < m; i++ {
		vcell[i * width + 0] = i
	}
	fmt.Println("i:",vcell)

	// cell for j of n(s2)
	for j := 1; j < n; j++ {
		vcell[0 * width + j] = j
	}
	fmt.Println("j:",vcell)
	count := 0
	
	for j := 1; j < n; j++ {
		for i := 1; i < m; i++ {
			if s1[i] == s2[j] {
				count += 1
				vcell[i * width + j] = vcell[(i - 1) * width + (j - 1)]
				fmt.Println("si[i] == s2[j]:",vcell, "count=",count)
			} else {
				deletion := vcell[(i - 1) * width + j] + 1
				fmt.Println("deletion:",vcell)
				insertion := vcell[(i * width + (j - 1))] + 1
				fmt.Println("insert:",vcell)
				substitution := vcell[((i - 1) * width + (j - 1))] + 1
				fmt.Println("sub:",vcell)
				vcell[i * width + j] = MinInt(deletion,insertion,substitution)
				mind := (i * width + j)
				count += 1
				fmt.Println("Min:",vcell, "count=",count, "idx", mind)
			}
		}
	}
	fmt.Println("Done:",vcell, "final value",(m * width + 0))
	return vcell[m * width + 0]
}

func main() {
	fmt.Println(LevenshteinThree("stri","str"))
}

/*
*** OUTPUT
initial [0 0 0 0 0 0 0 0 0 0 0 0]
i: [0 0 1 0 2 0 3 0 0 0 0 0]
j: [0 1 2 0 2 0 3 0 0 0 0 0]
si[i] == s2[j]: [0 1 2 0 2 0 3 0 0 0 0 0] count= 1
deletion: [0 1 2 0 2 0 3 0 0 0 0 0]
insert: [0 1 2 0 2 0 3 0 0 0 0 0]
sub: [0 1 2 0 2 0 3 0 0 0 0 0]
Min: [0 1 2 0 2 1 3 0 0 0 0 0] count= 2 idx 5
deletion: [0 1 2 0 2 1 3 0 0 0 0 0]
insert: [0 1 2 0 2 1 3 0 0 0 0 0]
sub: [0 1 2 0 2 1 3 0 0 0 0 0]
Min: [0 1 2 0 2 1 3 2 0 0 0 0] count= 3 idx 7
deletion: [0 1 2 0 2 1 3 2 0 0 0 0]
insert: [0 1 2 0 2 1 3 2 0 0 0 0]
sub: [0 1 2 0 2 1 3 2 0 0 0 0]
Min: [0 1 2 0 1 1 3 2 0 0 0 0] count= 4 idx 4
si[i] == s2[j]: [0 1 2 0 1 1 0 2 0 0 0 0] count= 5
deletion: [0 1 2 0 1 1 0 2 0 0 0 0]
insert: [0 1 2 0 1 1 0 2 0 0 0 0]
sub: [0 1 2 0 1 1 0 2 0 0 0 0]
Min: [0 1 2 0 1 1 0 2 1 0 0 0] count= 6 idx 8
Done: [0 1 2 0 1 1 0 2 1 0 0 0] final value 8
1
*/