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 an arbitrary word $ W_i $, which is composed of a set of (up to) five letters. We seek a sequence of m words $ W_1, W_2, \dots, W_m $ such that the set of letters in those words, denoted S, covers the first N letters of the alphabet, or more generally, covers some target set T of letters.

We wish to minimize m, subject to the restriction that T must be a subset of (contained in) S.

Let C(j) denote the coverage of the jth word in a sequence, that is, the number of elements of the target set T that are contained in the set of letters S that compose the first j words $ W_1, W_2, \dots, W_j $.

Let us consider a two-word example:

Target set:
T = {a, b, c, d, e}

Words:
W1 = abbot
W2 = ended

Letters:
S = {a, b, d, e, n, o, t}

Coverage:
C(2) = 4 

Letters in common: (a, b, d, e)

Can possibly use binary string, e.g.,

abbot --> {a, b}
11000

ended --> {d, e}
00011

{abbot, ended} --> {a, b, d, e}
11011

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