prisoners_without_coin_flip.py

'''
Code to solve the puzzle [Circular Prison of Unknown Size](https://puzzling.stackexchange.com/questions/16168/the-circular-prison-of-unknown-size)
'''

import random
import logging
from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

def powerset_without_empty_or_full(iterable):
    iterable = list(iterable)
    return [x for x in powerset(iterable) if len(x) > 0 and len(x) < len(iterable)]

log = logging.getLogger(__name__)

MAX_NUM_PRISONERS = 12
NUM_PRISONERS = random.randrange(2, MAX_NUM_PRISONERS + 1)

def main():
    print(f'Number of prisoners: {NUM_PRISONERS}')
    prisoners = [Prisoner(i == 0) for i in range(NUM_PRISONERS)]

    switches = [False for _ in range(NUM_PRISONERS)]
    lights = {p: False for p in prisoners}

    while True:
        try:
            switches = [p.choice(lights[p]) for p in prisoners]
        except Answer as e:
            result = 'correct' if e.num == NUM_PRISONERS else 'incorrect'
            print(f'Prisoner answered: {e.num} ({result})')
            break

        log.debug(f'switches: {switches}')

        room_lights = switches[1:] + switches[:1]
        lights = {p: room_lights[i] for (i, p) in enumerate(prisoners)}

        random.shuffle(prisoners)

class Answer(Exception):

    def __init__(self, num):
        self.num = num

class Prisoner(object):

    def __init__(self, master):
        self.master = master
        self.choice_generator_instance = self.choice_generator()

    def choice(self, light):
        self.light = light
        return next(self.choice_generator_instance)

    def choice_generator(self):

        def test_fill(active, iterations):
            for _ in range(iterations):
                yield active
                active = active or self.light
            for _ in range(2 ** iterations):
                yield active
                active = active and self.light
            self.fill_result = active

        # Determine an upper bound on the number of prisoners
        i = 1
        while True:
            log.debug(f'upper bound iteration: {i}')
            active = self.master
            yield from test_fill(active, i)
            if self.fill_result:
                break
            i += 1
        upper_bound = 2 ** i

        # Check if number of prisoners meeting a condition is nonzero
        def fill(active):
            for _ in range(upper_bound):
                yield active
                active = active or self.light
            for _ in range(upper_bound):
                yield active
                active = active and self.light
            self.fill_result = active
            log.debug(f'fill result: {self.fill_result}')

        # Assign the prisoners specific groups
        num_groups = 2
        my_group = 0 if self.master else 1

        done = False

        while not done:
            done = True
            for subset in powerset_without_empty_or_full(range(num_groups)):
                yield my_group in subset
                received_subset_light = self.light
                for j in range(num_groups):
                    yield from fill(my_group == j and received_subset_light)
                    intersection = self.fill_result

                    yield from fill(my_group == j and not received_subset_light)
                    difference = self.fill_result

                    if intersection and difference:
                        if my_group == j and not received_subset_light:
                            my_group = num_groups
                            log.warning(f'new group created; this prisoner now member of group {my_group}')
                        num_groups += 1
                        done = False

        raise Answer(num_groups)

if __name__ == '__main__':
    logging.basicConfig(level=logging.WARNING)
    main()