module Exercise_4 where

import Data.List
import Data.Array as A

editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = aux lenA lenB
  where
    aux i 0 = i
    aux 0 j = j
    aux i j | arrA ! (i-1) == arrB ! (j-1) = mem ! (i-1, j-1)
            | otherwise = minimum [x | x <- options i j, x >= 0] + 1

    options i j = [ mem ! (i-1, j),
                    mem ! (i, j-1),
                    mem ! (i-1, j-1),
                    if i > 1 && j > 1
                             && arrA ! (i-1) == arrB ! (j-2)
                             && arrA ! (i-2) == arrB ! (j-1)
                    then mem ! (i-2, j-2)
                    else - 1
                  ]

    mem = A.listArray bounds [aux i j | (i, j) <- A.range bounds]

    lenA   = length a
    lenB   = length b
    arrA   = listArray (0, lenA-1) a
    arrB   = listArray (0, lenB-1) b
    bounds = ((0, 0), (lenA, lenB))

{-H4.1.11-}
{-WETT-}
calculateScores :: [String] -> String -> Int -> [(String, Int)]
calculateScores [d] x min
  | min == 0                        = []
  | abs (length d - length x) > min = []
  | distance >  min                 = []
  | distance <= min                 = [(d, distance)]
  where
    distance = editDistance d x

calculateScores (d:ds) x min
  | min == 0                        = []
  | abs (length d - length x) > min = calculateScores ds x min
  | distance >  min                 = calculateScores ds x min
  | distance <= min                 = (calculateScores ds x distance) ++ [(d, distance)]
  where
    distance = editDistance d x

findAlternatives :: [String] -> String -> [String]
findAlternatives ds x = (fst . unzip) $ takeWhile ((min ==) . snd) scores
  where
    scores = calculateScores ds x (maxBound::Int)
    min = snd $ scores !! 0


spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect d xs = [findAlternatives d x | x <- xs]
{-TTEW-}