[HN Gopher] Project Euler
___________________________________________________________________
Project Euler
Author : tosh
Score : 205 points
Date : 2021-11-13 17:33 UTC (5 hours ago)
(HTM) web link (projecteuler.net)
(TXT) w3m dump (projecteuler.net)
| marcodiego wrote:
| Took a look at the simplest problem: 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.
|
| The naive idea is: iterate from 0 to 1000, test each number, add
| it to an (initially zeroed) accumulator when adequate. A little
| bit of thinking... ok, sum the multiples of 3, add the multiples
| of 5 and subtract multiples of 15. A little more bit of thinking:
| sum of multiples of 3, 5 and subtract multiples of 15. These can
| be calculated using an arithmetic progression formula in O(1) and
| limits can be found using rest of division operation.
|
| Cool! Even a simple problem made me think of a naive solution and
| how to iteratively improve it.
| rand846633 wrote:
| An you explain me the difference between your solution 2 and 3?
| kadoban wrote:
| 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.)
| rfreiberger wrote:
| 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.
| kadoban wrote:
| 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.
| danielvaughn wrote:
| 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.
| baby wrote:
| I hope they're paying him for all the time he's gonna spend
| doing these exercises
| throwaway81523 wrote:
| 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.
| btilly wrote:
| 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.
| kadoban wrote:
| 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.
| balls187 wrote:
| 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.
| throwaway81523 wrote:
| 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.
| exdsq wrote:
| 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.
| jorgesborges wrote:
| 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/
| sokoloff wrote:
| You may find Advent of Code a better fit than Project Euler if
| the intent is to focus on coding rather than math.
| mikepurvis wrote:
| Definitely, though some of the AoC challenges are pretty
| mathy too, or at least benefit from some basic knowledge
| around combinatorics, factoring, etc.
| xcambar wrote:
| 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.
| atomicnumber3 wrote:
| They seem to be interested in short-form programming
| puzzles, I don't really see how your comment applies to
| that.
| xcambar wrote:
| 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.
| vlunkr wrote:
| I don't know why you've decide to compare these things
| and get immediately hostile about it.
| shiado wrote:
| 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.
| [deleted]
| siddboots wrote:
| 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!
| nnoitra wrote:
| Do DT problems pop-up in PE? To me it seems most are related to
| number theory.
| philiplu wrote:
| 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.
| nsa_magic wrote:
| 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.
| wging wrote:
| 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.
| ajakate wrote:
| For people that love Project Euler, check out project rosalind!
| http://rosalind.info/about/
|
| 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.
| kadoban wrote:
| 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.
| gigalord wrote:
| I learned to code on the side from Project Euler 9 years ago. It
| changed my life.
| mdturnerphys wrote:
| 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/
| dang wrote:
| 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)
| rotexo wrote:
| 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.
| klyrs wrote:
| 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.
| adenozine wrote:
| 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!
| can16358p wrote:
| 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.
| mirekrusin wrote:
| 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.
| weatherlight wrote:
| I've spent 30 hours on this problem I and I've never solved
| it.
|
| https://projecteuler.net/problem=453
| robocat wrote:
| That is fun!
|
| I keep thinking I have a core intuition for a solution, and
| then corner cases ruin it!
| marcodiego wrote:
| 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.
| siddboots wrote:
| 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?
| marcodiego wrote:
| Note: Q(m + 1, n) = 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 edges on the new line is n *
| (n - 1) / 2 . The problem is: moving each edge of each
| quad that can be generated in Q(m, n) to the new possible
| edges may generate quads that break the rules.
|
| 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.
| marcodiego wrote:
| 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.
| [deleted]
| marcodiego wrote:
| 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).
| philiplu wrote:
| 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.
| Dopameaner wrote:
| My suggestion would be to use Pick's Theorem.
| adenozine wrote:
| Oh, now this one has that "simple-enough" vibe to it that
| would make someone go crazy.
|
| Looks beautiful.
| Imnimo wrote:
| 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.
| yeellow wrote:
| 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.
| emi2k01 wrote:
| 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...
| kaba0 wrote:
| 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)
| karmakurtisaani wrote:
| 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!
| enriquto wrote:
| This is a very beautiful geometric problem!
|
| EDIT: removed hint.
| random314 wrote:
| Good problem! Solution is very simple
|
| Edit : REMOVED HINT
| ketanmaheshwari wrote:
| 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
| Smaug123 wrote:
| (Note for everyone: Project Euler requests that people only
| post public solutions to problems 1-100, per
| https://projecteuler.net/.)
| guessmyname wrote:
| 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
| chrisaycock wrote:
| PE is untimed and no one is looking over my shoulder. Plus
| there's a right answer---no hidden test suite.
| omosubi wrote:
| 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
| MontagFTB wrote:
| 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.
| wging wrote:
| 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.
| cameronh90 wrote:
| Makes me wonder if there's something like Project Euler but
| for more programming-like problems. Logic, application of
| well known algorithms, modelling, etc.
| gfosco wrote:
| Also, CodeChef. https://www.codechef.com/
| kadoban wrote:
| 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).
| wging wrote:
| I really like Advent of Code for that.
| https://adventofcode.com/
| Igelau wrote:
| 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.
| Q6T46nT668w6i3m wrote:
| LeetCode
| rawling wrote:
| CodeWars?
| elsjaako wrote:
| There is cryptopals for crypographic security exploit
| stuff. It's very good!
|
| https://cryptopals.com/sets/1
| julienpalard wrote:
| 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).
| __s wrote:
| 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
___________________________________________________________________
(page generated 2021-11-13 23:00 UTC)