import qualified Data.Array as A
import Data.Ord(comparing)
import Data.List(minimumBy)

data Action = A | D | M | N
instance Show Action where
    show A = "A"
    show D = "D"
    show M = "M"
    show N = "N"
type Path = [Action]
type Cost = Int

cost :: Action -> Cost
cost N = 0
cost _ = 1

editDist :: [Char] -> [Char] -> (Cost, Path)
editDist x y = (c, reverse p)
             where (n,m) = (length x, length y)
                   x' = A.listArray (1,n) x
                   y' = A.listArray (1,m) y
                   (c, p) = editDist' x' y' n m

editDist' :: A.Array Int Char -> A.Array Int Char -> Int -> Int -> (Cost, Path)
editDist' x y n m = dist n m
                  where dist 0 0 = (0, [])
                        dist i 0 = process (i-1) 0 D
                        dist 0 j = process 0 (j-1) A
                        dist i j | x A.! i == y A.! j = process (i-1) (j-1) N
                                 | otherwise = minimumBy (comparing fst) [process (i-1) j D, process i (j-1) A, process (i-1) (j-1) M]
                        process i j act = let (d,s) = dp A.! (i,j) in (d + cost act, act:s)
                        dp = A.listArray ((0,0),(n,m)) [dist i j | (i,j) <- A.range ((0,0),(n,m))]

