Letter Coverage: Difference between revisions

Revision as of 09:27, 16 August 2017

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

A Simpler Example

Suppose we are considering 2-letter words taken from a 5-letter alphabet abcde. We can represent a given word as a binary string/bit vector:

ab = 11000
ce = 00101
ae = 10001

etc. Now, we wish to write a dynamic program that will find the smallest set of words such that taking the union of each bit vector gives 11111.

Definitions

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

@@ Line 11: / Line 11: @@
 ==Solution==
-===Definitions===
+===A Simpler Example===
-Consider an arbitrary word <math>W_i</math>, which is composed of a set of (up to) five letters. We seek a sequence of m words <math>W_1, W_2, \dots, W_m</math> 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 <math>W_1, W_2, \dots, W_j</math>.
+Suppose we are considering 2-letter words taken from a 5-letter alphabet ''abcde''. We can represent a given word as a binary string/bit vector:
-Let us consider a two-word example:
 <pre>
-Target set:
+ab = 11000
-T = {a, b, c, d, e}
+ce = 00101
+ae = 10001
-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)
 </pre>
-Can possibly use binary string, e.g.,
+etc. Now, we wish to write a dynamic program that will find the smallest set of words such that taking the union of each bit vector gives 11111.
-<pre>
+===Definitions===
-abbot --> {a, b}
-ended --> {d, e}
-{abbot, ended} --> {a, b, d, e}
-</pre>
 ===Solution Procedure===