[QUIZ: Solution] Banned Words #9

[Michael Ulm]

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}
@Count = 0
end

def countReset
@Count = 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)
@Count += 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: (e-mail address removed)
Visit our Website: www.isis-papyrus.com