A solution to the 100 prisoners problem. Directions for trying out your own strategy are included.

prisoners.py

#!/usr/bin/python

# For more information: http://www.cut-the-knot.org/Probability/LightBulbs.shtml

# To implement your own strategy, simply implement a Prisoner
# class which has a single method visit_room() which returns boolean
# according to the answer provided to the warden.

# Global variables n (number of prisoners for simulation) and
# lightbulb (the lightbulb where True is on and False is off)
# are provided for you. You may only change lightbulb, and may
# only do so within visit_room().

import random

class Warden:
    def __init__(self):
        global n

        self.seen = [False]*n

    def choose(self, prisoners):
        global n

        k = random.randint(0, n - 1)
        self.seen[k] = True
        return prisoners[k].visit_room()

    def decide(self):
        return reduce(lambda x, y: x and y, self.seen, True)

class Prisoner:
    leader_chosen = False

    def __init__(self):
        global n

        if (not Prisoner.leader_chosen):
            self.leader = True
            self.count = n - 1
            Prisoner.leader_chosen = True
        else:
            self.leader = False
            self.lightbulb_flipped = False

    def visit_room(self):
        global lightbulb

        if (self.leader):
            if (lightbulb):
                lightbulb = False
                self.count -= 1

                if (self.count == 0):
                    return True
        else:
            if (not lightbulb and not self.lightbulb_flipped):
                lightbulb = True
                self.lightbulb_flipped = True

        return False

def simulate(num_prisoners):
    global n
    global lightbulb

    n = num_prisoners
    lightbulb = False

    warden = Warden()
    prisoners = [Prisoner() for x in range(n)]

    while (not warden.choose(prisoners)):
        pass

    return warden.decide()

if __name__ == "__main__":
    if (simulate(100)):
        print "Prisoners Win!"
    else:
        print "Warden Wins!"