Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Project Euler #01 on HackerRank, Performance issue?
(Jean Lopes)
2. Re: Project Euler #01 on HackerRank, Performance issue?
(Brandon Allbery)
3. Re: Project Euler #01 on HackerRank, Performance issue?
(Jean Lopes)
----------------------------------------------------------------------
Message: 1
Date: Tue, 27 Jan 2015 23:33:16 -0200
From: Jean Lopes <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<CAKeoKsj-F+Coryvqk4qFf3goJoa0YsBdTpPdOz5+K+Z+prx=r...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Yes, that would work, but this approach will exceeding the time limit of 5
seconds. Keep in mind that this program should process 100.000 numbers
which will range from 1 to 1.000.000.000 in under five seconds
My current implementation it won't succeed regarding the time factor, but I
did get some insights, I know where to look now (I guess)!
Just to illustrate what I am saying: for instance this function
> sum [3,6..9999999]
Takes ~1 second to return, and these are just the multiples of 3, to get
the real answer I would have to first sum the multiples of 5 and 15...
2015-01-27 23:09 GMT-02:00 Animesh Saxena <[email protected]>:
> why not just use infinite series. mathematically...
>
> series 1 = Mutiples of 3
> series 2 = Multiples of 5
> Apply filter and sum to get the answer
>
> -Animesh
>
> On Jan 27, 2015, at 04:43 PM, Jean Lopes <[email protected]> wrote:
>
> Your solution runs really quick! I'll study it. Thank you
>
> 2015-01-27 22:25 GMT-02:00 Lyndon Maydwell <[email protected]>:
>
>> 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 <[email protected]> wrote:
>>
>>> Thats actually what I did...
>>>
>>> 2015-01-27 22:11 GMT-02:00 Lyndon Maydwell <[email protected]>:
>>>
>>> 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 <[email protected]>
>>>> 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 <[email protected]>:
>>>>>
>>>>>> On Tue, Jan 27, 2015 at 6:29 PM, Jean Lopes <[email protected]>
>>>>>> 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
>>>>>> [email protected]
>>>>>> [email protected]
>>>>>>
>>>>>> unix, openafs, kerberos, infrastructure, xmonad
>>>>>> http://sinenomine.net
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> Beginners mailing list
>>>>>> [email protected]
>>>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>>>
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Beginners mailing list
>>>>> [email protected]
>>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> [email protected]
>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150127/9f9cda85/attachment-0001.html>
------------------------------
Message: 2
Date: Tue, 27 Jan 2015 20:37:58 -0500
From: Brandon Allbery <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<cakfcl4xs83wcg_xpov5vgq4cb4ggxngz0ysanur5_jnrxyp...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Tue, Jan 27, 2015 at 8:33 PM, Jean Lopes <[email protected]> wrote:
> Just to illustrate what I am saying: for instance this function
> > sum [3,6..9999999]
> Takes ~1 second to return, and these are just the multiples of 3, to get
> the real answer I would have to first sum the multiples of 5 and 15...
>
Yes, and what people are telling you is how to do this without generating
and iterating through the list, just using the description of it. This is
the key to Euler problems; you're using the brute force solution, not the
math that lets you skip the slow part and get the answer immediately.
(I've been keeping quiet because I'm not very good at this kind of math
myself; I just recognize that Euler problems are always looking for it and
that almost any time you find yourself iterating through a generated list
of numbers, you're doing it wrong. Even in the cases where you *do* need to
do so, there's usually some math that will cut the search space down
considerably; you'll run into this if you do one of the Euler problems
involving prime numbers, most likely.)
--
brandon s allbery kf8nh sine nomine associates
[email protected] [email protected]
unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150127/baee0cf7/attachment-0001.html>
------------------------------
Message: 3
Date: Wed, 28 Jan 2015 07:23:10 -0300
From: Jean Lopes <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Project Euler #01 on HackerRank,
Performance issue?
Message-ID:
<cakeoksgrd0ff-1uykt2hnucrgvmusj6hgfr4_wkkjgc0fe_...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
@Arjun Comar: I would like this walkthrough!
2015-01-27 22:37 GMT-03:00 Brandon Allbery <[email protected]>:
> On Tue, Jan 27, 2015 at 8:33 PM, Jean Lopes <[email protected]> wrote:
>
>> Just to illustrate what I am saying: for instance this function
>> > sum [3,6..9999999]
>> Takes ~1 second to return, and these are just the multiples of 3, to get
>> the real answer I would have to first sum the multiples of 5 and 15...
>>
>
> Yes, and what people are telling you is how to do this without generating
> and iterating through the list, just using the description of it. This is
> the key to Euler problems; you're using the brute force solution, not the
> math that lets you skip the slow part and get the answer immediately.
>
> (I've been keeping quiet because I'm not very good at this kind of math
> myself; I just recognize that Euler problems are always looking for it and
> that almost any time you find yourself iterating through a generated list
> of numbers, you're doing it wrong. Even in the cases where you *do* need to
> do so, there's usually some math that will cut the search space down
> considerably; you'll run into this if you do one of the Euler problems
> involving prime numbers, most likely.)
>
> --
> brandon s allbery kf8nh sine nomine
> associates
> [email protected]
> [email protected]
> unix, openafs, kerberos, infrastructure, xmonad
> http://sinenomine.net
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150128/b41074a2/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 79, Issue 35
*****************************************
