Yet again this is a Google Interview Questions for Intern from careerup. The following is the original problem description of that thread.
"Question: Two players A and B are playing a game. Pots of gold, each with
varying number of coins are placed in a single line. The rules of the game are:
1) Players play turn by turn.
2) On each turn a player can pick a pot of gold from either end of the line. He
gets all the gold in that pot. The next pot of gold on that end is now available
for picking.
What is the maximum number of gold can the first player get ?"
2. Analysis 1) Players play turn by turn.
2) On each turn a player can pick a pot of gold from either end of the line. He
gets all the gold in that pot. The next pot of gold on that end is now available
for picking.
What is the maximum number of gold can the first player get ?"
As some contributors on that thread pointed out that the owner of this thread was not very clear about two questions
- Are two players playing competitively or cooperatively?
- Are the gold pots are known to two players?
If the gold pots are unknown to two player and the only known pots are these two at the two ends available to pick, then there is not really much strategy to play. As the very limited information is available, like
- Two pots available to pick at the two ends
- The gold that two players are holding before the next pick
Assume that the number of gold in each pot, the number of pots are completely random and each game is independent. Therefor repeating many games does not really bring statistical hint for next games. All the two players can do is to make a pick based on the very limited information.
If the gold pots are known to two players, not matter if the players are playing competitively or cooperatively there is a global optimal/maximal gold that the first player can gain. If not single global maximal (many ways of picking to reach the maximal gold for the first player, for instance all pots with the same amount of gold), one of the ways to pick is what we are looking for. If only one global maximal available, the each picking of the first player will be critical because there might be one only way of picking that can take the first player to the unique global maximal. This will be a game between two players who can think deep forward.
In this blog I will discuss the scenarios that the gold pots are known to the two players. And these two players can play either competitively or cooperatively.
3. Solution
As I briefly discussed in last section, very limited information are available to the two players.Only the two pots at the two ends and the gold that they are currently holding now are available to be considered. My strategy is rather simple as well. Focus on the short term run as not enough information available to plan in the long run.
- Competitive play: both players pick the bigger pots at the two ends
- Cooperative play: the first player picks the bigger pot and the 2nd pick the smaller pot
4. C++ Implementation
// ********************************************************************************
// IMPLEMENTATION
// ********************************************************************************
#include <vector>
size_t MaxGoldCooperativeAndUnknown(const std::vector<size_t>& goldPots)
{
if (goldPots.empty()) {
return 0;
}
size_t endIndex = goldPots.size() - 1;
if (endIndex == 0) {
return goldPots[0];
}
size_t gold = 0;
size_t whoseTurn = 0; // Even: first player; Odd: second player
for (size_t startIndex = 0; startIndex < endIndex;) {
if (goldPots[startIndex] > goldPots[endIndex]) {
if (whoseTurn & 1) {
--endIndex; // the second player pick up smaller one
}
else {
gold += goldPots[startIndex];
++startIndex; // the first player pick up bigger pot
}
}
else
{
if (whoseTurn & 1) {
++startIndex; // the second player pick up smaller one
}
else {
gold += goldPots[endIndex];
--endIndex; // // the first player pick up bigger pot
}
}
++whoseTurn;
}
return gold;
}
size_t MaxGoldCompetitiveAndUnknown(const std::vector<size_t>& goldPots)
{
if (goldPots.empty()) {
return 0;
}
size_t endIndex = goldPots.size() - 1;
if (endIndex == 0) {
return goldPots[0];
}
size_t gold = 0;
size_t whoseTurn = 0; // Even: first player; Odd: second player
for (size_t startIndex = 0; startIndex < endIndex;) {
if (goldPots[startIndex] > goldPots[endIndex]) {
if (whoseTurn & 1) {
++startIndex; // the second player pick up bigger one
}
else {
gold += goldPots[startIndex];
++startIndex; // the first player pick up bigger pot
}
}
else
{
if (whoseTurn & 1) {
--endIndex; // the second player pick up bigger one
}
else {
gold += goldPots[endIndex];
--endIndex; // the first player pick up bigger pot
}
}
++whoseTurn;
}
return gold;
}
// ********************************************************************************
5. Reflection on the Strategy
Because of limited information available and the simple strategy, this is really not a fun game to play. And the game does not really depends on how well the two players can play and it completely depends on how the gold pots is generated.
Another question is if this is a win-or-lose game. If yes, then the player can consider taking disadvantage pick for the short run in order to gain more in the long run. For instance if one player knows that the gold is much less than the opponent. Then probably it is worth taking the risk to take some bold picks in order to swing the game. This can't be called a strategy but be really just a gamble, because there is not really any evidence to bring you different game result by taking disadvantage picks based on the assumption in Section 3.
Surely with known gold pots, it would be much fun to play. Because each pick of the first player will potentially be deciding moment if he/she can reach the global maximal gold. I will discuss it in my next two blogs.
No comments:
Post a Comment