News for hackers. Stuff that matters.
Re:Project Euler by guessmyname on Monday October 14, 2024 @07:28PM (#41843301)
Lattice Paths — 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?
Re:Project Euler by dotancohen on Monday October 14, 2024 @08:02PM (#41843557)
> How many such routes are there through a 20x20 grid?

Is it 21! ?

Re:Project Euler by mdp2021 on Monday October 14, 2024 @08:09PM (#41843596)
No. It's 20!/(10!x10!)

You have 20 slots to be filled with 10 items vs other 10 items.

Re:Project Euler by noapologies on Monday October 14, 2024 @08:20PM (#41843664)
Close, 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.

Re:Project Euler by mdp2021 on Monday October 14, 2024 @08:26PM (#41843698)
Oops! 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.

Re:Project Euler by dotancohen on Tuesday October 15, 2024 @04:14AM (#41846175)
Now 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.

Re:Project Euler by Jtsummers on Monday October 14, 2024 @08:08PM (#41843587)
Nope, and only off by a few orders of magnitude.
Re:Project Euler by dotancohen on Tuesday October 15, 2024 @04:16AM (#41846184)
If it is any comfort, my answer produced a non-negative integer - just like the true answer ))
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.
Re:Project Euler by Sohcahtoa82 on Monday October 14, 2024 @07:48PM (#41843464)
Yup! That was it!

Good job on the ASCII art, btw.

Re:Project Euler by FredPret on Monday October 14, 2024 @10:17PM (#41844288)
Did you just whip out that amazing ASCII art or do you use a tool?
Re:Project Euler by guessmyname on Monday October 14, 2024 @11:14PM (#41844563)
ASCII 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/) or something similar.