[Tutor] Python code trouble!

[Steven D'Aprano]

Hello John,


You are still posting from the future. Please fix your computer so that 
it is no longer set 12 hours in the future. Or perhaps your computer is 
just set in the wrong time zone.


John wrote:
> Hi all,
> 
> I have attempted to create a programme which removes every Nth person 
> from the list until there is only one name remaining. N is inputted by 
> the user.

Ah, the Josephus problem! Trickier than it seems.

http://en.wikipedia.org/wiki/Josephus_permutation


> Here is the code:
> 
> def survivor(names, step):
>     next = names

This line is pointless. It just assigns a new name to the same list. Why 
not just work directly with "names" instead of the misleading "next"? 
(Next what?)

>     while len(next) > 1:
>      index = step - 1
>      next.remove (next[index])

This does not do what you think it does, but even when it does, it 
doesn't it slowly and inefficiently.

You start of with an index. You want to delete the item at that index. 
So you start by retrieving the item at that index, then instruct the 
list to search from the beginning of the list for something which 
matches, then delete that. So consider what happens if you have a really 
huge list, with tens of thousands of items, and ask to delete the last 
one: even though you know you want to delete the last item, the remove() 
method has to check every single item first.

Worse, what if there are duplicates? The *first* duplicate found will be 
removed, instead of the one at the given index.

If you want to delete the name at an index, you should just directly 
delete the name at the index:

del names[index]


>         index = index + step - 1

This line is wrong. It means that you take one fewer step each time than 
you expect. For instance, if you take step = 4, you should step along 
indexes 3, 3+4=7, 7+4=11, 11+4=15, ... but instead you step along 
indexes 3, 3+4-1=6, 6+4-1=9, 9+4-1=12, ...


>         while index > len(next):
>             index = index - len(next)
>         if index == len(next):
>             index = 0

You can combine both of those with a single test:

     while index >= len(names):
         index = index - len(names)


>     return names[0]
> 
> 
> 
> To me is appears to be correct, however when i test it i get the 
> following message:

Obviously it isn't correct. Here's a version which is not correct either:

def eliminate(names, step):
     index = -1
     while len(names) > 1:
         print names
         index += step
         while index >= len(names):
             index -= len(names)
         del names[index]
     return names[0]

but it is simple to read. Can you see what is wrong with it? Hint: 
perform the elimination by hand, eliminating every fourth person:

Starting names: Fred Wilma Barney Betty Scooby Shaggy Daphne Fred Wilma
1st round: Fred Wilma Barney ----- Scooby Shaggy Daphne Fred Wilma
2nd round: Fred Wilma Barney ----- Scooby Shaggy Daphne ---- Wilma
3rd round: Fred Wilma ------ ----- Scooby Shaggy Daphne ---- Wilma
4th round: Fred Wilma ------ ----- Scooby Shaggy Daphne ---- -----
5th round: Fred Wilma ------ ----- Scooby ------ Daphne ---- -----
6th round: Fred Wilma ------ ----- ------ ------ Daphne ---- -----
7th round: Fred Wilma ------ ----- ------ ------ ------ ---- -----
8th round: Fred ----- ------ ----- ------ ------ ------ ---- -----

But when I use my function:

py> eliminate(['FredF', 'Wilma', 'Barney', 'Betty', 'Scooby', 'Shaggy', 
'Daphne', 'Fred', 'Wilma'], 4)
'Daphne'

I get the wrong person. Why? Watch when I do this instead:

Starting names: Fred Wilma Barney Betty Scooby Shaggy Daphne Fred Wilma
1st round: Fred Wilma Barney Scooby Shaggy Daphne Fred Wilma
2nd round: Fred Wilma Barney Scooby Shaggy Daphne Fred
3rd round: Fred Wilma Barney Scooby Daphne Fred
4th round: Fred Wilma Scooby Daphne Fred
5th round: Fred Scooby Daphne Fred
6th round: Fred Daphne Fred
7th round: Fred Daphne
8th round: Daphne

Can you see why the two processes are different? The second one is much 
easier to program, but it is completely different from what you would do 
in real life.

I told you the problem was tricker than it first appears :)




-- 
Steven