4 ms·
Lattice Paths — https://projecteuler.net/problem=15 https://projecteuler.net/problem=15 > Starting in the top left corner of a 2x2 grid, and only being able to
by guessmyname 2y ago
Lattice Paths — https://projecteuler.net/problem=15 https://projecteuler.net/problem=15
> Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
─────────┐ ────┐ ────┐
┌───┬───┐│ ┌───│───┐ ┌───│───┐
│ │ ││ │ │ │ │ │ │
├───┼───┤│ ├───└────┐ ├───│───┤
│ │ ││ │ │ ││ │ │ │
└───┴───┘│ └───┴───┘│ └───│───┘
▼ ▼ └────▶
│┌───┬───┐ │┌───┬───┐ │┌───┬───┐
││ │ │ ││ │ │ ││ │ │
└─────────┐ └────┐───┤ │├───┼───┤
│ │ ││ │ │ │ ││ │ │
└───┴───┘│ └───│───┘ │└───┴───┘
▼ └────▶ └─────────▶
> How many such routes are there through a 20x20 grid?
- Sohcahtoa82 2y agoYup! That was it! Good job on the ASCII art, btw.
- dotancohen 2y ago> How many such routes are there through a 20x20 grid? Is it 21! ?
- Jtsummers 2y agoNope, and only off by a few orders of magnitude.
- dotancohen 2y agoIf it is any comfort, my answer produced a non-negative integer - just like the true answer ))
- mdp2021 2y agoNo. It's 20!/(10!x10!) You have 20 slots to be filled with 10 items vs other 10 items.
- noapologies 2y agoClose, it's 40!/(20!*20!) 20 Rs, 20 Ds in a 20x20 grid. Example pattern: RRDDDR...D (40 letters) Basically the number of permutations, with repetition, of 20 Rs and 20 Ds.
- mdp2021 2y agoOops! Thanks, just distraction... It's that first I wanted to see the general solution to those kind of problems (and I gave the solution for a wrong one in the class), then I wanted to verify the C implementation of the solution with POPCNT like the OP seems to have done (I am writing the code)... Edit: ...and yes, it seems that brute-forcing (counting to one trillion) takes more time than I expected.
- dotancohen 2y agoNow I see it. Twenty items (R operations) in 40 slots: 40!/(20!) and the order of the items does not matter, so again divide by 20!. The remaining slots are D operations. The answer actually came to me in the shower this morning.
- fallingknife 2y agoAm I missing something here or would that be as simple as 2N nCr N for an NxN grid?
- xigoi 2y agoYou’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.
- philiplu 2y agoSomething 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.
- fallingknife 2y agoOn 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.
- nonameiguess 2y agoI'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.
- FredPret 2y agoDid you just whip out that amazing ASCII art or do you use a tool?
- guessmyname 2y agoASCII art by hand (⌐■_■) it only took me 5 minutes or so … That said, I think someone could have done it faster with a tool like Monodraw (https://monodraw.helftone.com/ https://monodraw.helftone.com/) or something similar.