Project Euler

[cottonvibes]

Has anyone here ever heard of Project Euler?
Project Euler

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!

__________________

"It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it." - Albert Einstein
check out my blog

[@ruantec]

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

__________________

Current development tools:

Visual C++.net, Visual C#.net
Visual VB.net, Visual Webdeveloper.net
Bloodshed Dev C++, Borland C++
Visual Basic 6

[fried_egg]

i will do this.

[runawayprisoner]

Problem 299 is killing my Macbook...

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.

[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.

__________________

"It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it." - Albert Einstein
check out my blog

[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

__________________
Check mah muzaks (norwegian nerdcore drum'n'bass-rap)
Myspace / Soundcloud / Youtube / Slask Studio
∀x((your(x)∧base(x))→arebelongto(x,us))
リンクをクリックしてお願いします。（日本語悪くてすみません）

[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!


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.

__________________

"It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it." - Albert Einstein
check out my blog

[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.

__________________
"Let be be finale of seem.
The only emperor is the emperor of ice-cream."
- Wallace Stevens

Me on Twitter

[@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.

__________________

Current development tools:

Visual C++.net, Visual C#.net
Visual VB.net, Visual Webdeveloper.net
Bloodshed Dev C++, Borland C++
Visual Basic 6

[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"?

__________________
"Let be be finale of seem.
The only emperor is the emperor of ice-cream."
- Wallace Stevens

Me on Twitter

[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...

__________________
"Let be be finale of seem.
The only emperor is the emperor of ice-cream."
- Wallace Stevens

Me on Twitter

[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]

Originally Posted by 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"?

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.

Originally Posted by serge2k

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

nice

__________________

"It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it." - Albert Einstein
check out my blog

---

Last edited by cottonvibes; July 27th, 2010 at 02:04.. Reason: Automerged Doublepost

[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.

__________________
I'm not young enough to know everything.

[cottonvibes]

Originally Posted by 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.

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).

__________________

"It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it." - Albert Einstein
check out my blog

[cottonvibes]

update:
solved 75 problems so far

25 more problems to go before level 3 :o

__________________

"It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it." - Albert Einstein
check out my blog