#!/usr/bin/python
##########################################################################
#
# Mean tosses to coin-toss patterns
#
# Scott Hendrickson
# 2008-Apr-03
#
# This work is licensed under a
# Creative Commons Attribution-Noncommercial 3.0 United States License
# See http://creativecommons.org/licenses/by-nc/3.0/us/
#
##########################################################################
import random, re

class coinTossSimulation:
	def __init__(this, pat):
		this.pattern = pat
		this.plen = len(pat)
		this.record = []
		this.iter = 20000
		this.simulated = False

	def simulate(this):
		for i in range(0,this.iter):
			count = 0
			cont = True
			this.tosses = ''
			while(cont):
				if random.random() >= 0.50:
					this.tosses += 'H'
				else:
					this.tosses += 'T'
				count += 1
				if this.pattern == this.tosses[-this.plen:]:
					cont = False
			this.record.append(count)
		this.simulated = True

	def meanTosses(this):
		if not this.simulated:
			this.simulate()
		return sum(this.record)/float(len(this.record))

	def printMeanTosses(this):
		print "E<N> for pattern '"+this.pattern+"': %.2f" % this.meanTosses()

	def setIter(this,n):
		this.iter = n

	def histogram(this):
		hist = {}
		for i in this.record:
			if i in hist:
				hist[i] += 1
			else:
				hist[i] = 1

		xmax = max(hist.keys())
		xmin = min(hist.keys())
		filledHist = []
		for i in range(xmin, xmax+1):
			if i in hist:
				filledHist.append((i,hist[i]))
			else:
				filledHist.append((i,0))
		return filledHist

class coinPermutations:
	def __init__(this, n):
		this.length = n
		this.items = 2**n
		this.generated = False
		this.plist = []

	def getPerms(this):
		if not this.generated:
			this.generate(this.items)
		return this.plist

	def generate(this, n):
		sl = ['' for i in range(0,this.items)]
		for i in range(0,this.length):
			bit = 'H'
			for j in range(0,this.items,2**(i+1)):
				bit = this.flipBit(bit)
				for k in range(0,2**(i+1)):
					sl[j+k] += bit
					bit = this.flipBit(bit)
		this.generated = True
		this.plist = sl

	def flipBit(this,b):
		if b == 'H':
			bit = 'T'
		else:
			bit = 'H'
		return bit

class coinPermutationsWOPattern(coinPermutations):
	"""Returns the number of permutations for n-1 tosses that do not include
	the target pattern"""
	def __init__(this, n, p):
		this.nperms = 2**n
		this.pat = p
		this.l = len(this.pat)
		this.patRE = re.compile(this.pat)
		# Setup base class to generate all permutations without the desired pattern
		# at the end.
		assert(n - this.l > 0)
		coinPermutations.__init__(this, n - this.l)

	def getPermsWOPat(this):
		if not this.generated:
			this.filter()
		return this.permsWOPat
		
	def getPerms(this):
		# list doesn't exist after filtering (to save memory)
		return None

	def filter(this):
		this.generate(this.items)
		this.permsWOPat = []
		while len(this.plist) > 0:
			i = this.plist.pop()
			# Permutation (n-l) + pattern (l) ( = n )
			full = i + this.pat[0:-1]
			# Exclude all permutations of ( n-1 ) that contain pattern
			if not this.patRE.search(full):
				this.permsWOPat.append(full)
		return this.permsWOPat

	def numPermWithoutPattern(this):
		if not this.generated:
			this.filter()
		return len(this.permsWOPat)
		
	def numPerms(this):
		return this.nperms


class countCoinPermutationsWOPattern(coinPermutationsWOPattern):
	"""Just count the permutaions without the pattern"""
	def __init__(this, n, p):
		this.nperms = 2**n
		this.pat = p
		this.l = len(this.pat)
		this.patRE = re.compile(this.pat)
		# Setup base class to generate all permutations without the desired pattern
		# at the end.
		coinPermutations.__init__(this, n)
		
	def filter(this):
		this.generate(this.items)
		this.permsWOPat = []
		while len(this.plist) > 0:
			i = this.plist.pop()
			# Exclude all permutations of ( n ) that contain pattern
			if not this.patRE.search(i):
				this.permsWOPat.append(i)
		return this.permsWOPat


if __name__ == '__main__':
	######################################
	# Examples
	######################################
	n = 22
	#####################################################
	# Counting permutations without the target pattern
	print "\n\nTosses\tcoinPermutationsWOPattern(TH)\ttotal permutations\tfraction"
	for r in range(1,n):
		p = countCoinPermutationsWOPattern(r, 'TH')
		nwo = p.numPermWithoutPattern()
		np = p.numPerms()
		print "%3d %6d %6d %.3f" % (r, nwo, np, float(nwo)/np )
		del p

	#####################################################
	# Counting permutations without the target pattern
	print "\n\nTosses\tcoinPermutationsWOPattern(HH)\ttotal permutations\tfraction"
	for r in range(1,n):
		p = countCoinPermutationsWOPattern(r, 'HH')
		nwo = p.numPermWithoutPattern()
		np = p.numPerms()
		print "%3d %6d %6d %.3f" % (r, nwo, np, float(nwo)/np )
		del p
	#####################################################
	# Counting permutations without the target pattern
	print "\n\nTosses\tcoinPermutationsWOPattern(THT)\ttotal permutations\tfraction"
	for r in range(1,n):
		p = countCoinPermutationsWOPattern(r, 'THT')
		nwo = p.numPermWithoutPattern()
		np = p.numPerms()
		print "%3d %6d %6d %.3f" % (r, nwo, np, float(nwo)/np )
		del p

	#####################################################
	# Counting permutations without the target pattern
	print "\n\nTosses\tcoinPermutationsWOPattern(THH)\ttotal permutations\tfraction"
	for r in range(1,n):
		p = countCoinPermutationsWOPattern(r, 'THH')
		nwo = p.numPermWithoutPattern()
		np = p.numPerms()
		print "%3d %6d %6d %.3f" % (r, nwo, np, float(nwo)/np )
		del p