From: Morton Goldberg <m_goldberg@...>
Date: 2006-10-09T09:10:10+09:00
Subject: Re: [QUIZ] Posix Pangrams (#97)

Here is my solution. It's not what I planned. I intended to submit an  
algorithm that would find all the minimal Posix pangrams, and I  
worked out a rather nice (IMO) recursive algorithm to do just that.  
But Ruby doesn't allocate enough stack space for that algorithm to  
run to completion <sigh>. So I've settled on an algorithm that finds  
just one minimal pangram, but uses pseudo-random numbers to produce a  
different pangram each time it is run.

My best pangram so far is

[
    "fg", "jobs", "qhold", "stty", "umask",
    "unexpand", "vi", "write", "zcat"
]

Regards, Morton

<code>
#! /usr/bin/env ruby -w
#
#  Created by Morton Goldberg on October 08, 2006.
#
# Ruby Quiz 97 -- POSIX Pangrams
#  quiz_97.3.rb

class Array

    def shuffle!
       n = size - 1
       while n > 0
          k = rand(n)
          self[k], self[n] = self[n], self[k]
          n -= 1
       end
       self
    end

end

# Removed c99, fort77, and m4 -- the complication they add is IMHO
# unedifying.
WORDS = %w[
    admin alias ar asa at awk basename batch bc bg 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 fuser gencat get getconf getopts
    grep hash head iconv id ipcrm ipcs jobs join kill lex link ln locale
    localedef logger logname lp ls 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
]

# Return true if _wds_ is a pangram.
def pangram?(wds)
    wds.join.split(//).uniq.size == 26
end

# Return array giving pangram statistics:
#     [<words>, <total-chars>, <repeated-chars>]
def stats(pan)
    tmp = pan.join.split(//)
    [pan.size, tmp.size, tmp.size - tmp.uniq.size]
end

# Given a pangram, return list of pangrams, where each panaram in the  
list
# is derived from the given one by removing one word.
def diminish(pan)
    result = pan.collect do |item|
       rest = pan - [item]
       rest if pangram?(rest)
    end
    result.compact.shuffle!
end

# Given a list of pangrams return a minimal pangram that can be derived
# from it.
def find_minimal(pans)
    pan = pans.pop
    reduced = diminish(pan)
    return pan if reduced.empty?
    find_minimal(reduced)
end

# Find a minimal pangram.
pangram = find_minimal([WORDS])
p pangram # =>
# [
#    "fg", "jobs", "qhold", "stty", "umask",
#    "unexpand", "vi", "write", "zcat"
# ]
p stats(pangram) # => [9, 39, 13]
</code>