Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Project Euler

projecteuler.net

Post reply on HN
Print view View original

41–50 of 172 posts

Re: Project Euler

#41

Post by colejohnson66 »

toAnswerIt wrote: post #32
jackweirdy wrote: post #21

Earlier quoted context omitted.

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is

to see it consider this: S = 1 + 2 + 3 + ... + n-1 + n + S = n + n-1 + n-2 + ...+ 2 + 1 = 2S = n+1 + n+1 + n+1 + ... + n+1 + n+1 every column sums to n+1

Random fact: this only works if the series is finite. Otherwise you end up with sum(1...inf) equaling -1/12.

Re: Project Euler

#42

Post by lostcolony »

toAnswerIt wrote: post #32
jackweirdy wrote: post #21

Earlier quoted context omitted.

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is

to see it consider this: S = 1 + 2 + 3 + ... + n-1 + n + S = n + n-1 + n-2 + ...+ 2 + 1 = 2S = n+1 + n+1 + n+1 + ... + n+1 + n+1 every column sums to n+1

I always understood it just by saying "Okay, if we take the last item and the first (so n+1), and then the second to last item and second item (so n-1 + 2 = n + 1), etc, we get to the middle in n/2 times. If it was odd, we have an extra n/2. But trying it out on a few series, and it's obvious it works out each way, odd or even, to n/2 * (n + 1).

Re: Project Euler

#44

Post by kccqzy »

bunderbunder wrote: post #10
delibes wrote: post #9

Ah, memories. Back in 2010 I whinged to colleagues who were using their fancy functional languages to solve problem 1 inefficiently in 2 lines of code... " Project Euler problem 1 :- It helps to know the sum of (1 .. x) is 0.5 * n * (n+1). Multiples of 3 less than 1000 are (3 .. 999) == (1 .. 333) * 3 = 0.5 * 333 * 334 * 3 = 166833 Multiples of 5 less than 1000 are (5 .. 995) == (1 .. 199) * 5 = 0.5 * 199 * 200 * 5 =…

The best point to be made from this isn't that it's more computationally efficient. It's that, compared to something like sum [x | x which is really just bluntly translating the question into a programming language and letting it take care of the rest, your approach involves some actual insight into the underlying math.

You can do the same in Python, which steals Haskell’s list comprehension.

By the way doesn’t the original problem say exclude multiples of 15?

IMO Python’s generators and coroutines are one of its most useful yet least appreciated features. Being able to suspend a function, resume it, get values from it, send values or exceptions to it is a highly powerful feature. You can use them to implement user-space cooperative threads, write a scheduler for that, implement message-passing concurrency, and do highly efficient multiplexed I/O in the style of asyncio.

Re: Project Euler

#45

Post by [deleted] »

jackweirdy wrote: post #21
delibes wrote: post #9

Ah, memories. Back in 2010 I whinged to colleagues who were using their fancy functional languages to solve problem 1 inefficiently in 2 lines of code... " Project Euler problem 1 :- It helps to know the sum of (1 .. x) is 0.5 * n * (n+1). Multiples of 3 less than 1000 are (3 .. 999) == (1 .. 333) * 3 = 0.5 * 333 * 334 * 3 = 166833 Multiples of 5 less than 1000 are (5 .. 995) == (1 .. 199) * 5 = 0.5 * 199 * 200 * 5 =…

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is

[deleted]

Re: Project Euler

#46

Post by tedmiston »

sevensor wrote: post #38

After hearing about it for years, I decided to start working through Project Euler about two weeks ago. It really is much more about math than programming, although it's a lot of fun to take on the problems with a language that has tail call optimization because so many of the problems involve recurrence relations. I like that the problems are constructed in a way that usually punishes you for trying to use brute for…

I agree with Project Euler being mostly about math. I prefer Codewars for practicing programming or learning a new language.

Re: Project Euler

#47

Post by tedmiston »

iandanforth wrote: post #39
10-6 wrote: post #3

shameless plug: I loved project euler and topcoder when I in high school. In 2011, there weren't really any nice, easy-to-use, interactive websites that allowed me to solve coding/algorithms challenges online easily, so that winter break my first year of college I made coderbyte.com for people to solve challenges online. Been running it ever since, but now there are like 20 similar websites as well.

Thank you! I love coderbyte. I especially love that you can immediately go back, correct your answer and get a perfect score. There is nothing more frustrating than a competitive screening tool that masquerades as an educational tool. Emphasizing mastery over getting it right on the first try is something that I deeply appreciate.

I haven't used Coderbyte yet, but I love the idea of going back and getting credit for showing what you learned / how you improved. (I mostly use Codewars which has a similar feature though.)

I've always wished academia worked this way. Seems logical to me. Everything else we do is iterative.

Re: Project Euler

#48

Post by somezero »

jackweirdy wrote: post #21
delibes wrote: post #9

Ah, memories. Back in 2010 I whinged to colleagues who were using their fancy functional languages to solve problem 1 inefficiently in 2 lines of code... " Project Euler problem 1 :- It helps to know the sum of (1 .. x) is 0.5 * n * (n+1). Multiples of 3 less than 1000 are (3 .. 999) == (1 .. 333) * 3 = 0.5 * 333 * 334 * 3 = 166833 Multiples of 5 less than 1000 are (5 .. 995) == (1 .. 199) * 5 = 0.5 * 199 * 200 * 5 =…

> It helps to know the sum of (1 .. x) is 0.5 * n * (n+1) This is cool. As someone out of full time education, and who dropped maths relatively early, where’s a good place to start learning some of this stuff? By stuff I mean things related to algebra and whatever the black magic I quoted is

Read G.H. Hardy's Introduction to Number Theory, Then possibly A Course of Pure Mathematics, also by him.

Note that the level for which you're aiming, is a level wherein such summation is much closer to triviality, than it is to `black magic` - whatever that means.

Re: Project Euler

#49

Post by tedmiston »

mathattack wrote: post #35
pacuna wrote: post #29

Earlier quoted context omitted.

good luck with that

His point is correct. There are usually efficient and inefficient ways to attack each problem. It's better to solve the math problem first, before the coding problem.

Only when the scale truly matters is the most efficient algorithm the best choice though.

For a lot of problems, especially in early stage startups, the brute force solution is more than sufficient and avoids premature optimization. Having perfect algorithms for everything comes with an opportunity cost in startup land that isn't aligned with whether or not your business succeeds most of the time.

(This really only applies when the efficient implementation doesn't already exist in the standard library or a package.)

Re: Project Euler

#50

Post by Veedrac »

I've solved #555 and #561, which were a lot of fun. Any other good recommendations? Some of the questions in that area look pretty intimidating, but those two were surprisingly approachable.
Post reply on HN