self_referential_test_generator.py

"""
Generates a self-referential test. There are 18 question-statements, answer to each being 1 (truth) or 0 (false).
Answer to the whole test is thus a 18-digit binary number.
"""

import random

questions_count = 18

convergence = 0.7


class QuestionException(Exception):
    pass


class CounterQuestion:
    def __init__(self, question_id, questions_count):
        self.question_id = question_id
        self.exact = random.choice(
            [True, False]) if question_id < questions_count - 1 else True
        self.limit = random.randrange(
            0 if self.exact else 1, questions_count - question_id)
        self.answer = random.choice(["0", "1"])

    def __str__(self):
        return "The answers to the questions after this one contain {} {} occurrences of {}".format("precisely" if self.exact else "at least", self.limit, self.answer)

    def check_answers(self, answers):
        count = answers[(self.question_id+1):].count(self.answer)
        return (self.exact and count == self.limit) or (not self.exact and count >= self.limit)


class ComparisonQuestion:
    def __init__(self, question_id, questions_count):
        if question_id == 0 or question_id == questions_count - 1:
            raise QuestionException("Can't be first or last")

        self.question_id = question_id
        self.positive = random.choice([True, False])

    def __str__(self):
        return "Answer to the previous question {} the same as the answer to the following question".format("is" if self.positive else "is not")

    def check_answers(self, answers):
        return (answers[self.question_id - 1] == answers[self.question_id + 1]) == self.positive


class SubstringQuestion:
    def __init__(self, question_id, questions_count):
        self.question_id = question_id
        self.substring = "".join(random.choices(
            ["0", "1"], k=random.randrange(2, 5)))
        self.positive = random.choice([True, False])

    def __str__(self):
        return "Test answers {}contain the substring {}".format("" if self.positive else "do not ", self.substring)

    def check_answers(self, answers):
        return (self.substring in answers) == self.positive


class FirstLastQuestion:
    def __init__(self, question_id, questions_count):
        self.question_id = question_id
        self.first = random.choice([True, False])
        self.answer = random.choice(["0", "1"])

    def __str__(self):
        return "This is the {} question, to which the answer is {}".format("first" if self.first else "last", self.answer)

    def check_answers(self, answers):
        checked_range = answers[:self.question_id] if self.first else answers[(self.question_id+1):]
        return self.answer not in checked_range and answers[self.question_id] == self.answer


question_classes = [
    CounterQuestion,
    ComparisonQuestion,
    SubstringQuestion,
    FirstLastQuestion
]


def bool_to_zero_one(b):
    return "1" if b else "0"


def count_answers(questions):
    count = 0
    for i in range(2**questions_count):
        answers = bin(i)[2:].zfill(len(questions))
        if all(bool_to_zero_one(questions[i].check_answers(answers)) == answers[i] for i in range(len(questions))):
            count += 1
    return count


def get_answers(questions):
    for i in range(2**questions_count):
        answers = bin(i)[2:].zfill(len(questions))
        if all(bool_to_zero_one(questions[i].check_answers(answers)) == answers[i] for i in range(len(questions))):
            return answers
    return None


def score(questions):
    count = count_answers(questions)
    if count == 0:
        return 2**questions_count + 1
    if count == 1:
        return -answers_diversity(get_answers(questions))
    return count


def random_question(question_id, questions_count):
    while True:
        try:
            return random.choice(question_classes)(question_id, questions_count)
        except QuestionException:
            continue


def print_questions(questions, answers):
    for i in range(len(questions)):
        print("{}. {} [{}]".format(i, questions[i], answers[i]))


def answers_diversity(answers):
    return len(answers) - abs(answers.count("0") - answers.count("1"))


last_questions = [random_question(i, questions_count)
                  for i in range(questions_count)]
last_score = score(last_questions)

best_score = last_score
best_questions = last_questions

print("===")
print("SCORE: {}".format(best_score))
print_questions(best_questions, "0"*questions_count)
print("===")

while best_score > -(questions_count/2):
    new_questions = last_questions[:]
    new_question_id = random.randrange(questions_count)
    new_questions[new_question_id] = random_question(
        new_question_id, questions_count)

    new_score = score(new_questions)

    if (new_score <= last_score) == (random.random() < convergence):
        last_questions = new_questions
        last_score = new_score

        if last_score < best_score:
            best_score = last_score
            best_questions = last_questions
            print("===")
            print("SCORE: {}".format(best_score))
            print_questions(best_questions, get_answers(best_questions))
            print("===")