You are not logged in. Please login at to post your questions!


Haskell Solution to PERMUT2

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 ""

asked 22 Dec '14, 04:28

noble_mushtak's gravatar image

accept rate: 16%

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 ) .

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.


answered 14 Nov, 20:52

davislor's gravatar image

accept rate: 0%

edited 14 Nov, 20:56

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 22 Dec '14, 04:28

question was seen: 530 times

last updated: 14 Nov, 20:56