Quantcast

Maximum PC

It is currently Tue Sep 16, 2014 8:24 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 16 posts ] 
Author Message
 Post subject: Programming Practice
PostPosted: Fri Feb 01, 2008 6:54 pm 
8086
8086

Joined: Fri Feb 01, 2008 6:50 pm
Posts: 5
Hi all fellow programmers. I thought I would share a resource that I have come across with you guys.

www.projecteuler.net/

This is an excellent way to get practice on your programming and it doesn't matter what language you know.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 1:01 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Very cool site. I went ahead and solved the fairly easy problem #50.

In the past, I've always recommended TopCoder to people needing practice problems and now I have one for people specializing a bit more in math problems... awesome!

Comparing the two sites, TopCoder is a better choice for someone practicing for an actual programming contest. You just can't practice for a real contest without having a clock ticking in the background making you insane! Also, if you need practice with more general algorithmic techniques, then TopCoder is again a better choice (especially since they've added problem statistics and categories). However, I really like Project Euler and if you want to learn a little math while practicing programming then it is going to be hard to beat. I'll certainly be spending some time there.

I've got to remember to tell Adak and Manta about this one. Great post -- glad to see that someone else around here uses a computer to 'compute' something! =)


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 2:01 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Problem #5 has a incredibly elegant solution. Beautiful.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 5:16 am 
8086
8086

Joined: Fri Feb 01, 2008 6:50 pm
Posts: 5
did you get a solution for problem #5 that solves it under a minute?


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 9:51 am 
Smithfield*
Smithfield*
User avatar

Joined: Fri Jul 09, 2004 9:17 am
Posts: 7159
Location: In HyperTransport
Gadget wrote:
Problem #5 has a incredibly elegant solution. Beautiful.


I'm not very good at number theory, care to explain. Does it take less than 19 multiplications?


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 12:22 pm 
Team Member Top 100
Team Member Top 100

Joined: Fri Sep 17, 2004 5:35 pm
Posts: 1176
I think he just means that it the Euclidean algorithm and the prime factorization method give really quick qolutions.

http://en.wikipedia.org/wiki/Least_common_multiple


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 12:33 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Problem #5 can actually be solved by hand if you have a calculator or function that computes the LCM of two numbers.

Those of you who don't wish to spoil a great little problem should stop reading now! LCM is a big hint btw.

---------------------------------------------------------------------------------
Let's do the example problem by hand. The first observation is that you never have to solve for the entire set of integers. The integers in {1 - 5} are multiples of those in {6 - 10}.

1 * 2 = 2;
2 * 2 = 4;
4 * 2 = 8;

We can get rid of 1, 2, and 4 because they're all multiples of 8. The same is true for 3 and 5 and we're now left with the set {6 - 10}. The second observation is that we're actually trying to find multiples of the numbers in the set and LCM would be the correct answer if there were only two numbers.

My notation for a stack is going to be {bottom of stack, ..., top of stack}. The algorithm/problem is just beautiful. Push the numbers onto a stack, then pop the top two off the stack, compute the LCM for these two numbers, push the LCM onto the stack. Repeat until there is only one number left on the stack.

{6, 7, 8, 9, 10} ==> LCM(10,9) = 90
{6, 7, 8, 90}
{6, 7, x}
{6, x}
{x}

Done. =)


Last edited by Gadget on Thu Feb 07, 2008 1:19 am, edited 1 time in total.

Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 12:37 pm 
8086
8086

Joined: Fri Feb 01, 2008 6:50 pm
Posts: 5
Well yes you can solve some of these by good old calc and paper and pencil but the point of this is to do it using a programming language and by the time you've done a whole bunch you'll have a nice library of functions. Example functions that calculate prime numbers .. odd even numbers . .. numbers with decimal values . .etc...


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 12:41 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kybo_Ren wrote:
I think he just means that it the Euclidean algorithm and the prime factorization method give really quick qolutions.

http://en.wikipedia.org/wiki/Least_common_multiple

You snuck that post in on me while I was typing up the solution. LCM is the important observation. Then the question becomes how to use it to solve for more than two numbers. I would be very interested to see a solution that didn't use LCM.

Also, the author should have done it for the set of integers from 1 to 1000. =)


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 12:42 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kubapl wrote:
Well yes you can solve some of these by good old calc and paper and pencil but the point of this is to do it using a programming language and by the time you've done a whole bunch you'll have a nice library of functions. Example functions that calculate prime numbers .. odd even numbers . .. numbers with decimal values . .etc...

Sure. Assuming that the algorithms aren't so naive that it takes a year to get the answer though. =)


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 12:44 pm 
Team Member Top 100
Team Member Top 100

Joined: Fri Sep 17, 2004 5:35 pm
Posts: 1176
Quote:
You snuck that post in on me while I was typing up the solution. LCM is the important observation. Then the question becomes how to use it to solve for more than two numbers. I would be very interested to see a solution that didn't use LCM.

Also, the author should have done it for the set of integers from 1 to 1000. =)

Haha, I guess I did :)
Your solution is pretty much what I would've done (I would've used a std::deque in C++, same idea though).


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 1:15 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kybo_Ren wrote:
Quote:
You snuck that post in on me while I was typing up the solution. LCM is the important observation. Then the question becomes how to use it to solve for more than two numbers. I would be very interested to see a solution that didn't use LCM.

Also, the author should have done it for the set of integers from 1 to 1000. =)

Haha, I guess I did :)
Your solution is pretty much what I would've done (I would've used a std::deque in C++, same idea though).

I actually did that using LISP. I had written the gcd and lcm algorithms a few days ago, then after figuring out the algorithm, I simply used them and the built in stack to push and pop the numbers. Having a stack just setting there in the interpreter is pretty nice. =)

The other method that I think should work is to find the prime factors of every number in the input set. Put all of the primes into a set then multiplying them together should give the correct answer as well. That's going to be quite a bit slower though.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 4:05 pm 
Team Member Top 100
Team Member Top 100

Joined: Fri Sep 17, 2004 5:35 pm
Posts: 1176
No, it should be fairly fast. Prime factorization for numbers less than enormous RSA-strength ones isn't that hard, so even for the first thousand numbers it would still be a perfectly acceptable algorithm.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 8:43 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kybo_Ren wrote:
No, it should be fairly fast. Prime factorization for numbers less than enormous RSA-strength ones isn't that hard, so even for the first thousand numbers it would still be a perfectly acceptable algorithm.

Well, I said quite a bit slower than the LCM algorithm. I didn't mean to imply that it would be incredibly slow. I guess 'acceptable' is somewhat open to interpretation.

From a practical point of view, I agree that you can probably solve fairly large instances in under a minute; however, I would bet that the same instance can be solved 3x to 10x faster using LCM (and why would anyone not want to use the pretty LCM algorithm instead!). I just might code up both algorithms and find the break-even point.

In terms of complexity theory, integer factorization is considered a hard problem for which no polynomial time algorithm is known to exist (at least on standard hardware -- see Shor's algorithm). As the number of bits increase.... blah, blah, blah -- you knew that though. =)


Top
  Profile  
 
 Post subject:
PostPosted: Sat Feb 02, 2008 9:24 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Problem #149 looks like fun.


Top
  Profile  
 
 Post subject:
PostPosted: Thu Feb 07, 2008 1:40 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Just out of curiousity... has anybody else solved more than 10 of the problems?


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 16 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group