# If desired, this code can be discussed in class prior to giving the
# assignment. Or it can be left up to the students to implement as
# part of the assignment.

import random

def weightedChoice(elements, weights):
    # verify the lists are the same length
    assert len(elements) == len(weights)
    total = sum(weights)
    r = random.uniform(0, total)
    w = 0
    for i in range(len(elements)):
        w += weights[i]
        if w > r:
            return elements[i]
    # all weights are zero if we get here, so pick at random
    return random.choice(elements)

# test program for weightedChoice
def test_wc(elements, weights, trials):
    bins = [0] * len(elements)
    for i in range(trials):
        x = weightedChoice(elements, weights)
        n = elements.index(x)
        bins[n] += 1
    for i in range(len(bins)):
        print "%s: %.1f%%" % (elements[i], 100.0*bins[i]/trials)
    print "Total: %.1f%%" % (100.0*sum(bins)/trials)

# example:
# test_wc(["a", "b", "c", "d", "e", "f"], [1.5, 2.5, 2, 3, 0, 0.1], 1000000)