Re: [Haskell-beginners] Project Euler #01 on HackerRank, Performance issue‏

Your solution runs really quick! I'll study it. Thank you 2015-01-27 22:25 GMT-02:00 Lyndon Maydwell :

Ah sorry, I didn't notice that you were doing that. The effectiveness of the trick really only comes into play though if you use an analytic solution for finding the sum of the multiples of 3, etc.

I haven't tested this code in a while, but here's what I wrote some time ago:

sum2 :: Integer -> Integer -> Integer -> Integer sum2 a b ceiling = aX + bX - abX where aX = sum1 a ceiling bX = sum1 b ceiling abX = sum1 (a * b) ceiling

sum1 :: Integer -> Integer -> Integer sum1 x ceiling = sum1' (even times) times x where times = ceiling `div` x

sum1' :: Bool -> Integer -> Integer -> Integer sum1' True times x = area where area = (times + 1) * (times * x) `div` 2

sum1' False times x = max + area' where max = times * x area' = sum1' True (times - 1) x

Please excuse the poor Haskell style as it is quite possibly the first Haskell program I ever wrote.

On Wed, Jan 28, 2015 at 11:15 AM, Jean Lopes wrote:

...

Thats actually what I did...

2015-01-27 22:11 GMT-02:00 Lyndon Maydwell :

I remember that when I had a look at Euler 1 I found that there's a fun

...

solution that should run in "constant" time.

You can find the sum of the multiples of 3, add the multiples of 5, and then subtract the multiples of 3*5.

Is that the kind of thing you're looking for?

- Lyndon

On Wed, Jan 28, 2015 at 10:57 AM, Jean Lopes wrote:

...

I'm not really good at math, maybe I am missing something obvious ? Maybe some pointers as of where to start studying math in order to avoid this brute force attempts, at least to help in this particular problem

2015-01-27 21:38 GMT-02:00 Brandon Allbery :

...

On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes wrote:

...

The problem to be solved: https://www.hackerrank.com/contests/projecteuler/challenges/euler001

It's worth remembering that the Euler problems are all about math understanding; often they are designed such that brute force solutions will time out or otherwise fail.

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners