I am very happy because I solved this problem with very little code:

"""

    100 people are standing in a circle with gun in their hands.
    1 kills 2, 3 kills 4, 5 kills 6 and so on till we are
    left with only one person. Who will be the last person alive?
    Write code to implement this ##efficiently.## <-[ Python is not efficient]

"""

persons = list(range(1,101)) # The question asks 1-indexing

while len(persons) > 1:
    for index, person in enumerate(persons):
        del persons[(index + 1) % len(persons)]

print(persons)
up vote 73 down vote accepted
+50

1. Encapsulate

Writing code at the top level of a module makes it hard to test the code and hard to measure its performance. It's best to encapsulate code in a function. Accordingly, I'd write:

def survivor(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        for index, _ in enumerate(persons):
            del persons[(index + 1) % len(persons)]
    return persons[0]

(The variable person is not used in the body of the for loop; it's convential to write _ for such variables, and that's what I've done here.)

2. The meaning of efficiency

Is this code "efficient" as the question asks? Normally in computing we use "efficient" to mean algorithmic efficiency: that is, the rate at which the resources used by the program grow as a function of the input, usually expressed in big-O notation.

The question says, "Python is not efficient", but according to the usual view of efficiency, the programming language does not matter: efficiency is a property of the algorithm, not of the language it's implemented in.

3. It's accidentally quadratic

What's the runtime of the survivor function, expressed as a function of \$ n \$? Well, looking at the time complexity page on the Python Wiki, we can see that the del operation on a list takes \$ O(n) \$ where \$ n \$ is the length of the list, and this is executed once for each person who is killed, resulting in an overall runtime of \$ O(n^2) \$.

It's possible to check this experimentally:

>>> t = 1
>>> for i in range(8, 17):
...     t, u = timeit(lambda:survivor(2**i), number=1), t
...     print('{:6d} {:.6f} {:.2f}'.format(2**i, t, t / u))
... 
   256 0.000138 0.00
   512 0.000318 2.31
  1024 0.000560 1.76
  2048 0.001363 2.43
  4096 0.006631 4.87
  8192 0.030330 4.57
 16384 0.132857 4.38
 32768 0.534205 4.02
 65536 2.134860 4.00

You can see that for each doubling of n, the runtime increases by roughly four times, which is what we expect for an \$ O(n^2) \$ algorithm.

Log-log plot of n against runtime in seconds

4. Making it linear

How can we speed this up? Well, we could avoid the expensive del operation by making a list of the survivors, instead of deleting the deceased. Consider a single trip around the circular firing squad. If there are an even number of people remaining, then the people with indexes 0, 2, 4, and so on, survive. But if there are an odd number of people remaining, then the last survivor shoots the person with index 0, so the survivors are the people with indexes 2, 4, and so on. Putting this into code form:

def survivor2(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
    return persons[0]

(You could shorten this, if you liked, using an expression like persons[(len(persons) % 2) * 2::2], but I don't think the small reduction in code length is worth the loss of clarity.)

Let's check that this is correct, by comparing the results with the original implementation:

>>> all(survivor(i) == survivor2(i) for i in range(1, 1000))
True

Notice how useful it is for testing that we have the code organized into functions.

Now, what's the runtime of survivor2? Again, looking at the time complexity page on the Python Wiki, we can see that the "get slice" operation takes time \$ O(k) \$ where \$ k \$ is the number of items in the slice. In this case each slice is half the length of persons, so the runtime is $$ O\left({n \over 2}\right) + O\left({n \over 4}\right) + O\left({n \over 8}\right) + \dots $$ which is \$ O(n) \$. Again, we can check that experimentally:

>>> t = 1
>>> for i in range(8, 25):
...     t, u = timeit(lambda:survivor2(2**i), number=1), t
...     print('{:8d} {:8.6f} {:.2f}'.format(2**i, t, t / u))
... 
     256 0.000034 0.00
     512 0.000048 1.40
    1024 0.000087 1.79
    2048 0.000142 1.63
    4096 0.000300 2.12
    8192 0.000573 1.91
   16384 0.001227 2.14
   32768 0.002628 2.14
   65536 0.006003 2.28
  131072 0.017954 2.99
  262144 0.043873 2.44
  524288 0.094669 2.16
 1048576 0.180889 1.91
 2097152 0.364302 2.01
 4194304 0.743028 2.04
 8388608 1.497255 2.02
16777216 3.094121 2.07

Now, for each doubling of n, the runtime increases by roughly two times, which is what we expect for an \$ O(n) \$ algorithm.

Log-log plot of n against runtime in seconds

5. Making it polylogarithmic

Can we do even better than this? Let's look at who the survivors actually are after each trip around the firing squad:

from pprint import pprint

def survivors(n):
    """Print survivors after each round of circular firing squad with n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
        pprint(persons, compact=True)

>>> survivors(100)
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41,
 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81,
 83, 85, 87, 89, 91, 93, 95, 97, 99]
[1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77,
 81, 85, 89, 93, 97]
[9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97]
[9, 25, 41, 57, 73, 89]
[9, 41, 73]
[73]

After each round, the gap between the survivors doubles. So after one round, the survivors are every 2nd person; after two rounds, every 4th person, after three rounds, every 8th person, and so on. When there are an even number of people, the first person remains the first survivor in the next round. But when there are an odd number of people, the third person becomes the first survivor in the next round.

So to solve this problem, we don't need to remember all the survivors, we only need to remember the first survivor, the gap between survivors, and the total number of survivors. Like this:

def survivor3(n):
    """Return the survivor of a circular firing squad of n people."""
    first = 1
    gap = 1
    while n > 1:
        gap *= 2
        n, odd = divmod(n, 2)
        if odd:
            first += gap
    return first

Once again, we should check that this is correct:

>>> all(survivor(i) == survivor3(i) for i in range(1, 1000))
True

How fast is this? Here, each time round the loop we just have some arithmetic operations on numbers of size no more than \$ n \$, taking \$ O(\log n) \$, and each time around the loop we divide the number of survivors by two, so the loop executes \$ O(\log n) \$ times, for an overall runtime of \$ O((\log n)^2) \$.

>>> t = 0
>>> for i in range(8, 60, 4):
...     t, u = timeit(lambda:survivor3(2**i), number=1), t
...     print('{:20d} {:8.6f} {:.6f}'.format(2**i, t, t - u))
... 
                 256 0.000014 0.000014
                4096 0.000012 -0.000001
               65536 0.000013 0.000001
             1048576 0.000015 0.000002
            16777216 0.000016 0.000002
           268435456 0.000018 0.000002
          4294967296 0.000022 0.000003
         68719476736 0.000030 0.000008
       1099511627776 0.000026 -0.000003
      17592186044416 0.000027 0.000001
     281474976710656 0.000031 0.000003
    4503599627370496 0.000032 0.000001
   72057594037927936 0.000035 0.000003

You can see that for each increase of n by a factor of 16, the runtime increases by a roughly constant amount, which is what we expect for a polylogarithmic algorithm.

Semi-log plot of n against runtime in seconds

Notice that the graph shows the runtime scaling roughly proportionally to \$ \log n \$ and not to \$ (\log n)^2 \$. That's because the values of \$ n \$ are small (less than \$ 2^{64} \$) and so in this range the arithmetic operations are effectively \$ O(1) \$. We'd have to use much larger values of \$ n \$ to show the asymptotic behaviour.

6. Further reading

This problem is (a simple case of) the well-known Josephus problem.

  • Beautiful answer, it was amusing to see the further optimization process but you forgot an optimization: if float.is_integer(log_2(len(survivors))): return survivors[0], you can test it with [survivor(2**i) for i in range(1,10)] – Caridorc Apr 6 '15 at 18:48
  • 8
    That doesn't improve the algorithmic efficiency: it's O(log n) to determine if n is a power of 2, so the test costs as much as it saves. – Gareth Rees Apr 6 '15 at 19:03
  • 11
    This is a terrific answer. I've learned quite a bit about algorithm analysis from this post. Thank you! – dotancohen Apr 6 '15 at 19:16
  • 8
    @raylu "looking" for a faster algorithm is certainly not "premature optimization". It's your job as a programmer when faced with a problem to evaluate potential solutions, and looking for algorithms better than the naive one are part of that process. Maybe they won't get implemented because they are too complex/time consuming to write for the benefit they would reap, that doesn't invalidate the process of looking for something better (especially in this simple case). I wish people would stop equating "premature optimization" with "begin by writing the slowest code you can think of". – Thomas Apr 7 '15 at 2:49
  • 1
    @Thomas I hardly said to begin with the slowest code you can think of. But "always looking" is certainly going to lead to many premature optimizations. Spending time thinking of better algorithms than the first thing that pops into your mind (which may or may not be the naive one) is often a waste of time if the code is going to run in basically no time and/or its performance is irrelevant. – raylu Apr 8 '15 at 21:31

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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