Blind Watch Maker 1 Sample
 ```""" BlindWatchMaker1.cobra The book is "The Blind Watchmaker" by Richard Dawkins. In Chapter 3, "Accumulating Small Changes", Dawkins distinguishes between "single-step selection" and "cumulative selection". This doc string is a poor substitute for reading the book, but here we go: Suppose you wish to randomly generate a desired line from Shakespeare: Methinks it is like a weasel Using a "single-step selection", you would generate 28 fresh, random letters at a time like so: Attempt 1: oufswgonxgjsqvfwlpmhhkhfcrxe Attempt 2: eqnhydvqghckpyzrvayjepnvzbbd Attempt 3: m qekjigucvn pqemcsjmqlbuo q Attempt 4: dsiwcrdgrz fqtytgljqziixjtsw Attempt 5: pplxjtccuzkilknocmtutsvjekrw Attempt 6: jmmj hrbndxyqw iabepvvvx ydy Attempt 7: vbs bgtimbidtmazqwdxtnjdfcap Attempt 8: rqjceuhlmyxjcswztawjuwheugfh Attempt 9: tpu gerxtg eqnt uvarklegsvv ...until you hit upon the desired line. The odds of success are astronomical. You would die before it happened. But using "cumulative selection", you would only *start* with 28 random letters. Thereafter, you reproduce the string with a slight mutation, evaluate its fitness with respect to the goal and choose between it or the original. The fittest survives and the weakest is cast aside. In this way, progress accumulates to reach the goal in seconds even though the micro-engineering was still random (mutating the string). That's because the macro-engineering was not (selection and reproduction). This Cobra program demonstrates the above. At the Lang.NET 2008 Conference (http://www.langnetsymposium.com/), I met Peli de Halleux from the Pex team at http://research.microsoft.com/pex/. We put this program through Pex and it automatically found legit errors in the code resulting in improvements to the contracts. Those additional contracts are marked "Pex" below. """ class BlindWatchMaker1 var _random = Random() def main goal = 'methinks it is like a weasel' alphabet = 'abcdefghijklmnopqrstuvwxyz ' duration1 = .runCumulativeSelection(goal, alphabet) duration2 = .runSingleStepSelection(goal, alphabet) factor = duration2 / duration1 print 'Single step selection took [Math.round(factor)] times longer than cumulative selection and *still* failed.' def runCumulativeSelection(goal as String, alphabet as String) as float require goal.length # Pex alphabet.length # Pex ensure result > 0 body print 'Cumulative Selection:' start = DateTime.now # wip stands for "work in progress" wip = .randomString(goal.length, alphabet) showAttempt = true generation = 1 while true score = .score(wip, goal) # 0..100 if showAttempt print ' attempt [generation.toString.padLeft(4)] [wip] ==> [score]%' if score >= 100 break mutantChar = alphabet[_random.next(alphabet.length)] mutantIndex = _random.next(wip.length) firstPart = wip[:mutantIndex] secondPart = wip[mutantIndex+1:] offspring = '[firstPart][mutantChar][secondPart]' if .score(offspring, goal) > .score(wip, goal) # we have a new, improved string showAttempt = true wip = offspring else # the offspring is no better than the parent (and possibly worse) showAttempt = false generation += 1 duration = DateTime.now.subtract(start) print ' duration: [duration]' return duration.totalSeconds def runSingleStepSelection(goal as String, alphabet as String) as float require goal.length alphabet.length ensure result > 0 body print 'Single Step Selection:' start = DateTime.now maxAttempts = 1_000_000 reportInterval = 100_000 maxScore = 0 for i in maxAttempts s = .randomString(goal.length, alphabet) if s == goal # this could theoretically happen, but never does print ' !!! SUCCESS !!!' print ' On attempt [i+1], a randomly generated string matched:' print ' [s]' break if .score(s, goal) > maxScore maxScore = .score(s, goal) if (i+1) % reportInterval == 0 print ' [i+1]...' if s <> goal print ' Giving up after [i] attempts of single step selection.' print ' Maximum score was [maxScore]%.' duration = DateTime.now.subtract(start) print ' duration: [duration]' return duration.totalSeconds def randomString(length as int, alphabet as String) as String require length > 0 alphabet <> '' ensure result.length == length test x = BlindWatchMaker1() assert x.randomString(5, 'ab').length == 5 s = x.randomString(1000, 'a') for c in s, assert c == c'a' body sb = StringBuilder() for i in length c = alphabet[_random.next(alphabet.length)] sb.append(c) return sb.toString def score(candidate as String, goal as String) as int """ Returns the score of the candidate string with regards to how closely it matches the goal. """ require candidate.length # Pex goal.length # Pex candidate.length == goal.length ensure result >= 0 and result <= 100 test bwcc = BlindWatchMaker1() assert bwcc.score('aoeu', 'aoeu') == 100 assert bwcc.score('aabb', 'aacc') == 50 assert bwcc.score('a b ', 'axbx') == 50 body score = 0 for i in goal.length if candidate[i] == goal[i], score += 1 value = (score / goal.length * 100) to int return value ```