root/cobra/trunk/Samples/BlindWatchMaker1.cobra

"""
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