PHP Pirate Challenge - The Survivor

[AceInfinity]

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, which man will be left alive?

This is an interesting exercise, I had fun with it, creating a loop version and a recursive version. The loop version removed the person who was killed immediately, while the recursive one iterated through all the survivors and determined which were to be killed, and did it at once per recursive call.

I had fun, and it took a little bit of thinking to accomplish. I had a nice little bug that took me a while to figure out. The reason was that I didn't break down the rules first, which would become the comments of the code. I just jumped in and it taught me a lesson: Even a seemingly simple application can be complicated if you don't follow the proper steps.

I will post the code for both versions in a follow-up, but I figured I would give everyone here a chance at it first.

The big key is that he has them stand in a circle, and keeps going until there is only one person left.

I seen this posted on someone's article space on another site. So I took a swing at it... Turned out to be pretty easy lol. Here was my C++11 solution:

Read More:

[NO-PARSE]#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	std::vector<int> v(1000);
	std::iota(v.begin(), v.end(), 1);
	std::rotate(v.begin(), v.begin() + 1, v.end());
	do
	{
		v.erase(v.begin());
		std::rotate(v.begin(), v.begin() + 1, v.end());
	} while (v.size() > 1);
	std::cout << v.front() << std::endl;
}[/NO-PARSE]

I'd suggest others try it on their own first before seeing the solution I came up with.

:thumbsup2:

 

[Laxer]

In python:

Read More:

captives = list(range(1,1000+1))
swordLoc = 1
while len(captives) != 1:
	captives.pop(swordLoc)
	swordLoc = (swordLoc+1)%len(captives)
print(captives[0])

Trivial algorithm could be easily written in any language... Python was most convenient because I don't have to compile it :lolg:

 

[AceInfinity]

It's even more fun when the rotations are consistent with a value > 1 because to get down to 1 element, you may have to do multiple rotations as the total elements get sufficiently smaller. Python makes it too easy for an increased difficulty though with range checking.

 

[Laxer]

Never said I had to take the hard route... The algorithm at it's core is very very simple as all you do is step from the first element 2,3,4...n mod the length of the list to give you the loop and remove(pop) whatever is at that index.

On a related note, looks like next term I will be programming using Haskell! Haven't touched that language in 6 years :roll eyes (sarcasti

 

[AceInfinity]

Haskell and J are amazing: J & Haskell Programming (I enjoy them both)

I also came up with a more efficient method:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int d = 0;
    const int k = 2;
    const int max_n = 1000;
    std::vector<int> v(max_n);
    std::iota(v.begin(), v.end(), 1);

    auto it = v.begin() + 1;
    while (v.size() > 1)
    {
        d = std::distance(it, v.end());
        v.erase(it);
        if (d > k) std::advance(it, k - 1);
        else it = v.begin() + k - d;
    }
    std::cout << " -> " << v.front();
    std::endl(std::cout);
}

I just used the earlier method because it was available, it was there for use, but this is better for a few reasons.