[Tutor] problem with circular list

[Jesse F. W]

Dear Tim, and all of you large snake fanciers,
	I doubt if this will be much help to you, but after reading your 
message, the problem seemed so interesting to me that I hacked up 
a version of it myself.  It seems to work.  It uses linked lists, as I 
think you have to, though I am not sure why. ;-)
	If anyone wants to see it, I will post it.
					Thank you all for your time,
						Jesse W
Tim Condit wrote:
> 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.
> 
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>