←back to thread

Project Euler #912: Where are the Odds?

(projecteuler.net)
165 points fzliu | 5 comments | 14 Oct 24 20:27 UTC | HN request time: 0s | source
Show context
Sohcahtoa82 ◴[14 Oct 24 23:20 UTC] No.41843245[source]▶
During the solving of a problem on Project Euler, I learned that compilers are smarter than me.

I don't remember the problem number or its title, but it involved starting from the top-left corner of a 2D grid and finding how many possible paths there are to get to the bottom-right corner while only moving either down or right.

My naive solution was a brute-force depth-first recursive search. On my CPU at the time, it took about 3 minutes to solve. I thought, the logic of this is incredibly simple, why not do it in assembly?

My assembly solution took 5 minutes.

I decompiled the compiled C code to see what it had done, but I couldn't understand it. My assembly knowledge was too basic.

Thinking on it now, I wonder if a modern compiler would solve the entire problem at compile-time and just hard-code the answer to be output at runtime.

replies(5): >>41843296 #>>41843301 #>>41843529 #>>41843878 #>>41844013 #
guessmyname ◴[14 Oct 24 23:28 UTC] No.41843301[source]▶
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?
replies(4): >>41843464 #>>41843557 #>>41843591 #>>41844288 #
1. fallingknife ◴[15 Oct 24 00:08 UTC] No.41843591[source]▶
Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?
replies(1): >>41850457 #
2. xigoi ◴[15 Oct 24 16:45 UTC] No.41850457[source]▶
You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.
replies(3): >>41853517 #>>41854050 #>>41854220 #
3. philiplu ◴[15 Oct 24 21:55 UTC] No.41853517[source]▶
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.

4. fallingknife ◴[15 Oct 24 23:09 UTC] No.41854050[source]▶
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.
5. nonameiguess ◴[15 Oct 24 23:38 UTC] No.41854220[source]▶
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.