On Fri, 06 Oct 2006 22:19:10 +0900, Ruby Quiz wrote:

> The three rules of Ruby Quiz:
> 
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
> 
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
> 
> http://www.rubyquiz.com/
> 
> 3.  Enjoy!
> 
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz message,
> if you can.
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> by Martin DeMello
> 
> A pangram is a sentence containing every letter of the alphabet at least once (a
> famous example in English being "the quick brown fox jumps over the lazy dog").
> For maximum style points a pangram should read smoothly, and have both as few
> repeated letters as possible (ideally zero), and as few words as possible.
> 
> This quiz extends the idea to the posix utilities[1] - write a program to find
> pangrammatic collections of posix utilities that (1) use the fewest utilities
> and (2) have the minimum number of repeated letters. In either case, break ties
> on the other criterion; that is, your first solution should also have as few
> repeated letters as possible, and your second one should use as few utilities as
> possible.
> 
> [1] http://www.unix.org/version3/apis/cu.html has a complete list

Finding the pangram with the minimum number of words is NP-Hard. The
reduction is from Minimum Set Cover[1]:

MINIMUM SET COVER:
INSTANCE: Collection C of subsets of a finite set S. 
SOLUTION: A set cover for S, i.e., a subset C' of C such that
every element in S belongs to at least one member of C'.
MEASURE: Cardinality of the set cover, i.e., size(C')

Reduction:
Each element in S becomes mapped to a unique letter in the alphabet used
by pangrams. (Note that in general, we can play Pangrams in any
langauage, the alphabet can be of length we want) Each subset K (which is
an element of C) becomes a word, made up of the letters corresponding to
the elements of K. Finding a pangram with the minimum number of words in
this setup would give a solution to the set-cover instance.

I suspect that the other optimization problem here may also be NP-Hard.
I'm not sure (in all of the 5 minutes that I'm writing this post) how to do
a simple reduction to that problem though.

--Ken Bloom

[1] http://www.ensta.fr/~diam//ro/online/viggo_wwwcompendium/node146.html

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.