[Tutor] problem with circular list

[Danny Yoo]

On Sun, 22 Jul 2001, Tim Condit wrote:

> I found this problem and thought it would be fun, but it's got me
> stumped.  The full text is at
> http://www.karrels.org/Ed/ACM/weur94p/prob_b.html .  To sum it up, there
> is a king, an executioner, and a variable number of condemned prisoners.

Ah, the Josephus problem!


> Every year at the games, the prisoners are lined up, and starting at the
> first prisoner, the executioner counts off syllables of a song or
> nursery rhyme from his youth (enie, menie, miney, moe... ) and executes
> the prisoner he stops on.  The same nursery rhyme is used for the whole
> "game".  The last prisoner is set free.  I looked around, and found some
> info about circular linked lists in C, but they are built using
> pointers.  So I devised my own routine, which doesn't work. :)
> 
> I figured for P number of prisoners, and S number of syllables,
> something like this would work:
> 
> def prisoner(P, S)
> 	Plist = range(P)
> 		pos = S			# current position of syllable count
> 	while len(Plist > 1):
> 		try:
> 			Plist.remove(prisoner referred to by pos)
> 		except:
> 			dist_to_end = len(Plist) - (index of pos) 
> 			pos = S - dist_to_end		# wrap to front of line
> 			Plist.remove(Plist[pos])

The only thing that might be missing is the moving of your pos; otherwise,
you'll alwasy be removing the Sth person.  Something like:

    pos = pos + S

should be part of your pseudocode.

If S = 2, for example, we want to make sure that we'll be eliminating the
"even" numbered people first.




> There are a few things that this does not address at all, like dealing
> with S larger than P, but I'll get to that.  This is what I have so far:
> 
> def prisoner(P, S):
>     import operator
> 
>     S = S - 1
>     Plist = range(P)
>     pos = S
>     while len(Plist) > 1:
>         try:
>             print "(try) removing prisoner %d" % (Plist[pos])
>             Plist.remove(Plist[pos])
>             pos = pos + S
>         except IndexError:

Side note: you can avoid depending on IndexError altogether by using the
"modulo" operator '%'.  The modulo operator is traditionally used for
things that "wrap around":

###
>>> for i in range(10):
...     print i % 3
...
0
1
2
0
1
2
0
1
2
0
###


Anyway, let's look again at your code:

>     while len(Plist) > 1:
>         try:
>             print "(try) removing prisoner %d" % (Plist[pos])
>             Plist.remove(Plist[pos])
>             pos = pos + S
>         except IndexError:
>             pos = pos + S
>             pos = pos - len(Plist)
>             Plist.remove(Plist[pos])
>     print "last man standing: %d" % (Plist[0] + 1)
> 
> 
> The problem I'm having is that pos is a number, but it needs to a
> location, if that makes sense.  The first time through, until pos
> exceeds len(Plist), it *appears* to work correctly, even though it's
> not.  After that, it bombs out.

You don't want to use remove(): it removes items from a list based on
an element's value, not position:


###
Help on built-in function remove:
 
remove(...)
    L.remove(value) -- remove first occurrence of value
###


What you'll want to use, instead, is the deleting operator, 'del':

###
>>> mylist = range(10)
>>> del mylist[0]
>>> mylist
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> del mylist[1]
>>> mylist
[1, 3, 4, 5, 6, 7, 8, 9]
###

del would be a more appropriate way to... execute the deletion.


Hope this helps!