module Exercise_4 where
import Data.List


editDistance :: Eq a => [a] -> [a] -> Int
editDistance as bs = fst $ memo la lb []            -- Ewwwwwwwwwwww o.O
    where
        memo :: Int -> Int -> [(Int, Int, Int)] -> (Int, [(Int, Int, Int)])
        memo x y list = if length erg > 0 then (minimum erg, list) else
                let (berechnung, newList) = distCalc x y list in
                (berechnung, newList ++ [(x,y,berechnung)])
            where
                erg = [z | (x1,y1,z) <- list, x1 == x, y1 == y]
                thrd (_,_,c) = c
        
        la = length as
        lb = length bs

        distCalc :: Int -> Int -> [(Int, Int, Int)] -> (Int, [(Int, Int, Int)])         -- What have I done?!?!
        distCalc aa bb list =   let (c1erg, c1list) = cond1 aa bb list in
                                let (c2erg, c2list) = cond2 aa bb c1list in             -- It hurts my eyes   x_x
                                let (c3erg, c3list) = cond3 aa bb c2list in             -- but...... it works...    
                                let (c4erg, c4list) = cond4 aa bb c3list in             -- I will never ever look at it again >.<
                                let (c5erg, c5list) = cond5 aa bb c4list in
                                let (c6erg, c6list) = cond6 aa bb c5list in
                                (minimum (c1erg ++ c2erg ++ c3erg ++ c4erg ++ c5erg ++ c6erg), c6list)
            where                                                                                       -- What is this Frankenstein-abomination I created?!?
                cond1 aa bb list = if aa == bb && bb == 0 then ([0], list) else ([], list)
                cond2 aa bb list = if aa > 0 then let (berechnung, newList) = memo (aa-1) bb list in ([berechnung+1], newList) else ([], list)
                cond3 aa bb list = if bb > 0 then let (berechnung, newList) = memo aa (bb-1) list in ([berechnung+1], newList) else ([], list)
                cond4 aa bb list = if ((aa > 0) && (bb > 0) && ((as !! (aa-1)) == (bs !! (bb-1)))) then let (berechnung, newList) = memo (aa-1) (bb-1) list in ([berechnung], newList) else ([], list)
                cond5 aa bb list = if ((aa > 0) && (bb > 0) && (as !! (aa-1) /= bs !! (bb-1))) then let (berechnung, newList) = memo (aa-1) (bb-1) list in ([berechnung+1], newList) else ([], list)
                cond6 aa bb list = if ((aa > 1) && (bb > 1) && (as !! (aa-1) == bs !! (bb-2))) && (as !! (aa-2) == bs !! (bb-1)) then let (berechnung, newList) = memo (aa-2) (bb-2) list in ([berechnung+1], newList) else ([], list)
                                    

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect (d:dict) (x:xs) = [spc x (editDistance x d) [d] dict] ++ spellCorrect (d:dict) xs
    where
        spc :: String -> Int -> [String] -> [String] -> [String]
        spc _ dst alrdyFound [] = alrdyFound
        spc word dst alrdyFound (x:dict) = if xdst < dst then spc word xdst [x] dict else if xdst == dst then spc word dst (alrdyFound ++ [x]) dict else spc word dst alrdyFound dict
            where xdst = editDistance x word
{-TTEW-}