Solving the prison light switch problem

prisoner.py

import random


class Person(object):
    moved = False
    known_prisoners = 0


class Prisoner(Person):

    def move(self, left_switch, right_switch):
        if not self.moved or not left_switch:
            self.moved = True
            return False, right_switch
        else:
            return left_switch, True


class Counter(Person):

    def move(self, left_switch, right_switch):
        if not self.moved:
            self.moved = True
            return False, False
        else:
            if right_switch:
                self.known_prisoners += 1
            return True, False


prison = []
num_prisoners = 6
for i in range(num_prisoners):
    prison.append(Prisoner())
prison.append(Counter())

left_switch = random.choice(range(2))
right_switch = random.choice(range(2))
solved = False

num_moves = 0

while not solved:
    num_moves += 1
    prisoner = random.choice(prison)

    left_switch, right_switch = prisoner.move(left_switch, right_switch)
    solved = prisoner.known_prisoners == num_prisoners

    print "Prisoner %d tries the switch" % prison.index(prisoner)
    if prisoner.known_prisoners > 0:
        print " Counter knows there are %d prisoners" % prisoner.known_prisoners

print "Solved in %d moves!" % num_moves