def weighted_choice(rand, choices):
    """Choose from a list of [(choice, weight), ...] options, randomly."""
    total = sum(w for c, w in choices)
    r = rand.uniform(0, total)
    upto = 0
    for c, w in choices:
        if upto + w >= r:
            return c
        upto += w
    assert False, "Shouldn't get here"