dice.py

import random
from collections import defaultdict

def raw_roll(num):
    dice = [random.randint(1, 10) for _ in range(num)]

    # Extra dice for 10s
    dice += [random.randint(1, 10) for _ in range(dice.count(10))]

    # Drop the lowest
    dice.remove(min(dice))
    dice += [random.randint(1, 10)]

    return dice

def score(groups):
    def score_group(group):
        if group >= 15:
            return 2
        elif group >= 10:
            return 1
        else:
            return 0

    return sum([score_group(group) * groups[group] for group in groups.keys()])

def best_score_for(dice, groups):
    if len(dice) == 0:
        return score(groups)

    die = dice[0]

    def one_branch(group):
        if group + die > 20 or groups[group] == 0:
            return 0
        recurse_groups = groups.copy()
        recurse_groups[group] -= 1
        recurse_groups[group + die] += 1
        return best_score_for(dice[1:], recurse_groups)

    return max([one_branch(group) for group in groups.keys()])


def roll(n):
    dice = raw_roll(n)
    num_groups = 1 + sum(dice) / 10
    groups = defaultdict(lambda: 0)
    groups[0] = num_groups
    return best_score_for(dice, groups)




# SLOPPY TESTING

def make_test_groups(dic):
    g = defaultdict(lambda: 0)
    for key in dic.keys():
        g[key] = dic[key]
    return g

print len(raw_roll(1)) <= 2
print len(raw_roll(10)) >= 10
print score({10: 2, 15: 2, 18: 1, 3: 1}) == 8
print best_score_for([], make_test_groups({10: 2, 15: 2, 18: 1, 3: 1})) == 8
print best_score_for([1], make_test_groups({10: 2, 15: 2, 14: 1, 3: 1})) == 8
print best_score_for([1, 2], make_test_groups({10: 2, 14: 2, 18: 1, 3: 1})) == 8

print roll(9)