[Tutor] problem with circular list

[Bruce Sass]

Hi,

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

The way I see it...
you have a list of prisoners,
and an index which may point past the end of the list.

So, you may need to reduce the index by some multiple of the
length of the list.  e.g., something along the lines of...

    while key >= len(list):
        key = key - len(list)

Using this approach I came up with the following for the circular
list part of the problem...

---8<---
class circList:
    def __init__(self, initial=None):
        if initial == None:
            self.data = []
        else:
            self.data = initial

    def __getitem__(self, key):
        length = len(self.data)
        if length > 1:
            key = key % length
            return self.data[key]
        elif length == 1:
            return self.data[0]
        else:
            return None  # or raise an exception

if __name__ == '__main__':
    c = circList([0,1,2,3])
    for i in range(10):
        print c[i],
--->8---

Output:
0 1 2 3 0 1 2 3 0 1

[Getting it to work with negative indicies and slices, or having it
 behave more like a regular list would be interesting (but not really
 relevent to the problem)... check out the UserList module, Section
 2 of the Library Reference and Section 3 of the Language Reference
 for more info.]

To make circList a little nicer you should implement a "pop" and
the "__len__" magic method, so you can do...

---8<---
rhyme = ["enie", "menie", "miney", "moe", "out", "you", "go"]
p = circList(["Bob", "Carol", "Ted", "Alice"])
number = len(p)
length = len(rhyme)
while number != 1:
    p.pop(len)
    number = number - 1
print p[0], "gets a pardon."
--->8---

Output:
Alice gets a pardon.


- Bruce