Circular logic killing test - PHP

[z3r0aCc3Ss]

I have this crazy test. The question is:
There are 100 people standing circular, from 1 to 100.
Person 1 has a sword. The logic is:
1st person will kill 2nd person and will hand over the sword to 3rd person. And this continues. When the sword comes to 97th person, he'll kill the 98th person and will handover the sword to 99th person.

He in-turn will kill 1st person and handover the sword to 3rd person. 3rd person will kill the 5th person, and will handover the sword to 7th person, and this continues.

I want to find out who will survive the last. I want to build this entire logic in PHP loops...

Any help will be highly appreciated.

[lilrofl]

So this is known as the Josephus problem, which should give you all the help you need to solve it.

The problem as stated however is incorrect: the 99th person kills the 100th person and passes the sword back to the 1st person, or simply put; on the first iteration all even persons are killed.

there are a few ways to solve the problem, many involve only one FOR or WHILE loop and an index;

ie:
for circle size of N where every Xth dude is killed the logic can be something like

Code: Select all

index = 0
for dude in range(1, N+1)
    index = (index + X) mod 1
    return index

You could of course write a function to populate a list with numbers 1-100, and then use the above logic to turn all elements who are killed to 0's; afterwards removing all elements in the list that are 0 and repeating. In this way you would be preforming the logic in a human readable, albeit more complex, way.

Code examples:
http://rosettacode.org/wiki/Josephus_problem

Logic behind the problem:
http://en.wikipedia.org/wiki/Josephus_problem

[bad_brain]

I have to read this again tomorrow....my head is spinning...

[z3r0aCc3Ss]

Yeah... it's called as Josephus problem. I got the solution online. But it doesn't satisfy me.
Something using nested loops will be more brain storming.

Code: Select all

function josephus($n, $k)
{
  if ($n == 1)
    return 1;
  else
    return (josephus($n - 1, $k) + $k-1) % $n + 1;
}
 
$n = 10;
$k = 2;
echo josephus($n, $k);