Beheading of knights, who survives?

Question

We have a round table of n knights, where n is some positive integer. These have failed to satisfy the expectations of the mad king and are sentenced to death. However as an act of mercy he goes around the table killing every other knight (starting with the second) until only one knight remains.

The question is: which seat do you need to pick to survive?

I wrote the primitive code below to tackle this problem:

while True:
    temp_num = input("Enter the number of knights: ")
    try:
        temp_num = int(temp_num)
        if temp_num <= 0:  # if not a positive int print message and ask for input again
            print("Sorry, the number of knights must be a positive integer, try again")
        else:
            knights_num = temp_num
            break
    except ValueError:
        print("That's not an integer!")     
# else all is good, val is >=  0 and an integer

# Create a table of knights and a temp table
knights_table = [i for i in range(1,knights_num+1)]
knights_temp_table = list(knights_table)

i = 1
while len(knights_temp_table)>1:
# print("Knights =",knights_temp_table , "(",knights_temp_table[i],")")
    knights_temp_table.pop(i)
    i = (i+1)%len(knights_temp_table)
print( "The knight who survived was no.",knights_temp_table[0] )

The code runs fine and outputs the expected values n=60> 57 and n=16 > 1 However from the code it is not clear why it works. So i had some questions below

• Could the table of knights be made using a generator?
• Is a code using try knights_temp_table[i+1] and knights_temp_table[i+2] and then iterating over the list for the exceptions clearer?
• Could one implement a linked list to make the code clearer instead of modulo?

I know the code is very simple and the problem I solved almost trivial. However any suggestions is much appreaciated since I am a semi-begginer / novice at python. * Are there any other general suggestions to improve the code, or running speed?

Answer 1

Use a function

You can move your entire input loop into a function. Call it something reasonable:

def get_num_knights():
    while True:
        num = input("Enter the number of knights: ")
        try:
            num = int(num)
            if num <= 0:  # if not a positive int print message and ask for input again
                print("Sorry, the number of knights must be a positive integer, try again")
            else:
                return num
        except ValueError:
            print("That's not an integer!")             

That's good for two reasons: modularity is always nice, and now you don't have to worry about name collisions. Just use num internally, and return when you're done.

Two lists

This:

knights_table = [i for i in range(1,knights_num+1)]
knights_temp_table = list(knights_table)

makes two lists. The first is a list-comprehension that produces a list, the second just copies it. There's no reason for the duplication. Furthermore,

range(1, knights_num + 1)

is already a list in python2.7. In python3 it's not, but you didn't tag the version, but you use parenthetical print.

Zero-indexing

Python is zero-indexed. The first element of list lst is lst[0], not lst[1]. When you pop the first element, you need to do pop(0) not pop(1). Your pop() loop is all off by one for that reason - you're starting with the second knight instead of the first.

Improved solution

knight_table = list(range(get_num_knights()))
i = 0
while len(knight_table) > 1:
    knight_table.pop(i)
    i = (i+1) % len(knight_table)
print( "The knight who survived was no.", knights_temp_table[0]+1 )

Avoiding pop()

Now, for particularly long numbers of knights, it's possible that the pop() time could dominate your code runtime. pop() is linear-time after all - we have to shift the elements down one by one. So it's possible that the following could perform better:

num = get_num_knights()
knight_table = [True] * num
i = 0
while num > 1:
    knight_table[i % len(knight_table)] = False
    num -= 1

    living = 0
    while living < 2:
        i += 1
        living += knight_table[i % len(knight_table)]

print( "The knight who survived was no.", i % len(knight_table))

Answer 2

Those poor knights.... what did they do to deserve that?

But, there is a mathematical treat that allows this problem to be solved in O(1) time, and space.

What does that mean? Well, it means that solving the problem for 1 knight takes just as long (and just as much memory) as solving it for 10, or 1000, or 1000000000000000 knights. How is this possible?

There's a pattern that emerges when you study this problem. If there is 1 knight, then knight 1 survives. If there's 2, then knight 1 survives, and, if we map this out for say the first 32 knights, we get:

1 -> 1
2 -> 1
3 -> 3
4 -> 1
5 -> 3
6 -> 5
7 -> 7
8 -> 1
9 -> 3
10 -> 5
11 -> 7
12 -> 9
13 -> 11
14 -> 13
15 -> 15
16 -> 1
17 -> 3
18 -> 5
19 -> 7
20 -> 9
21 -> 11
22 -> 13
23 -> 15
24 -> 17
25 -> 19
26 -> 21
27 -> 23
28 -> 25
29 -> 27
30 -> 29
31 -> 31
32 -> 1

Note that, at the powers-of-2, the surviving knight skips back to knight 1. Also, between the powers, the surviving knight increments by 2 (and is always odd).

The pattern is also easy to enumerate - find the largest power of 2 that's less than (or equal to) the count. Find how many knights there are after that power, double it, and add one.

It would look like this:

import math

def low_power(input):
    return 1 << int(math.floor(math.log(input, 2)))

def survivor(count):
    return 1 + 2 * (count - low_power(count))

So, calling survivor(16) will return 1. survivor(60) returns 57.

But, you can do crazy numbers now too, like survivor(98765432123456789) is 53415676171057707

See this code running on ideone: Knights

Note that you have now confirmed you are using Python 3.4. Python 3.1 introduced the bit_length() method. This makes the determination of the power much easier (from a programming perspective - bitlength can be thought of as an implementation of the log₂):

def low_power(input):
    return 1 << (input.bit_length() - 1)

The same code running bit_length in python 3 is shown here in ideone (also contains correct parenthesis for python 3 print statements).

Answer 3

Remember, this is a round table. So if it's a round table... what better to use than a circular buffer?

from collections import deque

knights_table = deque(range(1, knights_num + 1))

Then you can emulate this much more simply:

while len(knights_table) != 1:
    knights_table.popleft()   # killed
    knights_table.rotate(-1)  # skipped

print("The knight who survived was no.", knights_table.pop())

One big advantage (other than simplicity) is, whereas pop(i) is O(i) = O(n) for lists, popleft() and rotate(-1) are O(1) for deques.

knights_num should be extracted into a function, as others mentioned. However, this code is imperfect:

def get_num_knights():
    while True:
        num = input("Enter the number of knights: ")
        try:
            num = int(num)
            if num <= 0:  # if not a positive int print message and ask for input again
                print("Sorry, the number of knights must be a positive integer, try again")
            else:
                return num
        except ValueError:
            print("That's not an integer!")    

Your try covers a lot more than wanted, which is dangerous. Restrict its coverage. Personally I'd also do if not <wanted condition> rather than if <problematic condition>, since whitelists are generally simpler and safer than blacklists. YMMV.

def get_num_knights():
    while True:
        num = input("Enter the number of knights: ")
        try:
            num = int(num)
        except ValueError:
            print("That's not an integer!")
            continue

        if not num > 0:  
            print("Sorry, the number of knights must be a positive integer, try again.")
            continue

        return num

Answer 4

I'll answer your questions then give more general advice.

1. The way you could use a generator for this would involve making a list anyway. Really, this is not a case where generator expressions are necessary anyway since the lists will be quite small and not take up a lot of space.

2. Possibly, but I think the clever solution is good and you should just explain it in comments. The try except way is messy and not entirely clear either, as you'd increment by 1 when it'd seem like you should go up in 2s to skip every other.

3. Linked lists are not commonly used in Python, so I would largely refer to answer 2 here too.

---

Now for general advice. You should avoid using temp variables when you don't need to. There's no real reason to separate temp_num and knights_num here. You may have previously needed to but your current code is airtight without it.

Also, it's good to have as few lines as possible in your try block. Sometimes to avoid errors, but also for good readability. You could use the continue keyword in your except clause and then move the other lines down below. Also I'd flip your if. If the number is valid, then you can break. Otherwise explain the number needs to be positive. This way your print doesn't need to be in an else block.

So here's how I'd rewrite this opening:

while True:
    knights_num = input("Enter the number of knights: ")
    try:
        knights_num = int(knights_num)
    except ValueError:
        print("That's not an integer!")
    if knights_num > 0:
        break
    print("Sorry, the number of knights must be a positive integer, try again")

You notice I also stripped the comment, your if condition was pretty clear without it. You might also want to prevent the user entering 1, which is theoretically valid but doesn't match the intent of the program.

Now, you have a lot of redundancy here:

knights_table = [i for i in range(1,knights_num+1)]
knights_temp_table = list(knights_table)

For a start, you could assign range to a list directly without the list comprehension. You also don't need to make a copy of knights_table, because you only ever use one of these variables later. So again, cut the temp variable.