#!/usr/bin/python

# coinTossPattern
# This script takes one command-line argument which should be a string
# of H's and T's (e.g. HHTH) representing a pattern of heads & tails.
# The script runs a simulation of coin tosses to determine the average
# number of tosses before the given pattern will occur.
# E.g. it takes an average of  8 tosses for the pattern HHT to occur
#           but an average of 10 tosses for the pattern HTH to occur

# Cameron Hayne (macdev@hayne.net)  November 2007

import sys
import random

class History:
    # constructor for a History object with 'maxLength'
    def __init__(self, maxLength):
        self.maxLength = maxLength
        self.str = ""

    # add a letter at the end of 'str',
    # dropping left-most letter if necessary to respect 'maxLength'
    def append(self, letter):
        if len(self.str) < self.maxLength:
            self.str += letter
        else:
            self.str = self.str[1:] + letter

    # returns the value of 'str'
    def getStr(self):
        return self.str

# returns either "H" or "T"
def coinToss():
    if random.random() < 0.5:
        return "H"
    else:
        return "T"

# returns the number of tosses before 'pattern' occurred
def numTossesUntilPattern(pattern):
    n = len(pattern)
    # keep a history of the last 'n' tosses
    history = History(n)
    
    count = 0
    while True:
        count += 1
        history.append(coinToss())
        #print history.getStr()
        if history.getStr() == pattern:
            return  count

# main
pattern = sys.argv[1].upper()
total = 0
numIter = 10000
for i in range(numIter):
    total += numTossesUntilPattern(pattern)

avg = float(total) / numIter
print "avg is %.1f" % (avg)