As was foretold, we've added advertisements to the forums! If you have questions, or if you encounter any bugs, please visit this thread: https://forums.penny-arcade.com/discussion/240191/forum-advertisement-faq-and-reports-thread/

Options

Monoxide
Registered User, ClubPA regular

Project Euler

click it, it's an url dummy

I've started looking through these after reading the thread about it on Something Awful and they seem pretty neat. It's a great way to get some programming practice in or get some practice in while learning a new language. Since I've decided to toy with Python, I'll be trying to do these with that, but you can use any language you like.

click it, it's an url dummy

What is Project Euler?

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I've started looking through these after reading the thread about it on Something Awful and they seem pretty neat. It's a great way to get some programming practice in or get some practice in while learning a new language. Since I've decided to toy with Python, I'll be trying to do these with that, but you can use any language you like.

0

## Posts

Veegeezeeon0bliqueonSmasheronOh, maybe it's not a contest. D'oh.

These

arepretty cool, but shit, I have a too much real programming to do already.I'm dreaming about calling methods and objects every now and then.

Sheesh.

JasconiusonCold KoalaonEdit: This finally prompted me to download an environment at home, because while it'd be easier (and I'd be more in the mindset) to do it at work, I really shouldn't.

Cranked out the first few. I'm being nowhere near the most efficient manner possible, but it's more an effort to make sure I remember how to do some of this stuff (both math and programming-wise).

JragghenonThe first one needs modulus stuff! Yay!

LewishamonSmasheronProblem 3 was a cheat, because I didn't know how to specify whether a number was prime. Now I do! I'm using these to learn maths and Haskell at the same time. I did problem 1 all by myself, found out it was horribly slow, then used the clever Haskell way on the Internet. Again, learning is fun! Problem 1 and 7 I did all by myself. I like Problem 7 a LOT, as it really illustrates how much power Haskell's infinite lists can buy you. It's basically a one-liner, albeit with an expensive boolean test.

Haskell gurus: I require your help!

Is there a way I can merge these into one function so that it runs infinitely if not passed n, or up to the sequence if passed a limit?

EDIT: Answer - primesUpto n = takeWhile (< n) primeNumbers

Yayyyy.

LewishamonProblem 6 was so easy in Haskell.

p6 x = abs (sum (map square x) - square (sum x))

LewishamonMr_AnonymousonI have to sit and think about pretty much every line of Haskell I write, but it means that the code is cleaner, and better for it. You can't half ass a Haskell implementation of anything.

LewishamonI guess I'll probably switch to C for some of the later ones, especially the ones that require you to read ridiculous long .txt files

Randall_FlaggonMaybe I just don't get Haskell, but I count 22 lines.

NibbleonThat code has the answers to 4-5 questions. Admittedly, problem 7 builds on things from the other problems, but my point was that you can take things and adapt them very quickly. I did actually solve a problem in one line (the one about finding the difference between the sum of squares of all numbers in a sequence and the square of the sum of the numbers in the sequence), but I left it at work

LewishamonI ended up doing it by hand, then realised that there's an lcm function in the Prelude. At that point, of course, it was just a fold away.

Your solution to 7 is much briefer than mine, although that's probably because I just grabbed a prime list I already had that was designed for efficiency as much as readability (there are two lists building on each other, and two helper functions that might well exist elsewhere)

If you just want clarity (execution speed is abysmal) then this isn't bad.

LindenonThese are good stuff though, great find!

TechnicalityonI did that for the question about the sum of the primes less than a million (question 10?).

It took 2 hours on an Intel Mac But my Math is not good enough to do it more efficently.

LewishamonI could have written this faster if I just used a list instead of an IEnumerable. Execution time is around 3 seconds. This is obviously not optimal at all.

I know it seems like a lot of code, but most of it will be reused a lot.

Problem 1:

Problem 2:

Problem 3:

Problem 4:

Problem 7: (uses stuff from problem 10)

I just got 11, but the code is too ugly to post. I need to clean it up.

jackalonI did say that performance was bad!

My current code for that particular problem (using a generalised version of your primesUpto function) gives pretty reasonable timing.

The lists and first two helper functions are from literateprograms.org (was looking at these during my earlier explorations), and both functions work only with infinite sorted lists.

LindenonProblem 11:

I feel dirty because I looked up an algorithm for problem 12.

jackalonA little OT: but how do you feel about $ notation? I just read what it meant, which is to say it essentially wraps up the next thing in parathenses, so your code goes to:

Maybe I'm just stuck in my ways, but I find parens more obvious as to what is binding to what.

LewishamonI find it helpful, but mostly for obvious examples with several nested functions. That example is probably the result of me changing the code – I'm pretty sure there was more there initially. As an example, I had a main function in Problem 4 which contained

In this situation, I find the $ clearer than the parentheses, but there are certainly circumstances where the reverse would be true.

Incidentally, those functions are equivalent to but replacing the $ with parens causes a typing error. If we also surround the three functions with parens, it works as expected.

Clearly someone really wanted a variety of options. There's $!, as well, which causes strict evaluation.

Edit: This is also posted here, for any interested parties and to avoid cluttering this thread.

LindenonWoo! Finished the first 15.

jackalonjackalonI needed to speed up the function I used to sum the digits of BigIntegers:

The original:

Used DivideAndRemainder function instead of seperate function (twice the speed of original):

Broke number up into Integer sized chunks and then summed their digits (ten times the speed of the original):

I tried one that breaks the number up into long sized chunks, but it didn't run any faster. I tried a function that would split up the number into half on a power of 10 border and then subdivide that until it is down to integer size, but it ran slow. I think I did something wrong.

jackalonJaninonAlso, how many has everyone solved so far? I'm on 25. (I took a long hiatus.)

Cold KoalaonIt looks like Visual Basic. I think you can call Java classes in VB .NET to some extent, though I don't know the details.

MonoxideonSeveral Java classes can be used if you reference vjslib. I think most versions of Visual Studios should come with it. If not just install Visual J# 2005 Express Edition. It seems like a lot of trouble, but it is easier than implementing your own bigint library.

I have solved 36 problems so far, but I haven't touched any in at least a month. I'm glad this got resurrected. After a while it was just me talking to myself. I need to get back to work on 76.

jackalonProblem 1

Problem 2

It seems like I should be able to do this more easily. I actually had to use a control structure!

If you let it run long enough it will throw an overflow exception. That actually seems more correct than if it stopping, because the Fibonacci numbers don't stop.

Problem 3

Avert your eyes. There is imperative code ahead!

Problem 4

I could also speed it up if I could manage to only join when the value from the second range is greater than or equal to the value from the first range.

Problem 6

Problem 7 and 10

jackalonYeah, I was doing something wrong. This is much better.

jackalonJaninonAnyway 9 using LINQ:

EDIT:

Using nested froms seems to be appropriate than the explicit join. It looks like it could be more optimizable this way.

Here it is in a single LINQ query. It is getting ugly or beautiful. I'm not sure which.

I am digging the anonymous data types.

jackalonPython

JaninonProblem 5 (this is a lot of code for something that takes about a minute to solve on paper):

The disturbing thing is that it can all be smashed into one line of code.

Problem 12:

Problem 29:

This one turned out really well.

Problem 30:

This is the first one I tried from scratch with C# 3.0

jackalonGood lord. Mine might have a few more lines, but I think it's much more readable:

JaninonWell, the techniques are very different. I basically translated how the problem would be solved on paper. Yours looks like a good middle ground between simplicity and speed. If I am understanding your code correctly couldn't you include 11, 13, 17 and 19 in factors and get a pretty significant speed improvement?

jackalonJaninonI think this is how your code could be implemented in C#. How long does your code take to run? This takes a little over a minute and a half on an Athlon XP 1900+.

jackalon