> 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?Is it 21! ?
You have 20 slots to be filled with 10 items vs other 10 items.
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.
Edit: ...and yes, it seems that brute-forcing (counting to one trillion) takes more time than I expected.
The answer actually came to me in the shower this morning.
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.
Good job on the ASCII art, btw.
https://projecteuler.net/problem=81
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.
Here's a talk from an llvm conference with the details.
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".
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.