Re: [Haskell-cafe] why these two are not equivalent?
On Sun, Sep 13, 2009 at 09:57:50PM -0700, Iavor Diatchki wrote: (argh, sorry about that, I pressed something and gmail sent my unfinished email!) On Sun, Sep 13, 2009 at 9:54 PM, Iavor Diatchki iavor.diatc...@gmail.com wrote: Hi, It seems that the problem is the site is using GHC 6.6.1, and something was broken at the time (I have not looked into what that is). Here are the outputs that I get for the little example on the site that you posted: GHC 6.10.3 and C++: 03 10103538 1233 6160 0141 1 03 10103538 1233 6160 0142 1 30 10103538 1233 6160 0141 2 30 10103538 1233 6160 0142 2 30 10103538 1233 6160 0142 1 30 10103538 1233 6160 0143 1 30 10103538 1233 6160 0144 1 30 10103538 1233 6160 0145 1 30 10103538 1233 6160 0146 1 With GHC 6.6.1: 03 10103538 1233 6160 0141 1 03 10103538 1233 6160 0142 1 30 10103538 1233 6160 0141 2 30 10103538 1233 6160 0142 2 30 10103538 1233 6160 0142 1 30 10103538 1233 6160 0143 1 30 10103538 1233 6160 0145 1 30 10103538 1233 6160 0146 1 Note that in the second test case one line is missing, the one ending in 44. -Iavor Hi Iavor, Sweet, it makes a lot of sense. I haven't tried to run this with ghc-6.6.1, though. Thank you for doing this. Just for curiosity I'll try to find out what exactly fails under 6.6.1, just in case anyone else run into the problem in future (as I don't think they will upgrade the ghc any time soon). I'll eventually ask them to upgrade the ghc version. Any recommendation about which version should I ask for? Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why these two are not equivalent?
On Sat, Sep 12, 2009 at 9:52 PM, Diego Souza dso...@bitforest.org wrote: I assumed Data.Map was a tree internally and keep elements ordered, so the following would sort the input and print duplicates in O(n log n), as the C++ version does: sbank :: [B.ByteString] - [(B.ByteString,Int)] sbank = toAscList . fromListWith (+) . flip zip (repeat 1) Is it wrong to assume this? It worked for all tests cases I could think of though. That is part of the contract of toAscList (the Asc stands for ascending order), but because of the way Map is implemented, the result of toList is also sorted. --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why these two are not equivalent?
On Sun, Sep 13, 2009 at 11:34:16AM +0200, Max Rabkin wrote: That is part of the contract of toAscList (the Asc stands for ascending order), but because of the way Map is implemented, the result of toList is also sorted. Cool. It is good to know that toAscList and toList would produce the same output. However, I think the question remains open. Is this piece of haskell code any different (in terms of the output it produces) from the C++ version? Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why these two are not equivalent?
Hi, It seems that the problem is the site is using GHC 6.6.1, and something was broken at the time (I have not looked into what that is). Here are the outputs that I get for the little example on the site that you posted: GHC 6.10.3 and C++: On Sun, Sep 13, 2009 at 10:15 AM, Diego Souza dso...@bitforest.org wrote: On Sun, Sep 13, 2009 at 11:34:16AM +0200, Max Rabkin wrote: That is part of the contract of toAscList (the Asc stands for ascending order), but because of the way Map is implemented, the result of toList is also sorted. Cool. It is good to know that toAscList and toList would produce the same output. However, I think the question remains open. Is this piece of haskell code any different (in terms of the output it produces) from the C++ version? Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why these two are not equivalent?
(argh, sorry about that, I pressed something and gmail sent my unfinished email!) On Sun, Sep 13, 2009 at 9:54 PM, Iavor Diatchki iavor.diatc...@gmail.com wrote: Hi, It seems that the problem is the site is using GHC 6.6.1, and something was broken at the time (I have not looked into what that is). Here are the outputs that I get for the little example on the site that you posted: GHC 6.10.3 and C++: 03 10103538 1233 6160 0141 1 03 10103538 1233 6160 0142 1 30 10103538 1233 6160 0141 2 30 10103538 1233 6160 0142 2 30 10103538 1233 6160 0142 1 30 10103538 1233 6160 0143 1 30 10103538 1233 6160 0144 1 30 10103538 1233 6160 0145 1 30 10103538 1233 6160 0146 1 With GHC 6.6.1: 03 10103538 1233 6160 0141 1 03 10103538 1233 6160 0142 1 30 10103538 1233 6160 0141 2 30 10103538 1233 6160 0142 2 30 10103538 1233 6160 0142 1 30 10103538 1233 6160 0143 1 30 10103538 1233 6160 0145 1 30 10103538 1233 6160 0146 1 Note that in the second test case one line is missing, the one ending in 44. -Iavor On Sun, Sep 13, 2009 at 10:15 AM, Diego Souza dso...@bitforest.org wrote: On Sun, Sep 13, 2009 at 11:34:16AM +0200, Max Rabkin wrote: That is part of the contract of toAscList (the Asc stands for ascending order), but because of the way Map is implemented, the result of toList is also sorted. Cool. It is good to know that toAscList and toList would produce the same output. However, I think the question remains open. Is this piece of haskell code any different (in terms of the output it produces) from the C++ version? Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] why these two are not equivalent?
Hi, I was trying to solve a simple problem in SPOJ, however, after two weeks trying almost everything I could think of, I was still getting WrongAnswer. Then I decided to do the same thing in C++ and I really got puzzled when I got ACcepted. I tried to understand what was different without success. I hope someone can tell me why spoj says the Haskell version is wrong: http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3583 [Haskell,WA] http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3582 [C++,AC] The problem I'm talking about is this one: https://www.spoj.pl/problems/SBANK/ Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why these two are not equivalent?
On Sat, Sep 12, 2009 at 12:08 PM, Diego Souza dso...@bitforest.org wrote: Hi, I was trying to solve a simple problem in SPOJ, however, after two weeks trying almost everything I could think of, I was still getting WrongAnswer. Then I decided to do the same thing in C++ and I really got puzzled when I got ACcepted. I tried to understand what was different without success. I hope someone can tell me why spoj says the Haskell version is wrong: http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3583 [Haskell,WA] http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3582 [C++,AC] The problem I'm talking about is this one: https://www.spoj.pl/problems/SBANK/ Looks like the output should be sorted. The C++ version does this with the iterator over mapstring, int implicitly. I don't spot where your haskell version sorts the output. There could be other problems, that's just what I can notice in 2 minutes of looking. Good luck! Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why these two are not equivalent?
On Sat, Sep 12, 2009 at 12:46 PM, Jason Dagit da...@codersbase.com wrote: On Sat, Sep 12, 2009 at 12:08 PM, Diego Souza dso...@bitforest.orgwrote: Hi, I was trying to solve a simple problem in SPOJ, however, after two weeks trying almost everything I could think of, I was still getting WrongAnswer. Then I decided to do the same thing in C++ and I really got puzzled when I got ACcepted. I tried to understand what was different without success. I hope someone can tell me why spoj says the Haskell version is wrong: http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3583 [Haskell,WA] http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3582 [C++,AC] The problem I'm talking about is this one: https://www.spoj.pl/problems/SBANK/ Looks like the output should be sorted. The C++ version does this with the iterator over mapstring, int implicitly. I don't spot where your haskell version sorts the output. I take that back. I see how it sorts it now. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] why these two are not equivalent?
Looks like the output should be sorted. The C++ version does this with the iterator over mapstring, int implicitly. I don't spot where your haskell version sorts the output. There could be other problems, that's just what I can notice in 2 minutes of looking. Good luck! Jason, I assumed Data.Map was a tree internally and keep elements ordered, so the following would sort the input and print duplicates in O(n log n), as the C++ version does: sbank :: [B.ByteString] - [(B.ByteString,Int)] sbank = toAscList . fromListWith (+) . flip zip (repeat 1) Is it wrong to assume this? It worked for all tests cases I could think of though. Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
