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:
Project Euler
Moderators: phlip, Moderators General, Prelates

 Posts: 15
 Joined: Fri Aug 24, 2007 6:52 am UTC
 Location: Connecticut
 Contact:
Re: Project Euler
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:
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:
look chat date touch grep make unzip strip view finger mount fcsk more fcsk yes spray umount sleep

 Posts: 658
 Joined: Wed Oct 01, 2008 6:04 am UTC
Re: Project Euler
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:
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.

 Posts: 15
 Joined: Fri Aug 24, 2007 6:52 am UTC
 Location: Connecticut
 Contact:
Re: Project Euler
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

 Posts: 658
 Joined: Wed Oct 01, 2008 6:04 am UTC
Re: Project Euler
ok, currently I am working on Problem 54 in python
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
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
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).
 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
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 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.
Re: Project Euler
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!")

 Posts: 658
 Joined: Wed Oct 01, 2008 6:04 am UTC
Re: Project Euler
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
 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
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'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.
Re: Project Euler
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 p_{n}, 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?
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 p_{n}, 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
I'm trying to learn Common Lisp:
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?
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.
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Project Euler
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:
I find this enormously clearer, and easier to code. It unrolls into basically the same thing as the do form, though.
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)))
 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
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.
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.
Re: Project Euler
Yeah, Fibonacci is a perfect target for Haskelly goodness. I wanted to find a mappingandfolding 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.
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Project Euler
Well, you could always do it the simple way, then:
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.
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)))
 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
The eager way of defining fibonacci as a list is to do it as a recursive function:
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).
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.
Re: Project Euler
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.
 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
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 precalculated numbers and calculate from there, doing a lookup for each function call. The iterative way will also start with the two highest precalculated 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.
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 precalculated numbers and calculate from there, doing a lookup for each function call. The iterative way will also start with the two highest precalculated 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.
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Project Euler
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 mutationbased 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 precalculated numbers and calculate from there, doing a lookup for each function call. The iterative way will also start with the two highest precalculated 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 sideeffect: on my computer I can't execute (fibm 10000) immediately, but if I first execute (fibm 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, (fibm 50000) returns in about 2 microseconds. On the other hand, (fibi 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 version^{1}, 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:
Homework: rewrite fibmi to resize the array when you attempt to retrieve a value that is too large.
^{1}: Actually priming fibmi 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 makearray 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)))
 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
'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 higherlevel functions and is selfreferentially defined. Neither consume stack, because listtraversing is tailrecursive, 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).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.
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.
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Project Euler
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)))
 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
Timing code:
Interpreter:
Compiled with O2:
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:
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.
Spoiler:
Interpreter:
Code: Select all
<lots of fibs>
"Non primed: 0 479067000000"
"Primed : 0 40140000000"
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.

 Posts: 152
 Joined: Mon Nov 03, 2008 2:01 am UTC
Re: Project Euler
For problem 24 I wrote a very simple brute force method for achieving the possible permutations for 0, 1, and 2 in Python.
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.
Spoiler:
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.
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Project Euler
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.
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)))
 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
Generating all permutations using a generator:
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.
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.
Re: Project Euler
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.
Counting the import statement, it takes all of two lines and ~0.065 seconds to run.
Work smart, not hard.
Counting the import statement, it takes all of two lines and ~0.065 seconds to run.
 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
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.

 Posts: 152
 Joined: Mon Nov 03, 2008 2:01 am UTC
Re: Project Euler
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.
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
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]).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.
I forget if there was a point I was going to make. Oh well.

 Posts: 152
 Joined: Mon Nov 03, 2008 2:01 am UTC
Re: Project Euler
Guff wrote: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]).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.
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
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 nono 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.

 Posts: 152
 Joined: Mon Nov 03, 2008 2:01 am UTC
Re: Project Euler
Here could I PM the code to you?
Re: Project Euler
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
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 )
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:
i didn't really wanna bother thinking about deducting duplicates, so i went with a set...which would automatically do it for me.
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:
i didn't really wanna bother thinking about deducting duplicates, so i went with a set...which would automatically do it for me.

 Posts: 152
 Joined: Mon Nov 03, 2008 2:01 am UTC
Re: Project Euler
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 )
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:
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.
 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
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 loopvariable, 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 reuse 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.
Re: Project Euler
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.
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.
 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
I just looked it (the binomial factorial quotient thing) up on wikipedia, something I'm a little ashamed about.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'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.
Re: Project Euler
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 ) and got it to run in less than a minute.
Re: Project Euler
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?
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?
Who is online
Users browsing this forum: No registered users and 5 guests