public
Created

Haskell solution for CodeChef - Ambiguous Permutations (improved)

  • Download Gist
permutations.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.