A pangram is a string that contains every letter a
-z
of the English alphabet, case-insensitive. (It's OK if the pangram contains more than one copy of a letter, or if it contains non-letter characters in addition to the letters.)
Write a program or function whose input is a list of strings, and which outputs one or more strings which have the following properties:
- Each output string must be a pangram.
- Each output string must be formed by concatenating one or more strings from the input list, separated by spaces.
- Each output string must be the shortest, or tied for the shortest, among all strings with these properties.
Many programs will choose to output only one string; you'd only want to output more than one string if you'd otherwise have to write extra code to limit the output.
You may assume that the input contains no unprintable characters or spaces, and that no word in it is more than (26 times the natural logarithm of the length of the list) characters long. (You may not assume, however, that the input contains nothing but letters, or only lowercase letters; punctuation marks and uppercase letters are entirely possible.)
Input and output can be given in any reasonable format. For testing your program, I recommend using two test cases: a dictionary of English words (most computers have one), and the following case (for which a perfect (26-letter) pangram is impossible, so you'd have to find one containing duplicate letters):
abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz
You should include a sample of your program's output along with your submission. (This may well be different for different people as a result of using different word lists.)
Victory condition
This is a restricted-complexity code-golf challenge. The winner is the shortest program (in bytes) that runs in polynomial time. (A summary for people who don't know what that means: if you double the size of the word list, the program should become slower by no more than a constant factor. However, the constant factor in question can be as large as you like. For example, it's valid for it to become four times slower, or eight times slower, but not for it to become smaller by a factor of the length of the word list; the factor via which it becomes slower must be bounded.)