def checkTerrain(self, c):

        #Confirm current region
        c.resetRegion()
        if c.region is None:
            for r in self.regions:
                dist = util.distance(c.precisePos, r.pos)
                if dist <= MAP_REGION_SIZE:
                    c.region = r
                    break

        #Check for Fortress
        for i in self.structures:
            sTeam = i.team
            cTeam = c.team + 1
            if isinstance(i, mapstructure.Fortress) and (sTeam == cTeam):
                dist = util.distance(c.precisePos, i.precisePos)
                if (dist <= i.triggerSize):
                    c.currTerrain = FORTRESS
                    return
                 
        #Check all terrain circles in current region
        for i in c.region.terrainMasterList:
            circle = i[0]
            terrainType = i[1]
            dist = util.distance(c.precisePos, circle[0])
            if dist <= circle[1]:
                terrainType = self.terrainBasedOnWinter(terrainType, c)
                c.currTerrain = terrainType
                return

        c.currTerrain = self.terrainBasedOnWinter(PLAINS, c)

    def connected_to(self, res, cutoff=3.0):
        """
		Determine if another residue is connected to this residue, returns 0
		if res is not connected to self, returns 1 if connection is going
		from 5' to 3' and returns -1 if connection is going from 3' to 5'

        :param res: another residue
        :type res: Residue object

        """
        # 5' to 3'
        o3_atom = self.get_atom("O3'")
        p_atom = res.get_atom("P")
        if o3_atom and p_atom:
            if util.distance(o3_atom.coords, p_atom.coords) < cutoff:
                return 1

        # 3' to 5'
        p_atom = self.get_atom("P")
        o3_atom = res.get_atom("O3'")
        if o3_atom and p_atom:
            if util.distance(o3_atom.coords, p_atom.coords) < cutoff:
                return -1

        return 0

 def initialize(self):
     setupGraphs(self) # inits self.graph
     self.verbose = True
     self.bots = set()
     self.defenders = []
     self.attackers = []
     self.flagGetters = []
     self.scouts = []
     teamPosition, isTeamCorner = self.getStrategicPostion(self.game.team.flag.position)
     teamPosition = self.level.findNearestFreePosition(teamPosition)
     teamDirs = self.getDefendingDirs(teamPosition)
     enemyPosition, isEnemyCorner = self.getStrategicPostion(self.game.enemyTeam.flagScoreLocation)
     enemyPosition = self.level.findNearestFreePosition(enemyPosition)
     enemyDirs = self.getDefendingDirs(enemyPosition)
     for i, bot_info in enumerate(self.game.bots_available):
         bot = Bot(bot_info, self)
         if i < self.numOfDefenders:                
             self.defenders.append(bot)
         elif self.numOfDefenders <= i < self.numOfFlagGetters + self.numOfDefenders:
             self.flagGetters.append(bot)
         elif i %3 == 0 or len(self.attackers) < 2:
             self.attackers.append(bot)
         elif i %3 == 1:
             self.defenders.append(bot)
         else:
             self.flagGetters.append(bot)
             
     #TODO: priority decided based on distance
     teamPriority = 1 if distance(self.level.findRandomFreePositionInBox(self.game.team.botSpawnArea), teamPosition) < 25 else 0
     self.defendingGroup = Squad(self.defenders, Goal(Goal.DEFEND, teamPosition, isTeamCorner, priority=teamPriority, graph=self.graph, dirs=teamDirs), commander=self)
     enemyPriority = 1 if distance(self.level.findRandomFreePositionInBox(self.game.team.botSpawnArea), enemyPosition) < 25 else 0
     self.attackingGroup = Squad(self.attackers, Goal(Goal.DEFEND, enemyPosition, isEnemyCorner, priority=enemyPriority, graph=self.graph, dirs=[(self.game.enemyTeam.flagScoreLocation - enemyPosition, 1)]), commander=self)
     self.flagGroup = Squad(self.flagGetters, Goal(Goal.GETFLAG, None, None, graph=self.graph))
     self.squads = [self.defendingGroup, self.attackingGroup,self.flagGroup]

 def findMoveTarget(self, unit):
       enemies = [i for i in self.bots if i.getOwner() == 0 and self.playerID() == 1 and i.getPartOf() == 0 or i.getOwner() == 1 and self.playerID() == 0 and i.getPartOf() == 0]
       targetDist = util.distance(unit.getX(),unit.getY(),unit.getSize(),enemies[0].getX(),enemies[0].getY(),enemies[0].getSize())
       target = enemies[0]
       for e in enemies:
         if util.distance(unit.getX(),unit.getY(),unit.getSize(),e.getX(),e.getY(),e.getSize()) < targetDist:
           target = e
           targetDist = util.distance(unit.getX(),unit.getY(),unit.getSize(),e.getX(),e.getY(),e.getSize())
       return target

 def distancetest(self):
   print ''
   print '  c 0 1 2 3 4 5 6 7 8 9 X E'
   print 'r   - - - - - - - - - - - -'
   for r in range(self.width()):
     print str(r) + ' |',
     for c in range(self.height()):
       print util.distance([0,0], [r,c]) % 10,
     print '| ' + str(r)
   print '    - - - - - - - - - - - -'
   print '    0 1 2 3 4 5 6 7 8 9 X E'
   print ''

 def update_with_sr(self, sr):
   '''
   Adds the following to a filled-out Ride
    - distance to the original request location
    - distance to the closest destination
   '''
   self.search_request = sr
   self.start_distance = util.distance(
       (sr.start_lat,sr.start_long),
       (self.requests[0].start_lat, self.requests[0].start_long))
   self.end_distance = min([
     util.distance(
       (sr.end_lat,sr.end_long),
       (r.end_lat, r.end_long)) for r in self.requests])

    def checkForStop(self):
        if not self.target is None:
            currDist = util.distance(self.precisePos, self.target)

            nextLoc = []
            for i in range(2):
                nextLoc.append(self.precisePos[i] + self.vel[i]) 
            nextDist = util.distance(nextLoc, self.target)
            if nextDist > currDist:
                if len(self.targetBuffer) > 0:
                    self.target = self.targetBuffer[0]
                    self.targetBuffer = self.targetBuffer[1:]
                    self.startMovement()
                else:
                    self.stop()

def irregular_galaxy_calc_positions(positions, adjacency_grid, size, width):
    """
    Calculate positions for the irregular galaxy shape.
    """
    max_delta = max(min(float(universe_tables.MAX_STARLANE_LENGTH), width / 10.0), adjacency_grid.min_dist * 2.0)
    print "Irregular galaxy shape: max delta distance = {}".format(max_delta)
    origin_x, origin_y = width / 2.0, width / 2.0
    prev_x, prev_y = origin_x, origin_y
    reset_to_origin = 0
    for _ in range(size):
        attempts = 100
        found = False
        while (attempts > 0) and not found:
            attempts -= 1
            x = prev_x + uniform(-max_delta, max_delta)
            y = prev_y + uniform(-max_delta, max_delta)
            if util.distance((x, y), (origin_x, origin_y)) > width * 0.45:
                prev_x, prev_y = origin_x, origin_y
                reset_to_origin += 1
                continue
            found = not adjacency_grid.too_close_to_other_positions((x, y))
            if attempts % 10:
                prev_x, prev_y = x, y
        if found:
            pos = (x, y)
            adjacency_grid.insert_pos(pos)
            positions.append(pos)
        prev_x, prev_y = x, y
    print "Reset to origin {} times".format(reset_to_origin)

def stitching_positions(p1, p2):
    """
    Returns a list of positions between p1 and p2 between MIN_SYSTEM_SEPARATION and MAX_STARLANE_LENGTH apart
    """
    if 2 * universe_tables.MIN_SYSTEM_SEPARATION >= universe_tables.MAX_STARLANE_LENGTH:
        util.report_error("MAX_STARLANE_LENGTH must be twice MIN_SYSTEM_SEPARATION to "
                          "allow extra positions to be added to enforce MAX_STARLANE_LENGTH")
        return []

    max_dist = universe_tables.MAX_STARLANE_LENGTH
    min_dist = universe_tables.MIN_SYSTEM_SEPARATION
    p1_p2_dist = util.distance(p1, p2)
    if p1_p2_dist < max_dist:
        return []

    # Pick a random point in an 2:1 ratio ellipse and then rotate and slide it in between p1 and p2
    p1_p2_theta = acos((p2[0] - p1[0]) / p1_p2_dist)
    p1_p2_scale = (p1_p2_dist - 2*min_dist) / 2
    p1_p2_translation = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)

    radius_0space = uniform(0.0, 1.0)
    angle_0space = uniform(0.0, 2.0 * pi)
    rotated_point = (radius_0space * p1_p2_scale * cos(angle_0space + p1_p2_theta),
                     radius_0space * p1_p2_scale * sin(angle_0space + p1_p2_theta))

    p3 = (rotated_point[0] + p1_p2_translation[0], rotated_point[1] + p1_p2_translation[1])

    return [p3] + stitching_positions(p1, p3) + stitching_positions(p2, p3)

	def evaluation_function(self, node_id, cur_days):
		"""
		Evaluation function: if I add node_id to the job schedule, how good is it?
		@author Aaron Nagao

		@param <String> node_id = id of the job I am evaluating
		@return <float> estimate of the value of choosing node_id. Higher value = better choice.

		TODO: change manual weights of 1 to learned weights

		Features for evaluation function:
		# 1) Number of miles required to fulfill this job
		# 2) price of this job
		# 3a) After we deliver this job, how many other jobs are in the area?
		# 3b) After we deliver this job, what's the average price of other jobs in the delivery area?
		# TODO: avg gas price in the area?
		"""
		# key: <String>featureName => value: <tuple>(weight, featureValue)
		# Positive weights for good features.
		return 0
		features = dict()

		"""
		# First, check whether I can finish this job in time
		prevEnd_nextStart_nextEnd = self.distance_matrix[(prevJob['_id']['$oid'], nextJob['_id']['$oid'])] # miles required to drive to next job and fulfill next job (prevJob.end => nextJob.start => nextJob.end)
		
		(from_lng, from_lat) = nextJob['deliveryAddress']['location']['coordinates']
  		(to_lng, to_lat) = (self.start_lng, self.start_lat)
		nextEnd_home = util.distance(from_lat, from_lng, to_lat, to_lng)
		
		sumDays_nextJobAndHome = ( (prevEnd_nextStart_nextEnd + nextEnd_home) / util.MPH ) / 24 # day = miles / miles/hr / 24hr/day
		if cur_days + sumDays_nextJobAndHome > self.max_days:
			return float('-inf') # cannot take on this job
		"""
		
		# 1) Number of miles required to fulfill this job
		# negative weight (prefer shorter jobs)
		features['jobMiles'] = (-.2, util.distance(*self.graph.jobs[node_id]['pickup']+self.graph.jobs[node_id]['delivery']))

		# 2) price of this job
		features['jobPrice'] = (0.3, self.graph.jobs[node_id]['price'])
		
		# 3a) After we deliver this job, how many other jobs are in the area?
		(to_lat, to_lng) = self.graph.jobs[node_id]['delivery']
		to_i, to_j = int(to_lat), int(to_lng)  
		jobsInDeliveryArea = self.graph.delivery_grid[ (to_i, to_j) ]
		numJobsInDeliveryArea = len(jobsInDeliveryArea)
		features['numJobsInDeliveryArea'] = (0.3, numJobsInDeliveryArea)

		# 3b) After we deliver nextJob, what's the average price of other jobs in the delivery area?
		if numJobsInDeliveryArea == 0:
			avgPriceInDeliveryArea = 0
		else:
			avgPriceInDeliveryArea = sum([self.graph.get_price(job) for job in jobsInDeliveryArea]) / numJobsInDeliveryArea
		features['avgPriceInDeliveryArea'] = (0.1, avgPriceInDeliveryArea)
		
		# print features
		heur_score = sum([ v[0]*v[1] for k,v in features.iteritems() ]) / 10
		#print("heur score: " + str(heur_score))
		return heur_score # dot product of feature and its weight

 def heatAt(self, position):
     heat_from_sources = []
     for hs in self.hsources:
         dist = util.distance(position, hs.position)
         heat = hs.getHeat(dist)
         heat_from_sources.append(heat)
     return sum(heat_from_sources)

def check_distance_accuracy(jobs_file):
  distance_diffs = []
  c = 0
  total = 0
  with open(jobs_file) as f:
    for line in f:
      total += 1
      job = json.loads(line)
      if job['distanceInMiles'] <= 0: 
        c+= 1
        continue
      from_latlng = job['pickupAddress']['location']['coordinates']
      to_latlng = job['deliveryAddress']['location']['coordinates']
      geodesic_distance = util.distance(from_latlng[1], from_latlng[0], to_latlng[1], to_latlng[0])
      error = geodesic_distance/job['distanceInMiles']-1
      distance_diffs.append(error)

  print 'Missing distances: ', c/float(total)
  print 'Mean: ', numpy.mean(distance_diffs)
  print 'Stdev: ', numpy.std(distance_diffs)

  values = [int(p*100) for p in distance_diffs]
  counts = collections.Counter(values)
  X = sorted(counts.keys())
  Y = [counts[x] for x in X]
  

  fig = plt.figure()
  ax = fig.add_subplot(111)
  ax.plot(X, Y)
  ax.set_title('[Geodesic distance - Actual Distance] histogram')
  ax.set_xlabel('Miles')
  ax.set_ylabel('Count')
  plt.show()

    def resetRegion(self):
        if self.region is None:
            return

        if (util.distance(self.precisePos, self.region.pos) >
            MAP_REGION_SIZE):
            self.region = None

def getCorrespondencesForFace(selectedCorners, corners, currentFace, windowImage):
    h = compute2DHomography(selectedCorners)
    correspondences = []
    # for every possible corner in the face
    for x in range(0, BOX_NUM * 2):
        for y in range(0, BOX_NUM * 2):
            # project the possible corner (in the range [-1,1]x[-1,1]) into image space with the homography h
            scale = (BOX_NUM * 2 - 1.0) / 2.0
            projectedCorner = numpy.dot(h , numpy.array([x / scale - 1.0, y / scale - 1.0, 1]))
            projectedCorner /= projectedCorner[2]
            
            # find the closest corner from the corner detection set
            minDistance = 10000
            minCorner = None
            pos = (projectedCorner[0], projectedCorner[1])
            for corner in corners:
                dist = util.distance(corner, pos)
                if dist < minDistance:
                    minDistance = dist
                    minCorner = corner
            
            # check if the closest corner belongs to this corner -> add correspondence and paint a circle + the coordinates
            if minDistance < MIN_DISTANCE_THRESHOLD:
                coord3d = create3dCoord(currentFace, x + 1, y + 1)
                intPos = (int(pos[0] * ratio), int(pos[1] * ratio))
                cv.Circle(windowImage, intPos , 6, cv.RGB(0, 0, 255))
                # cv.PutText(windowImage, str(coord3d), intPos, DEFAULT_FONT , cv.RGB(0, 0, 255))
                correspondences.append((minCorner, coord3d))
            
    print("found " + str(len(correspondences)) + " correspondences")
    return correspondences

def PerformIDEACluster(clusters,test,dataset="Unknown", treatment="IDEACLUSTER", disregardY=False):
    Stats = DefectStats()
    if type(test[0].klass()) is str:
        for instance in test:
            Closest = [sys.maxint, None]
            for cluster in clusters:
                for quadrant in cluster.quadrants:
                    if distance(instance.Coord(), quadrant.center()) < Closest[0]:
                        Closest[0] = distance(instance.Coord(), quadrant.center())
                        Closest[1] = cluster
            train = []
            for quadrant in Closest[1].quadrants:
                train.extend(quadrant.ClassCoords())
            Stats.Evaluate(NaiveBayesClassify(instance.Coord(),train, disregardY), instance.klass())
        Stats.StatsLine(dataset, treatment)
    del Stats

def cornerProbabilityGivenParticleLocation(observation, particle):
  '''
  Calculates P(e|x_t), given that observation is the (scalar) distance
  to the corner
  TODO: r, theta = observation
  '''
  obs_dist, obs_heading = observation
  
  prob = 0.0
  for corner in corners:
    # calculate distance to corner
    distance = util.distance(particle[0:2], corner)
    # calculate the relative heading w.r.t particle position and heading
    heading = util.normalizeRadians(util.heading(particle[0:2], corner) - particle[2])
    
    # TODO tune sigmas
    # (assume P(e|x_t) ~ exp{-1/2 * |distance - obs_dist| / sigma_1^2} 
    #                    * exp{-1/2 * |heading - obs_heading| / sigma_2^2} )
    prob += numpy.exp(-0.1 * numpy.abs(distance - obs_dist) +
      -7 * numpy.abs(heading - obs_heading))
    '''
    if corner is corners[0]:
      print particle, 'hdg:', heading
      print numpy.exp(-0.1 * numpy.abs(distance - obs_dist) +
        -10 * numpy.abs(heading - obs_heading))
      print numpy.exp(-1 * numpy.abs(heading - obs_heading))
    '''
  
  return prob

 def initialize(self):
     if self.type == self.PROXIMAL:
         # Setup initial potential synapses for proximal segments
         n_inputs = self.region.n_inputs
         cell_x, cell_y = util.coords_from_index(self.cell.index, self.region._cell_side_len())
         for source in range(n_inputs):
             # Loop through all inputs and randomly choose to create synapse or not
             input_x, input_y = util.coords_from_index(source, self.region._input_side_len())
             dist = util.distance((cell_x, cell_y), (input_x, input_y))
             max_distance = self.region.diagonal
             chance_of_synapse = ((MAX_PROXIMAL_INIT_SYNAPSE_CHANCE - MIN_PROXIMAL_INIT_SYNAPSE_CHANCE) * (1 - float(dist)/max_distance)) + MIN_PROXIMAL_INIT_SYNAPSE_CHANCE
             add_synapse = random.random() < chance_of_synapse
             if add_synapse:
                 self.add_synapse(source)
     else:
         # Distal
         cell_index = self.cell.index
         for index in range(self.region.n_cells):
             if index == cell_index:
                 # Avoid creating synapse with self
                 continue
             chance_of_synapse = DISTAL_SYNAPSE_CHANCE
             add_synapse = random.random() < chance_of_synapse
             if add_synapse:
                 self.add_synapse(index, permanence=0.15)
     log_message = "Initialized %s" % self
     log(log_message)

def irregular2_galaxy_calc_positions(positions, size, width):
    """
    Calculate positions for the irregular2 galaxy shape
    """
    adjacency_grid = AdjacencyGrid(width)
    max_delta = max(min(float(fo.max_starlane_length()), width / 10.0), adjacency_grid.min_dist * 2.0)
    print "Irregular2 galaxy shape: max delta distance =", max_delta
    origin_x, origin_y = width / 2.0, width / 2.0
    prev_x, prev_y = origin_x, origin_y
    reset_to_origin = 0
    for n in range(size):
        attempts = 100
        found = False
        while (attempts > 0) and not found:
            attempts -= 1
            x = prev_x + uniform(-max_delta, max_delta)
            y = prev_y + uniform(-max_delta, max_delta)
            if util.distance(x, y, origin_x, origin_y) > width * 0.45:
                prev_x, prev_y = origin_x, origin_y
                reset_to_origin += 1
                continue
            found = not adjacency_grid.too_close_to_other_positions(x, y)
            if attempts % 10:
                prev_x, prev_y = x, y
        if found:
            pos = fo.SystemPosition(x, y)
            adjacency_grid.insert_pos(pos)
            positions.append(pos)
        prev_x, prev_y = x, y
    print "Reset to origin", reset_to_origin, "times"

 def refresh(self):
     tcod_map = self.game.dungeon.tcod_map
     if self.entity is self.game.player:
         libtcod.map_compute_fov(tcod_map,
                                 self.entity.x,
                                 self.entity.y,
                                 PLAYER_FOV_RADIUS)
     else:
         libtcod.map_compute_fov(tcod_map,
                                  self.entity.x,
                                  self.entity.y,
                                  self.creature.perception)
     if self.entity is self.game.player:
         for x in range(len(self.fov_map)):
             for y in range(len(self.fov_map[0])):
                 self.fov_map[x][y]=int(libtcod.map_is_in_fov(tcod_map,
                                                              x,y))
     else:
         self.clear()
         for x in range(self.entity.x-self.creature.perception,
                        self.entity.x+self.creature.perception+1):
             for y in range(self.entity.y-self.creature.perception,
                            self.entity.y+self.creature.perception+1):
                 fov_num = int(libtcod.map_is_in_fov(tcod_map,x,y))
                 if fov_num:
                     if (x-self.entity.x==0 or
                         y-self.entity.y==0 or
                         abs(x-self.entity.x)-abs(y-self.entity.y)==0):
                         fov_num += 1
                     if util.distance(self.entity.x,self.entity.y,x,y)<=self.creature.perception//3:
                         fov_num += 1
                 try:
                     self.fov_map[x][y] = fov_num
                 except IndexError: pass

  def act(self, acting_unit):
    # First chooses closest foe as target:
    chosen_target = None
    shortest_so_far = 999 # shortest distance of a foe so far
    for other_unit in self.things:
      if (other_unit.allegiance == 'gaia' or
          other_unit.allegiance == acting_unit.allegiance or
          other_unit.quantity <= 0):
        continue  # invalid unit, not a foe
      dist = util.distance(other_unit.coord, acting_unit.coord)
      if dist < shortest_so_far:
        shortest_so_far = dist
        chosen_target = other_unit

    if chosen_target == None:
      return

    # Now moves toward target:
    # really hacky:
    cur = acting_unit.coord
    self.move(
      acting_unit,
      util.coord_sum(
        cur,
        util.direction_from(cur, chosen_target.coord)))

    # Now shoots target:
    self.shoot(acting_unit, chosen_target)