Page 5 of 11

Re: Project Euler

Posted: Sat Jan 31, 2009 5:17 am UTC
by mammothman
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;
}


Re: Project Euler

Posted: Sat Jan 31, 2009 5:59 am UTC
by keeperofdakeys
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

Re: Project Euler

Posted: Sat Jan 31, 2009 6:40 am UTC
by mammothman
Oh wow, thanks a lot, that definitely cuts some time off.

Re: Project Euler

Posted: Sun Feb 01, 2009 7:11 am UTC
by keeperofdakeys
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

Re: Project Euler

Posted: Sun Feb 01, 2009 8:32 am UTC
by jaap
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).

Re: Project Euler

Posted: Sun Feb 01, 2009 2:43 pm UTC
by Berengal
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.

Re: Project Euler

Posted: Mon Feb 02, 2009 4:24 am UTC
by e946
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!")

Re: Project Euler

Posted: Mon Feb 02, 2009 6:20 am UTC
by keeperofdakeys
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

Re: Project Euler

Posted: Thu Feb 05, 2009 8:21 pm UTC
by Berengal
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 2:05 am UTC
by Guff
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?

Re: Project Euler

Posted: Fri Feb 06, 2009 3:20 am UTC
by Briareos
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?

Re: Project Euler

Posted: Fri Feb 06, 2009 4:03 am UTC
by Xanthir
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 4:21 am UTC
by Berengal
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 4:26 am UTC
by Briareos
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 4:34 am UTC
by Xanthir
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 4:56 am UTC
by Berengal
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).

Re: Project Euler

Posted: Fri Feb 06, 2009 6:57 am UTC
by Carnildo
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 10:13 am UTC
by Berengal
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 6:28 pm UTC
by Xanthir
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.

Re: Project Euler

Posted: Fri Feb 06, 2009 10:50 pm UTC
by Berengal
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).

Re: Project Euler

Posted: Fri Feb 06, 2009 11:28 pm UTC
by Xanthir
Out of curiosity, mind timing that for the 50000th number? Before and after priming, please.

Re: Project Euler

Posted: Sat Feb 07, 2009 12:51 am UTC
by Berengal
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.

Re: Project Euler

Posted: Mon Feb 16, 2009 9:38 pm UTC
by HenryGifford
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.

Re: Project Euler

Posted: Mon Feb 16, 2009 9:54 pm UTC
by Xanthir
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.

Re: Project Euler

Posted: Mon Feb 16, 2009 10:15 pm UTC
by Berengal
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.

Re: Project Euler

Posted: Wed Feb 18, 2009 2:50 pm UTC
by Guff
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.

Re: Project Euler

Posted: Wed Feb 18, 2009 4:07 pm UTC
by Berengal
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.

Re: Project Euler

Posted: Wed Feb 18, 2009 8:07 pm UTC
by HenryGifford
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.

Re: Project Euler

Posted: Thu Feb 19, 2009 2:55 am UTC
by Guff
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.

Re: Project Euler

Posted: Thu Feb 19, 2009 3:37 am UTC
by HenryGifford
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...

Re: Project Euler

Posted: Thu Feb 19, 2009 3:45 am UTC
by Guff
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.

Re: Project Euler

Posted: Thu Feb 19, 2009 3:51 am UTC
by HenryGifford
Here could I PM the code to you?

Re: Project Euler

Posted: Thu Feb 19, 2009 4:32 am UTC
by Guff
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.

Re: Project Euler

Posted: Mon Feb 23, 2009 7:41 pm UTC
by aido179
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.

Re: Project Euler

Posted: Mon Feb 23, 2009 7:58 pm UTC
by HenryGifford
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.

Re: Project Euler

Posted: Mon Feb 23, 2009 9:26 pm UTC
by Berengal

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!

Re: Project Euler

Posted: Thu Feb 26, 2009 2:30 am UTC
by Guff
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.

Re: Project Euler

Posted: Thu Feb 26, 2009 2:42 am UTC
by Berengal
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.

Re: Project Euler

Posted: Thu Feb 26, 2009 3:04 am UTC
by Guff
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.

Re: Project Euler

Posted: Thu Feb 26, 2009 7:28 am UTC
by mabufo
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?