Re:Project Euler
by fallingknife on Monday October 14, 2024 @08:08PM
(#41843591)
Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?
[ Parent
| on HN ]
You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.
Something this illustrates, though - once you solve a problem, read the forum thread (the link will be at the bottom of the problem page when solved).
I learned so much poring over the solutions of earlier solvers. Without that knowledge, there's no way I could have gotten lots of later problems.
Sure, problem #15 is very early and I happened to know the answer right off, back the first day I started solving PE problems. But even so, there are some gems in the posts from other solvers.
Re:Project Euler
by fallingknife on Tuesday October 15, 2024 @07:09PM
(#41854050)
On second look I think it can be further generalized to N+M nCr M for all grids NxM where N >= M since the number of ways should depend on combinations of the smaller number.
Re:Project Euler
by nonameiguess on Tuesday October 15, 2024 @07:38PM
(#41854220)
I'm a bit disappointed I didn't see this quicker back when I did this problem like 15 years ago or whatever it is now. My solution was to use matrix exponentiation on the adjacency matrix of the path graph, which is a heck of a lot better than brute force enumeration of all paths, but still roughly cubic rather than linear like computing a bunch of factorials. Even as a math major, I'd done a lot more linear algebra than combinatorics.