Haskell Solution to PERMUT2

general
, ,
1

The permut2 problem requires something along the lines of indexing an array and for Haskell, indexing long arrays can be a hard task because it has single-linked lists. However, I’m pretty new to Haskell since I’ve only known it for two weeks, so maybe I’m just not thinking in Haskell. Does anyone have a Haskell solution to this problem that passed, or is this just something not for functional programming languages?

Here’s what I tried, but it was too slow:


import System.IO
import Control.Monad

checkPos :: [Int] -> (Bool, Int) -> Int -> (Bool, Int)
checkPos reals (isOK, num) ind = (if isOK then (reals !! (ind-1)) == num+1 else False, if isOK then num+1 else num)

main = do
    num <- getLine
    let real = read num
    if (real /= 0) then do
        nums <- getLine
        let reals = map read $ words nums
        if (fst $ foldl (checkPos reals) (True, 0) reals) then putStrLn "ambiguous" else putStrLn "not ambiguous"
        main
    else putStr ""
2

It’s been a while since you posted, but there have been several Haskell solutions posted since then. Here’s mine:

{-# LANGUAGE BangPatterns, OverloadedStrings #-}
{-# OPTIONS_GHC -O3 #-}

import Data.Array.Unboxed (UArray, (!), assocs, listArray)
import qualified Data.ByteString.Lazy.Char8 as B8
import Data.ByteString.Builder (Builder, byteString, toLazyByteString)
import Data.ByteString.Builder.Extra (byteStringCopy, flush)
import Data.Maybe (fromJust)
import Data.Monoid ((<>), mempty)

main :: IO()
main = B8.interact ( toLazyByteString . parse . tokenize )

tokenize :: B8.ByteString -> [[Int]]
tokenize = map ( map (fst . fromJust . B8.readInt) .
                 B8.words ) .
           B8.lines

parse :: [[Int]] -> Builder
parse [[0]] = mempty
parse ([n]:as:xs) = let a :: UArray Int Int
                        a = listArray (1,n) as
                        b = if all (\(i,j) -> a!j == i) (assocs a)
                            then byteString "ambiguous\n" <> flush
                            else byteString "not ambiguous\n" <> flush
                    in b <> parse xs
parse (x:_) = error $ "Invalid input: " ++ show x ++ "."
parse [] = error $ "Unexpected end of input."

(The way the program turned out, I admit, tokenize and parse ended up with misleading names.)

If you removed the fast I/O and just generate a [String], it’s basically equivalent to mapping the computation of b within parse to each imput line.

An important general tip with Haskell is that you can use data structures other than linked lists, and it’s usually a good idea. Most recent functional languages use trees, not lists, as their default structure.