We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I'd say this problem is both Recursion and Game Theory, and I get why it might be placed in either category but I'd say it's more Game Theory than recursion. You can't solve it without both, but the "Advanced" part is mostly a full undertanding of the Sprague-Grundy theorem and how it applies to multi-sub games. For those that might be struggling here's a good progression:
Recursive Attempts
Start with a simple mini-max implementation using True/False. Essentially, you take each state, ex: XXIIIXII, and calculate all possible moves from that state and which player is making the move. Then recursively proceed again from that state to find moves for depth + 1. You're essentially creating branches to find out all terminal states. A branch that ends in a True state for player1 means player1 will win. Obviously, this quickly baloons in complexity and memory requirements as you're recursively checking each branch depth first. You'll pass maybe the first 2 or 3 tests, depending on your language, and timeout on the rest.
If you examine the all moves possible from a state, you may deduce that many moves are essentially equivalent. For example, given the state: XIIIIX, knocking down pin state[1] is exactly the same thing as knocking down pin state[4]. Both result in a group of 3 pins. Just as knocking down pin state[2] is the same as knocking down pin state[3] because both result in creating groups of [1, 2] pins. The point here is a lot of actions are equivalent. Instead of representing a "state" as the placements of bowling pins, represent the state of the game as "groups" of pins. So XXIIIXII becomes [3, 2] and XIIIXXIXIIX becomes [3, 1, 2]. Moves will either diminish a group, split a group, or remove a group. This will remove duplicate branches, but will only help pass maybe a few more tests. The majority will time out.
Game Theory
In order to solve the problem within the testing timouts, you need to understand the Sprague-Grundy theorem. I won't go into details about how that works (Google search if you don't know). The important part is the Grundy number of n is the xor of n's component sub games. If you have a game of [1, 2, 2, 1], you can simple xor the Grundy numbers of each element. But if you have any group more than 2, that group essentially represents a set of sub-games. For example: 4 can be divided into [3], [1, 2] and [1, 1] games. The Grundy of 4 then represents the xor of the result of each game. This is the recursion necessary to solve the problem. You still have a 3 to deal with and that represents the xor of another set of games.
The last element you should consider is caching. Using the Sprague-Grundy theorem will get you far, but you'll still end up re-caclulating a lot of games. So passing a cache (dict) that keeps track of the grundy for specific values of n will help you pass all the tests.
Bowling Pins
You are viewing a single comment's thread. Return to all comments →
I'd say this problem is both Recursion and Game Theory, and I get why it might be placed in either category but I'd say it's more Game Theory than recursion. You can't solve it without both, but the "Advanced" part is mostly a full undertanding of the Sprague-Grundy theorem and how it applies to multi-sub games. For those that might be struggling here's a good progression:
Recursive Attempts
True/False. Essentially, you take each state, ex:XXIIIXII, and calculate all possible moves from that state and which player is making the move. Then recursively proceed again from that state to find moves for depth + 1. You're essentially creating branches to find out all terminal states. A branch that ends in aTruestate for player1 means player1 will win. Obviously, this quickly baloons in complexity and memory requirements as you're recursively checking each branch depth first. You'll pass maybe the first 2 or 3 tests, depending on your language, and timeout on the rest.XIIIIX, knocking down pinstate[1]is exactly the same thing as knocking down pinstate[4]. Both result in a group of 3 pins. Just as knocking down pinstate[2]is the same as knocking down pinstate[3]because both result in creating groups of[1, 2]pins. The point here is a lot of actions are equivalent. Instead of representing a "state" as the placements of bowling pins, represent the state of the game as "groups" of pins. SoXXIIIXIIbecomes[3, 2]andXIIIXXIXIIXbecomes[3, 1, 2]. Moves will either diminish a group, split a group, or remove a group. This will remove duplicate branches, but will only help pass maybe a few more tests. The majority will time out.Game Theory
In order to solve the problem within the testing timouts, you need to understand the Sprague-Grundy theorem. I won't go into details about how that works (Google search if you don't know). The important part is the Grundy number of
nis the xor of n's component sub games. If you have a game of[1, 2, 2, 1], you can simple xor the Grundy numbers of each element. But if you have any group more than 2, that group essentially represents a set of sub-games. For example:4can be divided into[3],[1, 2]and[1, 1]games. The Grundy of4then represents the xor of the result of each game. This is the recursion necessary to solve the problem. You still have a3to deal with and that represents the xor of another set of games.The last element you should consider is caching. Using the Sprague-Grundy theorem will get you far, but you'll still end up re-caclulating a lot of games. So passing a cache (
dict) that keeps track of the grundy for specific values ofnwill help you pass all the tests.Here's an example using Python 3: https://www.hackerrank.com/challenges/bowling-pins/submissions/code/44192663