Project Euler is a lot of fun if you like a dash of math in your programming. The problems generally won't apply to your job or even to interviews, so don't go in expecting that.
My favorite is https://projecteuler.net/problem=113, "Non-Bouncy Numbers." It takes some clever tricks to figure out but doesn't require any significant background knowledge, and the optimizations required to get it to run within 60 seconds (at least for my approach) all felt reasonable.
During the solving of a problem on Project Euler, I learned that compilers are smarter than me.
I don't remember the problem number or its title, but it involved starting from the top-left corner of a 2D grid and finding how many possible paths there are to get to the bottom-right corner while only moving either down or right.
My naive solution was a brute-force depth-first recursive search. On my CPU at the time, it took about 3 minutes to solve. I thought, the logic of this is incredibly simple, why not do it in assembly?
My assembly solution took 5 minutes.
I decompiled the compiled C code to see what it had done, but I couldn't understand it. My assembly knowledge was too basic.
Thinking on it now, I wonder if a modern compiler would solve the entire problem at compile-time and just hard-code the answer to be output at runtime.
> Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
Oops! Thanks, just distraction... It's that first I wanted to see the general solution to those kind of problems (and I gave the solution for a wrong one in the class), then I wanted to verify the C implementation of the solution with POPCNT like the OP seems to have done (I am writing the code)...
Edit: ...and yes, it seems that brute-forcing (counting to one trillion) takes more time than I expected.
On a side note, I remember when the website got hacked [1][2].
Many people, including myself, migrated to other platforms, but Project Euler problems always remained math-focused compared to the myriad of other websites like LeetCode and HackerRank, among others, listing programming-focused problems, which eventually popularized the use in modern tech interviews.
I wouldn't. The majority of problems there have mathematical optimizations which real problems never do. Worse if you start thinking in the way those problems encourage you to your programs will be completely invalidated even with a tiny change in the spec.
A good set of questions would be something between the advent of code - where the problems are hard because the spec is so bad on purpose - and project Euler - where the spec is so exact you don't really need a computer to solve the problems with enough thinking.
Something like 'plot the histogram of collatz sequence lengths of the first 100,000 numbers'.
For those who enjoy regular streams of programming puzzles similar to Project Euler, The Weekly Challenge is another fun resource: https://theweeklychallenge.org
I don't know that I'd gauge anything by popularity with the HN crowd. It's also a diverse group. I'm closing in on a hundred problems solved, in a not very completion-ist fashion (I've got a whole bunch of skips and random choices of puzzles).
Maths isn't my strongest suit, and I have no academic comp-sci background, so there's been a number of these I sort of brute force and then go read the answers in the thread; or I brute force the first few integers in the sequence and then try and wrap my head around what https://oeis.org/ is attempting to tell me about them.
It has challenged me a bit on some of my fundamentals with programming, really making me think about efficiency etc.
While I've done most of the problems in rust so far, I've been having to refresh my knowledge of Go recently, so I've started porting answers between the two languages, and it's definitely helping there a bunch.
It’s my game plan for keeping my brain active in retirement. Been heavily involved for the past 7 years. Been at the 100% solved level since summer 2023, though I’m back to one away the past couple weeks - PE910 is _hard_
I've got a bachelor's in math, but that's 40+ years ago. I had intended to go on for a PhD in math, but fell into computers instead - programming was easier and way more lucrative, even in the early 80s. Once I was retired and found my way to Project Euler, it became an obsession, tickling that desire to go deeper into math that I had in my college days.
I attacked roughly the first 250 problems in order. The early problems build on each other to introduce new topics. I also got good at figuring out the right search term to find some random paper in number theory, combinatorics, probability, whatever.
Later problems introduced new, more niche areas, like chromatic polynomials and impartial & partisan game theory. But by then, I found it much easier to figure out what part of math a problem was based on and how to find relevant literature.
It helps to be really really stubborn, and to have the patience to let a problem stew in my brain, sometimes for weeks at a time. That seems to help lead to that Eureka moment.
It’s been discussed quite a bit in the past. I love Project Euler, but haven’t been active for a few years. Even then I felt like the social aspect of it wasn’t designed for newcomers; a lot of activity on new problems happens as soon as it becomes available and then it mostly freezes. The problems get pretty hard on average once you’re past the first hundred, one reason I personally found it hard to keep going.
Has here been any work done to find out about the average HN user? It seems like it would be a hard thing to do but it might be interesting to see. I do not even know what sort of metrics would be useful to measure.
Project Euler is a lot of fun if you like a dash of math in your programming. The problems generally won't apply to your job or even to interviews, so don't go in expecting that.
My favorite is https://projecteuler.net/problem=113, "Non-Bouncy Numbers." It takes some clever tricks to figure out but doesn't require any significant background knowledge, and the optimizations required to get it to run within 60 seconds (at least for my approach) all felt reasonable.
More than a dash. I would describe Project Euler as math problems that you need a computer to solve.
During the solving of a problem on Project Euler, I learned that compilers are smarter than me.
I don't remember the problem number or its title, but it involved starting from the top-left corner of a 2D grid and finding how many possible paths there are to get to the bottom-right corner while only moving either down or right.
My naive solution was a brute-force depth-first recursive search. On my CPU at the time, it took about 3 minutes to solve. I thought, the logic of this is incredibly simple, why not do it in assembly?
My assembly solution took 5 minutes.
I decompiled the compiled C code to see what it had done, but I couldn't understand it. My assembly knowledge was too basic.
Thinking on it now, I wonder if a modern compiler would solve the entire problem at compile-time and just hard-code the answer to be output at runtime.
Lattice Paths — https://projecteuler.net/problem=15
> Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
> How many such routes are there through a 20x20 grid?Yup! That was it!
Good job on the ASCII art, btw.
> How many such routes are there through a 20x20 grid?
Is it 21! ?
No. It's 20!/(10!x10!)
You have 20 slots to be filled with 10 items vs other 10 items.
Close, it's 40!/(20!*20!)
20 Rs, 20 Ds in a 20x20 grid.
Example pattern: RRDDDR...D (40 letters)
Basically the number of ways to arrange 20 Rs and 20 Ds.
Oops! Thanks, just distraction... It's that first I wanted to see the general solution to those kind of problems (and I gave the solution for a wrong one in the class), then I wanted to verify the C implementation of the solution with POPCNT like the OP seems to have done (I am writing the code)...
Edit: ...and yes, it seems that brute-forcing (counting to one trillion) takes more time than I expected.
Nope, and only off by a few orders of magnitude.
Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?
Sounds like problem 15 [1]?
[1]: https://projecteuler.net/problem=15
Yup! That was it!
If you want a few similar problems, in ascending order of difficulty, try #81 through #83:
https://projecteuler.net/problem=81
https://projecteuler.net/problem=82
https://projecteuler.net/problem=83
Why problem 912 specifically?
On a side note, I remember when the website got hacked [1][2].
Many people, including myself, migrated to other platforms, but Project Euler problems always remained math-focused compared to the myriad of other websites like LeetCode and HackerRank, among others, listing programming-focused problems, which eventually popularized the use in modern tech interviews.
[1] https://news.ycombinator.com/item?id=9990221
[2] https://www.reddit.com/r/math/comments/28jp7x/x/
It's the most recent
The OG LeetCode. Highly recommend, helpful for becoming fluent in a programming language.
I wouldn't. The majority of problems there have mathematical optimizations which real problems never do. Worse if you start thinking in the way those problems encourage you to your programs will be completely invalidated even with a tiny change in the spec.
A good set of questions would be something between the advent of code - where the problems are hard because the spec is so bad on purpose - and project Euler - where the spec is so exact you don't really need a computer to solve the problems with enough thinking.
Something like 'plot the histogram of collatz sequence lengths of the first 100,000 numbers'.
I'd argue you can usually find problems on project euler that are a little more obscure than what you'd typically get on leetcode.
For those who enjoy regular streams of programming puzzles similar to Project Euler, The Weekly Challenge is another fun resource: https://theweeklychallenge.org
I love Project Euler, it’s my go-to for learning the basics of new programming languages I want to learn.
I have spent a little time with Project Euler. Is it very popular with those here at HN?
I don't know that I'd gauge anything by popularity with the HN crowd. It's also a diverse group. I'm closing in on a hundred problems solved, in a not very completion-ist fashion (I've got a whole bunch of skips and random choices of puzzles).
Maths isn't my strongest suit, and I have no academic comp-sci background, so there's been a number of these I sort of brute force and then go read the answers in the thread; or I brute force the first few integers in the sequence and then try and wrap my head around what https://oeis.org/ is attempting to tell me about them.
It has challenged me a bit on some of my fundamentals with programming, really making me think about efficiency etc.
While I've done most of the problems in rust so far, I've been having to refresh my knowledge of Go recently, so I've started porting answers between the two languages, and it's definitely helping there a bunch.
It’s my game plan for keeping my brain active in retirement. Been heavily involved for the past 7 years. Been at the 100% solved level since summer 2023, though I’m back to one away the past couple weeks - PE910 is _hard_
Wow. The idea of getting to 100% on PE is almost incomprehensible to me. I've solved basically none outside the first couple pages.
What was your strategy like? How much math background do you have?
I've got a bachelor's in math, but that's 40+ years ago. I had intended to go on for a PhD in math, but fell into computers instead - programming was easier and way more lucrative, even in the early 80s. Once I was retired and found my way to Project Euler, it became an obsession, tickling that desire to go deeper into math that I had in my college days.
I attacked roughly the first 250 problems in order. The early problems build on each other to introduce new topics. I also got good at figuring out the right search term to find some random paper in number theory, combinatorics, probability, whatever.
Later problems introduced new, more niche areas, like chromatic polynomials and impartial & partisan game theory. But by then, I found it much easier to figure out what part of math a problem was based on and how to find relevant literature.
It helps to be really really stubborn, and to have the patience to let a problem stew in my brain, sometimes for weeks at a time. That seems to help lead to that Eureka moment.
Do you have a favorite?
[flagged]
It’s been discussed quite a bit in the past. I love Project Euler, but haven’t been active for a few years. Even then I felt like the social aspect of it wasn’t designed for newcomers; a lot of activity on new problems happens as soon as it becomes available and then it mostly freezes. The problems get pretty hard on average once you’re past the first hundred, one reason I personally found it hard to keep going.
To be honest, I don't see people talking about it that much. But I'm certain that it would appeal to a good chunk of the people here.
But isn’t it mathematical computing? I feel like leetcode DSA is closer to your average HN user
Has here been any work done to find out about the average HN user? It seems like it would be a hard thing to do but it might be interesting to see. I do not even know what sort of metrics would be useful to measure.
Project Euler 241 I have never really understood...
Check if the sum of number's divisors divided by the number itself gives x.5
This is cool! Are there solutions I can check my answers against?
Yes make an account and you can enter your solutions