You are not logged in. Please login at www.codechef.com 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

5★noble_mushtak
12812
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 ) .
           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.

link

answered 14 Nov, 20:52

davislor's gravatar image

3★davislor
213
accept rate: 0%

edited 14 Nov, 20:56

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×533
×30
×13

question asked: 22 Dec '14, 04:28

question was seen: 530 times

last updated: 14 Nov, 20:56