It was a dark stormy night, the staff of DIC had been running all night up this steep mountain trying to avoid the hordes of newbies asking for solutions. “Run for the cave!” yelled supersloth. So the crew ran into the cave hoping to elude the beasts that will not let a programming master sleep. Shortly after the 10 staffers made it safely inside… “BOOM POW CRASH!” the cave entrance collapses and the DIC staff are trapped! Except for a small hole that will surely lead to their capture by the newbies if they exit out of it. What will the DIC staff do?!?! Find out on another exciting entry of the Programming Underground!
“Great, now we are stuck here, thanks a lot sloth!” cried Capty. Sloth quickly replied “die!” Skyhawk looked around and noticed that all ten of the staff made it into the cave. PsychoCoder the Crazy, Supersloth the Wise Guy, Skyhawk the Destroyer, Marko the Giant, 1lacca the Professor, NickDMax the Angry, Amadeus the Righteous, Jayman9 the Ninja, Capty99 the panzy, and Martyr2 the Theoretician.
“I don’t know about you guys, but I am not going to surrender to those newbies” shouted Amadeus. Skyhawk piped up and said “Oh what do you want to do? Stay and fight them? Did you see how many of them there were? I am sure Psycho could distract some of them with a tutorial, but not all of them. They all don’t like C# or VB.NET you know.” Capty chimed in and asked “Is there any way we can just surrender because I am not like you guys. I have a loving man at home that is missing me, it is dinner time, and this cave does nothing for my complexion. I just want to go home.”
Staring around at one another 1lacca mentions a faaaaabulous idea. He tells the rest of the staff his plan to commit suicide but in a logical way. “How about we all stand in a circle and every nth person kills themselves until no one is left. That way the newbies won’t take us alive and we can die with our integrity!” NickDMax asks “What number will we substitute for N in our equation? Damn it people, we have to know these things! Be logical!” After a brief pause and looking stumped, skyhawk shouts out “3! Every third person will kill themselves! And don’t be a bunch of chickens! MarkoDaGeek, network them!” So Marko the Giant starts hooking everyone up into a circle for the round robin of carnage to begin. “Hey Marko, do you mind if I be the 10th person in the circle? I figured you guys are much better at all this stuff than I am. After all, Psycho and I are only Mentors. What the hell do we know?”
“Sure thing Martyr, you stand here in place number 10. All set Skyhawk, need a sacrificial dagger?” Skyhawk pulls out a huge dagger with a 10 inch blade. “Nah, I got it Marko. I carry this on me for when I need to take out a rogue poster on the board. Ok guys, here we go, first up is place number 3, that would be you Jayman9! Say your peace and may god greet you with honor at the pearly gates of heaven!”. Jayman takes the blade and stabs himself in the chest and twists it. He falls to the ground. “Ok, next up is you Amadeus!” said Skyhawk.
The round robin of suicides continue until two people are left standing… Psycho and Martyr2. The next round begins and the turn lands on Psycho. “It has been nice knowing you Martyr… oh and thanks for helping me with that C# program the other day!” He then kills himself, leaving only Martyr2. Standing there for a minute he smiles and says to himself “Gosh, what a bunch of freaks! I guess no one has heard of the Josephus algorithm. I am out of here!” Martyr2 then walks out to the newbies and gives up. He is now a tortured soul working to satisfy the demands of the newbies, but at least he is alive. He ends up retiring to a nice plot of land on the beach and sipping a nice glass of ice water while watching his super hot girlfriend run around half naked on the shore.
So how did Martyr2 do it? How did he know where to stand to land out of harms way? Was he lucky? No, he used the Josephus algorithm and we will show you how!
The algorithm was rumored to have started back around the first century AD from a jewish mathematician named Flavius Josephus. He supposedly had a problem similar to our DIC story above. He, and several other jews, got trapped in a cave where the Romans were waiting outside. Instead of committing suicide like the others, he stood in the round robin ring to avoid having to kill himself. He eventually gave up to the Romans after everyone else killed themselves.
The algorithm involves X number of elements in a circle where every Nth element is removed until there is only one sole survivor (eat your heart out Jeff Probst!). In our example below, we create a set of nodes which have two pointers and a value. The value simply holds the number in the circle and identifies each node. Each pointer points to the next node in the group of (alive) elements, one for the previous node in the circle and one for the next node in the circle. This is commonly referred to as a double linked list of nodes.
The trick to this list of nodes is that the tail of the list then refers to the head node of the list, completing the circle. When a node is determined for “killing” it tells its previous node partner to point to the next node after it. It then tells the next node in the loop to then point back to the previous node. By setting these two pointers to one another, it removes itself from the circle.
So lets dive into the code in C++….
#include <iostream>
using namespace std;
// Define the structure of our node
struct node {
int value;
node *previous;
node *next;
};
int main(){
int numPeople = 0;
cout << "Enter the number of people: " << endl;
cin >> numPeople;
// Create a head node
node *curNode = new node();
curNode->value = 1;
// Create a temp node
node *temp = curNode;
// Create a chain of nodes
// Each node has a pointer to next and previous nodes
// Plus it has a number for its value.
for (int i = 2; i <= numPeople; i++) {
curNode->next = new node();
curNode->next->previous = curNode;
curNode = curNode->next;
curNode->value = i;
}
// Attach the tail node back to the head.
// Remember to make the head then point to the tail as its previous node.
curNode->next = temp;
curNode->next->previous = curNode;
// Lets move the current node back to head.
curNode = curNode->next;
int nthkilled = 0;
// Prompt for the nth person to kill on each iteration.
cout << "Enter the nth number killed: " << endl;
cin >> nthkilled;
int counter = 1;
// Lets move around the ring clockwise
// ... and let the carnage begin!
// We loop through the nodes killing every nth person
// We know we have one left standing when the node points to itself.
while (curNode->next != curNode) {
// Compare the count to the value of nth killed
// We kill the node (by kicking it out of the chain)
// Then reset our counter. You could use modulus here
// if you like.
if (counter == nthkilled) {
cout << "Killed: " << curNode->value << endl;
// Here we are telling the previous node to point
// to the current nodes next node.
curNode->previous->next = curNode->next;
// We then tell the next node's previous pointer
// to point to the current nodes previous node.
curNode->next->previous = curNode->previous;
// Just record the next node because we are going
// to free the current node.
node *next = curNode->previous->next;
delete(curNode);
// We then advance the current node to the next
// node to complete the kill (no pointers are now
// pointing at the killed node.
curNode = next;
counter = 1;
}
else {
// Not a time to kill, so move to the next node
// and advance our counter.
curNode = curNode->next;
counter++;
}
}
// By the time the loop ends, we have our sole survivor.
cout << "Survivor: " << curNode->value << endl;
delete(curNode);
return 0;
}
You can read through the in-code comments to see what is going on. Of course this could be simplified a bit, but for newbies reading I have set it up to be very verbose, especially where we deal with the pointers.
Essentially we create a ring of nodes by creating a head node and then a series of “chain nodes” which we then attach to the head. After the middle links have been added, we tell the tail to attach back up to the head. Now each node’s pointers point to the node before and after it in the circle.
Next we ask for the “Nth person to kill” number. Using that number, we begin a loop which counts each node. When the number N is reached, we change the nodes pointers, delete the node pointer (to free up resources) and then reset the counter. Otherwise we just move onto the next node in the line and increment the counter.
We will stop the loop when we have only one node. We will know this because the node will point to itself. After exiting the loop, we simply display the value of the survivor. So if we say a chain of 10 nodes where every 3rd node is killed off, the surviving node is number 10… our good old Martyr2.
I hope you have enjoyed the algorithm. It is a good practice in node creation, pointer linking, and double linked list setup. This setup could be anything from a ring network where each node is an actual computer or something as trivial as our story. I hope you enjoyed reading the post and thank you for reading!
🙂
