Indiv assign 1

probB.py

import operator as op
import random
from functools import reduce
from datetime import datetime


''''
This four functions were used to find the lower bound
'''


#compute combination of n out of r
def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(op.mul, range(n, n - r, -1), 1)
    denom = reduce(op.mul, range(1, r + 1), 1)
    return numer / denom

#compute the mass function for a binomial of paramater (n,p) given K
def binomial(K, n, p):
    sumi = 0
    for i in range(K + 1):
        sumi += ncr(n, i) * (p) ** i * (1 - p) ** (n - i)
    return sumi

#Compute the the lower bound needed to solve the problem
def min_k(eps, p):
    # K is the number of times we should run the A algorithm
    K = 0
    desired_prob = 10
    while desired_prob > eps:
        #computing the discrete density function
        desired_prob = binomial(K // 2, K, p)
        print(K, desired_prob)
        print()
        K += 1
    print('end')
    print(K, desired_prob)

#We simply call the precedent function to get the lower bound
def test_binomial():
    # print(binomial(2,3,0.5))
    eps = 10 ** -6
    p = 0.75
    print(min_k(eps, p))


'''
This functions were used to verify the correctness of the algorithm
'''

def debug(tab, res):
    print('elments :', tab)
    print('most freq : ', res)
    print()
    
#return the first element that is at least prop% freq
def freq_at_least(tab, prop=0.5):
    freq = dict()
    n = len(tab)
    for e in tab:
        if e in freq:
            freq[e] += 1
        else:
            freq[e] = 1

    for element, freq in freq.items():
        if freq / n > prop:
            return element

    # if no element is at least prop frequent return anything
    return tab[0]
    

def alg_problem_B(K, right_answer, p=0.75):
    tab = [0] * K
    for i in range(K):
        #this if else simulate the behaviour of algorithm A
        if random.random() >= (1 - p):
            tab[i] = right_answer
        else:
            # This way we can have a variety of incorrect answers by adding noise
            tab[i] = right_answer + random.uniform(1, 4)

    res = freq_at_least(tab)
    return (res == right_answer)

#Running the function several time to see the accuracy of our program
def benchmark(nb_simulation=10**6):
    correct = 0
    for i in range(nb_simulation):
        random.seed(datetime.now())
        correct += 1 if alg_problem_B(23, 1) else 0

    print()
    print('correct', correct)
    print('nb simulation', nb_simulation)
    print('accuracy', (correct / nb_simulation) * 100, '%')


if __name__ == '__main__':
    right_answer = 1
    # print(alg_problem_B(23, right_answer))
    benchmark()