Any interest in a Project Euler Group? - Page 6 - Programming -- Two Plus Two Poker Forums

MrWooster · 06-02-2011, 03:54 AM

Python is more of a scripting language than Ruby

Aceium · 06-02-2011, 04:43 PM

I'm liking Python a lot.

Got the first problem in 5 lines. Love short programs.

sorrow · 06-02-2011, 11:28 PM

Quote:

Originally Posted by MrWooster

Python is more of a scripting language than Ruby

I've found its good for scripting and for OO in larger problems. So far it seems ideal for this problem set.

Feel free to pull from me again

MrWooster · 06-03-2011, 04:03 AM

Have pulled in your latest changes... looks like you are running away with it at the moment.

As an interesting experiment, I am going to write some solutions in javascript and see how they compare speed wise to yours.

MrWooster · 06-03-2011, 05:10 AM

I have just committed my first solution that is written in javascript (using NodeJS as the interpretor).

I have also added a utils folder to the repository with a 'speedTest.py' script (https://github.com/guyht/2p2-Euler-P...s/speedTest.py). This takes one or more solutions, runs them multiple times and compares the average time taken to run each solution.

Code:

Usage:

speedTest.py -[hn] file1 file2 file3

Options:
         -n Number of times to test each solution, default 1000
         -h Display this usage information

Example:
       speedTest.py -n 500 ./user1/solution.py ./user2/solution.py

For example, comparing mine and Sorrows solutions for problem 1:

Code:

2p2-Euler-Project/utils$ ./speedTest.py -n 20 ../problem-1/mrwooster/solution.js ../problem-1/Sorrow/solution.py 
Running 20 times for each solution
Testing solution ../problem-1/mrwooster/solution.js
Average execution time: 0.210370731354
Testing solution ../problem-1/Sorrow/solution.py
Average execution time: 0.171406471729

So Sorrows solution is slightly faster than mine

Note: Both files must be executable (chmod +x) and they will both need environment declarations at the top (e.g. #!/usr/bin/env python).

Also, if you wish to run my solution you will need NodeJS installed.

sorrow · 06-03-2011, 05:42 AM

Quote:

Originally Posted by MrWooster

I have also added a utils folder to the repository with a 'speedTest.py' script (https://github.com/guyht/2p2-Euler-P...s/speedTest.py).

Nice!

Quote:

Code:

2p2-Euler-Project/utils$ ./speedTest.py -n 20 ../problem-1/mrwooster/solution.js ../problem-1/Sorrow/solution.py 
Running 20 times for each solution
Testing solution ../problem-1/mrwooster/solution.js
Average execution time: 0.210370731354
Testing solution ../problem-1/Sorrow/solution.py
Average execution time: 0.171406471729

So Sorrows solution is slightly faster than mine

Hmm - not my results:

Code:

../utils/speedTest.py -n 20 mrwooster/solution.js Sorrow/solution.py 
Running 20 times for each solution
Average execution time: 0.118206512928
Testing solution Sorrow/solution.py
Average execution time: 0.0457811713219

For amusement I also wrote solution-2.py
Testing solution Sorrow/solution-2.py
Average execution time: 0.0434150695801

I'm using a pretty stock Lenovo Thinkpad (circa 2007/2008?) + Ubuntu

MrWooster · 06-03-2011, 06:05 AM

I think the actual execution times will vary a lot between different systems, but the comparison should always be the same....

Just re-written my solution in C and its much faster...

Code:

 ./speedTest.py ../problem-1/mrwooster/csolution ../problem-1/mrwooster/solution.js ../problem-1/Sorrow/solution.py 
Running 10 times for each solution
Testing solution ../problem-1/mrwooster/csolution
Average execution time: 0.0438689947128
Testing solution ../problem-1/mrwooster/solution.js
Average execution time: 0.173312973976
Testing solution ../problem-1/Sorrow/solution.py
Average execution time: 0.130370759964

MrWooster · 06-03-2011, 06:19 AM

I have updated speedTest.py to ignore output from the solutions so you dont have to manually remove the lines of numbers.

MrWooster · 06-03-2011, 06:40 AM

Hmm... I think comparing different languages with the speed test script is not going to be a fair comparison as the bulk of the time taken is loading up the environment. I profiled my javascript code in the application itself and it tool less than 1 millisecond to run.

So the speed test can be used to compare solutions in the same language (as the time taken to load the environment will be the same), but not when comparing different languages.

MrWooster · 06-03-2011, 07:04 AM

Sorrow, did my solution 2 in python so I could get a good comparison. Also speedTest.py now uses arrays to keep track of times (a little more accurate).

Our code is quite different but execution times are v similar. To be honest, I think that the programs at the moment are so small that it is almost impossible to compare their speeds...

Code:

Running 20 times for each solution
Testing solution ../problem-2/Sorrow/solution.py
Average execution time: 0.13228982687
Testing solution ../problem-2/mrwooster/solution.py
Average execution time: 0.133040070534

Sholar · 06-03-2011, 06:41 PM

Quote:

Originally Posted by MrWooster

Hmm... I think comparing different languages with the speed test script is not going to be a fair comparison as the bulk of the time taken is loading up the environment.

Definitely. You want to run the code that does the work N times, not the entire program. Also, compiler optimization (or lack thereof) is going to make a big difference. (And there may be something even more important than those two factors that I don't know about.)

Learning Python has been on my to do list for a while...maybe this isn't a half-bad way to start that.

sorrow · 06-03-2011, 11:37 PM

Quote:

Originally Posted by MrWooster

Hmm... I think comparing different languages with the speed test script is not going to be a fair comparison as the bulk of the time taken is loading up the environment. I profiled my javascript code in the application itself and it tool less than 1 millisecond to run.

So the speed test can be used to compare solutions in the same language (as the time taken to load the environment will be the same), but not when comparing different languages.

I think loading the environment is a legitimate cost but...

Quote:

Originally Posted by MrWooster

Sorrow, did my solution 2 in python so I could get a good comparison. Also speedTest.py now uses arrays to keep track of times (a little more accurate).

Our code is quite different but execution times are v similar. To be honest, I think that the programs at the moment are so small that it is almost impossible to compare their speeds...

This.

Better for testing might be problem 12 - takes about 6 seconds on my machine, and isn't the smartest algorithm or problem 14 - takes about 2 minutes and is brute force.

Sorrow

Victor Kros · 06-04-2011, 09:27 AM

Hey guys, i like thinking about problems like this. So i might chime in from time to time. I am not very good at programming efficiently, so i hope to learn something about that here.

Sorrow did you use Mersenne primes to set an upper and lower bound for problem 12?

With problem 14 you can eliminate so many numbers. For example all numbers x<=500000 because 2x would produce a longer chain. In the same way you can eliminate all numbers of the form 3n+1. As well as the numbers for which y=(x*2-1)/3<=1000000 (if y is an integer) etc.

Victor Kros · 06-04-2011, 10:01 AM

solved problem 14 in 3.416 seconds in matlab, it is brute force after eliminating some possibilities. Is one supposed to post the code itt? Or is that annoying?
matlab claims it took 0.000000 to do the first problem.

sorrow · 06-04-2011, 10:48 AM

Quote:

Originally Posted by Victor Kros

Hey guys, i like thinking about problems like this. So i might chime in from time to time. I am not very good at programming efficiently, so i hope to learn something about that here.

I'm only an average programmer with no particular math skills, i'm doing the problems to get my brain working again.

Quote:

Originally Posted by Victor Kros

Sorrow did you use Mersenne primes to set an upper and lower bound for problem 12?

The triangle number problem? I'm using a pretty simple factor generation method how would I use Mersenne primes?

Quote:

Originally Posted by Victor Kros

With problem 14 you can eliminate so many numbers. For example all numbers x<=500000 because 2x would produce a longer chain.

Should have thought of that...

Quote:

Originally Posted by Victor Kros

In the same way you can eliminate all numbers of the form 3n+1. As well as the numbers for which y=(x*2-1)/3<=1000000 (if y is an integer) etc.

Are you sure ?

I just added a rule to eliminate ((i % 3) -1) and it doesn't find the number with 525 in its sequence, which probably means i'm misunderstanding you.

Quote:

Originally Posted by Victor Kros

solved problem 14 in 3.416 seconds in matlab, it is brute force after eliminating some possibilities. Is one supposed to post the code itt? Or is that annoying?
matlab claims it took 0.000000 to do the first problem.

We are publishing the code publicly in git repositories MrWoosters repo is at https://github.com/guyht/2p2-Euler-P...commits/master

Sorrow