Project Euler
projecteuler.net
projecteuler.net
I like that the problems are constructed in a way that usually punishes you for trying to use brute force. Sometimes there's a problem that doesn't have a more elegant solution, though, as if to remind us that brute force often works remarkably well.
- There are problem explanations and an accompanying textbook.
- You can structure the solutions with unit tests that test for known good values.
- There's a graph of problems.
The forums are a fantastic resource once you already know how to solve the problem.
Personally I would like to have a little orientation system to pick a book to learn and get challenges focusing on the subject to reinforce them.
Yes, that's tautologically true. You do have to put in some effort and thought.
I ended up spending too much time per problem (days to weeks) and then I got a kid, so that time is being spent on better things.
He went on to become a PhD in maths and just pointed me in the right direction when I couldn't figure stuff out myself.
So, honestly you just doing 1-100 as a classical musician is really surprising and amazing to me. Great job!
[1]: http://exercism.io
This illustrates one of my favorite things about Project Euler. How you perceive it depends totally on your background: programmers say it's mostly math, math people say it's mostly programming!
One example was adding one hundred 100 digit numbers and returning the first 10 digits of the sum. The forums were full of "only the first 11 digits matter", "no the first 12 digits matter because there are 100 different numbers and 10^2 is 100", etc.
No one considered:
000...00x90
111...11x9
000...01x1
This is true to a degree. My first venture into Project Euler I was using Python, and some of the early problems involve manipulations of lists of numbers. These were almost non-problems using Python. Coming back to those same problems using C, they became a little more challenging.
One of the most important lessons I learned from PE was all the computer power in the world won't outrun a good algorithm.
Me and some friends has been written some solutions for ProjectEuler on a lot of different languages for years. Sincerly, I have a giant feedback from them and we have awesome people writing things on the problem_solved-walled threads per question.
I love the ProjectEuler way to "lock" and "force" the user really solve the problem in your own before getting further for more deep analysis. For me, copy-paste solution don't help in anything to your skills of abstractions! For that reason, for me StackOverflow sometimes may be so evil for non-engineer/non-dev problems. Beginneers should avoid it mainly and search more deeply.
BTW, this is the repo: https://www.github.com/DestructHub/ProjectEuler
It's also very good to learn algorithm and maths. Some problems can even be solved without any programming. And for some, a certain amount of math is necessary to have a efficient solution to the problem.
Ps: you can find the first 50 problems in french here : https://www.lucaswillems.com/fr/articles/19/project-euler-tr...
But nice job translating them :-)
Here's a fairly comprehensive list of those problems, but it hasn't been updated in a while, e.g., 601 is solvable with pencil and paper but it's new enough that it isn't on the list.
It's presented as an advent calendar (so a challenge per day of December) and when you unlock the first half it gives you a second challenge based in the same domain.
There's at least a couple of previous years too, if you just want to crack on and work though something.
It is also a great platform to learn a new programming language. I'm using it as an opportunity to improve my (small) knowledge of rust.
" 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 = 99500
We must subtract common multiples (those of 15), so (15 .. 990) = (1 .. 66) * 15 = 0.5 * 66 * 67 * 15 = -33165
166833 + 99500 - 33165 = 233168
O(1) solution FTW :P Nice looking code is good, but a smart algorithm makes a big difference. "
OK, I was a smug arsehole, but there's a point to be made y'know?
sum [x | x <- [1..999], (mod x 3 == 0) || (mod x 5 == 0)]
The sum of x for x from one to 999 where x mod three is zero or x mod five is zero.
well, the bit in square brackets is a comprehension. `sum `is just ordinary function application.
This might be fixed some time or never. There is little push for ultimate performance and actually identifying arithmetic forms in recursive loops in the front-end is hard. (Heck it sometimes fails to tail optimize.)
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.
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
This looks like it has some ok examples: https://www.tutorialspoint.com/discrete_mathematics/discrete...
You can also start your way up from the basics in Khan's Academy.
Wikipedia[0], MathWords[1] and Brilliant[2] might be some good resources for you.
[0] https://en.wikipedia.org/wiki/Lists_of_mathematics_topics [1] http://www.mathwords.com/ [2] https://brilliant.org/
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
Yes, you can play a nice trick with that sum if you ignore the fact that inf-inf is meaningless.
The math involved in reaching this identity is akin to dividing by zero.
It's disingenuous to assert that is same as the sum of that infinite series without the associated caveats. By the definitions of infinite series that we all learned in calculus, that is a divergent series with no sum.
Edit: Wolfram Alpha[0] has a good graphic showing why this series converges to -1/12 (the one with the red line, drawing a peach-like shape). It also gives an intuition as to how complex numbers are influencing the results despite being omitted from the equation.
The funny thing is that, since then, I've looked at that formula several times and can't for the life of me figure out I got from the above formula to the the sum of the range formula. I guess younger me was smarter than current me.
n^2 = sum(1..n) - sum(1..n-1) = 2sum(1..n-1) + n
=> n^2 - n = 2sum(1..n-1) => n(n-1) = 2*sum(1..n-1) => sum(1..n-1) = n(n-1)/2
And you can rewrite that as... sum(1..n) = n(n+1)/2
Let's start with a 4x4 square:
OOOO
OOOO
OOOO
OOOO
Divide it into two triangles:
OOOO
OOO O
OO OO
O OOO
Note that one of the triangles has a side of (n-1) and other has a side of n. Now, let's see how many elements has each triangle. As I said, we can use diagonal lines. So the first diagonal has 1 element:
O
We then add the second diagonal, which has 2 elements (I'll use lower caps for the elements that were already present):
oO
O
The third one has 3 elements:
ooO
oO
O
And finally we add the last one:
oooO
ooO
oO
O
It's easy to see how this procedure can be extended to any triangle and to any square (which can be divided in two triangles).
So we can see that:
1) A triangle of side n has sum(1..n) elements.
2) A square of side n can be decomposed into a triangle of side n and another one of side (n-1).
3) Now you can use some basic algebra to determine the value of sum(n): if sum(n-1) + sum(n) = n^2, and sum(n-1) + n = sum(n), then 2·sum(n) = n^2+n, therefore sum(n) = (n^2+n)/2, or if you prefer, sum(n)=n·(n+1)/2.
This is an awesome visualization, by the way.
Yes. I meant n^2 = sum(1..n-1) + sum(1..n).
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.
[1] https://www.amazon.com/Magic-Math-Solving-Figuring-Out/dp/04...
Combinatorics is one of my favorite fields I always feel it has a lot of cool gems like that one and the proofs are often really intuitive. Combinatorics is all about counting things like the number of possible poker hands given a single deck or the number of ways you can seat 4 people around a table.
It was already mentioned below but, discrete math is another good one. Discrete math includes combinatorics, graph theory, set theory, logic, and number theory. All of these have really cool little tidbits of information. My Discrete Math course was my favorite class at university so far. One of the first random bits of information I learned in that class was that any number is divisible by 9 if the sum of it’s digits are divisible by 9 this was posed to us in one of our first homeworks to be proven or disproven and we were able to prove it using some algebra.
I've been working with a continuation-pasing style variant of Joy (https://en.wikipedia.org/wiki/Joy_programming_language https://github.com/calroc/joypy) and tried it on the Project Euler problem 1: https://github.com/calroc/joypy/blob/master/docs/3.%20Develo...
I came up with a solution that generalizes to blocks of terms, but yours is much much nicer! Cheers!
""" Between 0 and 990 inclusive there are sixty-six "blocks" of seven terms each, starting with:
[3 5 6 9 10 12 15]
[978 980 981 984 985 987 990]
The Advent of Code 2017 includes a puzzle involving a "spiral" memory grid and I had a similar thing where I was able to figure out a simple mathematical way to solve the puzzle: https://github.com/calroc/joypy/blob/master/docs/Advent%20of...
I'm not explaining it well 'cause I'm all excited to show it.
Many of the bioinformatics problems are also pure Math and CS, so it's probably of broad interest beyond just an interest in biology.
My one criticism is that the examples for some problems are trivial and don't adequately account for any of the complexity of the problem. It can feel a bit like the "Learn to Drawn an Owl" meme: Step 1) Draw an oval. Step 2) Draw the rest of the owl.
I've always wished academia worked this way. Seems logical to me. Everything else we do is iterative.
Sadly, only a small portion of the solutions posted are retained, so if you're not looking for Python or C you'll probably only see a couple of different variations in your language of interest. It would be a huge deal for learning new languages if we could retain all solutions and then sort or filter by language.
I would really like to see something similar for actual programming challenges though. Some real-world examples, maybe with predefined test cases that you then solve and optimize for CPU/Memory/Time/lines/whatever.
Also as a liberal arts in programming, Euler, is fun in the sense of a well done proof is fun in math. If that is your thing you'll enjoy Euler, otherwise as in most programming you will brute force your way to a solution.
The best approach is probably somewhere in the middle. Best example I've seen of this are the "workshopper" lessons on NodeSchool.
For a lot of people, programming has nothing to do with their work, it is just a hobby. Project Euler and the like are great fun for kinds like that.
https://uva.onlinejudge.org/index.php?option=com_onlinejudge...
Having said that the problems in project Euler are more math based in nature.
For instance I often start interview with asking candidate to write a program to find a palindrome. After they answer that my follow up question is to write a program to find the longest palindrome in a given string which is a question taken from project euler.
Here I am mainly interested in their logic and approach to problem solving rather than a workable solution first time round. I don't give take-away problems neither do candidates have to do this in their daily jobs.
That said, I believe the 100-150 easiest (i.e. solved by the most people) problems are all OK. Many of them take one hour or less. I think, it never took more than a weekend for one.
Many of the ~2006 problems can be brute forced nowadays with a low level language, which makes them quite a bit easier.
Don't get sucked in!
Solved 38 problems and forgot my password after a short pause, haven't been able to log in for years :(
Once you find "the" trick, is there still a lot of computation involved? Do you still write loops? How many orders of magnitude times do those loops run? How do you know when your code is too computationally intensive and you haven't found "the" trick yet?
This never happened to me. No one seems to know the site. They seem to be mostly interested in Top Coder and similar platforms.
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.)
Most of the elegant solutions do exist in libraries out there, but the point is to pass down the underlying knowledge.
I don't think it's really fair to liken something like mathematics to the startup world, something that has all sorts of nondeterministic factors involved.
So project Euler does not always steer you simply to a correct answer, they also want you to achieve that answer in a particular way.
That's what happens when time-to-solution is what you optimize for. I'm sure it's familiar to startup programmers :).
But many problems cannot be solved using brute force. They will give you one problem that can be solved using brute force, then in a later problem they increase some n to the point where it cannot be solved using brute force. So it forces you to find a better solution.
There are literally thousands of problems here www.mathalon.us