Tackling LeetCode Problem 2550: Count Collisions of Monkeys on a Polygon
This is 5th in a series of articles I've been writing on my own process of mastering data structures and algorithms in python with LeetCode and ChatGPT. Enjoy!
There is a regular convex polygon with n vertices. The vertices are labeled from 0 to n - 1 in a clockwise direction, and each vertex has exactly one monkey. The following figure shows a convex polygon of 6 vertices.
Each monkey moves simultaneously to a neighboring vertex. A neighboring vertex for a vertex i can be:
A collision happens if at least two monkeys reside on the same vertex after the movement or intersect?on an edge.
Return the number of ways the monkeys can move so that at least one collision happens. Since the answer may be very large, return it modulo 109 + 7.
Note that each monkey can only move once.
?
Example 1:
Input: n = 3
Output: 6
Explanation: There are 8 total possible movements.
Two ways such that they collide at some point are:
- Monkey 1 moves in a clockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 2 collide.
- Monkey 1 moves in an anticlockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 3 collide.
It can be shown 6 total movements result in a collision.
Example 2:
Input: n = 4
Output: 14
Explanation: It can be shown that there are 14 ways for the monkeys to collide.
?
Constraints:
Initial Thoughts
I remember at the beginning of starting to confront LeetCode problems I made these judgments based on my ability that something was more difficult than it seemed. And problems with diagrams like this, I'd go "Jesus Christ" a lot of times for. But once you get pass that and actually judge a problem by what it really is, you are going to discover a lot of verbose problems being actually quite simple, and a lot others being the totally opposite lol.
The context in which the problem is discussed is basically graphs. They talk about edges and vertices.
I noticed early on that you are able to visualize this like a binary string, where each position in the string can take either a 1 or a 0.
The monkeys can each one make one movement. They can go left or right, or we can think of it as they can go 1 or they can go 0. There has to be one decision for each monkey. So the absolute possible total of combinations of monkey movements in a n-vertex polygon will be the total combinations that you get with n positions in the binary string.
Because there are n positions and each one of the positions can take two values, either a 1 or a 0 you basically have 2n combinations.
Now the problem becomes (which was actually the only hint this problem had) counting the combinations that don't produce collisions in order to subtract it from that value of total possible combinations of movements which I know now to be 2n.
Past Experiences
Vertices and edges are basic nomenclature that you deal with on problems that make use of graphs of any kind. But I could also, interestingly enough, relate this to even elementary level mathematics or geometry, where they talk about vertices and edges. Everything goes full circle one way or another.
There are a lot of problems that make you think about edges and vertices. I remember a lot of times being confused of what they meant by vertices and edges and kind of like mistaking one for the other. But now it's quite fast to understand what people are talking about in my head while I read. I guess the reading comprehension in regards to that kind of context and vocabulary has improved in me.
And yeah, there's a lot of problems about that. So if at the beginning you feel kind of slow with them or their nomenclature, keep grinding, is not that they get easier, but you actually get harder.
There are also a lot of problems about basically having to surround or enumerate possibilities. Actually, there's a literal Enumeration tag where you have to discover and list each one of the problem's edge cases and decide how to handle them explicitly.
In this case it is conceptually kind of similar because you discover that each monkey can move one direction or the other in one step. They can't go any further at once. So those options of movements are the cases that we enumerate, account for and handle in our code. Then we have to think about the possible combinations of that.
If there's not only one monkey, but it's two monkeys or three monkeys or four, and the number of monkeys depends on the number of vertices in the polygon and each have the ability to make one decision or another, that together make a set of combinations of final decisions accounting for what each monkey decides to do.
So, in summary, confronting LeetCode I've found, problems about both graphs, and things that have to do with enumeration and explicitly with binary stuff: binary strings and bit manipulation, other common ones. The first even if it's just geometric problems that are easy like this or complex problems that you still have to think abstractly about graphs and edges while working with arrays.
And the second for an actual wide and varied range of use cases.
领英推荐
ChatGPT interaction
I didn't use ChatGPT this time around. Neither this time, nor the time I approached the problem for the first time back in April.
I actually started using it more heavily right after this when I purchased the GPT-Plus and decided to use it as an instructor.
But this second time I approached this problem, I can definitely see how my discussions with it regarding Bit Manipulation, Enumeration, and Graphs, particularly the vocabulary around graphs, has remarkably eased the difficulty of reading problem statements. And narrowing down the possible solutions.
I actually find myself making less inappropriate assumptions. And this not only happens with problems I've seen. I still find, with new problems that I confront, that I have a narrower and more targeted set of possibilities of assumptions to make about them, and that I'm each time more likely to get them right.
So I find that my assumptions, first of all, are each and each time more accurate. And I think it's to a great degree due to how ChatGPT and I have interacted in the context of solving other problems ranging in topics and difficulty on LeetCode with this approach high level approach first.
Discoveries.
Reviewing this problem, having confronted it already before, It's difficult to tell if I came up with a solution by myself just now.
I mean, probably every short-term memory queue that was left from the first time that I saw it is erased enough, but maybe far back into the longer-term memory part of my brain there may still be some pattern established only from that time that I suffered in frustration trying to come up with a solution to the problem.
I think about this, because this time I actually found the solution to be super straightforward.
What I mean is, I do know I have now further insights on how to verify that the assumption I made about the correct solution is correct, but it is difficult to know if making that right assumption was directly influenced by having encountered and remembering somehow the patterns in the solution the first time around.
In any case, there was a big moment of realization when I understood, first of all, what I explained earlier about understanding this as Bit Strings: the combinations of decisions that are possible for all the monkeys to make. The second one was discovering that as the great majority of the combinations would produce collisions, I had to worry about counting the ones where no collisions happened.
And so I did, and I discovered the only way that not have collisions, neither on vertices nor edges, happen is by having all the monkeys moving in the same direction, which can be either clockwise or the other way around.
Which means subtracting 2 from the total possible combination of decisions that they can possibly make.
Solution
class Solution:
def monkeyMove(self, n: int) -> int:
mod = 10 ** 9 + 7
return (pow(2, n, mod) - 2) % mod
Tricky parts
Remember how I just talked about how sometimes rather verbose problems would be super easy and the other way around? well, that's basically what I just got into trying to understand in depth what we need to be doing with the modular operation.
And we don't need to go so far back. The only thing that we need to know is that if we have a set of numbers that we want to evaluate and the result after the evaluation is going to be super big, one way we can set a boundary for what those values can be is using the modulus operation.
Basically if you apply modulus to any value, you force the result to be inside a range from zero to the value you are applying the mod with [0, mod], which makes all the results of doing modulo on some number non-negative and up until modulo, including it. And if you evaluate over modulo a number that's bigger than that, it's going to give you a result that is in that range.
So the modulo operation is a lot of times, including this one, used to make values fit into a range.
And in the case of our problem, it effectively gives us a bound for values that could be huge. In this case, we can't directly calculate 2n and then just subtract 2 from it because n could be super huge, and the result even bigger.
Or it can also be small and when we substract 2 from it could make it negative, so applying module again brings it back to somewhere in [0, mod].
And if I remember correctly, all of those modular arithmetic considerations for optimization are intrinsic to the way the pow function in Python works.
Optimization
This is of the type of LeetCode problems that on the way to the only test-passing solution you optimize most of it. The runtime rankings are pretty tight and would through my code answer around the whole percentile spectrums.
So in summary, we know pow is optimized to get the power of a number like crazy, and us handling the mod to get to the solution makes us use it optimally.
What I learned
Returning solutions modulo a number is a fairly common pattern. Particularly in competitive programming questions of this type just by the nature of such high number returning problems and us wanting to give boundary to them. Both on the problem statement design and coming up with a solution ends.
The question has a tag recursion that I barely see how applies. I guess there could be another way to solve the problem that uses it, maybe to generate and count combinations but the Math solution gives a more straightforward approach.
In my experience, modular arithmetic in general has a wide range of applications and in a lot of problems they are touched upon but as secondary to the main topics of a question. So to a great degree is one of topics not tagged on LeetCode but still basic and assumed to have some familiarity with.
Further
ChatGPT got me in touch with the rabbit hole of modular arithmetic I could get into if I wanted. But I got out once I had more clarity on the nature of using module, how to use it, and why they commonly use it on some problem questions. Also the value 10**9 + 7 in relation to that.
Another common pattern is finding solution post from user lee215 and so I did review his this time to get some insight and curious of if there were further improvements which could be made to the solution I came up with.