// EditDistance
package main

import (
	"bufio"
	"fmt"
	"os"
)

func edit_distance(word1 string, word2 string) int {
	distance := make([][]int, len(word1)+1)
	for i := range distance {
		distance[i] = make([]int, len(word2)+1)
	}
	for i := 0; i <= len(word1); i++ {
		distance[i][0] = i
	}
	for j := 0; j <= len(word2); j++ {
		distance[0][j] = j
	}
	for i := 1; i <= len(word1); i++ {
		for j := 1; j <= len(word2); j++ {
			candidate1 := distance[i-1][j] + 1
			candidate2 := distance[i][j-1] + 1
			candidate3 := distance[i-1][j-1] + 1
			if word1[i-1] == word2[j-1] {
				candidate3 -= 1
			}
			if candidate1 < candidate2 && candidate1 < candidate3 {
				distance[i][j] = candidate1
			} else if candidate2 < candidate3 {
				distance[i][j] = candidate2
			} else {
				distance[i][j] = candidate3
			}
		}
	}
	return distance[len(word1)][len(word2)]
}

func main() {
	input_file, err := os.Open("edit.in")
	if err != nil {
		fmt.Println(err)
	}
	defer input_file.Close()
	scanner := bufio.NewScanner(input_file)

	output_file, err := os.Create("edit.out")
	if err != nil {
		fmt.Printf("error creating file: %v", err)
		return
	}
	defer output_file.Close()

	for scanner.Scan() {
		word1 := scanner.Text()
		scanner.Scan()
		word2 := scanner.Text()
		answer := edit_distance(word1, word2)
		// fmt.Println("The edit distance between", word1, "and", word2, "is", answer)
		output_file.WriteString(fmt.Sprintf("The edit distance between %s and %s is %d\n",
			word1, word2, answer))
	}
}