# Beheading of knights, who survives?

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?

• Based on your code I presume you're using Python 2.7. But can you confirm it? Your code runs differently in different versions. – SuperBiasedMan Sep 14 '15 at 16:22
• You might also be interested in these Java reviews : codereview.stackexchange.com/questions/56951/… / codereview.stackexchange.com/questions/86023/… – Josay Sep 14 '15 at 16:24
• Oh I am running 3.4 what are those differences? I thought it was mainly the use of parenthesis. – N3buchadnezzar Sep 14 '15 at 20:15
• @N3buchadnezzar In Python3 range will return a generator function instead of a list directly, which is presumably why you called list(). In Python 2.x, range just returns a list directly, making that step skippable. Apart from that the only difference for you is the print function needing parentheses in 3, whereas in 2 you could leave them out (but it's not advised). – SuperBiasedMan Sep 14 '15 at 20:39
• FYI This is the centuries-old Josephus Problem – smci Sep 14 '15 at 21:57

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))

• "you're starting with the second knight instead of the first." I think that's intentional if every other knight is to be popped off. – SuperBiasedMan Sep 14 '15 at 15:57
• @Barry I disagree. every other suggests that the first is not an other – njzk2 Sep 15 '15 at 19:16

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 log2):

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).

• @holroy - yeah, I suck at code reviews where the review is basically "do it this other way" - an algorithmic review, rather than a code review. The other answers cover much of the non-algorithmic aspects also (go on, and +1 them too). – rolfl Sep 14 '15 at 17:31
• No, no a very fine answer indeed. Being a math undergrad I also came to the same conclusion. But as mentioned I wanted to sharpen my rusty skills in programming, not mathematics ^^ – N3buchadnezzar Sep 14 '15 at 20:17

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

• Python elegance at its finest – ThorSummoner Sep 22 '15 at 5:01
• Nice answer. One small nitpick for your input function. Here you assign a string to a variable called number. Which is only used as input of int. I would either give it its own name or directly move the input into the try block : num = int(input(... – magu_ Jul 1 '16 at 16:08
• @magu_ Moving the input into the try is bad practice because errors from the input call should be handled differently to errors from the int call. If you want to give it a different name when referring to a string, feel free, but I don't see the imperative to do so myself. – Veedrac Jul 1 '16 at 23:15

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.