0
\$\begingroup\$

I came across the following challenge. Here is my implementation in Python 3.7

A room has 100 chairs numbered from 1-100. On the first round of the game the FIRST individual is eliminated. On the second round, the THIRD individual is eliminated. On every successive round the number of people skipped increases by one (0, 1, 2, 3, 4...). So after the third person, the next person asked to leave is the sixth (skip 2 people - i.e: 4 and 5).

This game continues until only 1 person remains.

Which chair is left by the end?

I actually don't know what the true answer is, but my code outputs 31.

I think this is the fastest solution and at worst has an O(N^2) time complexity

n = 100
skip = 0
players = [x for x in range (1, n+1)]
pointer = 0
while len(players) > 1:
    pointer += skip
    while pointer >= len(players):
        pointer = pointer - len(players)
    players.pop(pointer)
    skip += 1
print(players[0])
\$\endgroup\$
1
\$\begingroup\$
  • The loop

    while pointer >= len(players):
        pointer = pointer - len(players)
    

    is a long way to say pointer %= len(players).

  • You'd be in a better position factoring the computations into a function,

    def survivor(n):
        skip = 0
        players = [x for x in range (1, n+1)]
        pointer = 0
        while len(players) > 1:
            pointer += skip
            while pointer >= len(players):
                pointer = pointer - len(players)
            players.pop(pointer)
            skip += 1
        return players[0]
    

    and adding an if __name__ == '__main__' clause. This way it is easy to generate first few results.


TL;DR

I did so, generated first 20 numbers,

    1 2 2 2 4 5 4 8 8 7 11 8 13 4 11 12 8 12 2

and search this sequence in OEIS.

Surprisingly there was a match. A closer inspection demonstrated that the problem is a Josephus problem with eliminating every n-th person. Try to prove, or at least convince yourself, that it is indeed the case.

Further reading revealed that there is a linear solution.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.