Conceptually similar, but the problems are focused around bioinformatics. Most lot of the problems contain some background context that teaches you a little biology/statistics as well.
Recently, however, I introduced it at work as a way of encouraging the team I manage to work collaboratively. We have a fortnightly catch up where we talk through solutions, pick new problems (we have a script that randomly picks an easy, medium and hard problem, which has become an exciting ritual), and then we have an initial discussion about each of the new problems.
It's a good way to foster group work. It's also a great way to introduce people to using version control and pull-requests in a non-scary way!
But there are definitely more CS-oriented problems. I can recall problems solved by using segment trees, Aho-Corasick, simple parsing, etc. And lots and lots of dynamic programming.
Also, working your way through the first 100 problems will require writing code to evaluate poker hands and solve Sudoku boards.
What other sites are you looking at? I don't actually know that I'd recommend any puzzle sites to a new programmer. The ones I know of are for fun, not for improving your software dev skills.
As someone with a math background, that was the only problem in the first 100 that I didn't find pretty straightforward.
But yeah, as a good programmer with a job at a large company, you _definitely_ don't need to do 100 PE problems, and any company asking for that (for general software dev role) has lost their mind.
Add to that, FAANG interview processes are mostly risk avoidant. They are more aimed at avoiding hiring bad candidates, than avoiding ignoring good ones. It is very often possible for a weak candidate to bullshit their way through interviews etc. Solving PE problems is harder to fake, at least without faking on purpose (by reading up on spoilers).
Also (and this includes Amazon) I've never had anyone on a loop/hiring manager tell me how to prep for an interview. That has entirely been the recruiter.
Or meet fellow devs at meetups and get into open source.
Or meet people at a local hacker space.
Basically, developing requires people to inject interesting projects and perspectives at you.
Yes. Coding requires social skills. I'm not taking that back.
I expect you to tell me you're well versed in both, but don't expect me to believe you.
Multiples of 3 or 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Cool! Even a simple problem made me think of a naive solution and how to iteratively improve it.
sum [i | i <- [1..1000], i % 3 == 0 || i % 5 == 0]
sum [3,6..1000] + sum [5,10..1000] - sum [15,30..1000]
rsum 3 + rsum 5 - rsum 15 where
rsum n = let (k,r) = 1000 `divMod` n in rsum' 0 (1000 - r) k
rsum' f l n = (n*(f + l)) `div` 2
sum_arithmetic_progression first last length =
-- to compute S = first + (first+k) + (first+2k) + … + (first+length*k = last)
-- write it backwards and add corresponding terms:
-- 2S = (first+last) + ((first+k)+(last-k)) + … + (last+first)
-- = (first+last) + … + (first+last)
-- \____ length times ___________/
(first + last) * length `div` 2
-- = sum [i | i<- [1..upperBound], i%n == 0] but fast
sum_multiples n upperBound =
sum_arithmetic_progression n last count where
(count,r) = upperBound `divMod` n
last = upperBound - r
subsets  = []
subsets (x:xs) = [set | sub <- subsets xs, set <- [x:sub,sub]]
-- given some sets [A,B,…,C] and a function count_intersection which acts like the sum of some function on the elements in the intersection of a list of sets, compute the count of their union using the inclusion–exclusion principle.
inclusion_exclusion count_intersection sets =
sum [count_intersection sub * (if odd (length sub) then 1 else -1) | sub <- subsets sets, sub != ]
answer = inclusion_exclusion sum_multiples' [3,5] where
sum_multiples' factors =
-- the sum of the numbers which are multiples of all the numbers in factors is the sum of the multiples of their lowest common multiple
sum_multiples (foldr lcm 1 factors) 1000
Solution 3 uses the closed-form solutions the the question "what is the sum of the multiples of k between x and y".
If you're not familiar with that last part, it's pretty easy to get there from the formula for the sum of numbers from 1 to n, ie n(n+1)/2 (which is itself ~easy to see by pairing up 1 and n, then 2 and (n-1) and etc.)
When I was last doing PE, that Knowledge was relatively fresh in my mind so I could know that the solution was Pell’s equation or whatever (good luck finding the wiki page if you don’t know the name…) but even then it felt a bit silly. I think the solution I was most proud of was to an older problem (they weren’t adding new ones at the time) with less than 100 solves and it basically boiled down to Gaussian elimination without much mathematical knowledge. Mostly I was proud because I got the achievement for solving one early.
This sometimes involved looking sequences up in OEIS, sometimes the closed for was obvious from the sequence, and sometimes I used differentials to find it.
Yes! This is when I knew I was in too deep lol
Also, I once spent over thirty cumulative hours on a single PE problem, and I never solved it, I gave up. Don't feel bad. It doesn't make you a bad programmer, just a bad mathematician. That's probably not that big of a deal!
I’m retired, and PE is my main intellectual stimulation for the past 5 years. I thought I might be done by now, but everything left is at least 80% difficulty, and I’ve given up estimating how long those will take, if ever.
I started PE to practice Python for fun, but it’s turned into so much more than that.
I've stuck with it mostly because I really enjoy learning math. I had plans to pursue a PhD in math back in college, 40+ years ago. But that's when I discovered computer programming, which was way easier, and paid much better. Now that I'm retired, I've got time to devote to Project Euler, which is satisfying that itch to keep learning.
Curious if you think it improved your programming or thought process when it comes to problem solving overall? I've been thinking of spending some time on Project Euler when I have a few spare cycles.
But I'd say it did improve my thought process, specifically the ability to dwell deeply on something, and wait for inspiration to strike. For the really hard problems, I often will hit that "Eureka!" moment when everything is suddenly obvious, and I think I'm getting better at that. A part of that, too, is my Google-fu has improved. As I delve into deeper parts of math, I seem able to come up with the key search phrase more quickly. It helps that I did my BSc in Math, 40 years ago, so reading academic papers wasn't foreign to me.
Excellent, that's what I was hoping to get out of it.
Hope you're enjoying retirement. All that free time now to do more programming :)
Or, maybe Q(m, n) can be calculated as a function of Q(m - 1, n), Q(m, n - 1) and Q(m - 1, n - 1). But calculating Q(m, n) may not be that important, maybe finding its factors is! So, all you have to do is to find the factors of Q(m, n) and then calculate a rest of division. So, maybe it is possible to find Q(m, n) mod x as a function of Q(m - 1, n), Q(m, n - 1) and Q(m - 1, n - 1). If this can be found, the problem becomes trivial.
Note that if we don't have to care about lines crossing, calculating Q(m + 1, n), Q(m, n + 1) and Q(m + 1, n + 1) as a function of Q(m, n) maybe easy. All that needs to be done is to find an expression for these that take line crossing into account, then use this expression to calculate a rest of division.
Also, note that Q(m, n) = Q(n, m), so if we can calculate Q(m + 1, n) as a function of Q(m, n) we can also do it for Q(m, n + 1). Calculating Q(m + 1, n) as a function of Q(m, n) doesn't seem complicated if it weren't by the rules "no straight angles and does not self-intersect". Maybe it can be done with some combinatorics, but seems beyond my skill. Also, expressing it in terms of combinations may also simplify calculation of rest of division.
If such relation can be found, I think the problem may be easily solved.
each valid quad of Q(m, n) moving an edge to another possible one in the new line +
each valid quad of Q(m, n) moving a vertex to the new line +
the same thing moving each unique valid quad of Q(m, n) to the new line.
The number of new possible vertices on the new line is (m + 1) . The problem is: moving each vertex of each quad that can be generated in Q(m, n) to the new possible vertices may generate quads that break the rules.
Finding a way to calculate both terms looks like good progress.
Hmmmm.... New ideas coming... Maybe we don't have to care about crossings: any crossing can be solved by reordering the vertices, so, all we have to care about is the number unique vertices positions!
I still don't know how to avoid straight angles though.
Consider U(m, n) as the number of new unique forms possible for Q(m, n). I'm not sure, but it looks like:
U(1, 1) = 1
U(m + 1, n) = U(m, n) * (n + (n+1)*n/2) - X
U(m, n + 1) = U(m, n) * (m + (m+1)*m/2) - X
If we can find X, then, I think Q is given by:
Q(m, n) = m*n*U(1, 1) + (m-1)*(n-1)*U(2, 2) + (m-2)*(n-2)*U(3, 3) +...+ 1*1*U(m, n)
Almost certainly we need to add terms into the DP state to compute X; unfortunately adding just the number of vertices doesn’t work as some triangles have two edges in which a point can be inserted to create a quadrilateral, while others only have one.
The difficulty is finding those terms, though…
Also, I think my previous formula is wrong. Maybe it is the sum of:
(m - i + 1)*(n - j + 1)*U(i, j)
But maybe it is still wrong because U(i, j) will re-count combinations from U(i - 1, j) and U(i, j - 1)...
Argh! This is complicated! I think I'll have to revisit it if I ever have a good idea.
For example, if you wanted to use DP to compute all-pairs-shortest-paths (Floyd-Warshall), you add a third parameter to the DP state ((f(u, v, k)).
I keep thinking I have a core intuition for a solution, and then corner cases ruin it!
Examples: cses.fi/problemset , codeforces.com , codechef.com , hackerrank.com (tho HR makes it harder to find the good problems every time I look).
As long as you just read the problem description first, and don't cheat by skipping right to the implementations.
There are hidden puzzles, you can solve for larger polygons like the 17-gon.
Recently ran into Project Euler again while benchmarking my recent Befunge JIT work. Most Befunge programs are pretty light computationally, but https://github.com/Mikescher/Project-Euler_Befunge solves the first 102 problems in Befunge
It's given me reason to go beyond spec & eventually I'll implement 64 bit cells with unbounded space so that I can execute their entire catalog
Some advice: people should definitely start off in linear order to warm up, and it's worth sticking with a problem for a while... but I think at some point it becomes valuable to skip around a bit and do the next one if you get stuck. These are the sort of problems where a fresh perspective can be very valuable.
Also, reading the solutions from the forum thread that is unlocked after you solve one will give you a LOT of insight - definitely do that.
How many angles exist from which shooting the laser, it will bounce N times and exit through the same hole it entered from?
I have tried doing it in the naive way by writing a scala program that calculates reflections on the sides of the triangle and my idea was that iterating the degree in small quantities and plotting the distance of the Nth ray to the enter/exit corner would give me a visual way to count the angles we are looking for. The accuracy of doubles disallowed me from doing even the given N=11 example, so I made/reuse a rational number lib and I got the correct number for this sample. But the actual question wants N on the order of millions…
I’m thinking that maybe some mathematical series could help, but haven’t tried cracking it since. But it was a great feeling writing even this easy version (I have even made a visual version with scala.js :D)
Years later, I was able to impress my colleagues by solving a similar problem someone posed over beers in an instant.
I think everyone saying that a simple solution exists has just solved it for me!
EDIT: removed hint.
When I first discovered PE* I checked the latest available problem, which was 202 that week. I remember thinking at the time that it was impossible to solve.
Fast forward a couple of years and a lot of solved PE problems. I took another go at 202 and I finally figured it out. The feeling of accomplishment I felt then...
*through an xkcd comic (https://xkcd.com/353/). The alt text mentions 20 small problems, which are problems from PE (IIRC this was specified in the now-defunct xkcd blog)
Edit : REMOVED HINT
What's fascinating to me about this one, though, is its difficulty level, versus what the design team thought that level would be. Those levels are set automatically based on how quickly PE members manage to solve it, and this one took 32 weeks to hit 100 solvers, for a 95% difficulty. But problems are usually scheduled in batches of 6, one per week, with an expected difficulty cadence of Medium, Easy, Medium, Easy, Medium, Hard. And #589 was expected to be an _easy_ problem! I can actually see, having solved it, why the team thought it deserved its easy slot, but, wow, did things work out differently.
For a more general favorite, I really enjoy solving any of the impartial game problems. I'm not pointing out which those are - part of the fun is discovering that that's what you're looking at.
> I learned so much solving problem XXX, so is it okay to publish my solution elsewhere?
> It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, that will rarely be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.
> However, the rule about sharing solutions outside of Project Euler does not apply to the first one-hundred problems, as long as any discussion clearly aims to instruct methods, not just provide answers, and does not directly threaten to undermine the enjoyment of solving later problems. Problems 1 to 100 provide a wealth of helpful introductory teaching material and if you are able to respect our requirements, then we give permission for those problems and their solutions to be discussed elsewhere.
I'd advise anyone who wants to solve the first 100 problems against looking their solutions online. They are simple enough to not require you to research complex topics to solve them as later problems do.
I'd recommend Rosetta Code  if someone wants to have a look at a programming language in action.
This is a fabulous way to learn new tricks and insights, as long as you’re up for sticking with it. Solving the problems does force you to be invested, and it’s great to see how much better/faster/smaller/smarter some other people’s solutions are once you’ve had to come up with your own way.
I do enjoy the learning aspect though, so what I feel is missing most of all, is a way to figure out what to study, in order to solve a problem, without giving away the solution.
Fair enough. I suppose many programmers suffer from anxiety during those interviews.
> Plus there's a right answer---no hidden test suite.
This statement makes no sense, though.
Both Project Euler and LeetCode-type of problems have a right answer, in fact, LeetCode-type of problems have more than one right answer, making them even easier than Project Euler problems.
Also, having a hidden test suite means nothing because the (single) test used to verify the answer for a Project Euler problem is also hidden.
Back in undergrad, we kept a leaderboard amongst each other to see who could solve the most problems. I had just learned python and thought I was cool.
Project Euler - https://news.ycombinator.com/item?id=15893911 - Dec 2017 (163 comments)
Project Euler Humble Return - https://news.ycombinator.com/item?id=10025042 - Aug 2015 (119 comments)
Project Euler has been hacked - https://news.ycombinator.com/item?id=9990221 - Aug 2015 (35 comments)
Project Euler's 500th problem - https://news.ycombinator.com/item?id=8977550 - Jan 2015 (56 comments)
Project Euler Returns - https://news.ycombinator.com/item?id=8181773 - Aug 2014 (100 comments)
Project Euler is partly back - https://news.ycombinator.com/item?id=7928107 - June 2014 (16 comments)
Project Euler is offline - https://news.ycombinator.com/item?id=7896621 - June 2014 (19 comments)
Project Euler - https://news.ycombinator.com/item?id=7056888 - Jan 2014 (134 comments)
Project Euler - https://news.ycombinator.com/item?id=1262968 - April 2010 (20 comments)
Project Euler - Fun Math and Programming Problems - https://news.ycombinator.com/item?id=86365 - Dec 2007 (10 comments)
I included the ones about the 2014 downtime because they're mostly general threads about PE.
Other general threads:
Project Euler 001 the Hard Way - https://news.ycombinator.com/item?id=22209793 - Feb 2020 (41 comments)
Consider Yourself a Developer? You Should Solve the Project Euler Problems - https://news.ycombinator.com/item?id=19174947 - Feb 2019 (31 comments)
Solving Project Euler problems - https://news.ycombinator.com/item?id=1062209 - Jan 2010 (27 comments)