Project Euler

[cottonvibes]

Has anyone here ever heard of Project Euler?
Project Euler (http://projecteuler.net/index.php?section=problems)

Essentially its a collection of computer science/math/programming problems which can be solved in any way you choose (c++, java, asm, mathematical analysis, etc...)

You sign-up and try and solve as much problems as you can.
Once you answer the correct question, you are able to access a forum-thread for that specific problem, where people list their own solutions to the problems. Often times you can learn more optimized ways to code your algorithm from looking at the way other people did it.

I've been solving project-euler problems in my free-time for about 2 weeks now and have solved 30 problems so-far.
I think some of you might also enjoy the challenge, so check it out!

[@ruantec]

mmmm sounds interesting... i may give a try one of this days. thank you for the link cotton :thumb:

[fried_egg]

i will do this.

[runawayprisoner]

Problem 299 is killing my Macbook... oO

How on Earth did someone use Java to solve it under 60 seconds...? 100,000,000 gives over billions of different cases to examine...

I'm gonna have a grand time looking at the different ways people solved it. :p

[cottonvibes]

oh yeah i forgot to mention, every problem is designed to be solvable in under 1 minute if you use an efficient algorithm.

the easier problems can be solved using brute-force/exhaustive-search, however the harder ones must be solved using an efficient algorithm because no pc can calculate the results of some of the harder problems in under 1-minute using brute-force alone.

[runawayprisoner]

Well got my results after a few hours. Obviously there are more efficient ways of doing it, I'm trying to develop a precise algorithm now...

The problem lies in the way some problems need to be proven or verified...

[TitanKvad]

Looks pretty interesting. Shall check this out

[serge2k]

UVa has a set of similar problems.

http://uva.onlinejudge.org/

[cottonvibes]

so anybody actively doing this still? xD
just got to level 2, solved 50 problems so far! :D


i've been using c++ for these problems, but i think a lot of these problems are best solved using languages that support big-integers and easy integer-to-string operations.
i found some random BigInteger class library for c++ which i've been using to solve some of the problems, but the problem is its super slow (the library's goal was readability, not speed), so many times i have to rely on other alternatives to solve the problems.

Many of the problems dealing with huge numbers (numbers with thousands or millions of digits) don't require you to compute the full-precision values.
usually you can just MOD the results with 10^10 and only keep the lower 10 digits valid during your computations.


so far all my solutions have a run-time of under a minute, most are under 1 second.
i feel bad when i can't get some of the programs running under a second, but oh well.

[Boltzmann]

Seems very interesting. I'll take a look later, but I'm guessing my incipient programming knowledge will probably prevent me from going very far.

[@ruantec]

Am planning to give a check but right now am very busy with something you're going to see by the end of this week ;) after that i guess am going to have some free time to spend solving some of them.

[Boltzmann]

Which language would be most suited to these problems, anyway?

cottonvibes says that C++ is not the optimal language, so what would qualify as a language "that support big-integers and easy integer-to-string operations"?

[serge2k]

Java.


I have solved 1-10, 14,16,18,20,25,29, and 67.

[Boltzmann]

Damn, I'm clueless about Java. This should be an opportunity for learning, though, as soon as I finish some work-related projects...

[Proto]

AFAIK people use a multitude of languges to solve this, and none can be said to be better than the other. You'll see most people using some C family language or Java, but I've seen people sloving them using Scheme and Ocaml. Personally I was going to use these problems as an excersice since I've been learning some Haskell.

[cottonvibes]

Which language would be most suited to these problems, anyway?

cottonvibes says that C++ is not the optimal language, so what would qualify as a language "that support big-integers and easy integer-to-string operations"?

a lot of the people that have submitted solutions seemed to have enjoyed using mathematica.

python looks like a nice language to use since it natively supports big integers, and the solutions using it look simple.
ruby is another language with built-in big number support that looks like it would be good to use.

i haven't tried python or ruby; but i know psxAuthor really likes ruby, so i'll take his word that its good.

both java and c# have big integer classes; i would learn c# over java if you pick one of those.
if you prefer functional programming languages, then f# supports big integers (but i hate functional programming).


The shortest solutions are from people using the programming language J.
Lots of times the solution in J is just 1-line of less than 20 characters, whereas the solution in other languages would be 20+ lines.
The code looks crazy though, here is an example of a solution in J:

_10{.":+/^~>:i.999x


also, although i haven't used it, matlab would probably be good to use as well.


that said, you can technically use almost any language, including assembly (which a few people seem to use for their solutions), but the ones i listed above are the ones that seem more suited to the task.

if you have good math analytical skills, there's a number of problems that can be solved by hand, but many are designed to be solved by computers.


I have solved 1-10, 14,16,18,20,25,29, and 67.

nice :thumb:

[serge2k]

I should note that we did 67 (and the related one) at an ACM practice before. So I didn't really do it myself.

[Grv]

What a great idea, bookmarked. Thanks for the links, cottonvibes and serge2k. :)

[cottonvibes]

I should note that we did 67 (and the related one) at an ACM practice before. So I didn't really do it myself.

I did an ACM problem for extra credit in my Programming III class that was similar to problem 67 but a lot harder.
I ended up modifying that code to solve problem 67 (and problem 18 with the smaller triangle).

So far, i've found problem 31 to be one of the most annoying problems on project euler. I had to read online about integer partitioning to solve it.

Problem 79 was one of the funner ones since I did that one by hand (and that's probably the best way to solve it).

[cottonvibes]

update:
solved 75 problems so far :D

25 more problems to go before level 3 :o