Project Euler(projecteuler.net)
projecteuler.net
Project Euler
https://projecteuler.net
130 comments
For me it's been other way round. I mean I was actually very much interested in genetics so I encountered Rosalind. Going through Rosalind, I realized I need to learn Python and I didn't know any programming till then. So my first lessons of Python were from Rosalind! I started loving Python and programming. Then I encountered Project Euler...
I have big love for PE. I've learnt so much in the process of trying to solve some of these problems. In particular, number theory and data structures are two fields that I have come to love almost entirely because of this website. I did a random selection of the first 200 problems on my own about a decade ago but ran out of steam as the problems got harder.
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!
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!
Do DT problems pop-up in PE? To me it seems most are related to number theory.
Most PE problems are more math than data-structure based. There are plenty of number theory problems, but lots of other areas as well, especially combinatorics and probability. I’ve learned about many more niche areas, like impartial games and chromatic polynomials, via PE.
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.
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.
So I'm a mostly self trained low level programmer and found Project Euler is great but there is a level of math knowledge that left me more puzzled on the formulas than actual coding. Is this something I should focus on as someone learning to code, or the other coding puzzle sites with "linked list" type of challenges are just as good.
No, you shouldn't focus on this. PE is _mostly_ a math site, which if you want to learn that is great, but it's not the same as programming.
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.
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.
A friend of mine applied to Amazon, and they told him he should do the first ~100 problems of Project Euler to prep for the interview. As someone who is not at all advanced in math, I found this to be fairly discouraging. I feel like I’m a reasonably strong programmer without advanced math knowledge, and not sure why it would be necessary for a general dev job.
Maybe it’s more about culture than skills? I’ve solved 80 PE problems (78 of which are in the first 100) because I enjoy it, and I’m pretty sure that I would get along very well in a team full of others who enjoy PE enough that they voluntarily solved >50 problems. Maybe the goal of that advice is to discourage people?
That’s awful actually. If it’s actually relevant to the job that’s one thing, but if it’s about selecting for areas of extracurricular interest it’s inherently excluding qualified people and implicitly harming your team by limiting present perspectives.
For SDE? This seems like strange advice to me.
That sounds like pretty bad advice. Does Amazon really ask interview questions based on those? I'd be very surprised if they did. Competitive programming problems as interview requirements are bad enough (don't get me wrong, I find the problems fun, they just don't have much to do with software dev).
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.
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.
I would say if you take a room full of programmers and select only the ones who managed to do the first 100 PE problems, you'll lose a lot of good ones that way. But all the ones you do select are almost sure to be pretty good, so in that regard it is an effective filter, plus then you get to complain about a lack of candidates and lobby for more tax breaks or whatever.
I think it’s more that the good ones you lose would be perfectly capable of doing the first 100 PE problems, they just have better things to do.
Maybe true, but you only have to worry about that if there are none left after your filtering operation. You are not trying to mine gold (find as many small nuggets as you can of a very rare substance among millions of tons of dirt). You are trying to find exactly N nuggets for some small N, that is the number of open slots you are trying to fill. If you can replace megabucks of excavation equipment (time-consuming interviews) with a simple screen (solve 100 PE problems) and N nuggets get through, you have saved yourself a lot of trouble.
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).
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).
From my understanding, Amazon's teams have a lot of autonomy so I wouldn't be surprised if a team took that approach.
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.
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.
You don't need a lot of math knowledge for the first 100 problems of Project Euler, but you do need some aptitude and problem solving ability (rather than knowledge per se). I think getting all 100 has to be pretty hard even if you are good at math. The first 20 or so are pretty doable. They get harder after that. I do know of some people who have gotten them all way beyond 100. I lost interest long before that.
You're likely to get stuck on https://projecteuler.net/problem=66 if you don't know about https://en.wikipedia.org/wiki/Pell%27s_equation.
As someone with a math background, that was the only problem in the first 100 that I didn't find pretty straightforward.
As someone with a math background, that was the only problem in the first 100 that I didn't find pretty straightforward.
Thanks, I think I see how to do this, but I haven't tried coding it yet. It is a cool problem and a quick script shows the dumb brute force approach starts failing at d=61. I will try coding my trick to see if it works, if I get some time.
Haha true. I got stuck on that problem for a few months before I gave up and started researching the math behind it.
I hope they’re paying him for all the time he’s gonna spend doing these exercises
If you’re learning to code try build stuff (unless you enjoy project Euler style challenges - enjoyment is the priority). Trying to model the inventory system of Skyrim or something is more useful in the long run than puzzles, IMO. When you find something feels wrong with your design; that’s when you start identifying new and better data structures.
I agree it’s more fun creating your own little games or problems to solve. Someone posted an elevator coding game here a couple months back[0]. Those are more fun to me. I found Euler too math-heavy and I spent most of my time in Wikipedia trying to understand the question.
[0] https://play.elevatorsaga.com/
[0] https://play.elevatorsaga.com/
You may find Advent of Code a better fit than Project Euler if the intent is to focus on coding rather than math.
Definitely, though some of the AoC challenges are pretty mathy too, or at least benefit from some basic knowledge around combinatorics, factoring, etc.
Or contribute to Hacktober fest.
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.
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.
They seem to be interested in short-form programming puzzles, I don't really see how your comment applies to that.
Open source projects and hacker spaces offer just so much more than short-term projects.
I expect you to tell me you're well versed in both, but don't expect me to believe you.
I expect you to tell me you're well versed in both, but don't expect me to believe you.
I don't know why you've decide to compare these things and get immediately hostile about it.
Eh, not a lot of hacker spaces here in Silicon Valley. Don't know about the state of affairs in OP's location.
There's no real need to know so much math for most professional programming jobs. Math problems tend to be over-represented on challenge sites because they are easy to implement.
Maybe checkout Advent of Code instead. Less mathy, more fun (IMO).
Took a look at the simplest problem:
Cool! Even a simple problem made me think of a naive solution and how to iteratively improve it.
Multiples of 3 or 5
Problem 1
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.
An you explain me the difference between your solution 2 and 3?
As in:
1.
1.
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` 21. is the best solution. That's because it is the only solution that encodes the problem in a way that it is still obvious what is being done. 2. and 3. are incomplete without a pile of documentation to explain why they do what they do and what you'd need to do to modify them in case the inputs change.
The first runs in linear[1] time and the last in constant time. One can write it more readably:
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 2 is still iterating, once by 3, then by 5 then by 15.
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.)
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.)
In general I think there are a lot of project Euler problems (at least after the first 100) that are basically “here is some theorem/construction you might see in undergrad (or maybe early postgrad) number theory, except we don’t tell you what it is, instead we just give you a problem to which it applies.” And if you don’t know the theorem you are SOL.
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.
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.
In my experience some of the most fun programming problems are the ones where an optimum solution is known to academia, but the participant doesn't know the optimum and has to cobble together the best suboptimal solution they can come up with on their own
When I was poking PE many many years ago, one approach I took was "make a brute-force solver, feed it small inputs, see if there is an easy way to reason myself to a closed form".
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.
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.
Years back I did a couple hundred problems on this site. It's very good at making you learn about important results in basic math and algorithm complexity. It forces you to write your own library of efficient functions for factoring, etc... because you have to use them so many times and as the problems get harder anything brute force will take too long.
> It forces you to write your own library of efficient functions for factoring, etc
Yes! This is when I knew I was in too deep lol
Yes! This is when I knew I was in too deep lol
I’m definitely curious about other people’s approach to Project Euler. My experience was that the first several were pretty straightforward, but I pretty quickly ran into a wall where I couldn’t rely on my intuition to generate a solution that would work in an acceptable time frame (python is a hobby for me, and I’m not sure that I have the quantitative ability to go much farther than that. Im curious how many other people look up algorithms and then implement them when they run into a similar wall, or how many people sit and think and implement ideas until they have an answer.
Project Euler problems for the most part aren't like brainteasers. Sometimes you just do not have the mathematical context to arrive at an optimal solution. Browse Wikipedia a bit or watch some math videos or something when you're stuck, and think about how to exploit the fast nature of computers with what rigorous mathematical understanding of the problem you have.
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!
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!
That one was #514 for me: https://projecteuler.net/problem=514
Did you try an experimental approach?
I haven't seen this problem before, but that seems extremely unlikely to work to me - I think there are 2¹⁰²⁰¹ cases (not equiprobable although you can find the weight of each somewhat "easily"), so are you really going to get a good enough sample to measure the expected value to "five decimal places" without figuring out a lot about the underlying structure?
I don't think it necessarily makes you a bad mathematician either. We all sometimes focus on a problem and start thinking inside the box whereas it has a simple out-of-the-box solution that we're missing because of our focus. Just like a novice programmer can sometimes easily spot an expert programmer's bug in a mere of minutes.
Ones that get you stuck are the best ones. That's the ones with potential to teach you something you didn't know and improve your skills. Find a way to fall in love with training. Don't fixate on holding the trophy.
I've spent 30 hours on this problem I and I've never solved it.
https://projecteuler.net/problem=453
https://projecteuler.net/problem=453
Heh, thanks for the nerd-sniping. I’m down to 25 unsolved problems (currently working on #522, for way more than 30 hours), but #453 is one I haven’t done anything with yet. So of course I took a look, had some thoughts, and will probably have to force myself to look away in an hour or two. But, ooh, maybe that one’s next.
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’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.
Out of curiosity how many hours have you put into it to get this far?
Whew, probably 5 to 10 thousand, at a wild guess? I ran through the first 106 problems (plus #243) in 23 days in April/May 2016, then dropped it for a year. Since then, I've plugged away pretty steadily, about 150 problems a year. That's tailed off as I'm getting close to the end. New problems show up once a week (except in summer), and I mostly keep up with those, but my success on the backlog is slowing down as what's remaining gets increasingly difficult. I'll probably solve around 80 this year, and it's that high just because of the new problems. Each old problem typically takes a week to a month, if I manage to get it at all. Some I let rest for a while, hoping inspiration will strike months later.
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.
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.
> Whew, probably 5 to 10 thousand
Impressive.
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.
Impressive.
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.
It probably didn't improve my programming - I started it as a fun way to learn Python, but I'm retired after 30 years in the business writing compilers and other programming tools/library code. Learning and programming data structures and algorithms is second nature by now.
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.
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.
> But I'd say it did improve my thought process, specifically the ability to dwell deeply on something, and wait for inspiration to strike
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 :)
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 :)
impressive, the tenacity to stick to project euler since it becomes very difficult and mathy. I have solved a few here and there, plan to come there some time in the future.
Nice!
Maybe there is a small list of "fundamental simple quadrilaterals" and any other simple quadrilaterals can be obtained by transforming elements from this small list. Maybe it is possible to find an expression to quickly calculate the number of simple quadrilaterals from the initial fundamental list.
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.
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.
This is broadly how I was thinking about it, but I don't have an intuition for why there would be a recurrence relation involving the factors of Q(m, n). What made you think of attacking it that way?
Because it may allow us to use dynamic programming to calculate Q(m, n) and because some new quadrilaterals can be easily generated simply by moving edges and vertices to new spaces when m or n is increased. So, it seems natural for me to try to write Q(m + 1, n) as a function of Q(m, n).
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.
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.
This made me think of... U(m, n) as the number of unique forms of Q(m, n). By unique forms, I mean forms that can't be obtained by simply translating previously found forms. Maybe it is easy to calculate Q(m, n) as a function of U(m, n) and maybe calculating U(m, n) as a function of U(m - 1, n) is a bit easier than calculating Q(m - 1, n).
[deleted]
Note: Q(m + 1, n) =
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.
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.
It might be easier to define f(m, n, v) where f(m, n, v) is the number of v-vertex shapes that can fit within a m-n square with exactly one vertex in the top left hand corner. Then Q(m, n) = \sum_{i \in m, j \in n} f(m, n, 4). f also lends itself to a much easier recurrence.
For me, it seems easy if we don't have to care about the imposed restrictions: no crossing and no straight angles.
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.
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.
If you didn’t care about the restrictions, then the answer is N*M choose 4.
I think I've made some progress... When one line is added to the problem, it allows us to put 1 or 2 vertices there, so...
Consider U(m, n) as the number of new unique forms possible for Q(m, n). I'm not sure, but it looks like:
If we can find X, then, I think Q is given by:
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)> If we can find X
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…
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…
What do you mean by "the DP state"?
Also, I think my previous formula is wrong. Maybe it is the sum of:
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.
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.
By DP state, I mean the arguments to the recursive function (for U, the state is the tuple (i, j)).
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)).
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)).
Sure! Dynamic programming, right?
Oh, now this one has that "simple-enough" vibe to it that would make someone go crazy.
Looks beautiful.
Looks beautiful.
That is fun!
I keep thinking I have a core intuition for a solution, and then corner cases ruin it!
I keep thinking I have a core intuition for a solution, and then corner cases ruin it!
My suggestion would be to use Pick's Theorem.
I did, it didn't lead to any success.
My approach has always been to read about relevant mathematical concepts but avoid looking at specific algorithms or code. I figure I'm not going to reinvent some concept from abstract algebra or rediscover some formula named after Euler, but I still want to have some challenge of figuring things out beyond just writing the code.
Project Euler is how I learn new languages (caveat, I don't deal in databases, web frameworks, etc). But... they're exercises in mathematics. It's easy to brute-force many solutions, but achieving actual high performance requires doing the math, and figuring out how to reduce the parameter space. Very big on "pick the right algorithm," even the best-performing brute-force just won't do it.
A big leap forward for me was learning how to properly use "lazy" data structures (i.e. streams) to pipeline the processing steps and stop as soon as a solution is found without any extra work. Memoization is also really important for some problems.
Project Euler is why I am a programmer - i spent many nights in university doing PE problems instead of studying and nothing in class gave me the visceral excitement like doing PE
I have found this series of problems to be a good way of getting started with a new language. Because they are straightforward, the main issue with the problem isn’t as much how you solve them, but how to get what I have in my head into a language I’m unfamiliar with.
They start off that way, so it is good for that, but that flips around in later problems... coding them is not the hard part. Many require nontrivial mathematical insight to solve in any practical time frame.
Makes me wonder if there's something like Project Euler but for more programming-like problems. Logic, application of well known algorithms, modelling, etc.
I really like Advent of Code for that. https://adventofcode.com/
There is cryptopals for crypographic security exploit stuff. It's very good!
https://cryptopals.com/sets/1
https://cryptopals.com/sets/1
Competitive programming sites are at least a lot more like that than PE.
Examples: cses.fi/problemset , codeforces.com , codechef.com , hackerrank.com (tho HR makes it harder to find the good problems every time I look).
Examples: cses.fi/problemset , codeforces.com , codechef.com , hackerrank.com (tho HR makes it harder to find the good problems every time I look).
Rosetta Code might fit the bill...
http://rosettacode.org/wiki/Rosetta_Code
As long as you just read the problem description first, and don't cheat by skipping right to the implementations.
http://rosettacode.org/wiki/Rosetta_Code
As long as you just read the problem description first, and don't cheat by skipping right to the implementations.
Stack exchange has their competitions, where, for example, you write a bot to compete against other bots, as well as code golf and things like "fastest solutions" to problems. I once wasted two weeks just reading the problems.
https://codegolf.stackexchange.com/tags
https://codegolf.stackexchange.com/tags
Also, CodeChef. https://www.codechef.com/
CodeWars?
LeetCode
That's exactly how I use them. After the first 50 or so the ROI of that diminishes and you need to move on to something more effective. For that I use a project that I keep re-doing in different languages / eco-systems (a simple spaced repetition learning application).
PE is fun. I feel like for the vast majority of programmer types though, something like: cses.fi/problemset , codeforces.com , codechef.com are better places to do problems. PE gets _very_ math heavy past the beginning ones. Competitive programming problems get difficult as well, but they focus more on algorithms and data structures that programmers are more likely to have a solid background for.
I recently got back into the Euclidia geometric puzzle app [0]. You start with compass and straightedge tools and build up the techniques to exactly construct the solution to various challenges with the minimal set of operations.
[0] https://www.euclidea.xyz/
[0] https://www.euclidea.xyz/
I found this app recently, it's great. It's a nice refresher on basic geometry, and I haven't done many geometric constructions in a while. It's a really neat way of exploring geometry and discovering insight after finishing a puzzle to try and optimize it
See also Ancient Greek Geometry https://sciencevsmagic.net/geo/#0A1.N
There are hidden puzzles, you can solve for larger polygons like the 17-gon.
There are hidden puzzles, you can solve for larger polygons like the 17-gon.
I solved about 270 problems several years ago, had fun doing it, mostly in python, but I reached a point where I just didn’t have the math theory chops to continue. I visit the site every now and then, try a few new problems, but without success. Some problems I can get started but seem to run into a brick wall. Others, I don’t even know how to approach the problem. All in all, however, it’s a great site to learn more about math.
I learned Python using Project Euler, and then created https://hackinscience.org, it's the same but different (only Python, running unit tests against your code).
Same here for me 15 years ago (& then C when my brute force approaches needed the perf boost to finish in a timely manner)
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
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
I really like Project Euler. I'm unsure why it's coming up now, but everyone is new to it at some point.
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.
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.
I am on a mission to solve 100 Project Euler problems using the Awk programming language. About 20 solved so far: https://github.com/ketancmaheshwari/projecteuler
(Note for everyone: Project Euler requests that people only post public solutions to problems 1-100, per https://projecteuler.net/.)
There is a very interesting problem I’ve yet to crack (as per the sites guidelines, do not share solutions here, please): You have a triangle with equal sides. You shoot a laser at the minuscule opening at one corner, where it gets inside and bounces off the inner surface of the sides.
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)
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)
This is a very beautiful geometric problem!
EDIT: removed hint.
EDIT: removed hint.
Good problem! Solution is very simple
Edit : REMOVED HINT
Edit : REMOVED HINT
A wonderful problem. I must have spent over a year thinking about this on and off before arriving to the critical insight. The funny thing with some of these problems is that you get an amazing rush on the moment you solve a problem, but afterwards just feel kinda stupid for not seeing the solution much much earlier.
Years later, I was able to impress my colleagues by solving a similar problem someone posed over beers in an instant.
Have fun!
Years later, I was able to impress my colleagues by solving a similar problem someone posed over beers in an instant.
Have fun!
I've seen this puzzle before and not had any idea how I'd solve it.
I think everyone saying that a simple solution exists has just solved it for me!
I think everyone saying that a simple solution exists has just solved it for me!
This problem holds a special place in my heart.
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)
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)
Project Euler was how I learned to program back in the days. I used to do a lot of Math but I was terrible at programming and really hated the way it was taught at school.
A friend got me hooked on PE by pointing me to #208 many years back. Lovely problem, recommended fun time. I wonder if folks here have favorite problems they've worked on as well.
For me, lots of candidates, but I'll go with #589, Poohsticks Marathon, because of my history solving it. I worked on it for a month after I'd solved about 200 problems, and got nowhere. Dropped it for 2 years, then decided after I'd solved 500 problems that I should give it another go for solution 501. I'd learned plenty of techniques in the interim, and finished it off in a couple days.
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.
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 love 202 for sentimental reasons (latest problem available when I picked up PE, seemed impossible at the time, felt thrilled to solve it) and 422 because I find the solution so elegant. I haven't touched PE in years but I still remember these problems and their solutions off the top of my head.
Is there a website that would gather different solution to those problems (or other similar problems, like Advent of Code) written in Python preferably sorted by some rating? I don't want to scroll the long list of similar solutions but I would like to see selected interesting attempts. I think it's a good way to learn new tricks and useful libraries, but searching for different solutions on blogs/git repos/long reddit threads is no fun.
Project Euler explicitly says this [1]:
> 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 [2] if someone wants to have a look at a programming language in action.
[1] https://projecteuler.net/about
[2] http://www.rosettacode.org/wiki/Category:Programming_Languag...
> 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 [2] if someone wants to have a look at a programming language in action.
[1] https://projecteuler.net/about
[2] http://www.rosettacode.org/wiki/Category:Programming_Languag...
Project Euler has exactly what you’re asking for. The catch is that you have to solve the problem first before seeing the list of selected solutions. Once you input the right answer, the solutions there are limited to solutions that have been upvoted, and recent solutions. The recent solutions disappear as new ones arrive, but the upvoted ones stick around.
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.
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.
If you're the competitive type, http://codeforces.com is also very good. You get an elo rating and they use chess titles (candidate master, master, grandmasters, etc). The lower division generally has around 20k participants per contest which mostly (but not always) happens on weekends.
I learned to code on the side from Project Euler 9 years ago. It changed my life.
I've enjoyed solving PE problems. I think I managed to clear about 50 of them, before loosing interest. To be honest, I think they are simply too hard for most average programmers, like myself. I only really have highschool level math skill, and when I get stuck, I don't even know what to look for or read up on. I'm simply too far removed from the level required.
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.
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.
I find it interesting how many people love solving problems like the ones available in Project Euler [1] and Advent of Code [2], but are opposed to solving similar problems during a technical interview at a tech company.
[1] https://news.ycombinator.com/from?site=projecteuler.net
[2] https://news.ycombinator.com/from?site=adventofcode.com
[1] https://news.ycombinator.com/from?site=projecteuler.net
[2] https://news.ycombinator.com/from?site=adventofcode.com
PE is untimed and no one is looking over my shoulder. Plus there's a right answer---no hidden test suite.
> PE is untimed and no one is looking over my shoulder.
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.
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.
Do you know if it's the same people, or just two significant (but possibly disjoint) populations of people?
Love PE.
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.
Good times.
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.
Good times.
[deleted]
Robert Martin has some cool videos on this.
https://www.youtube.com/watch?v=8L05WmSXv7k
Past related threads:
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)
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)
The website with problems in reverse engineering: https://challenges.re/
Created in similar vein as PE.
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.