SPOJ 6219. Edit Distance (EDIST) with F#

(*
* Problem URI : http://www.spoj.com/problems/EDIST/
* Problem Code : EDIST
* Date : 27.01.2013
*)
(*
* Algorithmic Technique
* =======================
* _Dynamic Programming_ with Memoization is applied to solve this problem (i.e. to
* compute _edit distance). First we derive a recursive definition of Edit Distance and * afterwards, solve the subproblems.
*
* Lets denote ``distance'' to be the function that calculates edit distance.
* The recursive definition can be stated as follows:
*
* Base cases:
* --------------
* distance ("","") --> 0
* distance ("",s2) --> |s2|
* distance (s1,"") --> |s1|
*
*
* distance (s1+ch1, s2+ch2) -->
* min{ distance(s1+ch1, s2) + 1, //cost: insertion of ch2 in s1+ch1
* distance(s1, s2+ch2) + 1, //cost: deletion of ch1 from s1
* distance(s1,s2) + (if ch1=ch2 then 0 else 1) // cost of substitution
* }
*)
open System
let min ((a:int), (b:int), (c:int)) =
Math.Min(a, Math.Min(b,c))
let computeEditDistance (source:string,target:string) =
let height,width = (source.Length, target.Length)
let grid: int [,] = Array2D.zeroCreate<int> (height+1) (width+1)
for h = 0 to height do
for w = 0 to width do
grid.[h,w] <-
match h,w with
| h,0 -> h
| 0, w -> w
| h, w ->
let s,t = source.[h-1],target.[w-1]
let insertion = grid.[h,w-1] + 1
let deletion = grid.[h-1,w] + 1
let substitution = grid.[h-1,w-1]+(if s = t then 0 else 1)
min (insertion, deletion, substitution)
grid.[height,width]
//Trivial IO Stuff
let parseLine() =
let word1 = System.Console.ReadLine()
let word2 = System.Console.ReadLine()
word1,word2
let solveEdist() =
let T = System.Console.ReadLine() // Total Number of cases
//printfn "string cases : %s" s
let numCases = System.Int32.Parse(T)
//printfn "cases : %d" numCases
for j = 1 to numCases do
parseLine()
|> computeEditDistance
|> printfn "%d"
solveEdist()
view raw edist.fs hosted with ❤ by GitHub

Please leave a comment if you have any question or suggestion. Thanks!

More on Edit Distance

[1] Section 5.5 of Algorithm Lecture note by Jeff Erickson
[2] Dynamic Programming Algorithm for Edit-Distance
[3] Edit Distance from Algorithmist
[4] Blog post  by Dave Fancher.

2 thoughts on “SPOJ 6219. Edit Distance (EDIST) with F#”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s