8 ms·

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. Bro

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 5y ago
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 5y ago
  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 5y ago
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
- adenozine 5y ago
  Oh, now this one has that "simple-enough" vibe to it that would make someone go crazy. Looks beautiful.
- marcodiego 5y ago
  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 5y ago
    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 5y ago
      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 5y ago
- robocat 5y ago
  That is fun! I keep thinking I have a core intuition for a solution, and then corner cases ruin it!
- philiplu 5y ago
  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.
  - hedgehog 5y ago
    Out of curiosity how many hours have you put into it to get this far?
    - philiplu 5y ago
      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.
      - alfiedotwtf 5y ago
        > 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.
- Dopameaner 5y ago
  My suggestion would be to use Pick's Theorem.
  - weatherlight 5y ago
    I did, it didn't lead to any success.
jkhdigital 5y ago
That one was #514 for me: https://projecteuler.net/problem=514 https://projecteuler.net/problem=514
- spudwaffle 5y ago
  Did you try an experimental approach?
  - schoen 5y ago
    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?

can16358p 5y ago

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 5y ago
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 5y ago

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

adenozine 5y ago
Oh, now this one has that "simple-enough" vibe to it that would make someone go crazy. Looks beautiful.
marcodiego 5y ago
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 5y ago
  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 5y ago
    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 5y ago
robocat 5y ago
That is fun! I keep thinking I have a core intuition for a solution, and then corner cases ruin it!
philiplu 5y ago
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.
- hedgehog 5y ago
  Out of curiosity how many hours have you put into it to get this far?
  - philiplu 5y ago
    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.
    - alfiedotwtf 5y ago
      > 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.
Dopameaner 5y ago
My suggestion would be to use Pick's Theorem.
- weatherlight 5y ago
  I did, it didn't lead to any success.

jkhdigital 5y ago

That one was #514 for me: https://projecteuler.net/problem=514 https://projecteuler.net/problem=514

spudwaffle 5y ago
Did you try an experimental approach?
- schoen 5y ago
  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?