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.
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.
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.
It probably didn't improve my programming - I started it as a fun way to learn Python, but I'm retired after 30 years in the business writing compilers and other programming tools/library code. Learning and programming data structures and algorithms is second nature by now.
But I'd say it did improve my thought process, specifically the ability to dwell deeply on something, and wait for inspiration to strike. For the really hard problems, I often will hit that "Eureka!" moment when everything is suddenly obvious, and I think I'm getting better at that. A part of that, too, is my Google-fu has improved. As I delve into deeper parts of math, I seem able to come up with the key search phrase more quickly. It helps that I did my BSc in Math, 40 years ago, so reading academic papers wasn't foreign to me.
impressive, the tenacity to stick to project euler since it becomes very difficult and mathy. I have solved a few here and there, plan to come there some time in the future.
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.
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?
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.
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).
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.
It might be easier to define f(m, n, v) where f(m, n, v) is the number of v-vertex shapes that can fit within a m-n square with exactly one vertex in the top left hand corner. Then Q(m, n) = \sum_{i \in m, j \in n} f(m, n, 4). f also lends itself to a much easier recurrence.
For me, it seems easy if we don't have to care about the imposed restrictions: no crossing and no straight angles.
Hmmmm.... New ideas coming... Maybe we don't have to care about crossings: any crossing can be solved by reordering the vertices, so, all we have to care about is the number unique vertices positions!
I still don't know how to avoid straight angles though.
I think I've made some progress... When one line is added to the problem, it allows us to put 1 or 2 vertices there, so...
Consider U(m, n) as the number of new unique forms possible for Q(m, n). I'm not sure, but it looks like:
U(1, 1) = 1
U(m + 1, n) = U(m, n) * (n + (n+1)*n/2) - X
U(m, n + 1) = U(m, n) * (m + (m+1)*m/2) - X
Where X is the number of invalid forms generated adding one or two vertices in the new line because of straight angles in diagonals. I'm considering only diagonals, because adding only one or two vertices in the new line will not align 3 vertices horizontally or vertically if all "previous forms" were valid.
Almost certainly we need to add terms into the DP state to compute X; unfortunately adding just the number of vertices doesn’t work as some triangles have two edges in which a point can be inserted to create a quadrilateral, while others only have one.
https://projecteuler.net/problem=453