Create a gist now

Instantly share code, notes, and snippets.

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 = 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment