Project Euler

[t̷s͢uk̕a͡t͜ư]

http://www.projecteuler.net

I know some of you must have heard of this, because it was here that I first heard of it and started on it. I didn't get very far before I stopped and forgot my login information.
Semi-recently, a computer science-oriented club I'm affiliated with has been discussing some of these problems, so I've gotten back in the game.

I've only really worked on them during biweekly club meetings, and I finished problem #25 earlier today at one of those meetings. (I've been doing them strictly in order, without skipping.)

Has anyone else worked on this / is anyone working on these problems actively?

[squibbles]

Ah yeah. I remember this.

My computing class used to work on these in yr 12 once we finished our assignments, since we were not allowed to play games and all the computers had been reoriented so the screens faced the teacher's desk.

More often then not we ended up just writing programs to solve them for us, though.

[t̷s͢uk̕a͡t͜ư]

More often then not we ended up just writing programs to solve them for us, though.

The directions tell you to do exactly that. The simplest of these are stupidly difficult without the aid of a computer.

[squibbles]

...that explains why we could never get so many of them. :|

Well, either way, I'm up for a bit of a community race right now with these. Anyone else?

[OneSevenNine]

Before I knew about project Euler, I thought I really liked math.

Looking at question 1 alone, there are 98047 (as of today) people that like math a lot more than I do.

I'd join the race except for the fact that I can't find a single problem that I wouldn't just write a program to brute-force, other than possibly the first one which I could probably manage. Unless brute-forcing is how you're supposed to do it, which I doubt it is.

[t̷s͢uk̕a͡t͜ư]

I'd join the race except for the fact that I can't find a single problem that I wouldn't just write a program to brute-force, other than possibly the first one which I could probably manage. Unless brute-forcing is how you're supposed to do it, which I doubt it is.

You're free to get the answer by any means you want, including brute-forcing. But many of the later problems introduce subtle complications that would make the brute force take ages if not optimized in some clever way.
If you want to get technical, the way I've solved most of these is through a brute-force approach, but very few of my solutions have taken more than a few seconds because I reduced the problem space dynamically based on the ongoing results of the brute-force search, and that is not something a common clueless code monkey would think or be able to do.

Additionally,

I've written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

And obviously, the first few problems are a breeze. They're supposed to be.

When I finished problem #25, it said I earned "first level" and gave me a tetrahedron-shaped badge. It was a little weird, sure, but it also said that I achieved what 79% of people who tried Project Euler problems have not. So even though there are thousands of solutions per problem, only a fraction of those have actually gotten meaningfully far in the latter problems.

[Scrivener]

this is fun, even though i know i'll eventually be halted by my reliance on my calculator, which is the only thing i can do programming of any real significance on.

[t̷s͢uk̕a͡t͜ư]

my calculator... the only thing i can do programming of any real significance on.

Ha!
Project Euler is not for you.

[Spawn of Yanni]

Always something I've wanted to have a shot at, but never attempted due to absolutely no experience with any sort of code in the history of ever. Just got done with a semester of Java so I'll probably be checking it out over summer, though.

[squibbles]

Just out of curiosity, what language will everyone be using? I'm tossing up between java and javascript myself.

I need to find myself a compiler, however, as I accidentally lost it in my OS change, and thus cannot do much with Java right now.

[sidke]

these were fun. AE royally creamed me on 220, i still haven't solved it
also python makes these a lot easier, letting you spend more time on actual problem solving than code debugging

[t̷s͢uk̕a͡t͜ư]

I've been using most of these problems as Ruby practice, actually.

Tangent:
Some time ago, I was interested in knowing a wide range of programming languages so that I had a bunch of useful tools to choose from for any particular task, but I noticed pretty quickly that just about anything I do with code fits pretty solidly into one of two categories:

1. I need it to run extremely quickly.
2. It's a totally non-intensive doodad that I want for convenience.

So for (A), I've focused on getting better at C, and for (B), the jury's still out. I've been doing a whole lot of C in the last few months, but before that, Python was probably the language I knew the best. Some features of Ruby stood out to me, though, so I wanted to give it a try. I read through the Ruby language specification, and it seems more consistent and enjoyable for me than Python, but I needed practical experience to verify that. Without projects to work on in Ruby, I decided to put it to the test in Project Euler.
However, some of the brute-force approaches I took on some of the problems were simply taking far too long in Ruby, and though some part of me feels like it's cheating at Ruby Practice when I recode my algorithm in C and have it finish in under a second, for some of these problems, I just want to move past them and never think about them again.

Regarding Java, I am beside myself with joy to know that every CS professor I've had at UCSC despises Java. Fuck it, deep and in the skull, while its children watch.

Oh, and I've also been learning Scheme on the side, starting with the famous SICP (the MIT "wizard book") and moving on through The Little Schemer, The Seasoned Schemer, and the Reasoned Schemer. I'm about 20% of the way through Seasoned Schemer right now, having read the previous two mentioned. I haven't learned nearly enough of the language to actually work on these problems, though... maybe I'll try to kludge Scheme into use when I learn enough about it. The problem is primarily that the books (and, heck, the language itself) are designed more to help you think about computer science in novel ways rather than to teach you to write production code. I'm learning all kinds of weird, mind-bendy tricks with lambda functions, but still have yet to learn basic I/O or string manipulation. I should probably move on to Common Lisp when I finish with The Reasoned Schemer or something.

[OneSevenNine]

You're free to get the answer by any means you want, including brute-forcing. But many of the later problems introduce subtle complications that would make the brute force take ages if not optimized in some clever way.
If you want to get technical, the way I've solved most of these is through a brute-force approach, but very few of my solutions have taken more than a few seconds because I reduced the problem space dynamically based on the ongoing results of the brute-force search, and that is not something a common clueless code monkey would think or be able to do.

Optimization of Brute-forcing? That's something I never thought about... I always assumed that the point was to find some sort of shortcut that you'd have to be a math/logic genius to recognize. I might try some with that in mind, though if I didn't think of it in the first place who knows how far I'll get.

Regarding Java, I am beside myself with joy to know that every CS professor I've had at UCSC despises Java. Fuck it, deep and in the skull, while its children watch.

Just my luck, Java is the standard for what high schools teach around here. After three years of it, I've been thinking about trying teach myself python or something over the summer.

[Scrivener]

I've been thinking about trying teach myself python or something over the summer.

Stupid BASIC programming.

[t̷s͢uk̕a͡t͜ư]

BASIC programming.

Fine, there is one thing worse than Java.

[otters]

BASIC programming.

Fine, there is one thing worse than Java.

If PHP counts, there are two things.

Still, my best language (until I get better at Ruby) is PHP, so that's what I've been using.

Incidentally, are there any better tactics than brute-forcing with Problem 1? (As in a for loop, starting at 3, incrementing by 1 each step, if divisible by 3 or 5 add to total sum)

[t̷s͢uk̕a͡t͜ư]

Incidentally, are there any better tactics than brute-forcing with Problem 1? (As in a for loop, starting at 3, incrementing by 1 each step, if divisible by 3 or 5 add to total sum)

You're doing upwards of 2000 computations (up to 2 division problems for each of 1000 iterations), and that's extremely wasteful. You can get away with it here for such a small range, but you'll need more clever solutions in later problems.

Although I shouldn't be talking, because I think the way I did it ended up being a little more costly in terms of CPU time, but I think it's more elegant. :p
What I did was build sets of all multiples of 3 and all multiples of 5, take their union (which will weed out duplicates), and the sum up the values in that union. Rather than write my own set-intersection functions, though, I assumed that Ruby's was good enough. It was only the first problem, after all.
My solution was a one-liner in Ruby:

Code: Select all

((1..333).map { |i| i*3 } | (1..199).map { |i| i*5 }).inject(0) { |sum, n| sum + n }

Or more clearly:

Code: Select all

threes = (1..333).map { |i| i*3 }
fives = (1..199).map { |i| i*5 }
union = threes | fives
union.inject(0) { |sum, n| sum + n }

[taaveti]

Personally, I would add three times the sum of the natural numbers <= 333 (which is the sum of the multiples of three < 1000) and five times the sum of the natural numbers < 200 (which is the sum of the multiples of five < 1000), then subtract fifteen times the sum of the natural numbers <= 66 (which is the sum of the multiples of fifteen < 1000, i.e. those which were double-counted).
Each of these sums is the sum of natural numbers 1..N for some finite N, which is to say there is a closed form: N * (N+1) / 2. Net result: three increments, six multiplications, three right shifts (which could actually be done at the end, for only one right shift), an add, and a subtract.

[t̷s͢uk̕a͡t͜ư]

Personally, I would add three times the sum of the natural numbers <= 333 (which is the sum of the multiples of three < 1000) and five times the sum of the natural numbers < 200 (which is the sum of the multiples of five < 1000), then subtract fifteen times the sum of the natural numbers <= 66 (which is the sum of the multiples of fifteen < 1000, i.e. those which were double-counted).
Each of these sums is the sum of natural numbers 1..N for some finite N, which is to say there is a closed form: N * (N+1) / 2. Net result: three increments, six multiplications, three right shifts (which could actually be done at the end, for only one right shift), an add, and a subtract.

This is far superior. I was trying to come up with this solution, but I thought for more than five seconds about how to do it, which is the threshold amount of time I'd spend on a problem that can be brute-forced in under a second.

[Brainwasher]

I'm tackling this after I finish my website mockup applet (java).

[scythe]

http://www.projecteuler.net

I know some of you must have heard of this, because it was here that I first heard of it and started on it. I didn't get very far before I stopped and forgot my login information.
Semi-recently, a computer science-oriented club I'm affiliated with has been discussing some of these problems, so I've gotten back in the game.

I've only really worked on them during biweekly club meetings, and I finished problem #25 earlier today at one of those meetings. (I've been doing them strictly in order, without skipping.)

Has anyone else worked on this / is anyone working on these problems actively?

My fault: http://forum.droni.es/viewtopic.php?f=32&t=2751

I haven't done a problem in months, but you can find me there under "_scythe". I think I've done about 37, the highest of which is #207.

[t̷s͢uk̕a͡t͜ư]

I've been taking 'em all strictly in numerical order. I'm up to #51. I'm pretty sure I know how to solve it, but I've been lazy about coding it up.

[Zephyr]

Okay I made an account, I can only do a little bit of programming, but I guess I'll try.
Would WolframAlpha help?

[squibbles]

Okay I made an account, I can only do a little bit of programming, but I guess I'll try.
Would WolframAlpha help?

For some puzzles, yeah, you could do it there, but you wouldn't be able to for a vast majority of them. :S

[Zephyr]

Mathematica is sooooooo expensive, what else is good for this?