Reply to thread

Message: [QUOTE="Ruby Quiz, post: 4450554"] 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: [URL]http://www.grayproductions.net/ruby_quiz/[/URL] 3. Enjoy! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= by Fredrik Jagenheim At work we discovered that they installed a spam filter that throws away e-mail that it considers spam. It doesn't use any Bayes Filter, it simply checks for certain words that it considers 'banned'. One word we discovered was 'sex', which is a Swedish word for the number six. So the phrase "I'll be home at six o'clock." will be classified as spam, thrown away and never seen. The Ruby Quiz I propose is to figure out which words are banned. Since the filter is a black box, we can only find out which words they are by sending email through it. The real problem is to find out how to do it with as *few* emails as possible. Of course I don't want the ruby community to do a Denial-of-Service on my employer's mailserver, so do it as a local filter; perhaps something like this: # by JEG2 # # A simple class for managing a filter that prevents to use # of a given _banned_words_ list. # class LanguageFilter # # Create a new LanguageFilter object that will # disallow _banned_words_. # Accepts a list of words, arrays of words, # or a combination of the two. # def initialize( *banned_words ) @banned_words = banned_words.flatten.sort @clean_calls = 0 end # A count of the calls to <i>clean?</i>. attr_reader :clean_calls # # Test if provided _text_ is allowable by this filter. # Returns *false* if _text_ contains _banned_words_, # *true* if it does not. # def clean?( text ) @clean_calls += 1 @banned_words.each do |word| return false if text =~ /\b#{word}\b/ end true end # # Verify a _suspect_words_ list against the actual # _banned_words_ list. # Returns *false* if the two lists are not identical or # *true* if the lists do match. # Accepts a list of words, arrays of words, # or a combination of the two. # def verify( *suspect_words ) suspect_words.flatten.sort == @banned_words end end filter = LanguageFilter.new "six" filter.clean?("I'll be home at six.") # => false filter.clean?("Do not taunt the happy fun ball!") # => true filter.verify("ball") # => false filter.verify("six") # => true filter.clean_calls # => 2 So, figure out how to find the hidden words, using as few calls to LanguageFilter#clean? as possible. Which algorithms do you find are effective when many words are blocked (like 10%) and which are effective when very few are blocked(1 in 20000)? All solutions should do better than this: ;) dict = ["foo", "bar", "six", "baz"] filter = LanguageFilter.new "six" p dict - (dict.dup.delete_if { |word| not filter.clean?(word) }) [/QUOTE]

Verification