All But One Shall Die!

[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

[JMK89]

OriginalGriff wrote:

"...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."

That quote always reminds me of the Simpsons!

[OriginalGriff]

Herman Melville for me, I'm afraid!

[ednrg]

Found the error in my ways :) It now works.

   static int FindLastManStanding(int startingPosition = 2)
    {
        int retVal = -1;
        bool lastWasKilled = false;
        List dead = new List();

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

        int max = captures.Max();

        for (int i = 1; i <= captures.Count; i++)
        {
            if (i % 2 == 0)
            {
                if ( max == captures\[i - 1\])
                    lastWasKilled = true;

                dead.Add(captures\[i - 1\]);
            }
        }

        dead.ForEach(x => captures.Remove(x));

        startingPosition = lastWasKilled ? 2 : 1;

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

        return retVal;
    }

[ednrg]

Is this the shortest solution?

var switcher = true;

var range = Enumerable.Range(1,1000).ToList();

while( range.Count > 1)
range = range.Where(x => (switcher = !switcher) == false).ToList();

range.Dump(); // (LinqPad)