# Problem of the DayA new programming or logic puzzle every Mon-Fri

## The Lone Survivor

There are 1,500 loyal servants sitting around the king's table when they decide to play a little game. The 1st servant gets a sword and kills the 2nd servant. He then gives the sword to the 3rd servant, who then kills the 4th servant and then gives the sword to the 5th. This continues so that the 1,499th servant kills the 1,500th servant and gives the sword back to the 1st servant.

Now the 1st servant kills the 3rd and gives the sword to the 5th. This process continues until only one servant remains. Which number servant is the lone survivor?

• Carlos - 3 years, 2 months ago

I think there is a small problem that needs to be answered before anyone can really resolve the problem: We have 1500 servants, a pair number, next round will have 750, still a pair number, then 375, not a pair number, which means that at the end of the round, there will be 1 guy left that has no one to kill, unless he has to kill the first. So my question is, if there is guy left in a round (which eventually happens) does he kill the first guy or does he hands the sword to the first guy?

Hopefully he kills the first guy, otherwise it's too easy.

• Max Burstein - 3 years, 2 months ago

It goes around in a circle. So once it reaches the highest number it goes back to the lowest number. So if there were 1-375 then 375 would kill 1 and pass to 3.

• Anonymous - 3 years, 2 months ago

Servant 953 wins after killing servant 1465.

I used C# to figure this out. I assumed that after a round the guy left with the sword kills the first guy.

``````public class Battle
{
public Battle(int intServants)
{
Servants = new List<int>();
int i = 1;
while (i <= intServants)
{
i++;
}
Console.WriteLine(String.Format("{0} Servants registered for battle", intServants.ToString()));
}

public List<int> Servants;

public void DoBattle()
{
bool blnBattleWon = false;
while (!blnBattleWon)
{
int intBattlingServant = Servants[0];
switch (Servants.Count)
{
case 1:
Console.WriteLine(String.Format("Servant {0} is the winner!", Servants[0].ToString()));
blnBattleWon = true;
break;
case 2:
Console.WriteLine(String.Format("Servant {0} kills Servant {1}!", Servants[0].ToString(), Servants[1].ToString()));
Servants.Remove(Servants[1]);
Servants.Remove(Servants[0]);
break;
default:
Console.WriteLine(String.Format("Servant {0} kills Servant {1} and hands the sword to Servant {2}", Servants[0].ToString(), Servants[1].ToString(), Servants[2].ToString()));
Servants.Remove(Servants[1]);
Servants.Remove(Servants[0]);
break;
}
}
}
}
``````
• Max Burstein - 3 years, 2 months ago

We have a winner! Nice job

• gulliver - 3 years, 2 months ago

Is there a way to solve this without programming it? Here's my effort in python:

``````def lone_survivor(l, option = 0): # option is if last guy is dead (0) or alive (1)
if len(l) == 1:
return l
else:
i = option
new_l = []
while i < len(l):
new_l.append(l[i])
i+= 2
if i == len(l) + 1:
return lone_survivor(new_l,1)
else:
return lone_survivor(new_l,0)
``````
• Max Burstein - 3 years, 2 months ago

The mathy way to do it is a left circular shift. The formula for which happens to be i + 1 % n which is essentially what the problem is asking for in a roundabout way. I didn't realize it either when I first solved the problem but I think it's definitely a cool/efficient solution.

• Dustin S - 3 years, 2 months ago

I used a circular linked-list to solve this! I agreed that the last servant standing is 953.

``````   //returns the id of the servant that wins the battle.
public int battle(int numberOfServants) {
if (numberOfServants <= 0) { return -1; }
if (numberOfServants == 1) { return 1; }
Node servantsInBattle = new Node(1);
servantsInBattle.next = servantsInBattle;
for(int i=2; i<=numberOfServants; i++) {
servantsInBattle.append(i);
}
Node cursor = servantsInBattle;
while (cursor.next != cursor) {
cursor.deleteNext();
cursor = cursor.next;
}
return cursor.data;
}

public class Node {
public Node next = null;
public int data;

public Node(int d) {
this.data = d;
}

public void append(int d) {
Node start = this;
Node end = new Node(d);
Node n = this;
while (n.next != start) {
n = n.next;
}
n.next = end;
end.next = start;
}

public void deleteNext() {
this.next = this.next.next;
}
}
``````
• Jt - 3 years, 2 months ago

Python

``````class Servant(object):
def __init__(self, pos):
self.pos = pos

def __str__(self):
return str(self.pos)

servants = list()
index = 1
while index <= 1500:
servants.append(Servant(index))
index = index + 1

index = 0
while len(servants) > 1:
servantToBeKilled = index + 1
if servantToBeKilled >= len(servants):
servantToBeKilled = 0

print("Servant " + str(servants[index]) + " kills servant " + str(servants[servantToBeKilled]))
servants.pop(servantToBeKilled)
index = index + 1
if index >= len(servants):
index = 0

print()
print(str(servants[0]) + " is the Highlander")

``````
• bumbleguppy - 3 years, 2 months ago

javascript. It took me too long to do this, but I tried to make an array utility that does the circular search and return the next index. I guess I could have done an Array.prototype.

``````function lastSurvivor(amountOfServants) {
var servants = [];
var i = 0;
var doomed = 0;  //stores array index value of victim
var hasSword = 0;  //stores array index value of killer

//initialize array with ordinal integer values
while(i < amountOfServants){
servants[i] = i + 1;
i++;
}

//start search loop
while(true){
//call nextElementCircular function to determine index of next victim
doomed = nextElementCircular(servants, hasSword, compare);

//respond to return value of nextElementCircular function if no element matching the compare function in found
if(doomed == -1) break;

//set array element value to zero to show the servant was killed
servants[doomed] = 0;

//set the index of the next killer
hasSword = nextElementCircular(servants, doomed, compare);
}

//returns the winner of the killing orgy
return servants[hasSword];

/* utility function - used to compare the array element integer value
when passed to the nextElementCircular function */
function compare(val){
return val > 0;
}
}

function nextElementCircular(arrayToSearch, fromIndex, compareFunction){
var elementIndex = fromIndex + 1;
var arrayLength = arrayToSearch.length;
while(true){
if(elementIndex === arrayLength) elementIndex = 0;
if(compareFunction(arrayToSearch[elementIndex])) return elementIndex;
elementIndex++;
if(elementIndex === fromIndex) return -1;
}
}

console.log(lastSurvivor(1500));
}
``````
• Zach - 3 years, 2 months ago

I did all the work in the actual for loop header itself, so there is no body at all. I think it's certainly less readable because of it, but its also a nice change so I'm keeping it that way.

``````    private static int next;

public static void Main (string[] args)
{
Console.WriteLine ("How many people are seated at the table?");

int swordHolder = 0;
int[] tableOfPeople = new int[numPeople];

for (int peopleKilled = 0; peopleKilled < numPeople - 1; peopleKilled++) {
Console.WriteLine ("{0} has the sword", swordHolder + 1);
swordHolder = killGuyNextTo (tableOfPeople, swordHolder);
}
}

private static int killGuyNextTo(int [] table, int swordHolder) {
for (next = swordHolder + 1; table [next % table.Length] == -1; next = ++swordHolder + 1)
;
table [next % table.Length] = -1;
return passTheSword (table, next) % table.Length;
}

private static int passTheSword(int [] table, int deadGuy) {
for (next = deadGuy + 1; table [next % table.Length] == -1; next = ++deadGuy + 1);
;
return next % table.Length;
}
``````
• Anonymous - 3 years, 2 months ago

Neat problem. In J:

``````survivor=: (}.@}: , {:)@(1&|.)^:_

survivor 1 2 3 4 5   NB. => 3
survivor >: i. 1500  NB. => 953
``````

Thanks for these Potds, and happy holidays!

• Anonymous - 3 years, 2 months ago

It's simpler. Gotta break free from the procedural mindset!

``````survivor=: (2&}. , {.)^:_
``````
• Eddy - 3 years, 2 months ago

I tried to keep the solution as tiny as I could in C - GitHub link

• MrZammler - 3 years, 2 months ago

Here's my attempt: ```C #include <stdio.h>

int servants[1500]; int cnt_alive=1500; int kill_next (int sword, int to_die); int next_alive (int sword);

int main(int argc, char *argv[]) { int i;

for (i=0;i<=1499;i++) servants[i]=1; //all alive at first

kill_next(0,1);

for (i=0;i<=1499;i++) if (servants[i]==1) printf("Servant [%d] is alive.\n", i+1);

return 0; }

int next_alive (int sword) { if (servants[sword]==1) return sword; else { sword++; if (sword>1499) sword=0; next_alive(sword); }

}

int kill_next (int sword, int to_die) { if (cnt_alive == 1) return;

printf("[%d] will kill [%d]\n",sword+1, to_die+1); servants[to_die]=0; cnt_alive--; sword = next_alive(to_die); to_die = next_alive(sword+1); kill_next(sword, to_die); }```

• MrZammler - 3 years, 2 months ago

Sorry for the mess, not really sure how to quote code...

• Anonymous - 3 years, 2 months ago

``````#include <stdio.h>

int servants[1500];
int cnt_alive=1500;
int kill_next (int sword, int to_die);
int next_alive (int sword);

int main(int argc, char *argv[])
{

int i;

for (i=0;i<=1499;i++)
servants[i]=1; //all alive at first

kill_next(0,1);

for (i=0;i<=1499;i++)
if (servants[i]==1)
printf("Servant [%d] is alive.\n", i+1);

return 0;
}

int next_alive (int sword)
{
if (servants[sword]==1)
return sword;
else {
sword++; if (sword>1499) sword=0;
next_alive(sword);
}

}
int kill_next (int sword, int to_die)
{
if (cnt_alive == 1) return;

printf("[%d] will kill [%d]\n",sword+1, to_die+1);
servants[to_die]=0;
cnt_alive--;
sword =  next_alive(to_die);
to_die = next_alive(sword+1);
kill_next(sword, to_die);
}
``````

Content curated by @MaxBurstein