monkey ZNO simulation

README.md

Results:

Cumulative distribution method (2019, by Taras Pavlov): 0.08891278153876137                                                                                                                                          
Simulation method (2019): 0.09003                                                                                                                                                                                    
Total simulation method (2019): 0.09858                                                                                                                                                                              
Total simulation method (2020): 0.04539                                                                                                                                                                              

zno.py

#!/usr/bin/env python3.8

import math
import random

# MC = MultiChoice questions
#  MC_variants - number of variants in a MC question, usually 5
# CC = Connection choice questions
#  CC_left = num choices in left column
#  CC_right = num choices in right column (to match left column)
# num_MC - count of MC questions
# num_CC - count of connection choice questions
# 
# passing_result - minimum score to pass ZNO. Each correct MC or CC connection adds 1 to score
# 
# num_people - how many monkeys play ZNO game

class ZNO:
    def __init__(self):
        # defaults
        self.MC_variants = 5
        self.CC_left = 3
        self.CC_right = 5
        self.num_MC = 20
        self.num_CC = 4
        
        self.passing_result = 11

        self.num_people = 100000

    def cumulative_distribution_method(self):
        if self.num_CC > 0:
            raise Exception("Cumulative distribution is not applicable!")
        
        p = 1 / self.MC_variants
        
        # https://en.wikipedia.org/wiki/Binomial_distribution#Cumulative_distribution_function
        return 1 - sum([ 
            math.comb(self.num_MC, i) * p**i * (1-p)**(self.num_MC - i)
            for i in range(0, self.passing_result)
        ])

    # Should be equal to cumulative distribution method
    def MC_simulation_method(self):
        if self.num_CC > 0:
            raise Exception("Cumulative distribution is not applicable!")
        
        p = 1 / self.MC_variants
        
        monkeys_passed = 0
        for monkey in range(self.num_people):
            score = 0
            for q in range(self.num_MC):
                score += 1 if random.random() <= p else 0
            if score >= self.passing_result:
                monkeys_passed += 1
        return monkeys_passed/self.num_people

    def MC_CC_simulation_method(self):
        monkeys_passed = 0
        for monkey in range(self.num_people):
            score = 0
            
            # MC questions
            p = 1 / self.MC_variants
            for q in range(self.num_MC):
                score += 1 if random.random() <= p else 0

            # CC questions
            cc_guessed = 0
            for q in range(self.num_CC):
                # generate pairs
                tests_pool = list(range(self.CC_right))
                test_pairs = [ 
                    tests_pool.pop(random.randrange(0, len(tests_pool)))
                    for test in range(self.CC_left) 
                ]
                guess_pool = list(range(self.CC_right))
                guess_pairs = [ 
                    guess_pool.pop(random.randrange(0, len(guess_pool)))
                    for test in range(self.CC_left) 
                ]
                guessed_CC = sum([
                    1 if correct == guess else 0
                    for correct, guess in zip(test_pairs, guess_pairs)
                ])
                score += guessed_CC
                cc_guessed += guessed_CC
                
            if score >= self.passing_result:
                monkeys_passed += 1
        return monkeys_passed/self.num_people

zno2019_taras = ZNO()
zno2019_taras.num_CC = 0
zno2019_taras.num_MC = 36

print('Cumulative distribution method (2019, by Taras Pavlov):', zno2019_taras.cumulative_distribution_method())
print('Simulation method (2019):', zno2019_taras.MC_simulation_method())

zno2019 = ZNO()
zno2019.CC_left = 4
print('Total simulation method (2019):', zno2019.MC_CC_simulation_method())

zno2020 = ZNO()
print('Total simulation method (2020):', zno2020.MC_CC_simulation_method())