News for hackers. Stuff that matters.
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?
Re:Project Euler by xigoi on Tuesday October 15, 2024 @12:45PM (#41850457)
You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.
Re:Project Euler by philiplu on Tuesday October 15, 2024 @05:55PM (#41853517)
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.