James Edward Gray II <james@grayproductions.net> writes:
I'm all about thinking outside the box. I think we should all learn
to love the guesswork!
Guess how I found the shortest solution.
James Edward Gray II
Hint: I didn't implement an algorithm myself.
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org
>
> There's also the matter of program structure. When dealing with an
> NP-Hard problem, you know that any solution geared to do a heuristic
> search quickly is not guaranteed to find the minimum.We haven't talked a lot about this in the past, but I take a pretty
relaxed approach to tough quiz problems. Find a good heuristic and
get close. That's fine with me.
I think it's fine. Now if you'd said "find a solution and then prove
using the symbolic algebra of your choice that it's optimal" would be
a different story.
Next Ruby Quiz: Prove that P = NP, unless it doesn't, in which case
prove that P != NP.
Martin
After a few optimization passes, I've finally figured out how to get
the optimal POSIX pangrams in about 30 minutes on a fast, modern
machine. I am still relatively new to Ruby so this application is
surely not as concise as it could be. To run it, save the two files,
create a posix-utilities.txt with the utilities, one per line, and run
the unit test.
-- pangrams.rb
#
# A set of routines to find minimal pangrams from an input set of
words. A pangram is a set of
# words that contain all the letters of the alphabet. Unless there are
some properties of
# pangrams that I am unaware of, finding the minimal pangrammatic
subset of a set of words
# is in a family of constraint-satisfaction problems that is
NP-complete, as in, there is
# not a way to find _the_ minimal subset that is guaranteed to run in
polynomial time with respect
# to the size of the dataset.
#
# The most common ways of finding excellent, but not provably perfect
solutions are to either
# use a non-deterministic algorithm, or to try to prune the number of
subsets that you search
# as much as possible, and backtrack as often as possible, quitting
after a pre-determined
# quality threshold has been reached.
#
# The Pangrams class below implements both of these algorithms,
providing methods to yield a
# specified number of random pangrams, or to do a backtracking search
to yield successively
# better pangrams.
#
# In order not to waste time trying non-pangrams, the strategy for
building pangrams is to
# build a list by finding the least common letter not already there,
and then searching for pangrams
# using the utilities containing the least-common missing letter. If at
any point the string
# is longer or has more repeated characters than the known minimums
then we stop searching and
# backtrack. So we abort early and try to limit the number of decisions
to try at each step.
#
# The search algorithm does not run in polynomial time, but for 160
elements, it can search the
# problem space in about 30 minutes on a fast, modern machine
(dual-core xeon). For larger datasets
# (like aspell) the non-deterministic approach would be more practical.
#
# Two minimal POSIX pangrams are:
# Minimal number of utilities: "zcat stty jobs cxref newgrp iconv
cksum qhold"
# Minimal repeated letters: "zcat tty jobs lex awk mv uniq chgrp df"
(4 repeats)
# (This is one of the ones that Christian found, in a different
order)
#
# Takes a list of words and creates a histogram of letters. The
histogram can then
# be queried for pangramness and repeated letter counts.
class LetterHistogram
# Initializes with a set of words
def initialize(words=nil)
@hist = Hash.new(0)
@total_letters = 0
words.each {|word| add word} unless words.nil?
end
# Adds a word to the pangram
def add(word)
word.scan(/./) {|l| @hist[l] = @hist[l] + 1 if ('a'..'z') === l}
@total_letters += word.size
end
# Returns true if this list of words has a pangram
def pangram?
return @hist.size == 26
end
# Returns the number of repeated letter
def repeats
@total_letters - @hist.size
end
# Returns a list of missing letters. Used in conjunction with the
WordLetterMap below to
# find a good word to add to the list to make a pangram.
def missing_letters
missing = Array.new
('a'..'z').each {|l| missing << l if @hist[l] == 0}
missing
end
end
# Contans a map of Letters => Words containing that letter
class WordLetterMap
def initialize(words)
@map = Hash.new
words.each {|w| add w}
end
# Adds a new word
def add(word)
word.scan(/./) do |l|
if ('a'..'z') === l
@map[l] = Array.new unless @map.has_key? l
@map[l] = @map[l] << word
end
end
end
# Return a list of words containing the least common missing letter
# Used to limit the number of choices as we search the minimal
pangram space
def least_common(words=nil, histogram=nil)
histogram = LetterHistogram.new words if histogram.nil?
min_words = nil
histogram.missing_letters.each do |l|
new_words = @map[l] - words
if min_words.nil? || min_words.size > words.size
min_words = new_words
end
end
return min_words
end
end
# Holds a list of words and generates minimal pangrams, both
non-deterministically,
# and by searching, backtracking to avoid non-minimal branches
class Pangrams
# Exception to throw when we have returned the maximum number of
pangrams
class AllDone < Exception
end
# Initialize with a word list
def initialize(words=nil)
if words.nil?
@words = Array.new
else
@words = words
end
end
# Adds a word to the set of words to produce pangrams
def add(word)
@words[@words.size] = word
end
# The number of words in the set of words
def size
@words.size
end
# Loads a list of words from a file
def self.from_file(filename)
p = Pangrams.new
File.new(filename).each_line {|line| p.add line.strip}
return p
end
# Yields randomly generated minimal pangrams to the passed block
def random(count,&block)
@word_letters = WordLetterMap.new @words
(0..count).each {|i| random_pangram([],&block)}
end
# Searches for good minimal pangrams, yielding the ones it finds to
the block
def search(max_count=0,&block)
@min_size = size
@min_repeats = 1000
@max_count = max_count
@count = 0
@word_letters = WordLetterMap.new @words
begin
pangram_search([],&block)
rescue AllDone
# Quit gracefully
end
end
private
# searches the pangram space by finding all words containing the
least common letter until
# a pangram has been built, passing each found pangram to the block.
The algorithm tries to
# be smart searching the word space by choosing the least common
letters first, making the
# overall space smaller. It also tries make smart use of backtracking
to avoid searching
# non-lucrative branches.
def pangram_search(words, &block)
# Bust out if we've found enough pangrams
raise AllDone.new if @max_count != 0 && @count > @max_count
h = LetterHistogram.new words
# If we already have more words or more repeats, then no need to
look any
# further, we should backtrack and try something else.
return if words.size >= @min_size && h.repeats >= @min_repeats
# This pangram is somehow minimal, so pass to the block
if h.pangram?
@min_size = words.size if words.size < @min_size
@min_repeats = h.repeats if h.repeats < @min_repeats
@count += 1
yield words,h
return
end
# No pangram yet, find children and descend
new_words = @word_letters.least_common words,h
new_words.each {|w| pangram_search words + [w], &block}
end
# Builds a pangram by finding the least common letter that is not
represented in the
# passed-in array, and recursing until a pangram is built. This
algorithm should build
# minimal pangrams almost all of the time (i.e. removing a word from
the set will make
# the word list non-pangrammatic and will yield very good pangrams,
but probably not the
# most optimal ones.
def random_pangram(words, &block)
# Do we already have a pangram? If so, pass to block and quit
h = LetterHistogram.new words
if h.pangram?
yield words,h
return
end
# Be non-deterministic, and descend on a random word
new_words = @word_letters.least_common words,h
new_word = new_words[rand(new_words.size)]
random_pangram words + [new_word], &block
end
end
-- test_pangrams.rb
require 'test/unit'
require 'pangrams'
# Unit test harness to test the histogram and the frequency map code,
and also to exercise the pangram
# generation code. The tests assume a list of posix words, one per
line, in 'posix-words.txt'
class TestPangrams < Test::Unit::TestCase
def test_histogram
l = LetterHistogram.new ['moon']
assert_equal false, l.pangram?
assert_equal 1, l.repeats
pangram = %w{the quick brown fox jumps over the lazy dog}
l = LetterHistogram.new pangram
assert_equal true, l.pangram?
l = LetterHistogram.new ['qwertyuiopasdfghjklzxcvbn'] # m is
missing
m = l.missing_letters
assert_equal 1, m.size
assert_equal 'm', m.first
end
def test_random_search
puts "-- Testing Random Pangram Generation --"
p = Pangrams.from_file 'posix-words.txt'
min_repeats_length = p.size
min_repeats = 1000
min_repeats_pangram = nil
min_size = 160
min_size_repeats = 1000
min_size_pangram = nil
count = 0
p.random(1000) do |p, hist|
repeats = hist.repeats
size = p.size
if repeats < min_repeats || repeats == min_repeats && size <
min_repeats_length
min_repeats_pangram = p
min_repeats = repeats
min_repeats_length = p.size
puts "New min-repeats pangram: #{min_repeats_pangram.join ' '}
with #{min_repeats} repeats"
$stdout.flush
end
if size < min_size || size == min_size && repeats <
min_size_repeats
min_size = size
min_size_repeats = repeats
min_size_pangram = p
puts "New min-size pangram: #{min_size_pangram.join ' '} with
#{min_size} words"
$stdout.flush
end
end
end
def test_backtracking_search
puts "--Testing backtracking search--"
p = Pangrams.from_file 'posix-words.txt'
min_repeats_length = p.size
min_repeats = 1000
min_repeats_pangram = nil
min_size = 160
min_size_repeats = 1000
min_size_pangram = nil
p.search(50) do |p, hist|
repeats = hist.repeats
size = p.size
if repeats < min_repeats || repeats == min_repeats && size <
min_repeats_length
min_repeats_pangram = p
min_repeats = repeats
min_repeats_length = p.size
puts "New min-repeats pangram: #{min_repeats_pangram.join ' '}
with #{min_repeats} repeats"
$stdout.flush
end
if size < min_size || size == min_size && repeats <
min_size_repeats
min_size = size
min_size_repeats = repeats
min_size_pangram = p
puts "New min-size pangram: #{min_size_pangram.join ' '} with
#{min_size} words"
$stdout.flush
end
end
end
end