4 ms·
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 quickl
by rotexo 5y ago
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.
- adenozine 5y agoProject 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 5y agoI 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 5y agoOnes 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 5y agoI've spent 30 hours on this problem I and I've never solved it. https://projecteuler.net/problem=453 https://projecteuler.net/problem=453
- adenozine 5y agoOh, now this one has that "simple-enough" vibe to it that would make someone go crazy. Looks beautiful.
- marcodiego 5y agoMaybe 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 5y agoThis 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 5y agoBecause 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.
- jkhdigital 5y agoThat one was #514 for me: https://projecteuler.net/problem=514 https://projecteuler.net/problem=514
- spudwaffle 5y agoDid you try an experimental approach?
- schoen 5y agoI 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?
- Imnimo 5y agoMy 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.
- klyrs 5y agoProject 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.
- jkhdigital 5y agoA 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.