#!/usr/bin/env python
#
# Iocaine Powder
# Originally devised by Dan Egnor for the first annual RoShamBo
# programming competition.  Translated into python by David Bau.
# See http://ofb.net/~egnor/iocaine.html

import rps
import random


def recall(age, hist):
  """Looking at the last 'age' points in 'hist', finds the
  last point with the longest similarity to the current point,
  returning 0 if none found."""
  end, length = 0, 0
  for past in xrange(1, min(age + 1, len(hist) - 1)):
    if length >= len(hist) - past: break
    for i in xrange(-1 - length, 0):
      if hist[i - past] != hist[i]: break
    else:
      for length in xrange(length + 1, len(hist) - past):
        if hist[-past - length - 1] != hist[-length - 1]: break
      else: length += 1
      end = len(hist) - past
  return end

class Stats:
  def __init__(self):
    self.sum = [[0, 0, 0]]
  def add(self, move, score):
    self.sum[-1][move] += score
  def advance(self):
    self.sum.append(self.sum[-1])
  def max(self, age, default, score):
    if age >= len(self.sum): diff = self.sum[-1]
    else: diff = [self.sum[-1][i] - self.sum[-1 - age][i] for i in xrange(3)]
    m = max(diff)
    if m > score: return diff.index(m), m
    return default, score

class Predictor:
  def __init__(self):
    self.stats = Stats()
    self.lastguess = -1
  def addguess(self, lastmove, guess):
    if lastmove != -1:
      diff = (lastmove - self.prediction) % 3
      self.stats.add(rps.beat(diff), 1)
      self.stats.add(rps.loseto(diff), -1)
      self.stats.advance()
    self.prediction = guess
  def bestguess(self, age, best):
    bestdiff = self.stats.max(age, (best[0] - self.prediction) % 3, best[1])
    return (bestdiff[0] + self.prediction) % 3, bestdiff[1]

ages = [1000, 100, 10, 5, 2, 1]

class Iocaine:
  def __init__(self):
    self.predictors = []
    self.predict_history = self.predictor((len(ages), 2, 3))
    self.predict_frequency = self.predictor((len(ages), 2))
    self.predict_fixed = self.predictor()
    self.predict_random = self.predictor()
    self.predict_meta = [Predictor() for a in xrange(len(ages))]
    self.stats = [Stats() for i in xrange(2)]
    self.histories = [[], [], []]
  def predictor(self, dims=None):
    if dims: return [self.predictor(dims[1:]) for i in xrange(dims[0])]
    self.predictors.append(Predictor())
    return self.predictors[-1]
  def move(self, them):
    if them != -1:
      self.histories[1].append(them)
      self.histories[2].append((self.histories[0][-1], them))
      for watch in xrange(2):
        self.stats[watch].add(self.histories[watch][-1], 1)
    rand = random.randrange(3)
    for a, age in enumerate(ages):
      best = [recall(age, hist) for hist in self.histories]
      for mimic in xrange(2):
        for watch, when in enumerate(best):
          if not when: move = rand
          else: move = self.histories[mimic][when]
          self.predict_history[a][mimic][watch].addguess(them, move)
        mostfreq, score = self.stats[mimic].max(age, rand, -1)
        self.predict_frequency[a][mimic].addguess(them, mostfreq)
    self.predict_random.addguess(them, rand)
    self.predict_fixed.addguess(them, 0)
           
    for meta, age in enumerate(ages):
      best = (-1, -1)
      for predictor in self.predictors:
        best = predictor.bestguess(age, best)
      self.predict_meta[meta].addguess(them, best[0])
 
    best = (-1, -1)
    for meta in xrange(len(ages)):
      best = self.predict_meta[meta].bestguess(age, best) 
    self.histories[0].append(best[0])
    return best[0]

iocaine = Iocaine()
last = -1
for turn in xrange(rps.turns):
  last = rps.play(iocaine.move(last))