Skip to content

Instantly share code, notes, and snippets.

@chrismilson
Last active April 11, 2020 01:06
Show Gist options
  • Save chrismilson/e8f4f4b9ba249ccc11c93352364bca9c to your computer and use it in GitHub Desktop.
Save chrismilson/e8f4f4b9ba249ccc11c93352364bca9c to your computer and use it in GitHub Desktop.
Matt Parker's Maths Puzzles - 3 - Scrabble

Scrabble Puzzle

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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment