Problem of the Day -- The Lone Survivor

The Lone Survivor

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

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

Permalink: http://problemotd.com/problem/the-lone-survivor/

Comments:

Carlos - 10 years, 8 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.

reply permalink
Max Burstein - 10 years, 8 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.

reply permalink

Anonymous - 10 years, 8 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)
        {
            Servants.Add(i);
            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]);
                    Servants.Add(intBattlingServant);
                    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]);
                    Servants.Add(intBattlingServant);
                    break;
            }
        }
    }
}

reply permalink

Max Burstein - 10 years, 8 months ago

We have a winner! Nice job

reply permalink

gulliver - 10 years, 8 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)

reply permalink

Max Burstein - 10 years, 8 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.

reply permalink

Dustin S - 10 years, 8 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;
        }
    }

reply permalink

Jt - 10 years, 8 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")

reply permalink

bumbleguppy - 10 years, 8 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;
    }
}

window.onload = function(){
    console.log(lastSurvivor(1500));
}

reply permalink

Zach - 10 years, 8 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 numPeople = Convert.ToInt32(Console.ReadLine ());
        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;
    }

reply permalink

Anonymous - 10 years, 8 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!

reply permalink
Anonymous - 10 years, 8 months ago
It's simpler. Gotta break free from the procedural mindset!
```
survivor=: (2&}. , {.)^:_
```
reply permalink
Eddy - 10 years, 8 months ago
I tried to keep the solution as tiny as I could in C - GitHub link

reply permalink
MrZammler - 10 years, 8 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); }```

reply permalink
MrZammler - 10 years, 8 months ago
Sorry for the mess, not really sure how to quote code...

reply permalink

Anonymous - 10 years, 8 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); 
}

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

The Lone Survivor

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri