Solving puzzle with programming

Today, I stumbled upon an interesting puzzle in whatsapp group. The puzzle goes as below:

100 people standing in a circle in an order 1 to 100.
No. 1 has a sword. He kills next person (i.e. no. 2) and gives sword to next to next (i.e no. 3). All person does the same until only 1 survives. Which number survives at the last?

Someone had already given answer but I thought to confirm it with programming as it could be a nice example of solving puzzle with programming. Before starting to code one must create logic/flow for it. This is how I broke down the puzzle.

- There are 100 people starting from 1 to 100.
Here, we can define an array with 100 elements with values from 1 to 100.

- No.1 has a sword. He kills next person (i.e. no. 2) and gives sword to next to next (i.e no. 3).
We have taken array element as a person. 1st person kills the next. So, starting from 1, we'll remove next element i.e. 2. Then first person gives sword to next to next i.e. 3. That person will also kill next person and this continues. Means, in array, we need to start with 1 and remove the every other (alternate) element till 100. (all the even numbers will be removed and we'll be left with odd numbers only in array).

- All person does the same until only 1 survives.
After first iteration, we will have an array with 50 elements and we again need to remove every other (alternate) element. We need to repeat this process until we have only 1 element in the array and the last remaining element is the answer of who survives at last.

The code could be as below (in PHP):


$numbers = range(1,100);	//define an array with 100 elements starting from 1 to 100
$round = 1;			//define a variable to keep note of how many rounds are required to get the answer (this is optional)
$temp = 1;			//Just a Boolean variable to remove alternate element

//As removing elements from array will be repetitive task we define a function which will remove elements.
function remove_elements(){
	global $numbers, $round, $temp;	//Use the variables inside function by defining them global
	foreach($numbers as $key=>$value){	//iterate the loop for each element of an array
		if($temp == 0) {
			unset($numbers[$key]); //remove alternate element
			$temp = 1;
		}
		else {
			$temp =0;
		}
	}
	echo "Round $round: ".implode(', ',$numbers)."
"; //print the round number and elements remained after removing elements in that round $round++; //increase the round number for each iteration if(count($numbers) != 1){ remove_elements(); //we are calling remove_elements function recursively until we are left with only one element in our array } } remove_elements(); //Call the function

Output of this program would be as below:


Round 1: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99
Round 2: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97
Round 3: 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97
Round 4: 9, 25, 41, 57, 73, 89
Round 5: 9, 41, 73
Round 6: 9, 73
Round 7: 73

So, this is how I solved the puzzle. Answer is 73rd person will survive at last. It was pretty simple one and didn't take much time but it can be a good exercise for students and freshers.

In interview many candidates fail to write the logic of simplest programs given to them. I am sure most of them don't try to do actual programming on their own so they can not develop logic to solve a problem. This is a very serious problem as if they can't think how to take on the problem, they can't code for it. I would advise computer science students and fresh graduates to try to solve such puzzles or problems by programming. It will help you to build your logic stronger. Once it is solved you can also try to solve the same puzzle/problem with different logic, it will show you that there could be multiple ways a problem can be solved in programming. Practising such things will surely help you to perform better in your interview and practical test.

Happy learning! Happy programming!

Comments

Nice Puzzle....Really brain storming....

Thanks Ashish. Hope you enjoyed solving it.

public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

private void btnSurvive(object sender, EventArgs e)
{
Soldiers objSolgier = new Soldiers(Convert.ToInt32(txtInput.Text));
MessageBox.Show(objSolgier + objSolgier.MySoldiers);
}
}
public class Soldiers
{
public List MySoldiers { get; set; }
public Soldiers(int range)
{
MySoldiers = new List();
MySoldiers.AddRange(Enumerable.Range(1, range));
}
public static string operator + (Soldiers obj, List items)
{
return KillSoldiers(items, 1, true)[0].ToString();
}
static List KillSoldiers(List items, int startIndex, bool bStart)
{
startIndex = bStart == true ? 1 : 0;
for (int i = startIndex; i < items.Count; ++i)
{
items.RemoveAt(i);
bStart = i == items.Count ? true : false;
}
while (items.Count > 1)
KillSoldiers(items, startIndex, bStart);
return items;
}
}

You got it wrong
in the second round 99 kills 1 ( they are in circle ),
in this way the only survivor will be 63

Actually in 2nd round 99 will be killed by 97 and the sword will go to 1. So, it's not wrong.

I agree

Thanks Savanth.

I was reading your solution after I saw a Javascript solution for this puzzle
Think it is good to share it as an alternative way
http://www.kodyaz.com/articles/javascript-array-puzzle-hundred-people-ar...

Hey I tried your source code but unfortunately its not working on my localhost it executed code 1 to 100 continuously
Is there any other method to do this logic behind that

Add new comment