9 ms·
Project Euler #912: Where are the Odds?
- toomuchtodo 2y agoThe OG LeetCode. Highly recommend, helpful for becoming fluent in a programming language.
- Cyclone_ 2y agoI'd argue you can usually find problems on project euler that are a little more obscure than what you'd typically get on leetcode.
- llm_trw 2y agoI 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'.
- KeplerBoy 2y agoThe AoC spec isn't bad though? The text always clearly states how your code has to behave, albeit it doesn't spell out every edge case you might overlook. Real world specs on the other hand is often contradictory and impossible to fullfil.
- metabagel 2y agoAdvent of Code is great for this.
- drewcoo 2y agoAgreed about learning a new language starting with PE. After that, I like to invent a big gnarly scenario that I don't have to completely solve, but one that takes me well out of the range of typical cookie-cutter tutorials. I want to find all the sharp edges on a new language/library/framework.
- tocs3 2y agoI have spent a little time with Project Euler. Is it very popular with those here at HN?
- n4r9 2y agoTo 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.
- glouwbug 2y agoBut isn’t it mathematical computing? I feel like leetcode DSA is closer to your average HN user
- tocs3 2y agoHas 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.
- n4r9 2y agoThere's certainly a strong element of computational mathematics. A lot of the problems deal with things like Mersenne Primes or Collatz sequences. On the other hand, there are problems like "Maximum Path Sum" which definitely make use of DSA-style tricks (https://projecteuler.net/problem=67 https://projecteuler.net/problem=67).
- dahart 2y agoIt’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.
- philiplu 2y ago
- throwaway918299 2y agoI love Project Euler, it’s my go-to for learning the basics of new programming languages I want to learn.
- londons_explore 2y agoProject Euler 241 I have never really understood...
- deleted 2y ago[deleted]
- andy81 2y agoCheck if the sum of number's divisors divided by the number itself gives x.5
- londons_explore 2y agoOh - I understand the question. I just don't understand how to calculate the answer up to 10^18 in a reasonable amount of time!
- RodgerTheGreat 2y agoFor those who enjoy regular streams of programming puzzles similar to Project Euler, The Weekly Challenge is another fun resource: https://theweeklychallenge.org https://theweeklychallenge.org
- bizzyskillet 2y agoThis is cool! Are there solutions I can check my answers against?
- dullcrisp 2y agoYes make an account and you can enter your solutions
- guessmyname 2y agoWhy 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 https://news.ycombinator.com/item?id=9990221 [2] https://www.reddit.com/r/math/comments/28jp7x/x/ https://www.reddit.com/r/math/comments/28jp7x/x/
- ThrowawayTestr 2y agoIt's the most recent
- Sohcahtoa82 2y agoDuring 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.
- johnsonjo 2y agoSounds like problem 15 [1]? [1]: https://projecteuler.net/problem=15 https://projecteuler.net/problem=15
- Sohcahtoa82 2y agoYup! That was it!
- wging 2y agoIf you want a few similar problems, in ascending order of difficulty, try #81 through #83: https://projecteuler.net/problem=81 https://projecteuler.net/problem=81 https://projecteuler.net/problem=82 https://projecteuler.net/problem=82 https://projecteuler.net/problem=83 https://projecteuler.net/problem=83
- Sohcahtoa82 2y agoCouldn't all three of those be solved using the A* path-finding algorithm?
- 2y ago
- SatvikBeri 2y agoProject 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 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.
- munchler 2y agoMore than a dash. I would describe Project Euler as math problems that you need a computer to solve.
- deleted 2y ago[deleted]
- byearthithatius 2y agoWell said, that is always how I saw it as well. The sort of math problem solving we did for fun in school but all the problems require programmatic thinking and usually eventually an algorithm. I learned so much from doing Eulers. Even basic stuff I thought I would know like the best way to get GCD
- wging 2y agoThat’s mostly right, but some of them don’t require a computer. I’ve never solved one with just pencil and paper, but in some of the solution threads you will actually find pencil and paper solutions. I’m not sure if any of the later problems work like that, though.
- kevinventullo 2y agoI miss having the time and energy to do these. Maybe in retirement :)
- deleted 2y ago[deleted]
- abnry 2y agoI have great memories of competing with a college friend to solve these problems. Since I last seriously did the problems, probably 15 years ago, they have added a lot more.
- degoodm 2y agoChatGPT o1 seems to understand the problem correctly but doesn't get far: https://chatgpt.com/share/670dbe0e-087c-8000-9856-996c3fbaa9b6 https://chatgpt.com/share/670dbe0e-087c-8000-9856-996c3fbaa9... o1 thought for 105 seconds, cycling through many relevant-sounding status messages like "looking for patterns," before writing a collection of thematic but flawed thoughts. The "Calculation Steps" approach is incorrect, but correctly implemented by the code. It flubs a basic calculation that it correctly implements in python: "10^16 mod (10^9 + 7) = 49" (it's actually 930000007) but succeeds in a seemingly harder calculation: "the modular inverse of 12 modulo 10^9 + 7 is 83333334" Finally, o1 claims the code prints "0" when it actually prints "982790507" (both wrong answers). Note: input was copied from the html-only Project Euler url since the formulas in the human-optimized url are not copyable: https://projecteuler.net/minimal=912 https://projecteuler.net/minimal=912
- joshlemer 2y agoI've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code puzzler site that is specifically geared towards little self-contained tasks that are more to do with forcing you to get familiar with the common everyday tasks of software development. Some example puzzlers could be like: - open an http server on port 80 - open a file and write this data to it - write temporary files to a location, deleting them when process exits - query a database - deal with such and such error scenario - find a way to test this component - bundle this code as an executable - sanitize user input here - make this behavior configurable - take the config from environment variable variable and/or config file and/or arguments - parse this data file You do get a bit of parsing and file handling with Advent of Code but imagine a series of dozens of small problems that grill you on every corner of the python filesystem api. Would be a lot less dry than reading docs cover to cover.
- aleph_minus_one 2y agoHave a look at Rosetta Code > https://rosettacode.org/wiki/Rosetta_Code https://rosettacode.org/wiki/Rosetta_Code This might be a little bit nearer to what you look for. --- > it would be cool if there were a code puzzler site that is specifically geared towards little self-contained tasks In my opinion the tasks on Project Euler or LeetCode are much more self-contained than what you suggest as alternatives: many of your suggestions are deeply intertwined with libraries (and understanding them) for doing the respective task instead of being self-contained programming tasks.
- hoten 2y agoto be fair, PE is not designed or meant for helping people learn a language. that isn't the project's intent. people do like to say they use PE for learning new languages, but I doubt that is a useful exercise beyond maybe the first dozen problems or so. And even then, if the solution isn't obvious to you, you're doing two things at once - learning a language and solving a math puzzle. I don't see why people would sign up to get frustrated like that.
- lynguist 2y agoChatgpt can write a solution for this problem if we go up to 10^10. 10^16 is too hard! I don’t understand this problem (I didn’t tackle it myself) but wanted to see how quickly chatgpt could solve it and how far along it would go. First it made a naive solution that would work until 10^6. Then we used that output to verify improved versions. And we managed to improve it until 10^10 only. (Staying within a minute timeout.) It did a DP approach (it suggested itself). I suggested to try numba and numpy. And with that it managed until 10^10. I think it’s still brute forcing it and one might leverage much better techniques in order to reach 10^16.
- kevinventullo 2y agoIt hadn’t occurred to me that PE is a pretty good test for ChatGPT or SOTA LLM’s in general. Even if explicit solutions for earlier problems do appear somewhere on the web, it’s probably a fairly safe bet that the latest version of ChatGPT did not include the latest Project Euler problem in its training data.