FLOLAC'18 prerequisite p4

caeser.hs

encode :: Int -> String -> String
encode key plain = [shift key p | p <- plain]
    where shift n c = ['A'..'Z'] !! mod (fromEnum c - fromEnum 'A' + n) 26

decode :: String -> (String, Int)
decode cipher = let key = (snd.maximum) search in (encode (-key) cipher, key)
    where search = zip (drop 25 $ convolve cipher_stats (letter_freqs ++ letter_freqs)) (0:[25,24..1])
          cipher_stats = [fromIntegral.length $ filter (==c) cipher | c <- ['A'..'Z']]

-- 1D discrete convolution altered from stackoverflow.com/a/39784716
-- Since SSE_ij := Σ(a_i - b_j)^2 = Σa_i^2 + Σb_j^2 - 2Σa_ib_j,
-- we can minimize SSE by maximizing Σa_ib_j
convolve :: [Double] -> [Double] -> [Double]
convolve xs ys = convolve' (reverse xs) ys
    where convolve' [] ys = []
          convolve' (x:xs) ys = add (map (*x) ys) (0 : convolve' xs ys)
          add xs ys = if length xs >= length ys
                         then zipWith (+) xs (ys ++ repeat 0)
                         else add ys xs

letter_freqs :: [Double]
letter_freqs = [0.08167, 0.01492, 0.02782, 0.04253, 0.12702,
                0.02228, 0.02015, 0.06094, 0.06966, 0.00153,
                0.00772, 0.04025, 0.02406, 0.06749, 0.07507,
                0.01929, 0.00095, 0.05987, 0.06327, 0.09056,
                0.02758, 0.00978, 0.02360, 0.00150, 0.01974,
                0.00074]

{-
    *Main> encode 10 "THEQUICKBROWNFOXJUMPSOVERALAZYDOG"
    "DROAESMULBYGXPYHTEWZCYFOBKVKJINYQ"

    *Main> decode "DROAESMULBYGXPYHTEWZCYFOBKVKJINYQ"
    ("THEQUICKBROWNFOXJUMPSOVERALAZYDOG",10)
-}