Project Euler

For questions about problems on the Project Euler web site. No spoilers. Please include the question number in the subject line of your post.

Project Euler

Postby pyjul » Wed Jun 04, 2014 2:01 pm

micseydel wrote:If you enjoyed this, you might want to check out Project Euler (especially problem 14).


Merci micseydel pour ton aide !

Thanks to you I cleaned a bit my script ;) .

If you enjoyed this, you might want to check out Project Euler (especially problem 14).


What a great idea. I registered to the Project Euler some weeks ago but the problems were not as easy as it seems to be ! Here was my attempt to solve the first problem...

Problem : If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Code: Select all
# -*- coding: utf-8 -*-

def algorithm(a):

    a -= 1
    _list = []

    while a > 0:

        if a % 5 == 0:
            _list.append(a)

        elif a % 3 == 0:
            _list.append(a)

        a -= 1

    return _list


def multiples_sum(_list):

    multiples_sum = sum(_list)
    return multiples_sum


def solve():

    i = algorithm(1000)
    e = multiples_sum(i)
    print e

solve()

... As you can see, I've used the brute force solution which isn't very ingenious...
Last edited by pyjul on Tue Jun 10, 2014 6:51 pm, edited 7 times in total.
Arx Tarpeia Capitoli proxima...
User avatar
pyjul
 
Posts: 14
Joined: Tue Jun 03, 2014 5:24 pm
Location: France

Re: Syracuse sequence

Postby stranac » Wed Jun 04, 2014 2:15 pm

You're repeating the same mistakes micseydel mentioned in your first code.

Why not just use sum()? (not to mention you gave the same name to the function and a variable in it)
Code: Select all
def multiples_sum(_list):

    multiples_sum = sum(_list)
    return multiples_sum


Your variable names could (and should) be better.
Also, the loop in the algorithm() functions should be a for loop.

Btw, this problem is easily written as a one-liner.
Friendship is magic!

R.I.P. Tracy M. You will be missed.
User avatar
stranac
 
Posts: 1137
Joined: Thu Feb 07, 2013 3:42 pm

Re: Syracuse sequence

Postby Kebap » Wed Jun 04, 2014 2:29 pm

Bonjour, welcome to the forums! :)

If you like to discuss Euler problems, maybe start a thread in the apropiate forum, as this thread is mainly about your completed script above. :geek:
Learn: How To Ask Questions The Smart Way
Join the #python-forum IRC channel on irc.freenode.net and chat with uns directly!
Kebap
 
Posts: 394
Joined: Thu Apr 04, 2013 1:17 pm
Location: Germany, Europe

Re: Project Euler

Postby pyjul » Wed Jun 04, 2014 7:36 pm

You're repeating the same mistakes micseydel mentioned in your first code.

Oh ! Autant pour moi, I've written this script before he mentioned the mistakes from the first program and I had better to correct my solution to the first Euler project problem before posting it. Mea culpa!

Your variable names could (and should) be better.

According to you, what is a "good" variable name ?

Also, the loop in the algorithm() functions should be a for loop.

Why ? The while loop 'while n > 0:' is quite good...

Btw, this problem is easily written as a one-liner.

Oh, well... I'm really curious to see how it would be to write this program in a single line !

I've reviewed my solution
Code: Select all
# -*- coding: utf-8 -*-

def multiples(n):

    return n % 5 == 0 or n % 3 == 0


def algorithm(n):

    numbers = []

    while n > 0:

        if multiples(n):
            numbers.append(n)

        n -= 1

    return numbers


def solve():

    numbers = algorithm(1000)
    return sum(numbers)
Last edited by pyjul on Fri Jun 06, 2014 8:52 pm, edited 4 times in total.
Arx Tarpeia Capitoli proxima...
User avatar
pyjul
 
Posts: 14
Joined: Tue Jun 03, 2014 5:24 pm
Location: France

Re: Syracuse sequence

Postby stranac » Wed Jun 04, 2014 8:01 pm

pyjul wrote:According to you, what is a "good" variable name ?

Something like limit instead of n, or numbers instead of _list.
i and e in your first code also make no sense.

pyjul wrote:Why ? The while loop 'while n > 0:' is quite good...

Because iterating over a list of numbers is exactly what a for loop is meant for.
This (btw, this is not what you want, since you don't want the 1000):
Code: Select all
# n initialized somewhere
while n > 0:
    # some stuff here
    n -= 1

Can be written as:
Code: Select all
for n in range(n, 0, -1):
    # some stuff here

Or more simply (with numbers growing):
Code: Select all
for n in range(n + 1):
    # some code here


pyjul wrote:Oh, well... I'm really curious to see how it would be to write this program in a single line !

Either this:
Code: Select all
sum(n for n in xrange(1000) if n % 3 == 0 or n % 5 == 0)

or this:
Code: Select all
sum(xrange(3, 1000, 3)) + sum(range(5, 1000, 5)) - sum(xrange(15, 1000, 15))
Friendship is magic!

R.I.P. Tracy M. You will be missed.
User avatar
stranac
 
Posts: 1137
Joined: Thu Feb 07, 2013 3:42 pm

Re: Project Euler

Postby pyjul » Wed Jun 04, 2014 8:15 pm

Thank you stranac ;)
Arx Tarpeia Capitoli proxima...
User avatar
pyjul
 
Posts: 14
Joined: Tue Jun 03, 2014 5:24 pm
Location: France

Re: Project Euler

Postby McCoffee » Sat Jun 28, 2014 11:39 pm

Hello, I am new here and I am a beginner/intermediate level python programmer. I am also interested in these kinds of problems. This post is not so much a question as it is another potential solution and an introduction of myself (so hopefully the answer is correct ;) ). I believe you can do this without for loops a la Gauss, where you add the highest multiple and the lowest multiple together and multiply that value with the total number of multiples below the upper bound and then divide by 2.
Code: Select all
def sumFunc(upper, mult)
   """based on summing up numbers from 1 to n
      n(n-1)/2"""
   upper -= 1 # below 1000
   numMults = upper/mult # total number of multiples (for 3 numMults = 333)
   highest = numMults*mult # highest number that is multiple (for 3 highest = 999)
   addy = highest + mult # sum these two numbers
   return addy*numMults/2 # divide by two because you would sum each of the numbers twice

def main():
   mult3 = sumFunc(1000,3)
   mult5 = sumFunc(1000,5)
   mult15 = sumFunc(1000,15)
   return mult3 + mult5 - mult15

if __name__ == "__main__":
   main()


In the specified case this seems to work (I checked with the for loop method), but I am unsure if it always works. I tested it with much higher upper bounds (10**9) and it is significantly faster than the for loop methods. An addition to the script could be calculating the lowest product of the 2 multiples of interest, so that it does not have to be hard-coded into the script.
Last edited by Mekire on Sun Jun 29, 2014 3:31 pm, edited 1 time in total.
Reason: First post lock.
McCoffee
 
Posts: 2
Joined: Sat Jun 28, 2014 10:20 pm


Return to Project Euler

Who is online

Users browsing this forum: Bing [Bot] and 1 guest