Problem of the Day
A 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?

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

Comments:

  • Carlos - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 months ago

    We have a winner! Nice job

    reply permalink

  • gulliver - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 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 - 9 years, 11 months ago

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

    survivor=: (2&}. , {.)^:_
    

    reply permalink

  • Eddy - 9 years, 11 months ago

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

    reply permalink

  • MrZammler - 9 years, 11 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 - 9 years, 11 months ago

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

    reply permalink

  • Anonymous - 9 years, 11 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

Content curated by @MaxBurstein