Problem:
In a game of Scrabble™, how many distinct sets of 7 tiles are worth 46 points?
This puzzle is the third of its kind from Matt Parker's Maths Puzzles.
Problem:
In a game of Scrabble™, how many distinct sets of 7 tiles are worth 46 points?
This puzzle is the third of its kind from Matt Parker's Maths Puzzles.
from tiles import tiles | |
class Scrabble: | |
tileList = list(tiles.values()) | |
n = len(tileList) | |
def countHands(self, k, p, bags = 1): | |
""" | |
Counts the number of distinct sets of k tiles worth p points. | |
Optionally set a number of bags to take tiles from. | |
""" | |
memo = {} | |
# This is a recursive problem, and since there is massive overlap of | |
# subproblems, memoisation will be a big win. | |
def rec(k, p, t): | |
# the base case is when we can take no more tiles. | |
if k == 0: | |
# if we need no more points, perfect! The tiles we took were a good fit. | |
if p == 0: return 1 | |
# Otherwise, we took some bad tiles that were worth too much or too little. | |
else: return 0 | |
# If we have run out of tiles in the bag, or our current group is too big, | |
# or we have too many points, we also failed. | |
if t >= self.n or k < 0 or p < 0: return 0 | |
if (k, p, t) not in memo: | |
# How many tiles could we possibly take, and what are they worth? | |
count, value = self.tileList[t] | |
# If we took some of them, how many ways can we fill up the remaining points? | |
memo[k, p, t] = sum( | |
rec(k - x, p - x * value, t + 1) | |
for x in range(min(k, count * bags) + 1) | |
) | |
return memo[k, p, t] | |
return rec(k, p, 0) | |
print(Scrabble().countHands(7, 46)) # 138 |
# The value for each tile is a pair (c, v) where c is the total number of tiles | |
# of that kind in a scrabble set, and v is the point value for the tile. | |
tiles = { | |
'a': (9, 1), | |
'b': (2, 3), | |
'c': (2, 3), | |
'd': (4, 2), | |
'e': (12, 1), | |
'f': (2, 4), | |
'g': (3, 2), | |
'h': (2, 4), | |
'i': (9, 1), | |
'j': (1, 8), | |
'k': (1, 5), | |
'l': (4, 1), | |
'm': (2, 3), | |
'n': (6, 1), | |
'o': (8, 1), | |
'p': (2, 3), | |
'q': (1, 10), | |
'r': (6, 1), | |
's': (4, 1), | |
't': (6, 1), | |
'u': (4, 1), | |
'v': (2, 4), | |
'w': (2, 4), | |
'x': (1, 8), | |
'y': (2, 4), | |
'z': (1, 10), | |
'blank': (2, 0) | |
} |