grades.py

import scipy.misc as sm
import math
import random
import itertools as it
import matplotlib
import matplotlib.pyplot as pp

def combine(all, result, d=1, totalpoints = 0, totallogprob = 0):
    """
    Computes the complete probability distribution over the total points.
    Only feasible for small numbers of questions

    :param all:
    :param result:
    :param d:
    :param totalpoints:
    :param totallogprob:
    :return:
    """
    if d > max(all.keys()):
        if totalpoints not in result:
            result[totalpoints] = 0.0
        result[totalpoints] += math.exp(totallogprob)
        return

    for points, prob in all[d].items():
        totalpoints += points
        if prob <= 0.0:
            return

        totallogprob += math.log(prob)

        combine(all, result, d + 1, totalpoints, totallogprob)


def sample(all, d = 1, totalpoints = 0):
    if d > max(all.keys()):
        return totalpoints

    comb = [(points, all[d][points]) for points in all[d].keys()]

    totalpoints += weighted_choice(comb)
    return sample(all, d + 1, totalpoints)

def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = random.uniform(0, total)
   upto = 0
   for c, w in choices:
      if upto + w >= r:
         return c
      upto += w
   assert False, "Shouldn't get here"


# Each q[x] maps a number of points to the probability that a random guesser gets that many points on question x
q = {}
q[1] = {1: 0.5, 0:0.5}

q[2] = {1: 1/3.0, 0: 2/3.0}

q[3] = {}
perms = math.factorial(6) / math.factorial(3)
q[3][3] = 1.0/perms
q[3][1] = 9.0/perms
q[3][0] = 1.0 - (q[3][3] + q[3][1])

q[4] = {1:1/4.0, 0: 3/4.0}

q[5] = {1:1/3.0 * 1/2.0, 2: 5/6.0}

q[6] = {1:1/4.0, 0: 3/4.0}

q[7] = {1:1/4.0, 0: 3/4.0}

q[8] = {1:1/1000.0, 0:999/1000.0}

q[9] = {}
q[9][3] = 1/64.0
q[9][1.5] = 6/64.0
q[9][0] = (64-7)/64.0

q[10] = {}
q[10][3] = 1/64.0
q[10][1.5] = 6/64.0
q[10][0] = (64-7)/64.0

q[11] = {}

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8]

tally = {0:0.0, 1:0.0, 2:0.0, 3:0.0, 4:0.0, 5:0.0, 6:0.0}
n = 0
for l in it.permutations(lst, 6):
    match = 0
    n += 1
    for i, j in enumerate(l):
        if i == j:
            match += 1

    tally[match] += 1

for key, value in tally.items():
    q[11][key/2.0] = value / n

q[12] = {}
q[12][3] = 1/64.0
q[12][1.5] = 6/64.0
q[12][0] = (64-7)/64.0

q[13] = {}
q[13][1] = 1.0/7.0
q[13][0] = 6.0/7.0

q[14] = {}
q[14][3] = 1/32.0
q[14][2] = 3/32.0
q[14][1] = 3/32.0
q[14][0.5] = 6/32.0
q[14][0] = (64-13)/64.0

q[15] = {}
q[15][3] = 1.0/4.0
q[15][0] = 3.0/4.0

q[16] = {}
q[16][3] = 1.0/6.0
q[16][0] = 5.0/4.0

q[17] = {}
q[17][3.0] = 4.0/10000.0
q[17][2.25] = ((36 + 16) * 2)/10000.0
q[17][0.75] = ((64 * 9 + 81 * 8 * 2) * 2)/10000.0
q[17][0.0] = (9 * 8 * 8 * 9)/10000.0
q[17][1.5] = 1.0 - (q[17][0.0] + q[17][0.75] + q[17][2.25] + q[17][3.0])

q[18] = {}
q[18][3] = 1/128.0
q[18][2] = 7/128.0
q[18][1] = 21/128.0
q[18][0] = 1.0 - (q[18][1] + q[18][2] + q[18][3])

q[19] = {}
q[19][3] = 1.0/4.0
q[19][0] = 3.0/4.0

q[20] = {}
q[20][3] = 1.0/5.0
q[20][0] = 4.0/5.0

q[21] = {}
q[21][3] = 1/128.0
q[21][2] = 7/128.0
q[21][1] = 21/128.0
q[21][0] = 1.0 - (q[18][1] + q[18][2] + q[18][3])

q[22] = {1:1/20.0, 0:39/40.0}

q[23] = {}
lst = [0, 1, 2, 3, 4, 5, 6, 7]

tally = {0:0.0, 1:0.0, 2:0.0, 3:0.0, 4:0.0}
n = 0
for i in range(9):
    for l in it.combinations(lst, i):

        correct = 0;
        for v in l:
            if v >= 0 and v <= 3:
                correct += 1
            else:
                correct -= 1

        correct = max(0, correct)

        tally[correct] += 1
        n += 1

for key, value in tally.items():
    q[23][(key/4.0) * 3.0] = value / n

q[24] = {}
lst = [0, 1, 2, 3, 4, 5]

tally = {0:0.0, 1:0.0, 2:0.0, 3:0.0, 4:0.0, 5:0.0, 6:0.0}
n = 0
for l in it.permutations(lst):

    correct = 0;
    for i, j in enumerate(l):
        if i == j:
            correct += 1

    tally[correct] += 1
    n += 1.0

for key, value in tally.items():
    q[24][key] = value / n

q[25] = {6:1/25.0, 0:24/25.0}

q[26] = {}
q[26][6] = 1/64.0
q[26][3] = 2/64.0
q[26][1.5] = 12/64.0
q[26][0] = (64-15)/64.0

q[27] = {}
q[27][6] = 1/6.0
q[27][0] = 5/6.0

q[28] = {0:1.0}

q[29] = {}
q[29][6] = 1/512.0
q[29][4] = 8/512.0
q[29][2] = 31/512.0
q[29][0] = 1.0 - (q[29][6] + q[29][4] + q[29][2])

q[30] = {0:1.0}
q[31] = {0:1.0}
q[32] = {0:1.0}

print('Computed per question probabilities. Combining by sampling.')

res = []
for i in range(1000000):
    res.append(sample(q))
    if i % 100000 == 0:
        print(i)

pp.hist(res, normed=True)
pp.xlim([0, 100])
pp.title('mean points: {}'.format(sum(res)/len(res)))

pp.savefig('histogram.pdf')