def T(a, s, s_prime):
#CENTER, INNER_RING, FIRST_PATCH, MIDDLE_RING, SECOND_PATCH, OUTER_RING, MISS = range(7)
  delta = s - s_prime
  p = 0.0
  probs = [.1, .2, .4, .2, .1]
  
  throw.init_board()
  
  if delta > 3*throw.NUM_WEDGES or delta < 0:
    return 0
  
  for ri in range(5):
    for wi in range(5):
      wedge_num = throw.wedges[(throw.angles[a.wedge] - 2 + wi) %
                               throw.NUM_WEDGES]
      ring_num = a.ring - 2 + ri;
      if ring_num > 6:
        ring_num = 6
      if ring_num < 0:
        ring_num = ring_num*(-1)
      
      points = throw.location_to_score(throw.location(ring_num, wedge_num))
      if points == delta:
        p += probs[ri]*probs[wi]
  return p

def T(a, s, s_prime):
  # takes an action a, current state s, and next state s_prime
  # returns the probability of transitioning to s_prime when taking action a in state s

  #so let's iterate over the possible places on the board we will hit and add up the ones that give the right score reduction

  if(s_prime>s):
    return 0.0

  if(s == 0 and s_prime == 0):
    return 1.0

  regions = {CENTER:0, INNER_RING:1, FIRST_PATCH:2, MIDDLE_RING:3, SECOND_PATCH:4,OUTER_RING:5,MISS:6}


  actions = darts.get_actions()

  score_diff = s-s_prime

  prob = 0.0

  wedge = throw.angles[a.wedge]
  ring = a.ring
  for wdel in range(-2,3):
    for rdel in range(-2,3):
      wedge_p = throw.wedges[(wdel+wedge)%NUM_WEDGES]
      ring_p = abs(ring+rdel)
      dscore = throw.location_to_score(throw.location(ring_p,wedge_p))
      if(dscore == score_diff):
        prob += 0.4/(2**abs(wdel))*0.4/(2**abs(rdel))
  return prob

def T(a, s, s_prime):
  # takes an action a, current state s, and next state s_prime
  # returns the probability of transitioning to s_prime when taking action a in state s

  p_transition = 0.0
  probabilities = [0.4, 0.2, 0.2, 0.1, 0.1]

  # trick to allow wrap around
  wedge_list = throw.wedges*3

  # calculate all 5 wedges you could end up in when aiming for a.wedge
  wedge_index = len(throw.wedges) + throw.wedges.index(a.wedge)
  candidate_wedges = [wedge_list[wedge_index], wedge_list[wedge_index+1], wedge_list[wedge_index-1], wedge_list[wedge_index+2], wedge_list[wedge_index-2]]

  # calulate all 5 regions/rings (some may be the same) you could end up in when aiming for a.ring, with prob array
  if a.ring == throw.CENTER:
    candidate_rings = [a.ring, throw.INNER_RING, throw.INNER_RING, throw.FIRST_PATCH, throw.FIRST_PATCH]
  elif a.ring == throw.INNER_RING:
    candidate_rings = [a.ring, throw.FIRST_PATCH, throw.CENTER, throw.MIDDLE_RING, throw.INNER_RING]
  else:
    candidate_rings = [a.ring, a.ring+1, a.ring-1, a.ring+2, a.ring-2]

  # for each (ring, wedge) pair, calculate point value, and check if it gets you from s to s_prime
  for w in range(len(candidate_wedges)):
    for r in range(len(candidate_rings)):
      # instantiation of location class
      real_location = throw.location(candidate_rings[r],candidate_wedges[w])
      if s - throw.location_to_score(real_location) == s_prime:
        p_transition += probabilities[r]*probabilities[w]

  return p_transition

def T(a, s, s_prime):
  # takes an action a, current state s, and next state s_prime
  # returns the probability of transitioning to s_prime when taking action a in state s
  if (T_CACHE.has_key((a,s,s_prime))):
    return T_CACHE[(a,s,s_prime)]

  def prob(i):
    if i == 0:
      return .4
    if abs(i) == 1:
      return .2
    if abs(i) == 2:
      return .1

  # Useful local variables
  diff = s - s_prime
  wedge_index = throw.wedges.index(a.wedge)

  # Set ring
  for r in [-2,-1,0,1,2]:
    ring = abs(a.ring+r)
    if ring > 7:
      ring = 7
    # Set wedge
    for w in [-2,-1,0,1,2]:
      wedge = throw.wedges[(wedge_index+w) % len(throw.wedges)]
      # Get score
      score = throw.location_to_score(
        throw.location(ring, wedge))
      if score == diff:
        ret = prob(r) * prob(w)
        T_CACHE[(a,s,s_prime)] = ret
        return ret
  return 0.

def T(a, s, s_prime):
  total_prob = 0.0
  for w in [x-2 for x in range(5)]:
    wedgefactor = 0.0
    if abs(w)==0: 
      wedgefactor = 0.4
    if abs(w)==1:
      wedgefactor = 0.2
    if abs(w)==2:
      wedgefactor = 0.1
    
    wedge = (a.wedge + w) % throw.NUM_WEDGES
    # this area
    for r in [x-2 for x in range(5)]:
      ringfactor = 0.0
      if abs(r)==0: 
        ringfactor = 0.4
      if abs(r)==1:
        ringfactor = 0.2
      if abs(r)==2:
        ringfactor = 0.1

      ring = abs(a.ring + r)
      if throw.location_to_score(throw.location(ring,wedge))==(s-s_prime):
        total_prob += ringfactor * wedgefactor
    
  return total_prob

 def test_T(self) :
     def act(r,w):
             return throw.location(r,w)
     
     self.assertEqual(mdp.T( act(throw.CENTER, 1), 100, 110), 0.0) 
     self.assertEqual(mdp.T( act(throw.CENTER, 1), 100, 80), mdp.T( act(throw.CENTER,1), 90, 70));
     bullseye = throw.location_to_score(throw.location(throw.CENTER, 1));
     self.assertEqual( mdp.T(act(throw.FIRST_PATCH, 1), 100, 100-bullseye), 0.1);  
     self.assertAlmostEqual( mdp.T(act(throw.INNER_RING, 1), 100, 95), 0.5);  

def T(a, s, s_prime):
    global T_cached

    if (a, s, s_prime) in T_cached:
        return T_cached[(a, s, s_prime)]

    # takes an action a, current state s, and next state s_prime
    # returns the probability of transitioning to s_prime when taking action a in state s
    target = s - s_prime
    target_locations = []
    p = 0.0

    # find all wedge/ring combos that would lead to s -> s' transition
    for i in range(-2, 3):
        current_wedge = get_adj_wedge(a.wedge, i)

        # iterate through all possible rings
        for j in range(-2, 3):
            ring = a.ring + j

            # off dart board
            if ring >= throw.MISS:
                continue

            # allow for ring "wrap around", e.g. the ring inside and outside the center
            # ring is the inner ring
            if ring < 0:
                ring = abs(ring)

            new_location = throw.location(ring, current_wedge)

            # hitting target would go from s -> s'!
            if target == throw.location_to_score(new_location):
                # calculate probability of hitting target
                if i == 0:
                    w_p = 0.4
                elif abs(i) == 1:
                    w_p = 0.2
                elif abs(i) == 2:
                    w_p = 0.1
                else:
                    assert False, "Impossible wedge"

                if j == 0:
                    r_p = 0.4
                elif abs(j) == 1:
                    r_p = 0.2
                elif abs(j) == 2:
                    r_p = 0.1
                else:
                    assert False, "Impossible ring"

                p += w_p * r_p

    T_cached[(a, s, s_prime)] = p
    return p

def start_game():
    global states, actions, Q
    states = darts.get_states()
    actions = darts.get_actions()

    for s in states:
        Q[s] = {}
        for a in range(len(actions)):
            Q[s][a] = 0

    return throw.location(throw.INNER_RING, throw.NUM_WEDGES)

def T(a, s, s_prime):
    # takes an action a, current state s, and next state s_prime
    # returns the probability of transitioning to s_prime when taking action a in state s
    # figure out where would give you that many points
    # figure out the probability of landing there
    prob = 0
    points = s - s_prime
    if points < 0:
        return 0
    #print points
    
    # Loop through to define transition function
    for i in range(-2,2):
        wedge_curr = (throw.wedges.index(a.wedge) + i)
        # Mod by number of wedges to wrap around if needed
        if wedge_curr >= throw.NUM_WEDGES:
            wedge_curr = wedge_curr%throw.NUM_WEDGES
        prob_wedge = 0.4/(pow(2, abs(i)))
        
        for j in range(-2,2):
            ring_curr = (a.ring + j)
            if ring_curr < 0:
                ring_curr = ring_curr % 7
            prob_ring = 0.4/(pow(2, abs(j)))
            
            '''if (a.ring == 0 and j < 0):
                ring_curr = 7 - ring_curr
            if (a.ring == 1 and j < -1):
                ring_curr = 7 - ring_curr'''
                
            if a.ring == 0:
                ring_curr = 7 - ring_curr
                if ring_curr == 0:
                    prob_ring = 0.4
                if ring_curr == 1:
                    prob_ring == 0.4
                if ring_curr == 2:
                    prob_ring = 0.2
            if a.ring == 1:
                ring_curr = 7 - ring_curr
                if ring_curr == 0:
                    prob_ring == 0.2
                if ring_curr == 1:
                    prob_ring = 0.5
                if ring_curr == 2:
                    prob_ring = 0.2
                if ring_curr == 3:
                    prob_ring == 0.1
            
            #print a.wedge, a.ring, j, i
            if(throw.location_to_score(throw.location(ring_curr, wedge_curr)) == points):
                prob += prob_wedge*prob_ring
                #print a.ring, j, i
    return prob

def EPoints(a, s):
  probs = [0.4, 0.2, 0.1, 0.1, 0.2]
  total = 0.

  for r_off in [-2, -1, 0, 1, 2]:
    for w_off in [-2, -1, 0, 1, 2]:
      r2 = min(throw.MISS, abs(a.ring + r_off))
      w2 = throw.wedges[(throw.wedges.index(a.wedge) + w_off) % len(throw.wedges)]
      score = throw.location_to_score(throw.location(r2, w2))
      if score > s:
        score = 0.
      total += probs[r_off] * probs[w_off] * score

  return total

def get_actions():
  global actions
  for wedge in throw.wedges:
    actions = actions + [throw.location(throw.CENTER, wedge)]
    actions = actions + [throw.location(throw.INNER_RING, wedge)]
    actions = actions + [throw.location(throw.FIRST_PATCH, wedge)]
    actions = actions + [throw.location(throw.MIDDLE_RING, wedge)]
    actions = actions + [throw.location(throw.SECOND_PATCH, wedge)]
    actions = actions + [throw.location(throw.OUTER_RING, wedge)]
  return actions

def start_game():
  global last_score, last_action, actions

  if last_score is None:
    actions = darts.get_actions()
    for s in darts.get_states():
      Q[s] =  {}
      for a in actions:
        Q[s][a] = 0.

  last_score = throw.START_SCORE

  print >>sys.stderr, 'start'

  last_action = throw.location(throw.INNER_RING, throw.NUM_WEDGES)
  print >>sys.stderr, last_action
  return last_action

def T(a, s, s_prime):
  # takes an action a, current state s, and next state s_prime
  # returns the probability of transitioning to s_prime when taking action a in state s
  possible_rings = []
  ring_prob = []
  if (a.ring == throw.CENTER):
    possible_rings = [throw.CENTER,throw.INNER_RING,throw.FIRST_PATCH]
    ring_prob = [PROBRING,2*PROBR1,2*PROBR2]
  elif (a.ring == throw.INNER_RING):
    possible_rings = [throw.CENTER,throw.INNER_RING,throw.FIRST_PATCH,throw.MIDDLE_RING]
    ring_prob = [PROBR1,PROBRING+PROBR1,PROBR1,PROBR2]
  elif (a.ring == throw.FIRST_PATCH):
    possible_rings = [throw.CENTER,throw.INNER_RING,throw.FIRST_PATCH,throw.MIDDLE_RING,throw.SECOND_PATCH]
    ring_prob = [PROBR2,PROBR1,PROBRING,PROBR1,PROBR2]
  elif (a.ring == throw.MIDDLE_RING):
    possible_rings = [throw.INNER_RING,throw.FIRST_PATCH,throw.MIDDLE_RING,throw.SECOND_PATCH,throw.OUTER_RING]
    ring_prob = [PROBR2,PROBR1,PROBRING,PROBR1,PROBR2]
  elif (a.ring == throw.SECOND_PATCH):
    possible_rings = [throw.FIRST_PATCH,throw.MIDDLE_RING,throw.SECOND_PATCH,throw.OUTER_RING,throw.MISS]
    ring_prob = [PROBR2,PROBR1,PROBRING,PROBR1,PROBR2]
  elif (a.ring == throw.OUTER_RING):
    possible_rings = [throw.MIDDLE_RING,throw.SECOND_PATCH,throw.OUTER_RING,throw.MISS]
    ring_prob = [PROBR2,PROBR1,PROBRING,PROBR1+PROBR2]
  elif (a.ring == throw.OUTER_RING):
    possible_rings = [throw.MIDDLE_RING,throw.SECOND_PATCH,throw.OUTER_RING,throw.MISS]
    ring_prob = [PROBR2,PROBR1,PROBRING,PROBR1+PROBR2]
  elif (a.ring == throw.MISS):
    possible_rings = [throw.SECOND_PATCH,throw.OUTER_RING,throw.MISS]
    ring_prob = [PROBR2,PROBR1,PROBRING+PROBR1+PROBR2]

  w_index = throw.wedges.index(a.wedge)
  possible_wedges = [(a.wedge),(throw.wedges[(w_index+1)%throw.NUM_WEDGES]),(throw.wedges[(w_index-1)%throw.NUM_WEDGES]),(throw.wedges[(w_index+2)%throw.NUM_WEDGES]),(throw.wedges[(w_index-2)%throw.NUM_WEDGES])]
  wedge_prob = [PROBWEDGE,PROBW1,PROBW1,PROBW2,PROBW2]

  final_prob = 0

  for i in range(len(possible_rings)):
    for j in range(len(possible_wedges)):
      myloc = throw.location(possible_rings[i],possible_wedges[j])
      if (s - (throw.location_to_score(myloc))) == s_prime:
          final_prob = final_prob + (ring_prob[i]*wedge_prob[j])
  return final_prob

def T(a, s, s_prime):
  # takes an action a, current state s, and next state s_prime
  # returns the probability of transitioning to s_prime when taking action a in state s
  if s_prime > s:
    return 0.

  probs = [0.4, 0.2, 0.1, 0.1, 0.2]
  total = 0.

  for r_off in [-2, -1, 0, 1, 2]:
    for w_off in [-2, -1, 0, 1, 2]:
      r2 = min(throw.MISS, abs(a.ring + r_off))
      w2 = throw.wedges[(throw.wedges.index(a.wedge) + w_off) % len(throw.wedges)]
      score = throw.location_to_score(throw.location(r2, w2))
      if score > s:
        score = 0.
      if score == s - s_prime:
        total += probs[r_off] * probs[w_off]

  return total

def T(a, s, s_prime):
  # takes an action a, current state s, and next state s_prime
  # returns the probability of transitioning to s_prime when taking action a in state s
  
  probability = 0.0

  # -2 -1 0 1 2
  for w in range(-2, 3):
    # hit the wedge (0)
    if abs(w) == 0:
      p_wedge = 0.4
    # hit region outside the wedge (-1 or 1)
    elif abs(w) == 1:
      p_wedge = 0.2
    # hit region outside of that (-2 or 2)
    else:
      p_wedge = 0.1

    # get the wedge and do % to loop around in case of going around circle
    wedge = (a.wedge + w) % throw.NUM_WEDGES

    # same thing, but now for the ring
    for r in range(-2, 3):
      # hit the ring
      if abs(r) == 0:
        p_ring = 0.4
      # hit region outside the ring
      elif abs(r) == 1:
        p_ring = 0.2
      # hit region outside of that
      else:
        p_ring = 0.1

      # get the ring and do % to loop around in case of going around circle
      ring = abs(a.ring + r)

      score = throw.location_to_score(throw.location(ring, wedge))
      if score == s - s_prime:
        probability += p_wedge * p_ring

  return probability

def T(a, s, s_prime):
  # takes an action a, current state s, and next state s_prime
  # returns the probability of transitioning to s_prime when taking action a in state s
  aRing = a.ring
  aWedge = a.wedge
  target = s - s_prime

  probs = [0.4, 0.2, 0.1]

  probability = 0
  for i in range (-2, 3):
    w = (throw.wedges.index(a.wedge) + i) % len(throw.wedges)
    wedge = throw.wedges[w]
    for j in range(-2, 3):
      ring = min(abs(aRing + j), 6)
      loc = throw.location(ring, wedge)
      score = throw.location_to_score(loc)
      if target == score:
        probability += probs[abs(i)] * probs[abs(j)]

  return probability

def get_target(score):

  if score <= throw.NUM_WEDGES: return throw.location(throw.SECOND_PATCH, score)
  
  return(throw.location(throw.INNER_RING, throw.NUM_WEDGES))

def start_game():

  return(throw.location(throw.INNER_RING, throw.NUM_WEDGES))

 def act(r,w):
         return throw.location(r,w)