That Project Euler problem was my first encounter with memoization. At the time, it felt like a magical solution, so I ended up solving it using the central column of Pascal's triangle, which was easier for me to understand back then.

I also tried a weird idea involving popcount, but it didn't scale. My approach was to represent each possible path with 0s (don't turn) and 1s (turn), testing the same number of 0s and 1s. However, even with popcount running in O(1) with hardware support, the total number of possible paths made the idea impractical :)

I appreciate where the author is coming from, as we often have much more context because of training that have since atrophied a bit, but in defense of the dynamic programming solution, this generalizes very well.

As stated, the choose(2n,n) solution of course works but as soon as you deviate from a square, things can get more complicated. What if it's a rectangle? An arbitrary shape? One with holes? The dynamic programming solution takes all of this in stride (assuming, of course, that the conditions of only going right and down still hold).

Pascal's triangle is, after all, a dynamic programming solution. It just so happens that there's a "closed form" solution to their entries.

I'm all for clever tricks but I also appreciate much more a solution that generalizes well and gives more insight into a class of problems.

Yeah, this is relatable. Part of it comes down to "use it or lose it." We atrophy when we don't exercise. But at the same time, it might come back to the OP faster than he thinks if he went into it. Also, I've found that with AI I'm able to ask specific questions where I'm hazy and pick things up faster than if I just had to watch hours of lectures to pick something up. (There's a place for both.)

I can definitely relate. My brain also wants to take the path of least effort now, even for simple things like adding two numbers which I could do very quickly in my head in my college days.

And with AI the path of least (initial) effort seems to be to just ask the model to solve it. It might get it wrong and then I'll prompt it again and again. But each individual prompt is fairly low effort on my part. Whereas coming up with the right solution myself might've taken less time but the initial effort is a lot more.

Last year I used to romanticize about building at least 1 thing each month completely by hand without any LLM coding help. The last such project I worked on was 6 months ago so sadly it's not going so well.

The trick to making these problems intuitive is to mentally rewrite them into a "how many permutations of this string are possible?" problem. Consider the 2 * 3 case.

    ...
    ...

One way you might get there is

    Right, right, right, down, down

Then you can rewrite this as

    RRRDD

You will always need 3 R's, and you will always need 2 D's. So how many unique strings can be made with this?

Well let's actually consider the degenerate cases.

    ABCDE

there are 5 places A can go, then 4 left B can go, then 3 left C can go, and so on, until we get 5! = 120 possible permutations of ABCDE. If you replace the B with another A to get

    AACDE

now there are only 60 permutations, because half of the original 120 only differed by where the A and the B were relative to one another. By that same logic,

    AACCE

has only 30 combinations, and

    AACCC

has only 10 (seeing why it's 10 and not 20 is actually the trickiest part imo, it's because there are 3! ways to arrange CDE, but only 1 to arrange CCC).

AACCC is isomorphic to RRDDD, which is how we get 10 possible paths to solve the 2*3 grid. We can check this with the binomial theorem: ((2+3) choose 3) = 10.

What's nice about this step by step approach is that it generalizes not just to non-square grids, but to multiple dimensions as well! Imagine trying to get from the top of a 3 by 3 by 3 Rubik's cube to the bottom, how do you do that? Well how many ways are there to rewrite

    AAABBBCCC

? The logic above would suggest 9! / (3! 3! 3!) = 1,680 unique paths. And you can just derive it by starting from the degenerate case and figuring out how to slice things up!

"Compute the first few terms and plug into OEIS" is very high on the reward:effort scale

Heh, this grid image is all too familiar to me right now.

I’m building a grid based game and engine, and I have a game replay format which is not video.

I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution.

Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering you can move 4 cells per second…

What’s the smallest worst-case raw compression artefact you can output for 1 player for a 1 minute game?

It’s an extremely fun problem to solve. I tried:

- encoding changes into bits eg using 2 bits for direction

- movement pattern batching (ie batching 2 moves into 3 bits)

- crowd patterns and movement prediction

- treating movement as a “projectile” and deriving intermediate states

And all sorts of other wild crap that I will write up about on game launch

Something I haven't seen anyone else mention is that this is problem 15. The author probably did the previous 14 problems too. IIRC the problems aren't strictly cumulative but you do generally end up warmed up and with hints about how to approach problem N efficiently from problems [1, N-1].

Skills do decay, I can't deny that. But even when I was still in school going back and doing an end-of-year problem for a class I took two years ago would have been harder than it was for me at the time... but it would have been easier than the first time if I warmed up properly with a bit of review and practice first, and I mean, not just three minutes glancing over things but taking some serious time for it.

We taught this problem in my college’s discrete math course. The intuition we gave is that it’s exactly equivalent to the number of ways to rearrange a string of 20 Rs and 20 Ds (corresponding to a right and down move)

Because the daily world has much less math in it than we care to admit. You don't need calculus to understand which elevator button needs to be pushed.