chuckbot8

This program has been disqualified.

Source code:

from collections import defaultdict
from heapq import nlargest
from operator import itemgetter
import random

class Counter(dict):
	def __init__(self, iterable=[], **kwds):
		self.update(iterable, **kwds)

	def __missing__(self, key):
		return 0

	def most_common(self, n=None):
		if n is None:
			return sorted(self.iteritems(), key=itemgetter(1), reverse=True)
		return nlargest(n, self.iteritems(), key=itemgetter(1))

	def update(self, iterable=None, **kwds):
		if iterable is not None:
			if hasattr(iterable, 'iteritems'):
				if self:
					self_get = self.get
					for elem, count in iterable.iteritems():
						self[elem] = self_get(elem, 0) + count
				else:
					dict.update(self, iterable) # fast path when counter is empty
			else:
				self_get = self.get
				for elem in iterable:
					self[elem] = self_get(elem, 0) + 1
		if kwds:
			self.update(kwds)

	def __add__(self, other):
		if not isinstance(other, Counter):
			return NotImplemented
		result = Counter()
		for elem in set(self) | set(other):
			newcount = self[elem] + other[elem]
			if newcount > 0:
				result[elem] = newcount
		return result

	def __mul__(self, other):
		if not isinstance(other, int):
			return NotImplemented
		result = Counter()
		for elem in self:
			newcount = self[elem]*other
			if newcount > 0:
				result[elem] = newcount
		return result


def buildMC(history, op_history, order):
	prev = tuple(history[-order:])
	n = len(history)
	hist = Counter()
	for i in xrange(order, n-1):
		tup = tuple(history[i-order:i])
		if tup == prev:
			hist.update((op_history[i],))
	normHist(hist)
	return hist

def normHist(hist):
	n = float(sum(hist.itervalues()))
	if n > 0:
		for key, val in hist.iteritems():
			hist[key] = val/n


if input == '':
	history = []
	op_history = []
	hist_maxlen = 300
	order = 4
	order_weights = [1]*(order+1)
	predictions = [None]*(order+1)
else:
	op_history.append(input)
	for i in xrange(1, order+1):
		if predictions[i] == input:
			order_weights[i] += 1

if len(history) > hist_maxlen:
	remove = hist_maxlen-len(history)
	history = history[remove:]
	op_history = op_history[remove:]

if len(history) >= 100:
	cnt = Counter()
	for i in xrange(1, order+1):
		hist = buildMC(history, op_history, i)
		pred = hist.most_common(1)
		if len(pred) == 0:
			predictions[i] = None
		else:
			predictions[i] = pred[0][0]
		cnt += hist*order_weights[i]
	most_frequent = cnt.most_common(1)

	if len(most_frequent) == 0:
		output = random.choice(["R","P","S"])
	else:
		reaction, freq = most_frequent[0]
		beat = {'R': 'P', 'P': 'S', 'S': 'R'}
		output = beat[reaction]
else:
	output = random.choice(["R","P","S"])


history.append(output)