
Hi I am practicing writing code in haskell, by solving problems at this site. http://spoj.pl. The problem http://spoj.pl/problems/FASHION , is pretty simple. 1. Given two lists A,B , of N numbers, sort them and take sum of products. i.e. Sum ai * bi I wrote a code, but seems to give "Time limit exceeded"!
Beginning of CODE loop t function | t == 1 = do function | otherwise = do { function; loop (t - 1) function }
prod [] [] = 0 prod (a:as) (b:bs) = a*b + prod as bs to_int :: [String] -> [Integer] to_int [] = [] to_int (x:xs) = (read x) : to_int xs doit = do n <- getLine a <- getLine b <- getLine let la = to_int (words a); lb = to_int (words b); in print (prod la lb) main = do t <- getLine loop (read t) doit << END OF CODE I would love to see if there is any improvement that can be done, to the code ... Thanks! Vimal

j.vimal:
Hi I am practicing writing code in haskell, by solving problems at this site. http://spoj.pl. The problem http://spoj.pl/problems/FASHION , is pretty simple.
1. Given two lists A,B , of N numbers, sort them and take sum of products. i.e. Sum ai * bi
I wrote a code, but seems to give "Time limit exceeded"!
We have a page for these SPOJ problems: http://haskell.org/haskellwiki/SPOJ#Techniques_for_dealing_with_problems_eff... With bytestring IO, you can aim to be around the speed of OCaml or C++, according to the existing bytestring entries. -- Don

* Vimal wrote:
Beginning of CODE loop t function | t == 1 = do function | otherwise = do { function; loop (t - 1) function }
prod [] [] = 0 prod (a:as) (b:bs) = a*b + prod as bs
prod = sum . zipWith (*)
to_int :: [String] -> [Integer] to_int [] = [] to_int (x:xs) = (read x) : to_int xs
This is the slow part. Prelude.read ist really slow. Futhermore use the recusion pattern again: to_int = map read
doit = do n <- getLine a <- getLine b <- getLine let la = to_int (words a); lb = to_int (words b); in print (prod la lb)
What is n used for?

prod = sum . zipWith (*)
This is the slow part. Prelude.read ist really slow.
Futhermore use the recusion pattern again: to_int = map read
What is n used for? @Lutz: Those are some nice tricks... Thanks! Now, the 'n' is for getting the number of numbers in the list. Which I don't need, since I had a way around it. I just had to skip that
@Donald: Thanks for the link. line...

I wrote a code, but seems to give "Time limit exceeded"! ?? Your code writes 15 to stdout which is correct (with the example given on the page).. You have to explain what you mean by >>seems to give "Time limit exceeded"<<
loop t function Does already exist. sequence $ replicate 10 function is a much shorter way :-)
oor perhaps mapM_ [ function | i <- [1..10] ] ) prod, to_int: You can both implement using higher order functions prod = sum . zipWith (*) to_int = map read Marc

On 8/9/07, Marc Weber
I wrote a code, but seems to give "Time limit exceeded"! ?? Your code writes 15 to stdout which is correct (with the example given on the page).. You have to explain what you mean by >>seems to give "Time limit exceeded"<<
I think Vimal is referring to a message from SPOJ rather than the compiler. I.e. the program runs too slowly so it is rejected by the judging software. -Brent

I get "Wrong answer" with the following code for the same problem... Is there something strange in this code : module Main where import qualified Data.ByteString.Char8 as B main = B.getLine >>= sequence_ . flip replicate hot . maybe 0 fst . B.readInt hot = do B.getLine men <- B.getLine women <- B.getLine print $ sum $ zipWith (*) (map (maybe 0 fst . B.readInt) $ B.words men) (map (maybe 0 fst . B.readInt) $ B.words women) ??? I get the expected results with my tests. -- Jedaï

Note that this code isn't more successful, clearly I have misunderstood one requirement : import qualified Data.ByteString.Char8 as B import Data.List (unfoldr) main = B.interact $ hot hot = B.unlines . map (B.pack . show) . processList . tail . unfoldr readInt1 readInt1 cs = do (n, cs') <- B.readInt cs return (n, B.tail cs') processList [] = [] processList (x:xs) = (sum $ zipWith (*) men women) : processList rest where (men,r1) = splitAt x xs (women,rest) = splitAt x r1 -- Jedaï

On 8/9/07, Chaddaï Fouché
I get "Wrong answer" with the following code for the same problem... Is there something strange in this code :
This problem description is not worded very well. You have to figure out the matching that maximizes the sum of hotnesses; you don't necessarily just do a sum . zipWith (*). -Brent

On 8/9/07, Brent Yorgey
On 8/9/07, Chaddaï Fouché
wrote: I get "Wrong answer" with the following code for the same problem... Is there something strange in this code :
This problem description is not worded very well. You have to figure out the matching that maximizes the sum of hotnesses; you don't necessarily just do a sum . zipWith (*).
Exactly. The description says: "Company XYZ has done the work for you, and now do xxx". This confused me a lot :-)

On 8/9/07, Marc Weber
I wrote a code, but seems to give "Time limit exceeded"! ?? Your code writes 15 to stdout which is correct (with the example given on the page).. You have to explain what you mean by >>seems to give "Time limit exceeded"<<
loop t function Does already exist. sequence $ replicate 10 function is a much shorter way :-)
oor perhaps mapM_ [ function | i <- [1..10] ] )
prod, to_int: You can both implement using higher order functions
prod = sum . zipWith (*) to_int = map read
Thanks :) Yes, I see no reason why the code should be rejected by the judge (Time limit exceeded) just because I had defined all the functions. I had done this on many other occasions, and they all had worked well. I think that it has a lot to do with the (read) function and how it is implemented. So parsing takes quite a bit of time, and eventually most of the time gets used up in processing input. But the new functions are wonderful :-) I had a hunch that these functions should have been defined, but I learnt a lot in the process of writing those functions again! -- Vimal
participants (6)
-
Brent Yorgey
-
Chaddaï Fouché
-
dons@cse.unsw.edu.au
-
Lutz Donnerhacke
-
Marc Weber
-
Vimal