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