module Exercise_4 where

import Data.List (find)

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = d (length a) (length b)
  where
    d i j = minimum [ x | Just x <- [dab0 i j, dab1 i j, dab2 i j, dab3 i j, dab4 i j, dab5 i j] ]
    dab0 i j
      | i == j && j == 0 = Just 0
      | otherwise = Nothing
    dab1 i j
      | i > 0 = Just $ (d (i - 1) j) + 1
      | otherwise = Nothing
    dab2 i j
      | j > 0 = Just $ (d i (j - 1)) + 1
      | otherwise = Nothing
    dab3 i j
      | i > 0 && j > 0 && a!!(i - 1) == b!!(j - 1) = Just $ d (i-1) (j-1)
      | otherwise = Nothing
    dab4 i j
      | i > 0 && j > 0 && a!!(i - 1) /= b!!(j - 1) = Just $ (d (i-1) (j-1)) + 1
      | otherwise = Nothing
    dab5 i j
      | i > 1 && j > 1 && a!!(i-1) == b!!(j-2) && a!!(i-2) == b!!(j-1) = Just $ (d (i - 2) (j - 2)) + 1
      | otherwise = Nothing
    fromJust (Just x) = x
    fromJust x = undefined

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect ws xs = [ fst <$> helper ws x | x <- xs ]
  where helper (w:ws) x = correct ws x [(w, wettEditDistance x w)] (wettEditDistance x w)

correct :: [String] -> String -> [(String, Int)] -> Int -> [(String, Int)]
correct [] x pairs minDistance = pairs
correct (w:ws) x pairs minDistance
  | abs (length w - length x) > minDistance = correct ws x pairs minDistance
  | snd pair > minDistance = correct ws x pairs minDistance
  | snd pair == minDistance = correct ws x (pair:pairs) minDistance
  | snd pair < minDistance = correct ws x [pair] (snd pair)
  where
    pair = (w, wettEditDistance w x)

wettEditDistance :: Eq a => [a] -> [a] -> Int
wettEditDistance a b = d (length a) (length b)
  where
    d 0 j = j
    d i 0 = i
    d i j = minimum [ x | Just x <- [ d1 i j,d2 i j,d3 i j, d4 i j, d5 i j ] ]
    d1 i j
      | i > 0 = Just $ arr!!(i - 1)!!j + 1
      | otherwise = Nothing
    d2 i j
      | j > 0 = Just $ arr!!i!!(j - 1) + 1
      | otherwise = Nothing
    d3 i j
      | a!!(i - 1) == b!!(j - 1) = Just $ arr!!(i-1)!!(j-1)
      | otherwise = Nothing
    d4 i j
      | a!!(i - 1) /= b!!(j - 1) = Just $ arr!!(i-1)!!(j-1) + 1
      | otherwise = Nothing
    d5 i j
      | i > 1 && j > 1 && a!!(i-1) == b!!(j-2) && a!!(i-2) == b!!(j-1) = Just $ arr!!(i - 2)!!(j - 2) + 1
      | otherwise = Nothing
    arr = [[ d x y | y <- [0..length b] ] | x <- [0..length a]]

{-TTEW-}