Skip to content

Instantly share code, notes, and snippets.

@mnstrspeed
Created October 27, 2013 02:50
Show Gist options
  • Save mnstrspeed/7177442 to your computer and use it in GitHub Desktop.
Save mnstrspeed/7177442 to your computer and use it in GitHub Desktop.
Haskell solution to BAPC 2013 Problem C
import Control.Monad
import Data.List
type Mapping = [(Char, Char)]
derive_mapping :: String -> [String] -> Mapping
derive_mapping plain encrypted =
merge_mappings $
filter is_consistent $
map (extract_mapping plain) $
filter (\s -> length s == length plain) encrypted
merge_mappings :: [Mapping] -> Mapping
merge_mappings [] = []
merge_mappings xs = foldr1 (intersectBy (\(ac, _) (bc, _) -> ac == bc)) xs
is_consistent :: Mapping -> Bool
is_consistent [] = True
is_consistent ((c, p) : xs) =
null (filter (\(nc, _) -> c == nc) xs) &&
null (filter (\(_, np) -> p == np) xs) &&
is_consistent xs
extract_mapping :: String -> String -> Mapping
extract_mapping p e = remove_dup_mappings $ flip zip p e
remove_dup_mappings :: Mapping -> Mapping
remove_dup_mappings [] = []
remove_dup_mappings (x : xs) = x : remove_dup_mappings (filter (x /=) xs)
decrypt :: Mapping -> String -> String
decrypt [] _ = "IMPOSSIBLE"
decrypt _ "" = ""
decrypt mapping (c : cs) = decrypt_char mapping c : decrypt mapping cs
decrypt_char [] _ = '?'
decrypt_char ((c, p) : cs) e
| c == e = p
| otherwise = decrypt_char cs e
run :: IO ()
run = do
num_encrypted <- readLn
encrypted <- replicateM num_encrypted getLine
decrypted <- getLine
message <- getLine
putStrLn $ decrypt (derive_mapping decrypted encrypted) message
main :: IO ()
main = readLn >>= \n -> replicateM_ n run
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment