bgm.py

import random
from statistics import mean


class Passed(Exception):
    pass

class Quiz():
    def __init__(self, solutions=None, debug=False):
        self.attempt_count = 0
        if solutions:
            self.solutions = solutions
        else:
            self.solutions = [random.choice([1,2,3,4]) for i in range(10)]
        self.debug = debug

    def submit(self, answers):
        self.attempt_count += 1
        score = 0
        for i in range(10):
            if answers[i] == self.solutions[i]:
                score += 1
        if self.debug:
            print(f'Attempt #{self.attempt_count:02d}:', answers, f'Score: {score:02d}', f'(Solutions: {self.solutions})')
        if score == 10:
            raise Passed(self.attempt_count)
        return score

def strategy(quiz):
    known = [0] * 10
    try:
        count = {}
        count[1] = quiz.submit([1] * 10)
        count[2] = quiz.submit([2] * 10)
        count[3] = quiz.submit([3] * 10)
        count[4] = 10 - count[1] - count[2] - count[3]
        if count[4] == 10:
            answers = [i if i != 0 else 4 for i in known]
            score = quiz.submit(answers)

        max1, max2, min1, min2 = sorted(count, key=lambda x: count[x], reverse=True)

        for i in range(9):
            answers = [i if i != 0 else max1 for i in known]
            known_count = 10 - known.count(0)
            answers[i] = max2
            score = quiz.submit(answers)
            if score - (known_count + count[max1]) == 1:
                known[i] = max2
                assert count[max2] > 0
                count[max2] -= 1
            elif score - (known_count + count[max1]) == -1:
                known[i] = max1
                assert count[max1] > 0
                count[max1] -= 1
            if count[max1] == 0 and count[max2] == 0:
                break
        else:
            if count[max1] == 1:
                known[9] = max1
            else:
                assert count[max2] == 1
                known[9] = max2
        if quiz.debug:
            cd_attempt = quiz.attempt_count - 3
            print(f'Tried {cd_attempt} times to find all max1/max2 answers.')

        if count[min1] == known.count(0):
            answers = [i if i != 0 else min1 for i in known]
            score = quiz.submit(answers)

        if count[min2] == known.count(0):
            answers = [i if i != 0 else min2 for i in known]
            score = quiz.submit(answers)

        for i in [i for i in range(10) if known[i] == 0]:
            answers = [i if i != 0 else min1 for i in known]
            answers[i] = min2
            known_count = 10 - known.count(0)
            score = quiz.submit(answers)
            if score - (known_count + count[min1]) == 1:
                known[i] = min2
            elif score - (known_count + count[min1]) == -1:
                known[i] = min1
                count[min1] -= 1
            else:
                raise Exception
        raise Exception
    except Passed as e:
        return e.args[0]

def main():
    import itertools
    attempt_count = []
    for seq in itertools.product([1,2,3,4], repeat=10):
        quiz = Quiz(list(seq))
        result = strategy(quiz)
        if result > 0:
            attempt_count.append(result)
    print(f'Ran {len(attempt_count)} times, average attempt count: {mean(attempt_count):.4f}; max: {max(attempt_count)}')

def test():
    quiz = Quiz([1, 1, 1, 1, 1, 1, 1, 1, 1, 2], debug=True)
    strategy(quiz)

main()