可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):
问题:
I was asked this question: similar question at google. Similar question was asked during Facebook interview.
Determine winner of 2/9 number game
Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice).
Whoever reaches N first wins.
The candidate should write a function that given N decides who wins (first or second player?)
Will a basic random choice of 2/9 for multiplication work or they'd want us to add intelligence in making moves. For ex: start with multiplication with 2 and multiply with 9 only when you see the other person will not be able to reach N quicker than you?
What is the best way to approach these type of questions?
回答1:
The best approach to this type of questions.
First you need to have the basic understanding of the theory of games. Really basic. That is you are conscious of the fact, that for a given number N there is either a winning strategy for player who starts or a winning strategy for his oponent. So you must assume that they both know the strategy and play the best moves they can.
Then you start to become familiar with the game. You practice on a low level. You quickly notice that for 2-9 the starter is winning, while for 10-18 he must lose. So your function is ready for a case of N<=18.
Then you start thinking of a general winning strategy. Knowing the strategy would give you the algorithm. After 5 minutes (the sooner the better) you understand that you won't fit in time to find the winning strategy, as it is not obvious in that case. So you decide to give the computer some basic principles and let it solve the puzzle for you. You know you'll use the recursion.
You try to find the rule for recursion. You may want to start from the end or from the beginning. I'll describe the approach from the end.
The goal of the game is to push your opponent to the zone, where he must give you the victory. And not get pushed to that zone yourself. From N/9 to N there is a zone for winning. If one is pushed to play from between N/9/2 and N/9, he must lose. (Because both his moves push his opponent to the winning zone.) So you write your function:
wins(n) {
// returns 1, if starting player is able to reach
// the range [n, 2*n) with his move
if (n<=18) {
if (n<=9)
return 1;
else
return 0;
} else {
// I must push him to the zone between N/9/2 and N/9
return wins(n/18);
}
If you reached that point, you passed. There are details left, like whether to use float or int, whether to round up or down using int. But in general you showed the right way of thinking and you're ready to face the interviewer :)
EDIT: Actually there is a mistake in the code above. "Winning" is not the same as "being able to reach the range (n,2n)". Maybe 2 functions are necessary here: wins(n) and reaches_slightly_above(n). The latter would be called in a recursive way, and the values returned below 18 should be different, resemble the ones in the solution of Peter de Rivaz. However the solution below and the general approach should be ok.
The alternative approach, going from bottom to up, would be to use the function:
wins(a,n) {
if (9*a >= n)
// I win easily
return 1;
else
// if one of my moves pushes the opponent to the zone
// where he's not able to win, then I win!
return !wins(2*a, n) || !wins(9*a, n);
}
If they ask for n, you return the value of win(1,n). The complexity of this algorithm is not obvious, but I believe it's logarithmic.
回答2:
Since they must reach exactly N, this is only possible if N is of the form 2^a * 9^b, with one of a, b allowed to be 0 as well.
Find a and b above: if a + b = even, then the second player will win, otherwise the first will win.
This is because, at each step, a player gets closer to either a or b by one, and therefore to a + b by one. So the problem reduces to: given k, if at each step a player must subtract 1 from k, which player will reach 0 first?
回答3:
The optimal play will normally be to play the opposite of the opponent's move except right at the start and end.
By comparing with a recursive solution, it turns out that the answer can be computed based on the most significant digit in a base 18 representation of the number-1 as follows:
def win29(n):
if n<=9: return True
n-=1
while n>=18:
n = n//18
return n==1 or 4<=n<=8
回答4:
Whether just trying to meet or meet or exceed N, this can be solved by determining strategies that will always win in various cases. I'll present 5 cases (or 2 cases, the second of which has 4 sub-cases) that cover all N and give the winning strategy for each.
Consider T = ceil( log(N)/log(18) ), that is let T be the smallest power such that 18^T meets or exceeds N.
If 18^(T-1) * 9 < N then the first player always loses to an ideal opponent. Whenever the first player chooses a 2, the second chooses a 9. And whenever the first chooses a 9, the second chooses a 2. In this way, the second player's turn always ends at a power of 18. After T rounds, the second player wins. The first player cannot win at the prior round because multiplying by 9 is not sufficient to exceed N (so neither is multiplying by 2).
So, now let's consider 18^(T-1) * 9 >= N and choose the smallest k such that 18^(T-1) * 2^k > N. There are four possibilities k = 1, 2, 3, or 4.
(k = 1) First player wins. The first player can start with a 2, and then play as the second player did above, playing the opposite number from the other player each subsequent turn until the next to last round. The second player will always be faced with a power of 18 times the initial 2. At 18^(T-2) * 2, player two can at most reach 18^(T-1) by multiplying by 9, which isn't enough to win, and can at least return 18^(T-2)*4 which player one can multiply by 9 to win with 18^(T-1)*2.
(k = 3) First player also wins. This time player one starts with a 9 and plays as before. The second player will always be faced with a power of 18 times the initial 9. At 18^(T-2) * 9, player two can at most reach 18^(T-2) * 9 * 9 < 18^(T-2) * 18 * 8 = 18^(T-1) * 2^3, so isn't enough to win, and can at least return 18^(T-1) by multiplying by 2 which player one will multiply by 9 and win.
(k = 2 or 4) Second player wins. Here the second player should play the opposite number as before, until near the end, so that each round player one starts with a power of 18. At 18^(T-2), player one can at most reach 18^(T-2)* 9 < 18^(T-1), so not enough to win. If he returns 18^(T-2)*9, player two wins with 18^(T-2)*9*9 > 18^(T-2)*18*4 = 18^(T-1)*2^2 If player one instead returns 18^(T-2)*2, player two returns 18^(T-2)*4. Player one can then make at most 18^(T-2)*4*9 = 18^(T-1)*2, which is still not enough. And now player one can at least return 18^(T-2)*8, which is enough for player two to meet the goal since 18^(T-2)*8*9 = 18^(T-1)*4.
回答5:
Yes, you are supposed to think of an optimal-play from both players and decide who will win.
Here, a simple recursive thinking could lead you to a solution.
If a player is with number n and n*9 >= N then the current player will win the game.
else, He will pass on either 2*n or 9*n, to the 2nd-Player.
Now, 1st-Player will lose the game only if both options provided by him(2*n and 9*n) to the 2nd-Player lead to a winning number for 2nd-Player, otherwise he will have a chance of picking a winning number again.
Hence, we could write a recursive approach as following:
since, all numbers in game are going to be of form: 2^i * 9^j we could write:
F(i, j) = true; if (2^i * 9^j * 9) >= N
!(F(i+1, j) && F(i, j+1)); otherwise
solution would be in F(0, 0), whether the 1st-Player wins or not.
回答6:
There are great answers if N can be divided by 2 and 9, and some good game theory approaches. Here is a simple dynamic programming approach in Javascript to provide the answer for any possible N.
function getWhoWins(n) {
if(getWhichPlayerWins(0, 1, n) === 0) {
console.log("First player wins for " + n);
} else {
console.log("Second player wins for " + n);
}
}
// Returns 0 if first, 1 if 2nd player would win
function getWhichPlayerWins(currentPlayer, currentNumber, targetNumber) {
if(currentNumber * 9 >= targetNumber) {
return currentPlayer;
}
var nextPlayer = (currentPlayer + 1) % 2;
if(getWhichPlayerWins(nextPlayer, currentNumber *2, targetNumber) === currentPlayer || getWhichPlayerWins(nextPlayer, currentNumber *9, targetNumber) === currentPlayer) {
return currentPlayer;
}
return nextPlayer;
}
The time complexity of this solution is O(2*logN) = O(logN).
回答7:
The answer (I'm not 100% sure):
r = N mod 18
if r belongs to (1,9] player 1 wins
if r belongs to (9,18) or is =1 then player 2 wins.
I don't have a full mathematic demonstration, so I could be wrong.
This should be the correct answer if both players (or at least one of them) know how to play it.
Do I get the job? :)
回答8:
Two-player, deterministic games such as this are studied by combinatorial game theory. This frivolous game theory has no relation with the more useful game theory of Neumann and Nash popular in economics. The seminal work is a delightful book called Winning Ways by Conway, Berlekamp & Guy.
Think. For any game, either:
- There is a strategy whereby the second player always wins, however the first player plays.
- There is a strategy whereby the first player always wins, however the second player plays.
Your game is a special case, an impartial game, where the state of the game looks the same to both players. The best example is a simple matchstick game called Nim. It happens that all impartial games are equivalent to Nim (this is the Sprague Grundy theorem), so all impartial games can be solved completely.
Let's solve your game. The possible states of the game are the positive integers. We'll classify each state as either winning for the second player (we'll label such games zero '0' games), or winning for the first player (we'll label such games star '*' games).
The integers greater than or equal to N are all zero games, because at this point the game is over. Whoever's move it is has already lost.
States where the player whose turn it is can move to the zero positions above are star games. Thus the integers n, N/9 <= n < N are all star games - the winning move is to multiply by 9.
States where the player whose turn it is has no choice but to move to star position are zero positions again. So integers n, N/9/2 <= n < N/9 are zero positions. Our player has lost.
And so on. Using the similar arguments we eventually classify all integers down to one.
For N=1000 say,
- Integers 1000 and above are zero games
- Integers 112 to 999 are star games (to win, multiply by 9)
- Integers 56 to 111 are zero games (the player can't win)
- Integers 7 to 55 are star games (multiply by 9 or 2 accordingly so to move to one of the zero games 56 to 111)
- Integers 4 to 6 are zero games (the player can't win)
- Integers 2 to 3 are star games (multiply by 2)
- The integer 1 is a zero game (the player can't win)
Generalising we reach Peter's conclusion https://stackoverflow.com/a/13367642/284795
回答9:
Interesting post, and answers.
I'd be tempted to propose a theoretical brute force function that enumerates all combinatorial paths using 2/9 factors to N <= 2X10^12 (or as close as possible).
I say "theoretical" because I'm assuming that kind of computing power is beyond even FB?
