[Tutor] problem with circular list

[Tim Condit]

Greetings, 

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.
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])
    print "last man standing: %d" % (Plist[0] + 1)

(this is pseudocode, but it's amazing to me how much easier it is to
write it this way than to try and describe it in plain English!)


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:
            # increment this before taking len(Plist) from it
            pos = pos + S

            # need two things: len(Plist) (easy) and index of current
            # position of pos with respect to len(Plist) (not so easy)
            # then pos = (S + len(Plist)) - pos
            pos = pos - len(Plist)
            print "(except) pos: %d, Plist: %s" % (pos, Plist)

            #try:
            #   pos_index = operator.indexOf(Plist, pos)
            #except TypeError:
            #   print "funky error"

            print "(except) removing prisoner %d" % (Plist[pos])
            Plist.remove(Plist[pos])
            #pos = pos + S
    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.


Thanks in advance,

-- 
Tim Condit                        Detroit NCC
800-414-5028                      Global Crossing

The plan was simple.  Unfortunately, so was Bullwinkle.