The 100 Prisoners Problem

Swami Gulagulaananda asked:
"Where would you stand to save your life?"

Here is a simple problem. Go ahead and try to solve it...

In an island are stranded 100 people and you are one among them. You were captured by tribals, who say that only one among the 100 can survive. And here is the condition. One of you is given an axe. And he has to hack and kill the guy to his right, and pass the axe to the guy after him. And the cycle continues...

So, if the people were numbered 1, 2, 3.... 100, then 1 kills 2, and gives to 3. 3 kills 4 and gives it to 5 and so on. The 99th guy kills 100th guy and passes it back to 1, who kills number 3 and so on. The question is, if you were in that group, where would you stand to be the last man standing?

And the solution is... *Spoiler Alert*
There are 3 ways of solving this.

Method I
One, is by finding a pattern. Do it for groups of 1, 2, 3 and so on... say till 10.

If the group had 1 guy, survivor = 1
If the group had 2 guys, survivor = 1
If the group had 3 guys, survivor = 3
If the group had 4 guys, survivor = 1
If the group had 5 guys, survivor = 3
If the group had 6 guys, survivor = 5
If the group had 7 guys, survivor = 7
If the group had 8 guys, survivor = 1

Just continue, you will see the pattern. For every number where the value is equal to 2 to power of n, as in 1, 2, 4, 8... the survivor is person 1. For any other number, the survivor is = 1 + (2 times the difference between the nearest two power number).

The answer by the way is 73rd position...

Method II
Programming! We played this game just to come up with answers... The following are the 3 solutions each one of us came up with in a different language...

Solution in Python (Shortest program written by co-worker Amod Pandey, but took the most time to finish :P)

	list = range(1,101)
	x = 0
	while (len(list) > 1):
	x = (x+1) % len(list)
	list.pop(x)print list[0]

view raw gistfile1.py hosted with ❤ by GitHub

Solution in Ruby, which I wrote - I finished second, I have some trace statement for help :

	#!/usr/bin/ruby
	axe_holder = 0 #Who has the axe in beginning. 0 is first guy
	n = 100 # Number of people
	######################
	a = *0..n-1
	while a.length > 1
	puts a.join(' ')
	puts 'Axe Holder: ' << a[axe_holder].to_s
	puts (a[(axe_holder + 1) % a.length]).to_s << ' was killed'
	a.delete_at((axe_holder + 1) % a.length)
	if a[axe_holder + 1] == nil
	axe_holder = 0
	else axe_holder = axe_holder + 1
	end
	end
	puts 'And the answer is ' << (a[0] + 1).to_s

view raw gistfile1.rb hosted with ❤ by GitHub

And this is what I wrote subsequently...

(100 - (2 ** (100.to_s(2).length - 1))) * 2 + 1

view raw gistfile1.rb hosted with ❤ by GitHub

And my final submission in Ruby, based on the PDF solution below...

(100.to_s(2)[1..-1] + 100.to_s(2)[0,1]).to_i(2)

view raw gistfile1.rb hosted with ❤ by GitHub

And Niyaz has written in Javascript... He finished coding the fastest. Here it is.

	var a = [];
	for(var k=0;k<100;k++) {
	a.push(1);
	}
	var i = 99;
	var axe = 0;
	while(i) {
	var j = axe;
	do{
	j = (j + 1) % 100;
	}while(a[j] == 0);
	a[j] = 0;
	i--;
	while(a[j] == 0) {
	j = (j + 1) % 100;
	};
	axe = j;
	}

view raw gistfile1.js hosted with ❤ by GitHub

Subsequent vastly improved solutions by Niyaz - One line solutions!!
This one is in Javascript

parseInt(((100).toString(2) + '1').slice(1), 2);

view raw gistfile1.js hosted with ❤ by GitHub

And one more in Python

int(bin(100 << 1 | 1)[3:], 2)

view raw gistfile1.py hosted with ❤ by GitHub

Finally, Shashank's Java code.

	public class PrisionerAlivePosition {
	static int[] obj = new int[100];
	public static int returnAlive(){
	int noOfAlive = 0;
	for (int i = 0 ; i < obj.length ; i++){
	if (obj[i] == 1)
	noOfAlive += 1;
	}
	return noOfAlive;
	}
	public static void main(String[] args) {
	int axePerson = 0;
	for(int i = 0 ; i < obj.length ; i++){
	obj[i]=1;
	}
	while (returnAlive() > 1){
	axePerson = killNext(axePerson);
	}
	System.out.println("Position to stand and remain alive "+ (getNextAlivePerson(0)+1));
	}
	public static int getNextAlivePerson(int temp){
	while(true){
	if (obj[temp] == 1){
	return temp;
	}
	temp = temp + 1;
	if (temp >= obj.length){
	temp = 0;
	}
	}
	}
	public static int killNext(int axePerson){
	axePerson = getNextAlivePerson(axePerson+1);
	obj[axePerson] = 0;
	System.out.println("killed Person "+(axePerson+1));
	return getNextAlivePerson(axePerson);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

And then I solved this using Linked Lists

	#!/usr/bin/python
	class Prisoner:
	number = 0
	next_prisoner = None
	max_prisoners = 100
	first = Prisoner()
	first.number = 1
	p = first
	# Create circle - Using Linked Lists
	for i in range(2, max_prisoners + 1):
	q = Prisoner()
	q.number = i
	q.next_prisoner = first
	p.next_prisoner = q
	p = q
	# Kill prisoners
	p = first
	while p.next_prisoner.next_prisoner.number != p.number:
	p.next_prisoner = p.next_prisoner.next_prisoner
	p = p.next_prisoner
	print p.number

view raw josepheus_linkedlist.py hosted with ❤ by GitHub

Method III
Apparently this problem is called Josephus problem. My friends Goutham Kamath and Prashanth Harshangi knew the problem along with a really fancy solution - they have provided the link to a PDF file here