I think one of the saddest thing is that the kind of person who would recognize, "we can solve this seemingly complicated problem by just applying this formula", would often have trouble even getting recognized in many corporate environments.
I managed a guy like that. He was capable of very complex thinking, but he wasn't in love with complexity, he was in love with simplicity. His solutions tended to be of the form, "we can ignore all these things, and just focus on X, and it will provide all the value." He'd notice something and simplify it and the benefit to the company would be measured in multiples of his salary.
Every manager who'd ever directly managed him knew what a treasure he was, but it was often hard for us to convince others of the value of his solutions because they were so simple, and people were convinced that hard problems must have complex solutions. (or else they would have solved them, right?)
He eventually got bored. He retired and joined a seminary.
I imagine this is where the reputation of a good manager comes in and the ability to say to their boss "hey, we should keep this guy... just trust me on this."
An intuitive motivation for the solution in the article (2n choose n). For an n*n grid you have to you will take 2n steps, n "over" and n "down". All that matters is the order of the steps. So if you think of there being 2n "slots", you have to pick n to be "over", and the rest are forced to be "down". So it's n choose 2n indeed.
You can also think of it another way, without using the formula combinations, and only the fact that there are n! permutations of n objects. We can think of this a permutation of 2n items, made up of two groups of n identical items each. Using (2n!) will overcount, due to the fact that each of the "over" steps are identical, and similarly for the "down" group. We have cut down our answer by dividing out all of the repeated sequences. There will be n! redundancies for all the ways we can permute the "over" group and, the same for the "down" group. So this results in (2n!) / (n! * n!), which is exactly equal to 2n choose n. See [1] which explains permutations with repetion this in general. [Note: We pretty much re-derived the formula for combinations!]
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
What a lot of games do is run a strictly deterministic simulation in lockstep. Then you don't save the path of every unit, you save one move command for the whole group. Then the game replays inputs, and the pathing algorithm should give the same result if there are no desyncs.
Yes you are definitely onto something! Love to see more people talking about deterministic games.
My game is strictly deterministic, so I get bot movement for free - but the player has agency so I need to capture their deviations
That’s the tricky part! Right now I do capture input (actually just deviations) and can replay whole games, but I think I’m at the limits in terms of compression - talking bytes here not KB
Noticing a pattern and just extending it without proving why it works is not really a solution. You can prove it without really "understanding" it using induction, but that still would be proof, same as just counting on a computer.
Even if you don’t know or remember the basics of combinatorics you can solve the problem with basic dynamic programming : start with the unit grid and then expend it.
Ha. When I found that problem I draw the grids and paths from the example, left for a coffee and when came back I just look at the drawings at an angle and thought "well this is just Pascal's triangle". And the solution was obvious.
me@localhost:~> bc
d=1; for(i=21; i < 41; i++){d *= i;}; print d; print "\n";
335367096786357081410764800000
n = 1; for(i = 1; i < 21; i++){n *= i;}; print n; print "\n";
2432902008176640000
d/n;
137846528820
I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to for-loops instead.
* - What it does contain is sine, cosine, exponential, log, arctan, and Bessel J (?!?!?!?!)
After the i-th iteration of the for loop, ans will contain n!/((n-i)!i!) which is exactly \binom{n}{i}, an integer.
Technically "ans" can grow above the final result in my example, but even that could be fixed if one really wants (e.g. i must divide either ans or n-i, you play a bit with divmod to figure out which division you do first.)
I think one of the saddest thing is that the kind of person who would recognize, "we can solve this seemingly complicated problem by just applying this formula", would often have trouble even getting recognized in many corporate environments.
I managed a guy like that. He was capable of very complex thinking, but he wasn't in love with complexity, he was in love with simplicity. His solutions tended to be of the form, "we can ignore all these things, and just focus on X, and it will provide all the value." He'd notice something and simplify it and the benefit to the company would be measured in multiples of his salary.
Every manager who'd ever directly managed him knew what a treasure he was, but it was often hard for us to convince others of the value of his solutions because they were so simple, and people were convinced that hard problems must have complex solutions. (or else they would have solved them, right?)
He eventually got bored. He retired and joined a seminary.
I imagine this is where the reputation of a good manager comes in and the ability to say to their boss "hey, we should keep this guy... just trust me on this."
An intuitive motivation for the solution in the article (2n choose n). For an n*n grid you have to you will take 2n steps, n "over" and n "down". All that matters is the order of the steps. So if you think of there being 2n "slots", you have to pick n to be "over", and the rest are forced to be "down". So it's n choose 2n indeed.
You can also think of it another way, without using the formula combinations, and only the fact that there are n! permutations of n objects. We can think of this a permutation of 2n items, made up of two groups of n identical items each. Using (2n!) will overcount, due to the fact that each of the "over" steps are identical, and similarly for the "down" group. We have cut down our answer by dividing out all of the repeated sequences. There will be n! redundancies for all the ways we can permute the "over" group and, the same for the "down" group. So this results in (2n!) / (n! * n!), which is exactly equal to 2n choose n. See [1] which explains permutations with repetion this in general. [Note: We pretty much re-derived the formula for combinations!]
[1] https://brilliant.org/wiki/permutations-with-repetition/
I've had the same experience looking back at solutions to old problem sets and wondering how I ever came up with them.
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
What a lot of games do is run a strictly deterministic simulation in lockstep. Then you don't save the path of every unit, you save one move command for the whole group. Then the game replays inputs, and the pathing algorithm should give the same result if there are no desyncs.
Yes you are definitely onto something! Love to see more people talking about deterministic games.
My game is strictly deterministic, so I get bot movement for free - but the player has agency so I need to capture their deviations
That’s the tricky part! Right now I do capture input (actually just deviations) and can replay whole games, but I think I’m at the limits in terms of compression - talking bytes here not KB
Tbh your student reasoning is still dangerous... the patterns could have not generalized nicely. see moser's circle problem
needed to justify viewing this as "arranging down vs right movements" as another comment outlines
The more i think about math these days, the more i see it as a muscle one must constantly train to achieve its potential.
Give it too long a rest and you have to go back at full blast for weeks on end to hope to ever achieve past performance.
I am very bad at math and have always been in awe of those who can do it well.
Noticing a pattern and just extending it without proving why it works is not really a solution. You can prove it without really "understanding" it using induction, but that still would be proof, same as just counting on a computer.
Even if you don’t know or remember the basics of combinatorics you can solve the problem with basic dynamic programming : start with the unit grid and then expend it.
Ha. When I found that problem I draw the grids and paths from the example, left for a coffee and when came back I just look at the drawings at an angle and thought "well this is just Pascal's triangle". And the solution was obvious.
* - What it does contain is sine, cosine, exponential, log, arctan, and Bessel J (?!?!?!?!)
Just noting that Python natively handles integers larger than the machine word size since version 2.5, so this would have worked in Python as well.
You don't need space for 40!/20!, for example:
The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.Good point. But what if `i` does not divide `ans` evenly? I suppose you could use floats and then round.
It always divides it evenly, that's why it works.
After the i-th iteration of the for loop, ans will contain n!/((n-i)!i!) which is exactly \binom{n}{i}, an integer.
Technically "ans" can grow above the final result in my example, but even that could be fixed if one really wants (e.g. i must divide either ans or n-i, you play a bit with divmod to figure out which division you do first.)