Project Euler #912: Where are the Odds?

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.

Sounds like problem 15 [1]?

[1]: https://projecteuler.net/problem=15

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?

Yup! That was it!

Yup! That was it!

Good job on the ASCII art, btw.

> How many such routes are there through a 20x20 grid?

Is it 21! ?

Nope, and only off by a few orders of magnitude.

Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?

No. It's 20!/(10!x10!)

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

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.

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.

If you want a few similar problems, in ascending order of difficulty, try #81 through #83:

https://projecteuler.net/problem=81

https://projecteuler.net/problem=82

https://projecteuler.net/problem=83

So fun fact, if you compile

  int sum(int n) {
      int sum = 0;
      for(int i = 0; i < n; i++) {
          sum +=i;
      }
      return sum;
  }

clang, with -O2, will turn this into the polynomial (n+1)*n//2. It can also do similar transformations for multiple loops.

https://godbolt.org/z/so6neac33

So if you do a brute force solution which could have been reduced to a polyomial, clang has a shot of doing just that.

We all have our skills and super powers and yours do not involve optimizing for time by switching from C to ASM. Fuck that! I bet you have super powers of some sort.

Compilers are not smarter than you - that's daft. The nutters that program the compilers and tweak and twiddle them, are better informed about how to deliver faster machine code for a given task.

One of your super powers is to know when to say: "fuck it, I'm trotting off and getting by with a five minutes runtime".

Did you just whip out that amazing ASCII art or do you use a tool?

I believe the term for this is scalar evolution.

Yep! That is it alright.

Here's a talk from an llvm conference with the details.

https://www.youtube.com/watch?v=AmjliNp0_00

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.

That is mind blowing, but it’s not immediately obvious to me that it’s equivalent for n > sqrt(INT_MAX). Is it? And if so, is the compiler somehow smart enough to know that?

Integer overflow is actually undefined behaviour thus the compiler is free to assume it doesn't happen.

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.

If it is any comfort, my answer produced a non-negative integer - just like the true answer ))

You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.

If you assume two’s complement arithmetic, then this is always equivalent because you’re basically just calculating the answer in a modular ring.

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.

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.

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.

Couldn't all three of those be solved using the A* path-finding algorithm?

Sshhh...