Morton Goldberg
10/9/2006 12:10:00 AM
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>