Reply to thread

Message: [QUOTE="Michael Ulm, post: 4450916"] Another lunchbreak used for debugging, but I present my official solution to the Quiz #9. Here is some sample output 15 words of 1000 found after 135 calls (expected 96.4228550642991) 21 words of 1000 found after 169 calls (expected 164.313332333478) 24 words of 1000 found after 186 calls (expected 222.183614864463) 39 words of 1000 found after 280 calls (expected 273.874191108301) 50 words of 1000 found after 329 calls (expected 319.623421186338) 67 words of 1000 found after 389 calls (expected 362.608933077592) 62 words of 1000 found after 393 calls (expected 402.75735262937) 80 words of 1000 found after 435 calls (expected 438.254450457805) 92 words of 1000 found after 484 calls (expected 472.825290910606) 94 words of 1000 found after 487 calls (expected 506.505348749998) 9 words of 1000 found after 87 calls (expected 96.4228550642991) 16 words of 1000 found after 143 calls (expected 164.313332333478) 23 words of 1000 found after 190 calls (expected 222.183614864463) 41 words of 1000 found after 276 calls (expected 273.874191108301) 34 words of 1000 found after 252 calls (expected 319.623421186338) 79 words of 1000 found after 443 calls (expected 362.608933077592) 60 words of 1000 found after 378 calls (expected 402.75735262937) 64 words of 1000 found after 398 calls (expected 438.254450457805) 75 words of 1000 found after 422 calls (expected 472.825290910606) 105 words of 1000 found after 537 calls (expected 506.505348749998) =============Proposed Solution to Quiz #9============= # this holds classes and methods to "solve" # ruby-talk quiz #9: Banned Words # # # creates the language filter class LanguageFilter def initialize(size, prob) @size = size if prob <= 0 or prob >= 1 # sanity check throw "illegal probability in LanguageFilter::initialize" end @badWords = [] @size.times {|k| @badWords.push(k) if rand < prob} [USER=33370]@Count[/USER] = 0 end def countReset [USER=33370]@Count[/USER] = 0 end def getBad @badWords end # checks if one of the numbers in the array testText is on the # badWords list def clean?(testText) sortedClean?(testText.sort) end # checks if one of the numbers in the array testText is on the # badWords list testText is assumed to be sorted def sortedClean?(testText) [USER=33370]@Count[/USER] += 1 binStart, binEnd = 0, @badWords.size testText.each do |current| binStart = binarySearch(current, binStart, binEnd) return false if @badWords[binStart] == current end return true end def test(testWords) [@count, testWords.sort == @badWords] end private def binarySearch(what, searchStart, searchEnd) return searchEnd if what > @badWords[searchEnd - 1] while searchEnd - searchStart > 1 testSearch = (searchStart + searchEnd) / 2 testWord = @badWords[testSearch] return testSearch if testWord == what if testWord < what searchStart = testSearch else searchEnd = testSearch end end return searchStart end end class QueryStrategy def initialize(prob) @prob = prob @qrob = 1.0 - prob @eNone = [0, 1] # expected value for interval without additional info @eOne = [0, 0] # expected values for interval with at least one bad word @kNone = [0, 1] # optimal interval query length in interval without info @kOne = [0, 0] # optimal interval query length in interval with one bad word @size = 2 @qToN = [1, @qrob] end def getStrategy(size, noInfo = true, quick = false) if size < @size return noInfo ? [@kNone[size], @eNone[size]] : [@kOne[size], @eOne[size]] end @size.upto(size) {|k| @qToN[k] = @qToN[k - 1] * @qrob} @size.upto(size) do |n| # compute F_p(n) minExp = n.to_f minK = 1 1.upto(n - 1) do |k| thisExp = (@qToN[k] - @qToN[n]) * @eOne[n - k] + (1 - @qToN[k]) * (@eOne[k] + @eNone[n - k]) if thisExp < minExp minK, minExp = k, thisExp end end @kOne[n] = minK @eOne[n] = 1.0 + minExp / (1 - @qToN[n]) # compute E_p(n) minExp = n.to_f minK = 1 1.upto(n) do |k| thisExp = @eNone[n - k] + (1 - @qToN[k]) * @eOne[k] if thisExp < minExp minK, minExp = k, thisExp end end @kNone[n] = minK @eNone[n] = 1 + minExp end @size = size + 1; return noInfo ? [@kNone[size], @eNone[size]] : [@kOne[size], @eOne[size]] end def findWords(filter, size) @myWords = [] getWordsRecursively(filter, 0...size, true) @myWords end private def getWordsRecursively(filter, range, noInfo) rangesize = range.end - range.begin return if rangesize == 0 if rangesize == 1 if noInfo @myWords.push(range.begin) unless filter.sortedClean?([range.begin]) else @myWords.push(range.begin) end else thisStrat = getStrategy(rangesize, noInfo) testRange = range.begin...(range.begin + thisStrat[0]) testArray = [] testRange.each {|k| testArray.push(k)} if filter.sortedClean?(testArray) getWordsRecursively(filter, (range.begin + thisStrat[0])...range.end, noInfo) else getWordsRecursively(filter, testRange, false) getWordsRecursively(filter, (range.begin + thisStrat[0])...range.end, true) end end end end # test testsize = 1000 10.times do |level| testprob = 0.01 * (level + 1) myfilt = LanguageFilter.new(testsize, testprob) strat = QueryStrategy.new(testprob) testWords = strat.findWords(myfilt, testsize) number, found = myfilt.test(testWords) if found puts "#{testWords.size} words of #{testsize} found after #{number} calls (expected #{strat.getStrategy(testsize)[1]})" else puts "word list not found after #{number} calls" end end -- Michael Ulm R&D Team ISIS Information Systems Austria tel: +43 2236 27551-219, fax: +43 2236 21081 e-mail: [email]michael.ulm@isis-papyrus.com[/email] Visit our Website: [URL="http://www.isis-papyrus.com"]www.isis-papyrus.com[/URL] [/QUOTE]

Verification