Instantly share code, notes, and snippets.

# dradtke/permutations.hs Created Aug 24, 2012

Haskell solution for CodeChef - Ambiguous Permutations (improved)
 import Control.Monad import qualified Data.IntMap as IM import qualified Data.List as L import Data.Maybe import Data.Text import qualified Data.Text.IO as TIO import Data.Text.Read import System.Exit main = forever \$ do -- get the number for this case, and exit if it's equal to 0 n <- TIO.getLine >>= \x -> either (\_ -> exitFailure) (\(a,_) -> return a) (decimal x) when (n == 0) exitSuccess -- read the input and calculate the answer rawInput <- liftM (L.words . unpack) TIO.getLine let p = L.map read rawInput :: [Int] putStrLn \$ solve p n solve :: [Int] -> Int -> String solve p n | p == inverse p n = "ambiguous" | otherwise = "not ambiguous" -- construct a map to speed up the process of finding -- the correct index for a given value inverseMap :: [Int] -> IM.IntMap (Int) inverseMap p = f IM.empty p 1 where f m [] _ = m f m (x:xs) i = f (IM.insert x i m) xs (i+1) -- convert a list of numbers into its inverse permutation inverse :: [Int] -> Int -> [Int] inverse p n = f [1..n] where m = inverseMap p f [] = [] f (x:xs) = m IM.! x : f xs