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

Here's my solution to the problem. I'm not quite sure why it doesn't
find the better result already found by Ezwan as I expected it to be
optimal - please point out my error if you see it. It may well be that
making it optimal would also make it converge much more slowly though.

This uses an A* search algorithm to find the sequence with the least
number of total letters that forms a pangram (= least number of
repeated characters). The script is enormous but on my laptop (1.4GHz
Celeron M processor, 768MB memory) it manages to find the following
solution in under 0.2 seconds:

Words: qalter jobs find chgrp awk uux mv zcat tty
Length: 34
Cost: 34
Pangram? true
Unused Letters:  (0)

I'll break the code into parts to make it easier to read:

#########################################
# Raw Data                              #
#########################################

LETTERS = (?a..?z)
WORDS = %w{admin alias ar asa at awk basename batch bc bg c99 cal cat
cd cflow chgrp chmod chown cksum cmp comm command compress cp crontab
csplit ctags cut cxref date dd delta df diff dirname du echo ed env ex
expand expr FALSE fc fg file find fold fort77 fuser gencat get getconf
getopts grep hash head iconv id ipcrm ipcs jobs join kill lex link ln
locale localedef logger logname lp ls m4 mailx make man mesg mkdir
mkfifo more mv newgrp nice nl nm nohup od paste patch pathchk pax pr
printf prs ps pwd qalter qdel qhold qmove qmsg qrerun qrls qselect qsig
qstat qsub read renice rm rmdel rmdir sact sccs sed sh sleep sort split
strings strip stty tabs tail talk tee test time touch tput tr TRUE
tsort tty type ulimit umask unalias uname uncompress unexpand unget
uniq unlink uucp uudecode uuencode uustat uux val vi wait wc what who
write xargs yacc zcat}

#########################################
# Statistics                            #
#########################################

# This is all the letters used by a particular word
USED_LETTERS = Hash.new do |h, word|
  letters = word.downcase.split(//)
  letters.uniq!
  h[word] = letters.map {|l| l[0]}.select {|l| LETTERS.include?(l)}
end

# This is the length in letters of a word (auto-caching)
WORD_LENGTH = Hash.new do |h, word|
  length = 0
  word.downcase.each_byte do |byte|
    length += 1 if LETTERS.include?(byte)
  end
  h[word] = length
end

# This is the minimum number of letters that must be included to add
# a particular letter into the sequence. It is the length (letters
only)
# of the shortest word containing this letter.
LETTER_COSTS = {}
WORDS.each do |word|
  letters = Hash.new{0}
  word.each_byte {|byte| letters[byte] += 1}
  letters.each do |letter, count|
    if !LETTER_COSTS[letter] || LETTER_COSTS[letter] >
WORD_LENGTH[word]
      LETTER_COSTS[letter] = WORD_LENGTH[word]
    end
  end
end

#########################################
# Pangram Class - Search Tree States    #
#########################################

class Pangram

  include Comparable

  def initialize(words = [])
    @words = words
  end

  def children
    remaining = WORDS - @words
    remaining.map do |word|
      Pangram.new(@words + [word])
    end
  end

  def unused_letters
    unless @unused
      @unused = LETTERS.to_a
      @words.each do |word|
        @unused -= USED_LETTERS[word]
      end
    end
    @unused
  end

  def length
    unless @length
      @length = 0
      @words.each do |word|
        @length += WORD_LENGTH[word]
      end
    end
    @length
  end

  def complete?
    unused_letters.length == 0
  end

  # Estimate of the cost to reach the end goal.
  # Must always over-estimate
  def heuristic
    unused_letters.inject(0) {|sum, letter| sum + LETTER_COSTS[letter]}
  end

  def cost
    unless @cost
      @cost = length + heuristic
    end
    @cost
  end

  def <=>(other)
    self.cost <=> other.cost
  end

  def stats
    %~
Words: #{@words.join(" ")}
Length: #{length}
Cost: #{self.length + self.heuristic}
Pangram? #{complete?}
Unused Letters: #{unused_letters.map{|l| l.chr}.join(", ")}
(#{unused_letters.length})
    ~.strip
  end
end

#########################################
# Ordered Queue for A* Search           #
#########################################

class OrderedQueue
  def initialize(array = [])
    @queue = array.sort
  end

  # Add items to the queue
  # This is optimised for large queues
  def add(items)
    sorted_items = items.sort
    idx = 0
    loop do
      break if idx >= @queue.length - 1
      qitem = @queue[idx]
      while !sorted_items.empty? && sorted_items.first < qitem
        @queue.insert(idx, sorted_items.shift)
        idx += 1
      end
      idx += 1
    end
    sorted_items.each {|item| @queue << item}
  end

  def pop
    @queue.shift
  end

  def empty?
    @queue.length == 0
  end
end

#########################################
# Search implementation                 #
#########################################

if $0 == __FILE__
  # Start queue with the empty initial pangram
  options = OrderedQueue.new([Pangram.new])
  loop do
    # Check for exhaustion
    if options.empty?
      puts "No solution could be found"
      exit 1
    end

    # Get the best current option
    option = options.pop

    # Check for completion
    if option.complete?
      puts option.stats
      break
    end

    # Add children to options
    options.add(option.children)
  end
end