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.