Python greed roll

Question

I am doing the Python Koans to practise Python a bit more and I got to the greed dice project. It is a very simple dice game that scores a set of up to five rolls.

These are the rules:

# A greed roll is scored as follows:
#
# * A set of three ones is 1000 points
#
# * A set of three numbers (other than ones) is worth 100 times the
#   number. (e.g. three fives is 500 points).
#
# * A one (that is not part of a set of three) is worth 100 points.
#
# * A five (that is not part of a set of three) is worth 50 points.
#
# * Everything else is worth 0 points.
#

Calls are made like this:

score([5])
score([1, 5, 5, 1])
score([3, 3, 3])

This is my implementation:

def score(dice):
    result = 0
    if len(dice) <= 5:
        dice_copy = sorted(dice)
        dice_dict = dict((i, dice_copy.count(i)) for i in dice_copy)
        if dice_dict.get(1) >= 3:
            result += 1000
            dice_dict[1] -= 3
        for number in dice_dict:
            if dice_dict.get(number) >= 3:
                result += number * 100
                dice_dict[number] -= 3
        if 1 in dice_dict:
            result += dice_dict[1] * 100
        if 5 in dice_dict:
            result += dice_dict[5] * 50

    return result

I am looking for:

• comments and tips on my code
• suggestions of Python-style ways of doing this
• improvement and optimizations of my code
• ideas of how to implement this in more interesting, original or interesting ways

I sorted the list before creating the dictionary because I think that would make the dictionary creation faster, but I ran some tests and found out that sorting the list actually makes the program slightly slower. I suppose my intention would only be effective in larger lists. Is my guess right?

Answer 1

The call to sorted doesn't help; .count doesn't know the dictionary is sorted and so can't utilize that fact. The call to sorted just slows things down.

One alternative is to use a loop like

dice_dict = {}
for die in dice:
    if die in dice_dict:
        dice_dict[die] += 1
    else:
        dice_dict[die] = 1

which operates in a single pass. This is encapsulated in the Counter class which does the same thing with just Counter(dice).

if dice_dict.get(1) >= 3 is undefined if there are no 1s in the input; .get will return None and None >= 3 returns an arbitrary result. You should use dice_dict.get(1, 0) >= 3, which defaults the argument to 0.

However, if using Counter every value is implicitly defaulted to 0, so you can just do dice_dict[1] >= 3.

Your next loop could also be fixed this way:

for number in dice_dict:
    if dice_dict[number] >= 3:
        result += number * 100
        dice_dict[number] -= 3

but you should just use dice_dict.items():

for number, count in dice_dict.items():
    if count >= 3:
        result += number * 100
        dice_dict[number] -= 3

You can support >= 5 items with a touch of math:

for number, count in dice_dict.items():
    result += (count // 3) * number * 100
    dice_dict[number] %= 3

// is integer division.

You can merge the first check with the second as so:

for number, count in dice_dict.items():
    value = 1000 if number == 1 else number * 100

    result += (count // 3) * value
    dice_dict[number] %= 3

Your <= 5 check can then be removed, but if you want to keep it you should throw an error instead of silently giving the wrong result.

With Counter you don't need the if x in check; they will default to 0.

This gives:

def score(dice):
    result = 0
    dice_dict = Counter(dice)

    for number, count in dice_dict.items():
        value = 1000 if number == 1 else number * 100

        result += (count // 3) * value
        dice_dict[number] %= 3

    result += dice_dict[1] * 100
    result += dice_dict[5] * 50

    return result

You can remove the mutation of dice_dict by doing modulo outside of the loop:

def score(dice):
    result = 0
    dice_dict = Counter(dice)

    for number, count in dice_dict.items():
        value = 1000 if number == 1 else number * 100
        result += (count // 3) * value

    result += (dice_dict[1] % 3) * 100
    result += (dice_dict[5] % 3) * 50

    return result

Answer 2

Is it guaranteed that the rolls are of up to 5 die? Otherwise the code doesn't work well. Also, count works without the sorting, so you could do directly

dice_dict = dict((i, dice.count(i)) for i in dice)

However, in this cases, it's just better to just go ahead and use the standard python library:

import collections
...
dice_dict = collections.Counter(dice)

Answer 3

I sorted the list before creating the dictionary because I think that would make the dictionary creation faster, but I ran some tests and found out that sorting the list actually makes the program slightly slower.

Why do you think it would be faster? Here i loops through all the items in the list, and sorting does not change the number of items. Neither is count able to skip any work, even if it called with the same argument multiple times in succession.

dict((i, dice_copy.count(i)) for i in dice_copy)

Sorting takes some time, so of course it makes the program slower.

I suppose my intention would only be effective in larger lists. Is my guess right?

With larger lists the use of count becomes a serious bottleneck, because it scans the whole list every time. Thus obtaining all the counts takes O(n²) time. Really only a single sweep through the list is necessary. collections.Counter will do it for you.

---

Note that these rules

# * A set of three ones is 1000 points
# * A one (that is not part of a set of three) is worth 100 points.

could be expressed in a slightly simpler way:

# * A one is worth 100 points.
# * A set of three ones is worth an extra 700 points 

You could follow that idea to simplify the program logic.

---

An alternative to using several if statements would be to use dictionaries to represent the scores table.

from collections import Counter

DIE_POINTS = {1: 100, 5: 50}
TRIPLET_POINTS = {1: 1000 - 3 * DIE_POINTS[1],
                  2: 200,
                  3: 300,
                  4: 400,
                  5: 500 - 3 * DIE_POINTS[5],
                  6: 600}

def score(dice):
    result = 0
    if len(dice) <= 5:
        counts = Counter(dice)
        for number, count in counts.items():
            result += count * DIE_POINTS.get(number, 0)
            if count >= 3:
                result += TRIPLET_POINTS[number]
    return result