Project Euler

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

mammothman
Posts: 15
Joined: Fri Aug 24, 2007 6:52 am UTC
Location: Connecticut
Contact:

Re: Project Euler

Postby mammothman » Sat Jan 31, 2009 5:17 am UTC

I found project euler through this thread a few days ago and since I've solved about 13 of the easier problems. But, doing problem 10 using the following code took about ten hours or so for it to finish calculating the sum of the primes. Does anyone have any advice on how I could improve the method I used? I'm not very good at C and I was doing most of the problems in Python before this one but I figured I could save a few hours by doing it in C.

Also I don't post very often as this is my second post, and I did post in the into thread a long time ago...but here we go:

Spoiler:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int getFactors(num)
{
    int divisorCount = 1;
    int i;
    for(i=1;i<num;i++)
    {
        if(num % i == 0) divisorCount++;
    }
    return divisorCount;
}

int main()
{

long x = 1;
int xto = 2e6;
long numPrimes = 1;
long currentPrime = 0;
long long sumPrimes = 0;
printf("Calculating primes below: %d\n", xto);

for(x=1;x<xto;x++)
{
    if(getFactors(x) == 2)
    {
        sumPrimes = sumPrimes + x;
        currentPrime = x;

    }
    if(x%20000 == 0) printf("Percent Done: %d\n", x/20000);
}
    printf("Sum of the Primes below %d: %lld", xto, sumPrimes);
    return 0;
}

look chat date touch grep make unzip strip view finger mount fcsk more fcsk yes spray umount sleep

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: Project Euler

Postby keeperofdakeys » Sat Jan 31, 2009 5:59 am UTC

mammothman wrote:I found project euler through this thread a few days ago and since I've solved about 13 of the easier problems. But, doing problem 10 using the following code took about ten hours or so for it to finish calculating the sum of the primes. Does anyone have any advice on how I could improve the method I used? I'm not very good at C and I was doing most of the problems in Python before this one but I figured I could save a few hours by doing it in C.

Also I don't post very often as this is my second post, and I did post in the into thread a long time ago...but here we go:

Spoiler:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int getFactors(num)
{
    int divisorCount = 1;
    int i;
    for(i=1;i<num;i++)
    {
        if(num % i == 0) divisorCount++;
    }
    return divisorCount;
}

int main()
{

long x = 1;
int xto = 2e6;
long numPrimes = 1;
long currentPrime = 0;
long long sumPrimes = 0;
printf("Calculating primes below: %d\n", xto);

for(x=1;x<xto;x++)
{
    if(getFactors(x) == 2)
    {
        sumPrimes = sumPrimes + x;
        currentPrime = x;

    }
    if(x%20000 == 0) printf("Percent Done: %d\n", x/20000);
}
    printf("Sum of the Primes below %d: %lld", xto, sumPrimes);
    return 0;
}



a few pointers:
when you test for primes, you only need to test WITH primes so:
start count at zero
do not include 1, it is not a prime number
after 2, every even number WILL NOT be a prime number; so don't test them
you only need to test for divisibility up to and including the square root, since factors are mirrored and prime numbers do not have factors none are mirrored
Last edited by keeperofdakeys on Sat Jan 31, 2009 7:02 am UTC, edited 1 time in total.

mammothman
Posts: 15
Joined: Fri Aug 24, 2007 6:52 am UTC
Location: Connecticut
Contact:

Re: Project Euler

Postby mammothman » Sat Jan 31, 2009 6:40 am UTC

Oh wow, thanks a lot, that definitely cuts some time off.
look chat date touch grep make unzip strip view finger mount fcsk more fcsk yes spray umount sleep

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: Project Euler

Postby keeperofdakeys » Sun Feb 01, 2009 7:11 am UTC

ok, currently I am working on Problem 54 in python

Code: Select all

def poker_hand(hand_1,hand_2):
   hands = []
   ranks = []
   result = []
   cards = ['A','2','3','4','5','6','7','8','9','T','J','Q','K']
   for hand in [hand_1,hand_2]:
      patterns = []
      values = [hand[0][0],hand[1][0],hand[2][0],hand[3][0],hand[4][0]]
      suite = hand[0][1]
      if hand[1][1] == suite and hand[2][1] == suite and hand[3][1] == suite and hand[4][1] == suite: patterns.extend(['Flush','0'])
      for x in xrange(0,9):
         if hand[0][0] == cards[0 + x] and hand[1][0] == cards[1 + x] and hand[2][0] == cards[2 + x] and hand[3][0] == cards[3 + x] and hand[4][0] == cards[4 + x]:
            patterns.extend(['Straight',cards[x]])
      for x in cards:
         if values.count(x) == 4:
            patterns.extend(['Four',x])
            cards.remove(x)
         elif values.count(x) == 3:
            patterns.extend(['Three',x])
            cards.remove(x)
         elif values.count(x) == 2:
            patterns.extend(['Pair',x])
            cards.remove(x)
      if values == ['T','J','Q','K','A']: patterns.extend(['Royal','0'])
      for x in xrange(len(cards) - 1,-1,-1):
         if cards[x] in values:
            patterns.extend(['High',cards[x]])
            break
      hands.append(patterns)
   for y in hands:
      rank = [[11]]
      if y.count('Pair') == 2:   put_pair = [8]
      elif y.count('Pair') == 1: put_pair = [9]
      else: put_pair = None
      for x in xrange(len(y)):
         if 'Royal' == y[x] and 'Flush' in y and rank[0][0] > 1: rank = [[1, y[x + 1]]]
         if 'Straight' == y[x] and 'Flush' in y and rank[0][0] > 2: rank = [[2, y[x + 1]]]
         if 'Four' == y[x] and rank[0][0] > 3: rank = [[3, y[x + 1]]]
         if 'Three' == y[x] and 'Pair' in y and rank[0][0] > 4: rank = [[4, y[x + 1]]]
         if 'Flush' == y[x] and rank[0][0] > 5: rank = [[5]]
         if 'Straight' == y[x] and rank[0][0] > 6: rank = [[6,y[x + 1]]]
         if 'Three' == y[x] and rank[0][0] > 7: rank = [[7,y[x + 1]]]
         if 'Pair' == y[x] and rank[0][0] > 8:
            put_pair.append(y[x + 1])
            rank = [[9]]
         if 'High' == y[x] and rank[0][0] > 10: rank = [[10,y[x + 1]]]
      if put_pair != None and rank[0][0] > 8: rank = [put_pair]
      ranks.extend(rank)
   if ranks[0][0] < ranks[1][0]: result = 1
   elif ranks[0][0] == ranks[1][0]:
      print ranks
      if cards.index(ranks[0][1]) > cards.index(ranks[1][1]): result = 1
      elif cards.index(ranks[0][1]) == cards.index(ranks[1][1]):
         if cards.index(hands[0][hands[0].index('High') + 1]) > cards.index(hands[1][hands[1].index('High') + 1]): result = 1
         elif cards.index(hands[0][hands[0].index('High') + 1]) == cards.index(hands[1][hands[1].index('High') + 1]): result = 0
   else: result = 2
   return result

this code crashes on about the forth round of cards, the ones before work
the suspect hands are ['TH', '8H', '5C', 'QS', 'TC'] ['9H', '4D', 'JC', 'KS', 'JS'], to run the code, use poker_hand(['TH', '8H', '5C', 'QS', 'TC'],['9H', '4D', 'JC', 'KS', 'JS'])
the error is 'ValueError: list.index(x): x not in list' on the line 'if cards.index(ranks[0][1]) > cards.index(ranks[1][1]): result = 1'
if I return the suspect lists back to the main code and run it there, it works but I require it in the function

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Sun Feb 01, 2009 8:32 am UTC

keeperofdakeys wrote:ok, currently I am working on Problem 54 in python


I find your code almost but not quite incomprehensible. I noticed that you remove elements from 'cards' when analysing a hand. I think this means that in the first loop (over the two hands) card values used in the first hand are ignored in the second.

I think a complete rethink and rewrite is in order. Why don't you write a function that takes just one poker hand and returns a score? (The score is a value such that better hands have higher scores, and only equally good hands have equal scores).

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Sun Feb 01, 2009 2:43 pm UTC

For that problem I actually created a Hand class and implemented __cmp__. I'm a little ashamed to say it was just a huge bunch of if statements resembling something of a mountain range if put on its side. I had created methods like isStraight and isTwoPairs, but the thing is that a full house is also a pair, two pairs and three of a kind.

It wasn't really hard to do though, just more work than I'd like.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
e946
Posts: 621
Joined: Wed Jul 11, 2007 6:32 am UTC

Re: Project Euler

Postby e946 » Mon Feb 02, 2009 4:24 am UTC

I stored each card value as an integer, and each "rank" as an integer, so in my __cmp__ method all I had to do was

Code: Select all

if( self.rank!=other.rank):
    return this.rank>other.rank
else:
    for (selfcard,othercard) in zip(self.cards, other.cards):
        if(selfcard!=othercard):
            return selfcard>othercard
raise Exception("Identical hands!")

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: Project Euler

Postby keeperofdakeys » Mon Feb 02, 2009 6:20 am UTC

jaap wrote:
keeperofdakeys wrote:ok, currently I am working on Problem 54 in python


I find your code almost but not quite incomprehensible. I noticed that you remove elements from 'cards' when analysing a hand. I think this means that in the first loop (over the two hands) card values used in the first hand are ignored in the second.

I think a complete rethink and rewrite is in order. Why don't you write a function that takes just one poker hand and returns a score? (The score is a value such that better hands have higher scores, and only equally good hands have equal scores).


thanks, it appears that the removing thing kind of made it kill itself
and I guess I should REALLY start commenting my code

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Thu Feb 05, 2009 8:21 pm UTC

I have been strugling with 230 for a few hours now, and am getting progressively closer to the solution. Exercising your mind is indeed awesome.

It's also fun to revisit already solved problems later to see if you can improve on your solution. I originally solved problem 204 in haskell in about 6 lines @ 3 seconds. I decided to try to do it in C since I'm teaching myself that properly, and my first solution was almost identical to my Haskell solution, about 120 lines @ 1.5 seconds. I then switched my mind from the infinitely lazy Haskell mindset over to the frugal minimalist C mindset and solved the same problem in 30 lines @ 0.07 seconds. I never would've been able to come up with that solution without the original solution though.

Basically, PE is awesome because it makes you think.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Fri Feb 06, 2009 2:05 am UTC

I really haven't worked on any new problems for at least a few weeks now. Instead, I've been going back to some I've already solved and cleaning up and trying to optimize my solutions. Which leads me to wonder what a good method for calculating the nth prime is.
So far, I've only used two different methods: brute force (using a trial division method and a while loop that breaks once it finds n primes) and returning the nth element of a list generated by a prime sieve called on [imath]n \ln{n} + n \ln{\ln{n}} + 2[/imath] (based on an upper bound stolen from Wikipedia and the fact that [imath]\pi(n)[/imath] and [imath]p_n[/imath] are inverses [there's probably an opportunity for a pedant to yell at me about this point, but its close enough for my standards]). I'm not sure which scales better, what with being relatively new to this whole computational complexity thing.

The problem I have with this is that both leave you with no choice but to calculate every prime less than pn, which seems like a waste. Maybe that's the only way feasible way to do it, but so far I've had no luck whatsoever on finding any alternative method. There seems to have been a hell of a lot more academic work done on the prime counting function than there has been on the nth prime function.
Any suggestions?

User avatar
Briareos
Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

Re: Project Euler

Postby Briareos » Fri Feb 06, 2009 3:20 am UTC

I'm trying to learn Common Lisp:

Code: Select all

(defun euler2 ()
  (do ((a 1 b)
       (b 2 (+ a b))
       (sum 0))
    ((> b 3999999) sum)
    (if (evenp b)
      (incf sum b))))

This gives the right answer. But it doesn't feel "functional" enough. I simply can't tell how functional common lisp is supposed to be -- the control structures in particular feel a lot more imperative. am i doin it rite?
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Fri Feb 06, 2009 4:03 am UTC

For fibonacci, you *want* to do it imperatively. The functional Fibonacci code is a beginners example of what *not* to do in an Algorithms course.

However, the do macro just plain sucks. Anything you can do with it, you can do much more clearly with the loop macro. You can see what I mean:

Code: Select all

(loop for a = 1 then b
      for b = 1 then c
      for c = (+ a b)
      until (> c 4000000)
      if (evenp c) sum c)

I find this enormously clearer, and easier to code. It unrolls into basically the same thing as the do form, though.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Fri Feb 06, 2009 4:21 am UTC

I think lisp just broke my brain a little with that sum thing. In my world sum takes a list as an argument and forgets its previous invocation the moment it returns.

Fibonacci I prefer to define using list transformations though: 'fibs = 0:1:zipWith (+) fibs (tail fibs)'. Not just is list manipulation prettier than imperative loops to describe, but it's full of maps, folds and shiny recursions making it much more useful and much easier to use. They have true mathematical beauty.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Briareos
Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

Re: Project Euler

Postby Briareos » Fri Feb 06, 2009 4:26 am UTC

Yeah, Fibonacci is a perfect target for Haskell-y goodness. I wanted to find a mapping-and-folding way to solve the problem in Lisp; that's why the imperative way irks me so. It just doesn't measure up to Haskell and its infinite lists.
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Fri Feb 06, 2009 4:34 am UTC

Well, you could always do it the simple way, then:

Code: Select all

(defmemoized fib (n)
    (if (< n 3)
        1
        (+ (fib (- n 1)) (fib (- n 2)))))

You just need an appropriate implementation of defmemoized. This does work wonderfully, though, up until the point you get a stack overflow.

If you install the SERIES package, you *should* be able to get the same laziness of Haskell.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Fri Feb 06, 2009 4:56 am UTC

The eager way of defining fibonacci as a list is to do it as a recursive function:

Code: Select all

fibs n = fibs' n 0 1 0 where
  fibs' n c a b | n == c = []
                | otherwise = b:fibs' n (c + 1) b (a + b)

It looks a bit silly in haskell, I'll admit. If I'm honest, I'm a bit tempted to try to do it with an until expression. (I don't know why, but I prefer until to defining my own tail recursive functions).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Project Euler

Postby Carnildo » Fri Feb 06, 2009 6:57 am UTC

Xanthir wrote:For fibonacci, you *want* to do it imperatively. The functional Fibonacci code is a beginners example of what *not* to do in an Algorithms course.

It depends on your language. In a pure functional language where functions are free of side effects, a recursive Fibonacci function is every bit as efficient as an iterative one: since calling a function with a given set of parameters will always produce the same results, you can cache the results of the function call rather than computing them again.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Fri Feb 06, 2009 10:13 am UTC

In a purely functional language you can't cache function calls based on its arguments, because the cache would also have to be a parameter, and it would update itself on each call.

Anyway, that's what the defmemoized macro supposedly does in his lisp example. In reality, memoizing every function call would become rather inefficient in the long run (most functions will only be called with the same argument once) so it isn't done unless explicitly told so. Even Haskell, which is perhaps the purest functional language around, doesn't memoize things unless you tell it to. Even if you do memoize, the naive functional way will possibly have to do more work than the iterative version (given that it is also memoized). The naive way will recurse down to the two highest pre-calculated numbers and calculate from there, doing a lookup for each function call. The iterative way will also start with the two highest pre-calculated numbers, but won't have to do the lookups.

Now, if you're talking about mathematics, then yes, both versions are equal. Mathematics isn't programming however, no matter how functional it is, because mathematics isn't about computing numbers.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Fri Feb 06, 2009 6:28 pm UTC

Berengal wrote:In a purely functional language you can't cache function calls based on its arguments, because the cache would also have to be a parameter, and it would update itself on each call.

Nah, he's talking about a compiler optimization, essentially. It's not a language feature per se, similar to how pure functional languages still compile down to mutation-based assembly.

Anyway, that's what the defmemoized macro supposedly does in his lisp example. In reality, memoizing every function call would become rather inefficient in the long run (most functions will only be called with the same argument once) so it isn't done unless explicitly told so. Even Haskell, which is perhaps the purest functional language around, doesn't memoize things unless you tell it to. Even if you do memoize, the naive functional way will possibly have to do more work than the iterative version (given that it is also memoized). The naive way will recurse down to the two highest pre-calculated numbers and calculate from there, doing a lookup for each function call. The iterative way will also start with the two highest pre-calculated numbers, but won't have to do the lookups.

Now, if you're talking about mathematics, then yes, both versions are equal. Mathematics isn't programming however, no matter how functional it is, because mathematics isn't about computing numbers.

This part is accurate, though. For a simple thing like Fibonacci, you should really never do the functional version. I'm not sure what goes on under the hood in the Haskell example in Berengal's sig, but it might be passable, and may be preferred anyway since it's lazy and will interact with the rest of the language well.

The naive iterative is simply the fastest way to do this, and it's so simple (at least in most languages, Lisp included) that there's almost never a reason to do it any other way. Memoizing it is a cute trick, and a very *useful* trick when you have a function complex enough that it can't be easily unrolled into an iterative version, but it's no replacement for iteration. In the fib example, the iterative version is linear in time complexity, while the memoized is O(n*logn) on a fresh cache (it does get faster with a primed cache, but never better than your hash lookup function). However, the iterative version is constant in storage, while the memoized is linear in memory and, for a fresh cache, in stack space. (Interesting side-effect: on my computer I can't execute (fib-m 10000) immediately, but if I first execute (fib-m 4000), it works. Apparently my stack is between 6k and 7k function calls wide.)

The one case where it might be useful is when you're repeatedly grabbing very large fibonacci numbers. Priming the cache for 50000 takes about 20 seconds, but afterwards, (fib-m 50000) returns in about 2 microseconds. On the other hand, (fib-i 50000) takes about 2 seconds every time you call it.

It's even faster, of course, to do as Berengal says, and memoize the iterative version. Since fibonacci is dependent on a single parameter, you can store it in a simple array, and remember what the highest value is. Experimentally, priming the array takes substantially less time than the memoized version1, and it can be done with a *single* call, rather than having to find a decent value that doesn't crash my stack and looping by the value to 50000. Once primed, retrieval time is literally too small to measure - my IDE is reporting 0 for the timing.

Code examples:
Spoiler:

Code: Select all

(defmemoized fib-m (n)
    "Memoized version of naive recursive fibonacci."
    (if (< n 3)
        1
        (+ (fib (- n 1)) (fib (- n 2)))))
;
(defun fib-i (n)
  "Basic iterative version."
  (if (< n 3)
      1
      (loop repeat (- n 2)
            for a = 1 then b
            for b = 1 then c
            for c = (+ a b)
            finally (return c))))
;
(let ((fib-array (make-array 50000 :initial-element 1 :fill-pointer 2)))
  "Smarter iterative fibonacci, which remembers previous calls."
  (defun fib-mi (n)
    (when (> n (length fib-array))
      (loop repeat (- n (length fib-array))
            for a = (aref fib-array (- n 3)) then b
            for b = (aref fib-array (- n 2)) then c
            for c = (+ a b)
            for i upfrom (length fib-array)
            do (setf (aref fib-array i) c))
      (setf (fill-pointer fib-array) n))
    (aref fib-array (1- n))))

Homework: rewrite fib-mi to resize the array when you attempt to retrieve a value that is too large.

1: Actually priming fib-mi for 50000 consistently takes about 2 seconds. However, it spends a large amount of time garbage collecting during this. The first time it spent 16 seconds GCing, the second time (after closing my Lisp to clear the image and priming it immediately) it spent 8.5 seconds (this is a consistent number across 3 restarts now). It has to do with initializing the huge array, I'm certain, because if I clear out the closure (without killing the image) and then prime it again, it only spends about 3 seconds GCing (again, consistent across several repeats). Strangely, telling make-array that it'll be dealing with bignums doesn't help the time at all.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Fri Feb 06, 2009 10:50 pm UTC

Xanthir wrote:I'm not sure what goes on under the hood in the Haskell example in Berengal's sig, but it might be passable, and may be preferred anyway since it's lazy and will interact with the rest of the language well.
'fibs = 0:1:zipWith (+) fibs (tail fibs)' works the same as 'fibs = f 1 0 where f a b = b:f b (a + b)', modulo the fact that the first version uses higher-level functions and is self-referentially defined. Neither consume stack, because list-traversing is tail-recursive, and both zipWith and 'f' are lazy, so they only calculate one list element before returning to the traversal function. Both are, in essence, the iterative version (the second one just shows it better).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Fri Feb 06, 2009 11:28 pm UTC

Out of curiosity, mind timing that for the 50000th number? Before and after priming, please.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Sat Feb 07, 2009 12:51 am UTC

Timing code:
Spoiler:

Code: Select all

import System.Time

fibs :: [Integer]
fibs = 0:1:zipWith (+) fibs (tail fibs)

timeFunction :: IO TimeDiff
timeFunction = do start <- getClockTime
                  print (last . take 50000 $ fibs)
                  stop <- getClockTime
                  return $ diffClockTimes stop start

main = do nonPrimed <- timeFunction
          primed <- timeFunction
          let TimeDiff {tdSec = nonPrimedSec, tdPicosec = nonPrimedPicosec} = nonPrimed
              TimeDiff {tdSec = primedSec, tdPicosec = primedPicosec} = primed
          print ("Non primed: " ++ (show nonPrimedSec) ++ " " ++ (show nonPrimedPicosec))
          print ("Primed : " ++ (show primedSec) ++ " " ++ (show primedPicosec))

Interpreter:

Code: Select all

<lots of fibs>
"Non primed: 0 479067000000"
"Primed : 0 40140000000"
Compiled with -O2:

Code: Select all

<lots of fibs>
"Non primed: 0 210325000000"
"Primed : 0 1322000000"

Note the number of digits in the picoseconds differ, as 'show' doesn't know its number is less than one. Made more readable they're:

Code: Select all

Interpreter
0.479067000000s
0.040140000000s

Compiled
0.210325000000s
0.001322000000s


Also note that the time includes the time to print the number as well. Lazy evaluation means that if nothing is printed, then nothing is computed either.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Mon Feb 16, 2009 9:38 pm UTC

For problem 24 I wrote a very simple brute force method for achieving the possible permutations for 0, 1, and 2 in Python.
Spoiler:

Code: Select all

list=[]
for a in range(0,3):
    for b in range(0,3):
           for c in range(0,3):
                   if not a==b and not b==c and not a==c:
                            list.append([a, b, c])
Now I know this is probably the most impracticle solution to the problem with all 10 numbers, but I was wondering a couple of things.
a) Is there any way for me to combine all those "for a in range" lines into 1?
b) Is there any way to test if an item appears twice in a list?

Thanks.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Mon Feb 16, 2009 9:54 pm UTC

You *don't* want to bruteforce it. It's definitely the wrong answer.

A simple optimization is to start with a list [0..9] and loop through it. On the inner loop, loop through [0..9] minus the number you're currently on. On that inner loop, loop through [0..9] minus the two numbers you're currently on. Etc. There are several different ways you could do this efficiently.

That's still not a *good* way to solve it, but it's a *better* way than what you're currently doing.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Mon Feb 16, 2009 10:15 pm UTC

Generating all permutations using a generator:

Code: Select all

def permute(list):
  if not list: yield []
  else:
    for e in list:
      l = list[:]
      l.remove(e)
      for p in permute(l):
        yield p + [e]


Not the most effective solution, but one of the more succinct versions. Note that this is indeed the wrong way to go about it. My computer takes a while to even count as high as the answer, just incrementing a number.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Wed Feb 18, 2009 2:50 pm UTC

Myself, I refrained from bruteforcing the answer for 24. Instead, I imported islice and permutations from itertools and let them do it for me.
Work smart, not hard. :D

Counting the import statement, it takes all of two lines and ~0.065 seconds to run.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Wed Feb 18, 2009 4:07 pm UTC

I simply leveraged factorial, div and mod. Excluding my own factorial definition (the name itself is almost as long as the entire definition) I did it all in two lines as well.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Wed Feb 18, 2009 8:07 pm UTC

Guff wrote:Myself, I refrained from bruteforcing the answer for 24. Instead, I imported islice and permutations from itertools and let them do it for me.
Work smart, not hard. :D

Counting the import statement, it takes all of two lines and ~0.065 seconds to run.


I feel like an idiot, not being able to figure out how to get "islice" or "permutations" to output anything besides <itertools.permutations object at 0x36b780>...

I guess I should learn more about generators.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Thu Feb 19, 2009 2:55 am UTC

HenryGifford wrote:I feel like an idiot, not being able to figure out how to get "islice" or "permutations" to output anything besides <itertools.permutations object at 0x36b780>...

I guess I should learn more about generators.
That's what I ran into when I first started out, too. Basically, iterators and generators on their own don't do much and aren't very useful for much of anything. When they become meaningful is when you use them in a for loop or call a function on them that does something with the elements, like list() or sum(). The main thing, I guess, is that even though you can't see the individual elements in the representation of the object, just have faith that they'll be there when you need them. Each element is only computed as it's needed, and going along with that is the fact that in general you can't treat them like lists (i.e. no subscripting like foo[bar:baz:blargh]).

I forget if there was a point I was going to make. Oh well.

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Thu Feb 19, 2009 3:37 am UTC

Guff wrote:
HenryGifford wrote:I feel like an idiot, not being able to figure out how to get "islice" or "permutations" to output anything besides <itertools.permutations object at 0x36b780>...

I guess I should learn more about generators.
That's what I ran into when I first started out, too. Basically, iterators and generators on their own don't do much and aren't very useful for much of anything. When they become meaningful is when you use them in a for loop or call a function on them that does something with the elements, like list() or sum(). The main thing, I guess, is that even though you can't see the individual elements in the representation of the object, just have faith that they'll be there when you need them. Each element is only computed as it's needed, and going along with that is the fact that in general you can't treat them like lists (i.e. no subscripting like foo[bar:baz:blargh]).

I forget if there was a point I was going to make. Oh well.

Ah, I got it in one line with just permutations from itertools, but it took about 15 seconds...

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Thu Feb 19, 2009 3:45 am UTC

HenryGifford wrote:Ah, I got it in one line with just permutations from itertools, but it took about 15 seconds...

Hmm. Given the length of the code it's hard to diagnose the problem without seeing the whole thing, and that's kind of a no-no with Project Euler.

My guess is that you're making a very large list at some point, but even then I'm not sure why it would be taking so long. On my relatively modest machine it can go through all three million permutations in less than three seconds, so that seems odd to me.

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Thu Feb 19, 2009 3:51 am UTC

Here could I PM the code to you?

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Thu Feb 19, 2009 4:32 am UTC

HenryGifford wrote:Here could I PM the code to you?

Sure. Can't guarantee I'll be able to figure it out, but I can try.

aido179
Posts: 16
Joined: Thu Dec 04, 2008 5:03 pm UTC

Re: Project Euler

Postby aido179 » Mon Feb 23, 2009 7:41 pm UTC

i heard about PE a few weeks ago...but back then, the only language i had any fluency in was GML (game maker language...from yoyogames.com if your interested :P )

so i decided i'd try and further my knowledge (always good thing). i had tried to learn c/c++ a few years ago along with java, java script, and a few others but python seemed to stick out to me as most suitable to start with (to get a basic knowledge of practical programming).

so i started with 1 today. i got a good result within 30 mins from reading the problem to output.

i'd only love to be critiqued on my code here...i have a LOT to learn.
heres what i used:

Spoiler:

Code: Select all

limit = 1000 #the amount to work up to
threes = [] # multiples of 3
fives = [] # multiples of 5
l = 0 # limit
numbers = set()#numbers to add, without duplicates

#3
while (l*3) < limit:
    threel = l*3
    threes[-1:] += [threel]
    l += 1

#5
l = 0 #reset l for 5
while (l*5) < limit:
    fivel = l*5
    fives[-1:] += [fivel]
    l += 1

numbers.update(threes, fives)
print sum(numbers)

i didn't really wanna bother thinking about deducting duplicates, so i went with a set...which would automatically do it for me.

HenryGifford
Posts: 152
Joined: Mon Nov 03, 2008 2:01 am UTC

Re: Project Euler

Postby HenryGifford » Mon Feb 23, 2009 7:58 pm UTC

aido179 wrote:i heard about PE a few weeks ago...but back then, the only language i had any fluency in was GML (game maker language...from yoyogames.com if your interested :P )

so i decided i'd try and further my knowledge (always good thing). i had tried to learn c/c++ a few years ago along with java, java script, and a few others but python seemed to stick out to me as most suitable to start with (to get a basic knowledge of practical programming).

so i started with 1 today. i got a good result within 30 mins from reading the problem to output.

i'd only love to be critiqued on my code here...i have a LOT to learn.
heres what i used:

Spoiler:

Code: Select all

limit = 1000 #the amount to work up to
threes = [] # multiples of 3
fives = [] # multiples of 5
l = 0 # limit
numbers = set()#numbers to add, without duplicates

#3
while (l*3) < limit:
    threel = l*3
    threes[-1:] += [threel]
    l += 1

#5
l = 0 #reset l for 5
while (l*5) < limit:
    fivel = l*5
    fives[-1:] += [fivel]
    l += 1

numbers.update(threes, fives)
print sum(numbers)

i didn't really wanna bother thinking about deducting duplicates, so i went with a set...which would automatically do it for me.


Well that's a lot of code for what is a pretty small problem... Not to give out any PE answers on here, but just one tip.

x%y gives the remainder of x/y. So if you typed "5%3" you'd get 2, because 3 goes into 5 once with a remainder of 2.

You can get the answer in one line of Python, so keep working at. You seem to have the right state of mind for it.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Mon Feb 23, 2009 9:26 pm UTC

Code: Select all

print sum(x for x in xrange(1,1000) if x % 3 == 0 or x % 5 == 0)


Really though, it's not too bad for a beginner programmer. I remember I did something similar when I solved that the first time. Kudos on the comments as well, they're saying what the code doesn't. Information in comments should never overlap information in the code.

Some comments on the code itself:
Reusing variables is usually considered bad. You can make as many of them as you want, and give them any name you want, so there's no reason why you should have to reuse l in two loops. Problems with reusing variables is that you might've e.g. forgotten to reset it before the second loop. Also, when you know you have to loop a finite number of steps and/or using a loop-variable, a for loop is usually preferable (in python looping x amount of times is simply 'for i in xrange(x):', more about xrange later). While is for when you have no easy way to know how many loops it takes to finish, (e.g. 'while n != 1: if n % 2: n = n * 3 + 1; else: n = n / 2') but this distiction is rather fuzzy, so don't worry too much about it. Here, however, it's not hard to see there are 1000/3 numbers divisible by 3 below 1000, and 1000/5 numbers divisible by 5. For loops also initialize your variables for you, so you don't have to worry about resetting them. In most other languages, for also introduces scope, so the looping variable isn't visible after you've finished with the loop. For some unknown reason, this doesn't apply to python... Most consider it a bug.

A list has an append method, so instead of doing 'threes[-1:] += [threel]' you can just do 'threes.append(threel)'.
Two things to help you discover such things are 'dir' and '__doc__'. 'dir' is a method that returns all attributes of an object, and '__doc__' is an attribute all objects have that contains a documentation string, hopefully describing the object. This is useful in helping you not reinventing the wheel. For example, you might have a string containing a chapter of a book. You want to work on each sentance individually, so you'd like some way to automatically split the string into a list of strings containing sentances. If you do 'dir(string)' you'll see that it has a method by the promising name of 'split', so you try that. Unfortunately, what you got back was a list of words, not sentances. by trying 'print string.__doc__' you get the docstring, telling you the default is to split on space, but if you want you can supply you own split token, such as the period.
There's always the internet too.

Functions are your friend. you've got two pieces of code that look almost identical with just a few minor adjustments. In the vast majority of cases this means it should probably be a function:

Code: Select all

def findAllMultiples(multipleOf, maxNumber):
  numberList = []
  for number in xrange(1, maxNumber / multipleOf + 1): # We need +1 because xrange stops on the number before
    numberList.append(number*multipleOf)
  return numberList

You can then replace half of your code with 'threes = findAllMultiples(3, limit); fives = findAllMultiples(5, limit)', and you also don't have to worry about resetting l.

Now for a bit on the algorithm:
Using a set was clever, but it would've been even cleverer to realize you don't actually need the collection of the numbers, just their sum. The problem here is the duplicates, and that's the remainder comes in. I'm not sure how familiar you are with it, so I'm going to assume you're not for the sake of completeness. I remember being taught about division and remainder in elementary school and used division all the time since then, it being an integral part of mathematics. Remainder, however, I had completely forgotten about until I started coding, where it became immediately useful and more prevailent than division. In python (and most languages) it's the operator %, which is actually the modulo operator, which is slightly different for negative numbers. Anyway, the following equation is always true except when b = 0: a / b = b * n + r. Here, n is the result of the division (remember, integer division always returns an integer, rounded towards zero) and r is the remainder of the division. This tells us that when r = 0 a must be a multiple of b, just because n has to be an integer.

Before we go on I'll explain range/xrange. Both do the same, essentially, but differ in how they do it. When given a number, range produces a list with all the numbers from 0 to that number minus one (the length of the list will be equal to the number which is usually what we want. When looping, the elements of the list are usually unimportant, but the length is not because it decides how many loops we'll do). 'range(5)' produces '[0,1,2,3,4]'. When given two numbers, it produces a list from the first number to the second minus one, so 'range(3,6)' produces '[3,4,5]'. When given three numbers it produces a list from the first, to the second (but not the second itself), using increments of the third, so 'range(3,10,3)' produces '[3,6,9]'. You can also give it negative increments, so 'range(5,0,-1)' produces '[5,4,3,2,1]'
xrange works just the same as range, except instead of creating all the numbers and returning a list, instead it returns a generator that produces the numbers one at a time when asked to. The for loop is smart enough to know what to do with a generator, making it possible to loop over all the numbers in a range without actually creating the list itself. The advantage of using a generator is that you don't have to waste memory and time creating and moving around large lists, while the disadvantage is that once a generator has returned something it forgets everything about it, making it impossible to re-use them. (You could create several generators generating the same thing, but that means calculating the same things several times as well when a list means only doing it once).

Combining remainder and xrange we can easily loop over all numbers below 1000 and collect the ones we want:

Code: Select all

totalSum = 0
for number in xrange(1,1000):
  if number % 3 == 0: # is a multiple of 3
    totalSum += number
  if number % 5 == 0 and not number % 3 == 0: # is a multiple of 5 and NOT a multiple of 3 (if it is, we already added it)
    totalSum += number

Once we've gotten this far, we see that we can remove the 'and not number % 3 == 0' bit by using 'elif' because that won't be run unless the first if is false. Seeing how both conditional statements do exactly the same, we can combine them into one by oring them together: 'if number % 3 == 0 or number % 5 == 0:'

If you're up on python syntax, you might know about list comprehension, which looks like '[statement(element) for element in sequence if condition(element)]', e.g. '[x*2 for x in xrange(1,5) if x != 4]' produces '[2,4,6,10]'. You might also know about generator comprehension, which is exactly the same except it looks like '(statement(element) for element in sequence if condition(element) )' and produces a generator instead of a list. If it's the only argument to a function, one pair of parenthesis is enough. This means we can easily feed the for loop a sequence of only the interesting numbers and removing the if, using 'for number in (x for x in xrange(1,1000) if x % 3 == 0 or x % 5 == 0):'.
You might also know about the 'sum' function, which takes a sequence of numbers and returns the sum of all of them, which is exactly what we do with our for loop, so we can replace that as well, yielding the final 'sum(x for x in xrange(1,1000) if x % 3 == 0 or x % 5 == 0)'.

There is an even more clever way to solve this problem, by only generating the numbers that are multiples of 3, 5 or both in such a way that there are no duplicates, but if you're able to do that you get the solution to problem 204 for free as well so I won't go into details.

I've also noticed I have a habit of turning the targeted intelligence level of my explanations down the more I explain until a kindergardener could make sense of it. Sorry if I did that here, I'm not being condescending!
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Thu Feb 26, 2009 2:30 am UTC

I just solved problem 231. It took me a while to write because I got sidetracked by trying to get my original method to work.
Then I remembered a nice theorem regarding the prime factors of factorials from a number theory book I've got. From there, I just treated the binomial coefficient as a quotient of factorials. Takes about 56 seconds to run, but I think I can probably cut that down a bit by making a few tweaks.

Edit: just got it down to 36.6 seconds. I love itertools.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Thu Feb 26, 2009 2:42 am UTC

Guff wrote:I just solved problem 231. It took me a while to write because I got sidetracked by trying to get my original method to work.
Then I remembered a nice theorem regarding the prime factors of factorials from a number theory book I've got. From there, I just treated the binomial coefficient as a quotient of factorials. Takes about 56 seconds to run, but I think I can probably cut that down a bit by making a few tweaks.
I just looked it (the binomial factorial quotient thing) up on wikipedia, something I'm a little ashamed about.

I'm not good with math. At least I'm not in a nerdy context. At least I'm able to run circles around most others when it comes to doing pieces in your mind, but that doesn't help much when you're past calculus.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Thu Feb 26, 2009 3:04 am UTC

Berengal wrote:I just looked it (the binomial factorial quotient thing) up on wikipedia, something I'm a little ashamed about.

I'm not good with math. At least I'm not in a nerdy context. At least I'm able to run circles around most others when it comes to doing pieces in your mind, but that doesn't help much when you're past calculus.

Well, I looked on Wikipedia too because I didn't remember what the exact formula was but it turned out to be simpler than I had realized. And if you think about it, it's not that hard to figure it out on your own. Problem: I don't think much.
Also, based on looking at the solutions in the problem's forum, there's a somewhat simpler method for directly calculating the exponent of each prime in nCk rather than having to do so for each of the factorials that make it up. But, I'm just glad I used only my own code (except itertools, but that doesn't count :P ) and got it to run in less than a minute.

User avatar
mabufo
Posts: 105
Joined: Sun Sep 09, 2007 11:17 pm UTC

Re: Project Euler

Postby mabufo » Thu Feb 26, 2009 7:28 am UTC

Hi guys, I'm fairly new to project Euler, I've only solved 5 problems so far. I'd like to make it past 10.

I'm thinking about writing a series of libraries and classes that will help solve the problems. Perhaps a matrix library, a prime number library, factoring, and things of that sort. Have any of you done this in the past? What libraries/classes would be the most useful to have?


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 9 guests