Matt Parker's Maths Puzzles - 3 - Scrabble

README.md

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.

solution.py

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

tiles.py

# 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)
}