Letter Coverage

Problem Description

The letter/word coverage problem is the problem of finding the minimum number of words from the five-letter-words set (see Five Letter Words) to cover X letters of the alphabet.

The problem has a couple of variations: we might provide a set of letters, and search for the smallest number of words that can cover those particular letters. Or we might give an integer N <= 26, and search for the smallest number of words that can cover the first N letters of the alphabet.

We may also wish to restrict our search to the first M words of the 5757 total five letter words.

For the sake of simplicity, we will start with the problem of considering the first N letters of the alphabet, and the shortest sequence of words that will provide coverage of those first N letters of the alphabet.

Solution

Definitions

Consider the ith sequence $ S_i $ of p words:

$ S_i = \{ W_1, W_2, W_3, \dots, W_j, \dots, W_p \} $

Now, the jth word is composed of a set of letters (up to five), denoted $ L_j $:

$ L_j = \{ L_1, L_2, \dots \} $

Solution Procedure

To solve dynamic programming problems, apply these three steps:

1. Formulate answer as recurrence relation/recursive algorithm

2. Show that the number of parameters taken on by the recurrence is bounded by a polynomial

3. Specify the order of evaluation for the recurrence so that partial results that are needed are always available