In this article, I will investigate and explain the Logical Pattern behind (in my opinion) one of the best questions in Computer Science: The Piracy Problem.
For all of you who hoped to find an article about downloading movies or software, I have to disappoint you. This is not about that kind of piracy. It's about one of the best algorithmic riddles that I have found so far. It's quite a read, but I hope you think it's worth it!
To start off, I'm going to send you here. This entire article is based upon that riddle.
Finished? Cool, isn't it? Logic and pattern recognition combined with a funny setting. There's a small extension to it on the same site here.
I thought about this riddle for a long time and decided to discover the logical pattern behind this problem. In the 6 pirates, 1 coin case, pirate number 5 dies if he would have to make the proposal, yet pirate number 6 lives, because he can count on 5's vote even if 5 gets no coins (because he would otherwise die). I was wondering, what other pirates would survive if there was only a single coin? Pirate 7, 8 and 9 would die again, since they can never convince resp. 4, 4 and 5 pirates to vote for them. Pirate 10 however, gets to live! Because 7, 8 and 9 would otherwise die, they vote for 10 even if they get nothing! Combined with 10's own vote and the vote of the pirate who gets the coin, 10 is able to secure 5 votes and gets to live another day.
Note that in this case, pirate 5 would not vote for pirate 10, because he knows he will get nothing anyway and if 10 walks the plank, so will 9, 8 and 7. 6 would then come to power and 5 would then vote for 6. He still gets nothing, but at least 4 other pirates have died. Him being a pirate, only his own life and getting gold pleases him more than seeing others die :-)
So, let's re-iterate the priorities that pirates use to vote, in order of importance:
- Priority 1: Stay alive
- Priority 2: Get as many gold coins as possible
- Priority 3: Get as many other pirates killed as possible (given priority 1 and 2 are equally satisfied)
- Priority 4: If a pirate is a senior and it doesn't matter to whom he gives a coin, he will give it to the LOWEST ranked pirate. So, if pirate number 6 can choose to give a coin to either 1 or 4, he will choose 1.
I then started to make spreadsheets of the number of coins that each pirate would get, when there are c coins available. Below is the spreadsheet of the 1 coin case. The rows represent the situation where there are a certain number of pirates and the columns represent what each pirate would get in those situations. a value of -1 (and a red color) means that the pirate in question dies in that given situation. The green cells represent the pirates who would vote in favour of the proposal. Please click to enlarge.
The 1 coin case
And here are the spreadsheets for 2 and 3 coins:
The 2 coins case
The 3 coins case
A clear pattern emerges! I have defined so-called "life lines": lines on which the most senior pirate is able to survive by counting on the votes of the pirates who would otherwise die. I've marked those rows with a light green color. The patterns that emerge are as follows:
- A life line occurs when the number of pirates is equal to a number in this set: For c number of coins and x > 1: 2x + 2c. So, for 1 coin, the life lines are 4, 6, 10, 18, 34...
- Before the first life line: If the most senior is even, all even pirates get a coin, all odd pirates get nothing. The most senior keeps what's left. When the most senior is odd, it's the odd pirates who get a share of the bounty. Note that the "first" life line fits this pattern as well. It's kind of a transitional line.
- After each life line, the most senior pirate dies and the others get the same as they got on the previous life line, until we get to the next life line.
- On each life line, the most senior pirate gives the coins to the most junior pirates who would otherwise get nothing. Note that these alternate on each subsequent life line, because otherwise, those juniors have no incentive to vote (because they would get the coins anyway).
The 0 coins case
Then, I created an algorithm (in Java). For a certain number of pirates and a certain number of coins, what does a certain pirate get? (Scrolling to the right is possible)
/**
* Avast, me hearties! This method returns me bounty, the number of dubloons me be gettin' when me be among these scurvy dogs! Yarr!
*
* @param numberOfCoins The total number of dubloons me and me mateys will divide...
* @param numberOfPirates The total number of scallywags in this bung hole!
* @param myIndex Me index! Big guys above me, sprogs below...
* @return
*/
public static int whatsMeBounty(int numberOfCoins, int numberOfPirates, int myIndex) {
int firstLifeLine = 2 + numberOfCoins*2;
if(numberOfPirates < firstLifeLine) { //We're under the first life line
if(myIndex == numberOfPirates) { //Me be the most senior
return numberOfCoins - (int) ((numberOfPirates-1)/2); //Integer division is floored, so me be gettin' what's left
} else { //Me not be the most senior
if(numberOfPirates % 2 == 0) { //The most senior is even
if(myIndex % 2 == 0) { //Me be even
return 1;
} else { //Me be odd
return 0;
}
} else { //The most senior is odd
if(myIndex % 2 == 0) { //Me be even
return 0;
} else { //Me be odd
return 1;
}
}
}
} else { //We're over or on the first life line
double lifeLineIndex = Math.log(numberOfPirates - numberOfCoins*2) / Math.log(2);
if(lifeLineIndex % 1 == 0) { //We're exactly on a life line
//If me be more senior than the most senior pirate on the preceding lifeLine (and this isn't the first life line), me be votin' to live, not to get coins
int precedingLifeLineSenior = (int) Math.pow(2, (lifeLineIndex-1) + numberOfCoins*2);
if(myIndex > precedingLifeLineSenior && numberOfPirates != firstLifeLine) { //Me be votin' to escape Fiddler's Green!
return 0;
} else { //Me only be votin' if me be gettin' a coin!
if(lifeLineIndex % 2 == 0) { //We're on an even life line, the first 'numberOfCoins' odd pirates get a coin
if(myIndex % 2 == 1 && myIndex <= numberOfCoins*2) {
return 1;
} else {
return 0;
}
} else { //We're on an odd life line, the first 'numberOfCoins' even pirates get a coin
if(myIndex % 2 == 0 && myIndex <= numberOfCoins*2) {
return 1;
} else {
return 0;
}
}
}
} else { //We're NOT on a life line
if(myIndex == numberOfPirates) { //Me be the most senior
return -1; //Shiver me timbers! Me be walkin' the plank!
} else { //Me not be the most senior, let's see what me be gettin' once that scurvy dog has visited Davy Jones's locker!
return whatsMeBounty(numberOfCoins, numberOfPirates-1, myIndex);
}
}
}
}
And that's that: The Logical Pattern behind Piracy.
Thanks to:
No comments:
Post a Comment