Diff two lines

linediff.go

package main

import (
	"fmt"
	"math"
	"os"
)

func main() {
	if len(os.Args) != 3 {
		fmt.Printf("%s [firststr] [secondstr]\n", os.Args[0])
		os.Exit(2)
	}

	var f, s []rune
	for _, r := range os.Args[1] {
		f = append(f, r)
	}
	for _, r := range os.Args[2] {
		s = append(s, r)
	}

	sec := diff(f, s)
	for _, sc := range sec {
		if sc.match {
			fmt.Printf("%s", sc.f)
		} else {
			fmt.Printf("[%s,%s]", sc.f, sc.s)
		}
	}
	fmt.Printf("\n")
}

type section struct {
	f, s  string
	match bool
}

func diff(f, s []rune) []section {
	tbl := distanceTable(f, s)

	i := len(tbl) - 1
	j := len(tbl[0]) - 1

	var sec []section
	var currRevSectionI, currRevSectionJ []rune
	var isMatch bool
	for i != 0 || j != 0 {
		var upperLeft int = math.MaxInt32
		var left int = math.MaxInt32
		var up int = math.MaxInt32
		if i > 0 && j > 0 {
			upperLeft = tbl[i-1][j-1]
		}
		if i > 0 {
			left = tbl[i-1][j]
		}
		if j > 0 {
			up = tbl[i][j-1]
		}
		if upperLeft <= left && upperLeft <= up {
			if !isMatch {
				if len(currRevSectionI) > 0 || len(currRevSectionJ) > 0 {
					sec = append(sec, section{reversedString(currRevSectionI), reversedString(currRevSectionJ), isMatch})
				}
				currRevSectionI = nil
				currRevSectionJ = nil
			}
			isMatch = true
			currRevSectionI = append(currRevSectionI, f[i])
			currRevSectionJ = append(currRevSectionJ, f[j])
			i--
			j--
		} else if left <= up {
			if isMatch {
				if len(currRevSectionI) > 0 || len(currRevSectionJ) > 0 {
					sec = append(sec, section{reversedString(currRevSectionI), reversedString(currRevSectionJ), isMatch})
				}
				currRevSectionI = nil
				currRevSectionJ = nil
			}
			isMatch = false
			currRevSectionI = append(currRevSectionI, f[i])
			i--
		} else {
			if isMatch {
				if len(currRevSectionI) > 0 || len(currRevSectionJ) > 0 {
					sec = append(sec, section{reversedString(currRevSectionI), reversedString(currRevSectionJ), isMatch})
				}
				currRevSectionI = nil
				currRevSectionJ = nil
			}
			isMatch = false
			currRevSectionJ = append(currRevSectionJ, f[j])
			j--
		}
	}
	if len(currRevSectionI) > 0 || len(currRevSectionJ) > 0 {
		sec = append(sec, section{reversedString(currRevSectionI), reversedString(currRevSectionJ), isMatch})
	}
	var reversedSec []section
	for i := len(sec) - 1; i >= 0; i-- {
		reversedSec = append(reversedSec, sec[i])
	}
	return reversedSec
}

func reversedString(r []rune) string {
	s := ""
	for _, rn := range r {
		s = string(rn) + s
	}
	return s
}

func distanceTable(f, s []rune) [][]int {
	dists := make([][]int, len(f))
	for i := range dists {
		dists[i] = make([]int, len(s))
	}

	for i := range f {
		for j := range s {
			if i == 0 && j == 0 {
				continue
			}
			minCost := math.MaxInt32
			if j > 0 {
				if dists[i][j-1]+1 < minCost {
					minCost = dists[i][j-1] + 1
				}
				if i > 0 && dists[i-1][j-1] < minCost {
					minCost = dists[i-1][j-1]
				}
			}
			if i > 0 {
				if dists[i-1][j]+1 < minCost {
					minCost = dists[i-1][j] + 1
				}
			}
			dists[i][j] = minCost
		}
	}
	return dists
}