All But One Shall Die!

Nagy Vilmos

Genghis Kahn, being in a good mood decides to spare one life of his 1,000 captives. He has them stand in a circle and runs a sword through every second man. If the first man is #1 [amongst Kahn's many crimes was a love for VB], which man will be left alive?

speramus in juniperus

Pete OHanlon

Well, unless Genghis Kahn decides to stand in the circle, he should be fine.

Lost User

The last one standing.

Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]

Abhinav S

The first man will be left standing.

Apps - Color Analyzer | Arctic | XKCD | Sound Meter | Speed Dial

Pete OHanlon

Doesn't that discriminate against people in wheelchairs?

Lost User

Khaaaaaaaan!

The language is JavaScript. that of Mordor, which I will not utter here
I hold an A-7 computer expert classification, Commodore. I'm well acquainted with Dr. Daystrom's theories and discoveries. The basic design of all our ship's computers are JavaScript.

Nagy Vilmos

He will be first down in the fourth time around...

speramus in juniperus

Abhinav S

Delving a little deeper... 1,3,5,7....99 1,5,9,13......97 1,9,17,25,33,41,49,57,65,73,81,89,97 9,25,41,57,73,89 9,41,73, 9,73 73 73 survives!

Apps - Color Analyzer | Arctic | XKCD | Sound Meter | Speed Dial

Nagy Vilmos

You're in the right area [not]. If it was 100, then 73 would survive but there were 1,000. [clue] For smaller cases:

Prisoners 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Survivor 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 3 5 7 9

There is a formula here... [fixed]

speramus in juniperus

OriginalGriff

"...to the last I grapple with thee; from hell's heart I stab at thee; for hate's sake I spit my last breath at thee." Don't think Ahab was too happy really... :laugh:

Richard Deeming

http://khanaas.com/kirk/vilmos/[^] :-D

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

Richard Deeming

Are you sure your clue is right? For example, with 14 prisoners, how can #15 be the survivor? :confused:

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

Nagy Vilmos

I'll see you and raise![^]

speramus in juniperus

Lost User

Pete O'Hanlon wrote:

Doesn't that discriminate against people in wheelchairs?

Not more than your average daily scrum :)

Bastard Programmer from Hell :suss: If you can't read my code, try converting it here[^]

Nagy Vilmos

Small mistyping, I fix...

speramus in juniperus

Richard Deeming

Brain's not working properly today - I can see the pattern, but I can't see the formula. Is the answer #977?

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

Nagy Vilmos

Well done! For the number of prisoners P find N, the highest power of 2 less than or equal to P. The survivor S, is: S = (P-N) * 2 + 1

speramus in juniperus

Richard Deeming

Ah! That's what I did. I was expecting a more mathematical formula than that. :)

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

ednrg

This is nasty and sloppy, but it figures it out to be 505. Where did I got wrong (other than write some horrific code :laugh: )?

class Program
{
    static List captures = new List();

    static void Main(string\[\] args)
    {
        PopulateCaptures();
        int survivor = FindLastOne();

        Console.WriteLine("The last one is: {0}", survivor);

        Console.Write("\\n\\nHit any key to continue...");
        Console.ReadKey();
    }

    static void PopulateCaptures()
    {
        for (int i = 1; i <= 1000; i++)
            captures.Add(i);
    }

    static int FindLastOne(int startingPosition = 0)
    {
        int retVal = -1;

        List dead = new List();

        if (captures.Count == 1)
        {
            retVal = captures\[0\];
            return retVal;
        }

        if (startingPosition == 0)
            startingPosition = 2;

        if (startingPosition == 1)
            captures.RemoveAt(0);

        for (int i = 1; i <= captures.Count; i++)
        {
            if (i % 2 == 0)
            {
                dead.Add(captures\[i - 1\]);
            }
        }

        foreach (int i in dead)
        {
            captures.Remove(i);
        }

        if (captures.Count % 2 != 0)
            startingPosition = 1;

        if (captures.Count == 1)
            retVal = captures\[0\];
        else
            retVal = FindLastOne(startingPosition);

        return retVal;
    }
}

Richard Deeming

Try this:

int index = 1;
var prisoners = Enumerable.Range(1, 1000).ToList();
while (prisoners.Count != 1)
{
while (index < prisoners.Count)
{
prisoners.RemoveAt(index);

    // We've killed a prisoner, so the rest of the list has moved up one place.
    // Therefore, we only need to move to the next place to skip the next prisoner.
    index++;
}

if (index == prisoners.Count + 1)
{
    // We killed the last one in the list; start the next round with the second in the list:
    index = 1;
}
else
{
    // We killed the second to last; start the next round with the first:
    index = 0;
}

}

Console.WriteLine(prisoners[0]);

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer