import random, math, re, pickle
class Markov:
	def __init__(self):
		self.dict = {}
		self.stripre = re.compile(r'\s+')

	def add(self, text, weight=0):
		x = 1
		text = self.stripre.sub(' ', text).split(' ')
		for word in text:
			previous = text[x-1]
			try: word = text[x]
			except: word = None

			try: self.dict[previous]
			except: self.dict[previous] = {}

			try: self.dict[previous][word] += float(1 + weight)
			except: self.dict[previous][word] = float(1 + weight)

			x = x + 1
		# {'bd': {'a': 1}, 'ca': {'b': 1}, 'ab': {'c': 2, 'd': 1}, 'da': {'b': 1}, 'bc': {'a': 1, None: 1}}
		return self.dict

	def walk(self, seed):
		try: prob = self.dict[seed]
		except: prob = self.dict[random.choice(self.dict.keys())]
		self.weighted = []
		for key, value in prob.items():
			for x in range(int(value)):
				self.weighted.append(key)
		result = random.choice(self.weighted)
		return result

	def sentance(self, length=10, seed='default', postimes=50):
		while seed == "default" or seed.endswith('.'): seed = random.choice(self.dict.keys())
		ending = random.choice(self.dict.keys())
		sentance = None
		for x in range(postimes):
			key = random.choice(self.dict.keys())
			if key.endswith('.'):
				ending = key
				break

		if seed == None or seed == "": sentance = self.walk(seed)
		else: sentance = seed
		for x in range(length-2):
			s = self.walk(sentance.split(' ')[x])
			if s == None: break
			while s == sentance.split(' ')[x]: s = self.walk(sentance.split(' ')[x])
			sentance = sentance + ' ' + s


		sentance = sentance + ' ' + ending
		return sentance + "\n"

	def respondTo(self, msg):
		return self.sentance(seed=random.choice(sorted(msg.split(' '), lambda x, y: len(y)-len(x))[:3]), length=random.choice(range(10,15)))

	def save(self, filename):
		fh = open(filename, 'w')
		pickle.dump(self.dict, fh)
		fh.close()

	def load(self, filename):
		try:
			fh = open(filename, 'r')
			self.dict = pickle.load(fh)
			fh.close()
		except:
			print "File not found. Not loaded. " + str(filename)

def test():
	m = Markov()
	m.add("dog cat dog cat dog chicken")
	cs = 0
	ds = 0
	ratios = []
	average = float(0)
	for i in range(500):
		for i in range(500):
			if m.walk("dog") == "cat":
				cs = cs + 1
			else:
				ds = ds + 1
		ratio = float(cs)/float(ds)
		ratios.append(ratio)
	print ratios
	for item in ratios:
		average = average + item
	average = average / float(len(ratios))
	print "------------------------------------\nIdeal: 2"
	print "Average: %f" % average
	print "Margin of error: %f%%" % (((2 - average)/2) * 100)

if __name__ == "__main__":
	test()