#!/usr/bin/python
from socket import *
from random import *
from string import *
from types import *
from math import *
import time
import sys
import re

INST_MOVE_NORTH 	= 0
INST_MOVE_EAST 		= 1
INST_MOVE_WEST 		= 2
INST_MOVE_SOUTH 	= 3
INST_NOOP 			= 4
INST_DROP			= 5
INST_PICK			= 6


class icfpInstruction:
	def __init__(self, robot=None, bid = 1, op = INST_NOOP, package_ids = None, bid_override = None):
		self.op = op
		self.bid = bid
		if type(package_ids) != ListType:
			package_ids = [package_ids]
		self.package_ids = package_ids
		self.robot = robot
		if bid_override == None:
			bid_override = 1
		self.bid_override = bid_override
		if robot == None:
			self.op = INST_NOOP


	def render(self):
		robot = self.robot
		# Check for legit values of everything
		try:
			if self.op != INST_NOOP and self.bid > robot.budget:
				print "[instruction] Bid too large, will kill robot.  Performing noop."
				raise  Exception("illegal op")

			elif self.op != INST_NOOP and abs(self.bid) > robot.budget:
				print "[instruction] Bid to large, will kill robot.  Performing noop."
				raise Exception("illegal op")
	
		except:
			print "MALFORMED INSTRUCTION.  Reverting to No-Op"
			self.op = INST_NOOP
			self.bid = 1

		# Render 
		op = self.op

		self.bid = int(self.bid)

		if self.bid_override == 0 and self.robot.world.queryAdjacentRobots() == []:
			bid = 1

		elif self.bid_override == 0 and self.robot.world.queryAdjacentRobots() != [] and \
			self.robot.world.queryWaterNearby > 0:
			bid += int(float(self.robot.budget) * self.robot.panicFactor)
		elif self.bid_override == 0 and self.robot.world.queryAdjacentRobots() != []:
			bid += int(float(self.robot.budget) * self.robot.aggressionFactor)

		cmd = str(self.bid) + ' '
		try:	
			if op == INST_MOVE_NORTH:
				cmd = cmd + 'Move N'
			elif op == INST_MOVE_EAST:
				cmd = cmd + 'Move E'
			elif op == INST_MOVE_WEST:
				cmd = cmd + 'Move W'
			elif op == INST_MOVE_SOUTH:
				cmd = cmd + 'Move S'
			elif op == INST_DROP:
				package_list = ''
				for pid in self.package_ids:
					pid = int(pid)
					package_list = package_list + ' ' + str(pid)
				cmd = cmd + 'Drop' + package_list
			elif op == INST_PICK:
				package_list = ''
				for pid in self.package_ids:
					pid = int(pid)
					package_list = package_list + ' ' + str(pid)
				cmd = cmd + 'Pick' + package_list
			else:	# Assume no-op
				cmd = '1 Pick'
				self.bid = 1
		except:
			# Default to no-op
			print "[instruction] An error occurred trying to send this ", \
				"instruction.  A no-op was sent instead."
			cmd = '1 Pick'
			self.bid = 1

		return cmd



#--------------------------------------------------
# constants
#--------------------------------------------------

# flags for real v. hypothetical package searching
REAL_ONLY = 0
HYPOTHETICAL_ONLY = 1
REAL_AND_HYPOTHETICAL = 2
#--------------------------------------------------

ESC			= 27
YELLOW		= '[33m'
BLUE		= '[34m'
MAGENTA		= '[35m'
CYAN		= '[36m'
WHITE		= '[37m'
CYAN_BACK	= '[46m'
BLUE_BACK	= '[44m'
BLACK_BACK	= '[40m'

class icfpBase:
	def __init__(self, x, y):
		self.x = x
		self.y = y
		self.packages = []

		# History of who's visited and when: 
		#  tuples of (robot, turn)
		self.visited = {}

	def addVisitor(self, robot, turn):
		try:
			self.visited[robot] += [turn]
		except:
			self.visited[robot] = [turn]

	# If optional robot is given, returns whether or not
	# this base has been visited by a specific robot
	def hasBeenVisited(self, robot=None):
		if robot != None:
			try:
				return self.visited[robot]
			except:
				return 0
		else:
			return len(self.visited)


class icfpPackage:
	def __init__(self, uid = 0, weight = None, x = None, y = None, destination_x = None, destination_y = None, hypothetical = 0):
		self.uid = uid
		self.weight = weight
		self.destination_x = destination_x
		self.x = x
		self.y = y
		self.destination_y = destination_y
		self.delivered = 0
		self.carrier = None 	# The robot carrying this package
		self.hypothetical = hypothetical

class icfpRobot:
	def __init__(self, addr=None, conn=None, uid = 0, budget = 0, capacity = 0):
		self.addr = addr 	# Address of robot client program
		self.conn = conn 	# TCP/IP socket connection to robot
		# Required game information
		self.uid = uid		# Unique identifier
		self.packages = []
		self.budget = budget
		self.points = 0
		self.alive = 1
		self.panicFactor = 1.0
		self.aggressionFactor = 1.0
		self.x = 2
		self.y = 2
		self.capacity = capacity

		# Internal use
		self.active_this_turn = 0

		# Statistical information
		self.kills = 0
		self.pushes = 0
		self.packagesDelivered = []
		self.history = []

	def remainingCapacity(self):
		cap = self.capacity
		for p in self.packages:
			cap -= p.weight
		return cap

	# Send my position to a connection
	def sendPosition(self, conn):
		conn.send('#' + str(self.uid) + ' X ' + \
			str(self.x) + ' Y ' + str(self.y) + ' ')

	
class icfpWorld:
	def __init__(self, mapfile = None, width=None, height=None):
		self.live_robots = {}
		self.dead_robots = {}
		self.gen = Random()
		self.bases = []
		self.packages = {} 	
		self.package_hash = {}
		self.robot_hash = {}
		self.arrayCache = None
		self.arrivalTrack_hash = {}
		self.world = []
		self.base_hash = {}
		self.width = width
		self.height = height
		if mapfile:
			self.readWorldFile(mapfile)
			self.createBorder()

	# Ring the map with walls
	# height and width are adjusted accordingly
	def createBorder(self):
		borderwall = ''
		for i in range(self.width + 2):
			borderwall = borderwall + '#'  

		for i in range(self.height):
			self.world[i] = '#' + self.world[i] + '#'
		
		self.world = [borderwall] + self.world + [borderwall]

		self.height = self.height + 2
		self.width =  self.width + 2
	
	def generateRandomWorld(self, width, height, 
		walls = 40, water=80, bases = 20, weight_max = 10, packages=40):
		# First create a totally blank world
		
		self.width = width
		self.height = height
		self.world = []
		self.packages = {}
		self.packages_hash = {}
		self.robot_hash = {}
		
		world = self.world

		strn = ''		
		for j in range(width):
			strn += '.'

		for i in range(height):
			world += [strn]

	
		print "   adding walls"
		# Populate with walls
		for i in range(walls):
			x, y = self.findOpenSquare()
			world[y] = world[y][0:x] + '#' + world[y][x+1:]
		print "   adding water"
		for i in range(water):
			x, y = self.findOpenSquare()
			world[y] = world[y][0:x] + '~' + world[y][x+1:]

		print "   adding ", bases, "bases"
		self.remainingPackages = bases
		packageUID = 1
		for i in range(bases):
			# Each base gets a package
			x, y = self.findOpenSquare()
			world[y] = world[y][0:x] + '@' + world[y][x+1:]
			self.bases += [ icfpBase(x+1, y+1) ]

		print "    adding ", packages, "packages"
		for i in range(packages):
			# Create a package
			base = self.bases[int(self.gen.random() * bases)]
			dest_x, dest_y = self.findOpenSquare()
			package = icfpPackage(
				uid = packageUID,
				weight = int(self.gen.random() * weight_max+1),
				x = base.x,
				y = base.y,
				destination_x = dest_x,
				destination_y = dest_y)
			packageUID += 1
			self.packages[package.uid] = package
			self.placePackage(package)
			base.packages += [package]
			# Fudge this.  It assumes that a border will be added
			# Coordinates will be off by (1,1) if no border
			# is added.
			package.destination_x += 1
			package.destination_y += 1

	def unhashstr(self, hstr):
		m = re.compile('(?P<x>\S+)_(?P<y>\S+)').match(hstr)
		return ( atoi(m.group('x')), atoi(m.group('y')) )

	def hashstr(self, x, y):
		return str(x) + '_' + str(y)

	def placePackage(self, package):
		hstr = self.hashstr(package.x, package.y)

#		print "PLACE PACKAGE ", package.uid, "at", hstr
		
		try:
			self.package_hash[hstr] += [package] 
		except:
			self.package_hash[hstr] = [package]

#		print "  packages at this location: ", self.package_hash[hstr]

	# Lifts a package from the map.
	# Does not delete it.
	def liftPackage(self, package):
#		print "LIFT PACKAGE ", package.uid, "from", package.x, package.y
		try:
			hstr = self.hashstr(package.x, package.y)
			self.package_hash[hstr].remove(package)
			if len(self.package_hash[hstr]) == 0:
				del(self.package_hash[hstr])
		except:
			# oops.  we probably tried to lift a package
			# that wasn't there.
			#print "[world] : warning, tried to lift package that isn't here"
			pass

	# Given a robot's UID, return the robot object
	# returns none if the robot does not exist or is dead
	def findRobot(self, uid):
		try:
			return self.live_robots[uid]
		except:
			return None

	# Given a package's UID, return the robot object
	# returns none if the package does not exist
	def findPackage(self, uid):
		try:
			return self.packages[uid]
		except:
			return None
		
	# Adds a robot to the array and places it on the map
	def addRobot(self, robot):
		if robot.alive == 1:
			self.live_robots[robot.uid] = robot
			self.placeRobot(robot)
		else:
			self.dead_robots[robot.uid] = robot
	
	# Adds a package to the world
	#  (and places it)
	def addPackage(self, package):
		self.packages[package.uid] = package
		
	# Move this robot to the dead stack!
	# Does not lift it from the map.
	def robotDied(self, robot):
		if robot.alive == 0:
			self.dead_robots[robot.uid] = [robot]
			del self.live_robots[robot.uid]

	# Places a robot on the map.
	def placeRobot(self, robot):
		hstr = self.hashstr(robot.x, robot.y)
		try:
			self.robot_hash[hstr] += [robot] 
		except:
			self.robot_hash[hstr] = [robot]

		base = self.findBase(robot.x, robot.y)
		if base != None:
			base.addVisitor(robot, self.turn)

		# Check for arrival tracking (i.e. robot traps)
		try:
			tracker =  self.arrivalTrack_hash[hstr] 
			remaining = []
			for i in tracker:
				try:
					if i[1][0].index(robot):
						remaining += [ i ]
				except:
					i[0](robot.x, robot.y, robot)	
				self.arrivalTrack_hash[hstr] = remaining
		except:
			None

	# Lifts a robot off of the map
	# Does not kill or delete it.
	def liftRobot(self, robot):
		hstr = self.hashstr(robot.x, robot.y)
		self.robot_hash[hstr].remove(robot)
		if len(self.robot_hash[hstr]) == 0:
			del(self.robot_hash[hstr])


	# Direction is 'E', 'W', 'N', or 'S'
	def moveRobot(self, robot, direction):
		if type(robot) == IntType:
			robot = self.findRobot(robot)
		if robot == None:
			print "Warning!   Tried to move non-existant robot."

		dest_x = robot.x 
		dest_y = robot.y
		if direction == 'E':
			dest_x += 1
		elif direction == 'W':
			dest_x -= 1
		elif direction == 'S':
			dest_y -= 1
		elif direction == 'N':
			dest_y += 1
		self.liftRobot(robot)	
		robot.x = dest_x
		robot.y = dest_y
		self.placeRobot(robot)


	# Remove all traces of a package from existence
	def vaporizePackage(self, package):
#		print "VAPORIZE PACKAGE ", package.uid
		self.liftPackage(package)
		del self.packages[package.uid]

	# kind can be:
	#  REAL_ONLY
	#  HYPOTHETICAL_ONLY
	#  REAL_AND_HYPOTHETICAL
	def queryPackages(self, x=None, y=None, kind=REAL_ONLY):

		if x == None or y == None:
			# packages at all locations
			packages = self.packages.values()
		else:
			hstr = self.hashstr(x, y)
			try:
				packages = self.package_hash[hstr]
			except:
#				print "No package found at ", hstr
				return []

		for p in packages:
			if p.carrier != None:
				packages.remove(p)

		if kind == REAL_ONLY:
			temp = []
			for p in packages:
				if p.hypothetical == 0:
					temp += [p]
			return temp
		elif kind == HYPOTHETICAL_ONLY:
			temp = []
			for p in packages:
				if p.hypothetical == 1:
					temp += [p]
			return temp
		else:
			return packages

	def queryAdjacentRobots(self, robot = None):
		if type(robot) == TupleType:
			x, y = robot
		else:
			x = robot.x
			y = robot.y
		robots = []
		robots += self.queryRobotsAt(x + 1, y)
		robots += self.queryRobotsAt(x - 1, y)
		robots += self.queryRobotsAt(x, y + 1)
		robots += self.queryRobotsAt(x, y - 1)
		return robots

    # Returns number of water squares nearby
	def queryWaterNearby(self, robot=None):
   		if type(robot) == TupleType:
			x, y = robot
		else:
			x = robot.x
			y = robot.y
	
		w = self.world
		return w[y+1][x] == '~' + \
		w[y-1][x] == '~' + \
		w[y][x+1] == '~' + \
		w[y][x-1] == '~'

	def queryRobotsAt(self, x, y):
		try:
			return self.robot_hash[self.hashstr(x, y)]
		except:
			return []
	
	def packagePickup(self, robot_uid, package_uid):
#		print "PACKAGE PICKUP robot ", robot_uid, " package", package_uid
		robot = self.findRobot(robot_uid)
		package = self.findPackage(package_uid)
		# Do we know about this package?
#		if package == None:
			# create the package with all the information
			# we know about it
#			package = icfpPackage(
#					uid = package_uid,
#					x = robot.x,
#					y = robot.y,
#					hypothetical = 1)

		robot.packages += [package]
		package.carrier = robot
		# Take it off the map!
		self.liftPackage(package)
	
	def packageDrop(self, robot_uid, package_uid, client):
		robot = self.findRobot(robot_uid)
		package = self.findPackage(package_uid)

		# Remove from robot's inventory
		robot.packages.remove(package)
		package.carrier = None

		# Is this the package's destination?
		package.x = robot.x
		package.y = robot.y
		if package.x == package.destination_x and \
			package.y == package.destination_y:
			# Make the package disappear
			#print "[World] Robot", robot_uid, "delivered package", package_uid 
			robot.points += package.weight
			package.delivered = 1
			client._PackageDelivered(package, robot)
			# Vaporize
			self.vaporizePackage(package)
		elif package.destination_x == None or package.destination_y == None:
			# We don't know destination of package.  It becomes hypothetical
			# because it may have been delivered successfully.
			package.hypothetical = 1
			client._PackageExistenceInQuestion(package)
			self.placePackage(package)
		elif package.destination_x != None and package.destination_y != None:
			# We know the destination of this package, and it's not there.
			# Put package back on the map
			self.placePackage(package)

	def findOpenSquare(self, notchar = None ):
		world = self.world
		height = len(world)
		width = len(world[0])
		dest_x = int(self.gen.random() * width)
		dest_y = int(self.gen.random() * height)
		# Caveat: This will loop infinitely if map is full
		if notchar == None:
			while world[dest_y][dest_x] != '.':
				dest_x = int(self.gen.random() * width)
				dest_y = int(self.gen.random() * height)
		else:
			while world[dest_y][dest_x] == notchar:
				dest_x = int(self.gen.random() * width)
				dest_y = int(self.gen.random() * height)
		return dest_x, dest_y


	def buildArrayCache(self):
		cache = []
		for i in self.world:
			temp = []
			for j in i:
				temp += [j]
			cache += [ temp ]
		self.arrayCache = cache

	# If beasts == 1, it will print robots and (known) packages
	def printWorld(self, beasts=None, robot=None):
		world = self.world

		height = len(world)
		width = len(world[0])

		if beasts == 1:
			if self.arrayCache == None:
				self.buildArrayCache()
			map = []
			for i in self.arrayCache:
				map += [ i[:] ]				

			for base in self.bases:
				color = None
				if base.hasBeenVisited(robot):
					color = CYAN
				elif base.hasBeenVisited():
					color = BLUE
				if color != None:
					map[base.y][base.x] = chr(ESC) + color + '@' + \
						chr(ESC) + WHITE 


			# Draw packages
			for p in self.packages.values():
				if p.carrier == None:
					if p.hypothetical == 1:
						pchar = '?'
					else:
						pchar = '$'
					base = self.findBase(p.x, p.y)
					color_back = BLACK_BACK
					if base:
						if base.hasBeenVisited(robot):
							color_back = CYAN_BACK
						elif base.hasBeenVisited():
							color_back = BLUE_BACK
					map[p.y][p.x] = chr(ESC) + MAGENTA + chr(ESC) +color_back + pchar + \
						chr(ESC) + WHITE + chr(ESC) + BLACK_BACK
			# Draw destinations of carried packages
			if robot != None:
				for p in robot.packages:
					pchar = str(p.uid)[-1]
					color = BLUE
					map[p.destination_y][p.destination_x] = chr(ESC) + BLUE + \
						pchar + chr(ESC) + WHITE


			# Draw robots
			for r in self.live_robots.values():
				if robot != None and r.uid == robot.uid:
					rchar = '*'
					color = CYAN
				else:
					rchar = str(r.uid)[-1]
					if len(r.packages) > 0:
						color = CYAN
					else:
						color = YELLOW
				map[r.y][r.x] = chr(ESC) + color + rchar + \
					chr(ESC) + WHITE

			world = []
			for i in map:
				world += [ join(i, '') ]

		print "world ", width, "x", height

		for i in range(height):
			print world[height-(i+1)]

	def saveWorld(self, filename):
		map_filename = filename
		packs_filename = filename + '.packs'

		map_file = file(map_filename, 'w')

		world = self.world

		height = len(world)
		width = len(world[0])
	
		for i in range(height):
			map_file.write(world[height-(i+1)] + "\n")

		map_file.close()

		packs_file = file(packs_filename, 'w')
		packs_file.write("[\n");
		indent = '  '

		first_base = 1
		for base in self.bases:
			if len(base.packages) > 0:
				if first_base == 1:
					first_base = 0
				else:
					packs_file.write(",\n\n")
					indent = '  '

				packs_file.write(indent + "( (" + \
					str(base.x) + ',' + str(base.y) + "), [\n")
				indent = indent + '  '
				first_pack = 1
				for pack in base.packages:
					if first_pack == 1:
						first_pack = 0
					else:
						packs_file.write(",\n");
					packs_file.write(indent + 'Mk {uid=' + \
						str(pack.uid) + ', ' + 'dest=(' + \
						str(pack.destination_x) + ',' + \
						str(pack.destination_y) + '), weight=' + \
						str(pack.weight) + '}')
				packs_file.write('])')
		packs_file.write("\n]\n");
		packs_file.close()

	# Clears traps at location
	def clearTraps(self, x, y):
		self.setTrap(x, y, None)

	# Note: Track arrival is a one-time affair
	# You should reset it if you want it to work more than once
	#--------
	# Clears traps if callback == None
	def setTrap(self, x, y, callback=None, exclude=[]):
		hstr = self.hashstr(x, y)
		if callback == None:
			self.arrivalTrack_hash[hstr] = []
		else:
			try:
				self.arrivalTrack_hash[hstr] += [ (callback, exclude) ]
			except:
				self.arrivalTrack_hash[hstr] = [ (callback, exclude) ]

	# returns distances[][] containing distance[y][x] from each point to (x, y)
	# or None if it is impossible
	def calculateDistances(self, x, y, maxSteps=0):
		# initialize distances to width x height size list of lists filled with None
		distances = [[None for i in range(self.width)] for j in range(self.height)]
		if self.world[y][x] != '@' and self.world[y][x] != '.':
			return distances;
	
		steps = 0 # how many steps away from destination (x, y) points in thisStep are
		nextStep = [[x, y]]
		distances[y][x] = 0
		while len(nextStep):
			steps += 1
			if maxSteps and steps > maxSteps:
				break
				
			thisStep = nextStep
			nextStep = [] # clear the list holding unevaluated neighbors of thisStep
			for i in range(len(thisStep)):
				ts_x = thisStep[i][0]
				ts_y = thisStep[i][1]
	
				# add neighbors of thisStep[i] if they're open terrain and have undetermined distance
				candidates = [[ts_x, ts_y+1], [ts_x+1, ts_y], [ts_x, ts_y-1], [ts_x-1, ts_y]]
				for j in range(len(candidates)):
					c_x = candidates[j][0]
					c_y = candidates[j][1]
					
					if (self.world[c_y][c_x] == '.' or self.world[c_y][c_x] == '@') and distances[c_y][c_x] == None:
						nextStep += [[c_x, c_y]]
						distances[c_y][c_x] = steps
	
		return distances

	# x and y are current location, distances is a list of lists holding distance from
	# each square to the destination
	def moveToDestination(self, x, y, distances):
		if distances[y][x] == None:
			return None
	
		candidates  = [[x, y+1], [x+1, y], [x, y-1], [x-1, y]]
		c_dist      = []
		finalists   = []
		moves = [INST_MOVE_NORTH, INST_MOVE_EAST, INST_MOVE_SOUTH, INST_MOVE_WEST]
	
		for i in range(len(candidates)):
			if(distances[candidates[i][1]][candidates[i][0]] != None):
				c_dist += [distances[candidates[i][1]][candidates[i][0]]]
		best_distance = min(c_dist)
	
		for i in range(len(candidates)):
			if(distances[candidates[i][1]][candidates[i][0]] == best_distance):
				finalists += [moves[i]];

		# select randomly 	
		return finalists[int(self.gen.random()*len(finalists))]

	def findBase(self, x, y):
		if len(self.bases) == 0:
			self.findBases()

		hstr = self.hashstr(x, y)
		try:
			return self.base_hash[hstr]
		except:
			return None

	# parses map info to find base coordinates
	def findBases(self):
		self.bases = []
		for j in range(self.height):
			for i in range(self.width):
				if self.world[j][i] == '@':
					base = icfpBase(x=i, y=j)
					self.bases += [base]
					self.base_hash[self.hashstr(i, j)] = base

DISTANCE_REAL = 0
DISTANCE_GEOMETRIC = 1

class icfpRouter:
	def __init__(self, client):
		self.client = client
		# Destination queue elements are tuples:
		# (x, y, callback function, callback arg)
		self.queue = []
		self.cruise_control_= 0 

		self.distance_cache = {}

	# arg1 and arg2 may be either:
	# a tuple (x,y)
	# a robot
	# a package
	# a base

	# If no arg2 is given, it the client's location is used
	#
	# kind may be either DISTANCE_REAL or DISTANCE_GEOMETRIC
	def distance(self, arg1, arg2=None, kind=DISTANCE_REAL):
		if arg2 == None:
			b_x, b_y = (self.client.robot.x, self.client.robot.y)
		elif isinstance(arg2, icfpPackage) or \
			isinstance(arg2, icfpRobot) or \
			isinstance(arg2, icfpBase):
			b_x, b_y = (arg2.x, arg2.y)
		else:
			b_x, b_y = arg2

		if isinstance(arg1, icfpPackage) or \
			isinstance(arg1, icfpRobot) or \
			isinstance(arg1, icfpBase):
			a_x, a_y = (arg1.x, arg1.y)
		else:
			a_x, a_y = arg1

		if (a_x, a_y) == (b_x, b_y):
			return 0

		if a_x == None:	
			a_x = 10000
		if a_y == None:	
			a_y = 10000
		if b_x == None:	
			b_x = 10000
		if b_y == None:	
			b_y = 10000

		if kind == DISTANCE_GEOMETRIC:
			a_x = float(a_x)
			b_x = float(b_x)
			a_y = float(a_y)
			b_y = float(b_y)
			return sqrt( (a_x - b_x) * (a_x - b_x) + (a_y - b_y) * (a_y - b_y) )
		elif kind == DISTANCE_REAL:
			distances = self.calculateDistances(a_x, a_y)	
			return distances[b_y][b_x]
	
	def clearQueue(self):
		self.queue = []

	# Remove first element of queue
	def cancelAction(self):
		if(len(self.queue) > 0):
			self.queue = self.queue[1:]
	
	def calculateDistances(self, x , y=None):
		world = self.client.world

		if isinstance(x, icfpPackage) or \
			isinstance(x, icfpRobot) or \
			isinstance(x, icfpBase):
			y = x.y
			x = x.x

		hstr = world.hashstr(x,y)

		try:
			return self.distance_cache[hstr]
		except:
			self.distance_cache[hstr] = world.calculateDistances(x, y)
			return self.distance_cache[hstr]

	def moveTo(self, x, y=None):
		robot = self.client.robot
		world = self.client.world

		if isinstance(x, icfpPackage) or \
			isinstance(x, icfpRobot) or \
			isinstance(x, icfpBase):
			y = x.y
			x = x.x

		return world.moveToDestination(robot.x, robot.y, self.calculateDistances(x, y))


	# Command is either of the form
	# (x, y, callback, callback_arg)
	# or
	# (instruction, callback, callback_arg
	# or
	# (callback, callback_arg)
	def cruiseControlAdd(self, command):
		if len(self.queue) == 0:
			self.cruise_control = 1		# Turn cc on
		self.queue += [ command ]

	def cruiseControl(self):
		robot = self.client.robot

		if self.cruise_control == 0:
			return None

		if len(self.queue) == 0:
			return None

		# The current command
		cmd = self.queue[0]

		# It's a destination command
		# Callback functions for destinations are given X, Y, Arg
		if len(cmd) == 4:
			x = cmd[0]
			y = cmd[1]
			if robot.x == x and robot.y == y:		# We're heeeerrre
				if (cmd[0], cmd[1]) == (x, y):
					# destination reached
					self.queue = self.queue[1:]
					if len(self.queue) == 0:
						# Turn off cruise control if queue empty
						self.cruise_control = 0
					if cmd[2] != None:
						# Callback function
						return cmd[2](cmd[0], cmd[1], cmd[3])
				return None
			else:	# keep moving
				op = self.moveTo(x, y)
				if op == None:
					return None
				else:
					return icfpInstruction(
						robot = robot,
						bid = 1,
						op = op)
		# It's a single instruction
		# Callback functions for single instructions are given only Arg
		elif len(cmd) == 3:
			self.queue[0] = (cmd[1], cmd[2])
			return cmd[0]
		# It's only a callback
		elif len(cmd) == 2:
			self.queue = self.queue[1:]	
			return cmd[0](cmd[1])

MAX_BUFFER_SIZE = 65000
ESC = 27
# ANSI clear screen code
CLEAR_SCREEN = chr(27) + '[2J'

class icfpClient:
	def __init__(self, host, port, animate=0, drawDelay = 0.4):
		self.rgen = Random()

		self.serverHost = host
		self.serverPort = port
		self.turn = 1
		self.animate = animate
		self.drawDelay = drawDelay

		self.recv_buffer = []
		
		# Game infomation
		self.uid = None
		self.robot = None
		self.world = None

#		self.socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
		self.socket = socket(AF_INET, SOCK_STREAM)

		self.router = icfpRouter(self)

		print "client initialized"

	def drawFrame(self):
		print CLEAR_SCREEN
		# -- diagnostics
		print "Turn: ", self.turn,  "Budget: ", self.robot.budget, "Packages:"
		packageWeightTotal = 0
		for i in self.robot.packages:
			packageWeightTotal += i.weight
		print "Points: ", self.robot.points, "Burden: ", packageWeightTotal, "/", self.robot.capacity
		print "On robot:  ",
		for p in self.robot.packages:
			print str(p.uid) + '(' + str(p.weight) + ')',
		print
		print "On ground: ",
		for p in self.world.queryPackages(self.robot.x, self.robot.y):
			print str(p.uid) + '(' + str(p.weight) + ')',
		print
		try:
			print self.tagline
		except:
			None
		self.world.printWorld(beasts = 1, robot=self.robot)	
		time.sleep(self.drawDelay)

	def recv_line(self):
		if len(self.recv_buffer) == 0:
			data = self.socket.recv(MAX_BUFFER_SIZE)
			self.recv_buffer = split(data[:-1], "\n")
#			print "RECEIVED----------------------"
#			print data,
#			print "------------------------------"
#			for s in self.recv_buffer:
#				print s
#			print "------------------------------"
		rline = self.recv_buffer[0]
		self.recv_buffer = self.recv_buffer[1:]
		return rline

	def start(self):
		s = self.socket
		print "Connecting to server at [" + self.serverHost + ':' + str(self.serverPort) + ']'
		s.connect((self.serverHost, self.serverPort))

		s.send("Player\n")

		# Receive map dimensions
	
		m = re.compile('(?P<x>\S+)\s+(?P<y>\S+)').match(self.recv_line())

		# Receive map
		self.world = icfpWorld(
			width = atoi(m.group('x')),
			height = atoi(m.group('y'))
		)
		self.world.turn = self.turn

		self.world.world = []
		for i in range(self.world.height):
			self.world.world += [self.recv_line()]
		
		# Add border to world
		
		self.world.createBorder()
		self.world.findBases()

		self.world.printWorld()

		# Receive player stats
		
		mexpr = '(?P<uid>\S+)\s+(?P<capacity>\S+)\s+(?P<budget>\S+)' 	
		m = re.compile(mexpr).match(self.recv_line())
		self.uid = atoi(m.group('uid'))
		self.capacity = atoi(m.group('capacity'))
		self.budget = atoi(m.group('budget'))

		print "UID ", self.uid
		print "Capacity ", self.capacity
		print "Budget ", self.budget

		self.parseServerReply(self.recv_line())

		# Make sure we got a robot
		if self.robot == None:
			print "ERROR: We have no robot!!"
			raise

		# throw away a line
#		self.recv_line()

		self.play()


	def parseServerReply(self, data):
		evts = split(data, '#')

		# Now we're going to flag all of the robots in the world as dead.
		# They'll be resurrected if their UID is listed in the server response.
		for r in self.world.live_robots.values():
			r.active_this_turn = 0

		for event in evts:
			ind = split(event)
#			print "   EVENT: ", ind



			if len(ind) > 0:

				try:
					robot_uid = atoi(ind[0])
				except:
					# uh-oh.  we died.
					print "___________ DEATH! _____________"
					print data
					raise Exception('Robot died.')

				i = 1
				while i < len(ind):
					if ind[i] == 'N' or ind[i] == 'S' \
						or ind[i] == 'E' or ind[i] == 'W':
						self.world.moveRobot(robot_uid, ind[i])
						self._RobotMoved(robot_uid)
					elif ind[i] == 'X':
						# Robot appeared X coordinate
						i += 1	
						x = atoi(ind[i])
						# Robot apperared Y coordinate
						i += 2
						y = atoi(ind[i])
#						print '    (x,y) ', x, ',', y
						
						# Add this robot to the world
						# if the world doesn't already
						# know about it:
						if self.world.findRobot(robot_uid) == None:
							robot = icfpRobot(uid = robot_uid)
							robot.world = self.world
							robot.x = x
							robot.y = y
							if robot_uid == self.uid:
								robot.budget = self.budget
								robot.capacity = self.capacity
								self.robot = robot
							self.world.addRobot(robot)
							self._RobotAppeared(robot)

					elif ind[i] == 'P':
						i += 1

						package_uid = None
						try:	
							package_uid = atoi(ind[i])
						except:
							i -= 1		# No package specified

						if package_uid != None:
							package = self.world.findPackage(package_uid)
							# Does the world already know about this package?
							if package == None:
								robot = self.world.findRobot(robot_uid)
								package = icfpPackage(
									uid = package_uid,
									x = robot.x,
									y = robot.y
									)
								self.world.addPackage(package)
								self.world.placePackage(package)
								self._PackageInfoLearned(package)

							self.world.packagePickup(robot_uid, package_uid)
							
							if package.hypothetical == 1:
								# We now know this package is real.
								package.hypothetical = 0
								self._PackageExistenceConfirmed(package)

							self._PackagePickup(robot_uid, package_uid)

					elif ind[i] == 'D':
						i += 1
						package_uid = None

						try:
							package_uid = atoi(ind[i])
						except:
							i -= 1		# No package specified

						if package_uid != None:
							# Does the world already know about this package?
							if self.world.findPackage(package_uid) == None:
								robot = self.world.findRobot(robot_uid)
								package = icfpPackage(
									uid = package_uid,
									x = robot.x,
									y = robot.y,
									hypothetical = 1
									)
								# It's hypothetical because it no longer exists if it was 
								# dropped on its destination -- but we don't know where its
								# destination is.
								self.world.addPackage(package)
								self.world.placePackage(package)	
								self._PackageInfoLearned(package)
							else:
								self.world.packageDrop(robot_uid, package_uid, self)
							self._PackageDrop(robot_uid, package_uid)

					i += 1

				robot_obj = self.world.findRobot(robot_uid)
				if robot_obj != None:
#					print "Robot ", robot_uid, " is still alive."
					robot_obj.active_this_turn = 1
				else:
					print "ERROR! CAN'T MARK ROBOT", robot_uid, "AS ACTIVE!"


		# Kill robots we didn't hear anything about
		for r in self.world.live_robots.values():
			if r.active_this_turn == 0:
				r.alive = 0
				self.world.liftRobot(r)
				self.world.robotDied(r)
				self._RobotDied(r)	

	# parses the string sent by the server each round about
	# packages in this space
	def updatePackageInfo(self, data):
		# data is the raw string sent by the server
		# it consists of groups of 4 integers, in the format:
		# 	uid dest_x dest_y weight
		pinfo = split(data)
		i = 0
#		if len(pinfo) == 0:
#			print "[client] no packages at location"

#		print "UPDATE PACKAGE INFO ", pinfo
		while(i < len(pinfo)):
			package_uid = atoi(pinfo[i])
			dest_x = atoi(pinfo[i+1])
			dest_y = atoi(pinfo[i+2])
			weight = atoi(pinfo[i+3])
#			print "[client] Package ", package_uid, "is here ", \
#				"(weight", weight,  "dest", dest_x, dest_y
			i+= 4
			# Update world
			package = self.world.findPackage(package_uid)
			if package is None:
				# World doesn't know about this package yet
				package = icfpPackage(
							uid = package_uid,
							weight = weight,
							destination_x = dest_x,
							destination_y = dest_y,
							x = self.robot.x,
							y = self.robot.y
				)
				self.world.addPackage(package)
				self.world.placePackage(package)
				self._PackageInfoLearned(package)
			else:
				if package.weight == None:
					package.weight = weight 
					package.destination_x = dest_x
					package.destination_y = dest_y
					self._PackageInfoLearned(package)
			
				# The package is on the ground.  It is clearly
				# not being carried.
				package.carrier = None		

			if package.hypothetical == 1:
				# We can now verify that this package exists
				package.hypothetical = 0
				self._PackageExistenceConfirmed(package)


		# Nuke all hypothetical packages that are here
		packages_here = self.world.queryPackages(
							self.robot.x,
							self.robot.y,
							HYPOTHETICAL_ONLY)
		if packages_here != None:
			for p in packages_here:
				if p.hypothetical == 1:
					self.world.vaporizePackage(p)
				else:
					print "ERROR! Tried to vaporize real package??"

	# play() is the main event loop.  It continues as long as
	# the connection with the server isn't broken
	def play(self):
		while(1):
			# Await list of packages at this location

#			print "---------Turn " + str(self.turn) + "-- budget " + str(self.robot.budget)
#			print "[client "+str(self.turn)+"] Awaiting package list"
			package_data = self.recv_line()
			self.updatePackageInfo(package_data)

			if self.turn == 1:
				self._GameStart()

			# Now is the time to make our decision on what to do!
			instruction = self._Turn()
			if isinstance(instruction, icfpInstruction) == 0:
				# set to default instruction (no-op)
				instruction = icfpInstruction()
			
			# send our instruction
			rendered_command = instruction.render()
#			print "[client "+str(self.turn)+"] sending command \"" + rendered_command + "\""
			self.socket.send(rendered_command + "\n")

			# Deduct from robot's balance
			self.robot.budget -= abs(instruction.bid)

			# Await the results
#			print "[client "+str(self.turn)+"] Awaiting turn results"
			results_data = self.recv_line()
			self.parseServerReply(results_data)
			self.turn += 1
			self.world.turn = self.turn		# Yeah, it's redundant.  So what?

#---------------------------------------------------------------
# Subclassibles!
#---------------------------------------------------------------

	# Returns an instruction (icfpInstruction)
	# class.  The icfpInstruction class is incapable
	# of sending malformed commands to the server;
	# worst case, it will default to trying to pick
	# up a package that's not there.
	def _Turn(self):

		if self.animate > 0 and (self.turn-1) % self.animate == 0:
			self.drawFrame()
		if self.animate < -1:
			self.animate += 1
		elif self.animate == -1:
			self.animate = 1

		# Check cruise control
		cc_instruction = self.router.cruiseControl()
		if isinstance(cc_instruction, icfpInstruction):
			return cc_instruction
		else:
			return None

	def _GameStart(self): 
		None

	def _RobotAppeared(self, robot):
#		print "Robot Appeared: ", robot.uid, "at", robot.x, robot.y
		None
		
	# Direction is N, S, E, or W
	def _RobotMoved(self, robot_uid):
#		print "Robot ", robot_uid, " moved ", direction
		None

	def _PackagePickup(self, robot_uid, package_uid):
#		print "Robot ", robot_uid, "picked up package", package_uid
		None

	def _PackageDrop(self, robot_uid, package_uid):
#		print "Robot ", robot_uid, "dropped package", package_uid
		None

	def _RobotDied(self, robot):
#		print "Robot ", robot.uid, "has expired!"
		None

	def _PackageInfoLearned(self, package):
#		print "Learned info about package ", package.uid
		None

	def _PackageExistenceConfirmed(self, package):
#		print "Package", package.uid, "is no longer hypothetical."
		None

	def _PackageExistenceInQuestion(self, package):
#		print "Package", package.uid, "has become hypothetical."
		None

	def _PackageDelivered(self, package, robot):
#		print "Package", package.uid, "has been delivered by robot", robot.uid
		None

ESC = 27						# ASCII code for ESC 
CLEAR_SCREEN = chr(ESC) + '[2J'	# ANSI clear screen code

PRIORITY_DROPOFF	= 3.0	# multiplier for prioritizing delivering packages
PRIORITY_PICKUP_R	= 4.0	#                         ... getting real packages
PRIORITY_PICKUP_H	= 2.0  	#                         ... getting hypothetical pickups
PRIORITY_BASE_RECON	= 5.0	#                         ... investigating bases
DISTANCE_COST		= 2.0   #                         ... penalizing distant priorities
FARSIGHTEDNESS		= 1.0	# small values favor very close objectives
PRIORITY_PICKUP_R_ADD	= 0.5	# bonus amount added to priority of any valid real pickup
PRIORITY_PICKUP_H_ADD	= 0.02	#                                         ... hype pickup
PRIORITY_DROPOFF_ADD 	= 0.5	#                                         ... dropoff
PRIORITY_BASE_RECON_ADD	= 0.4	#	                                      ... base recon
PACKAGE_CLUSTER_PREFERENCE = 0.2	# how much the robot prefers to grab packages with destinations near other packages being held
COWARDICE				= 0.3	# chance of moving in random safe direction if enemy is on adjacent square

class kClient(icfpClient):
	def _Turn(self):
#		if (self.turn-1) % 1 == 0:
#			self.drawFrame()	
		
		instruction = self.dropPackages()
		if instruction == None:
			instruction = self.getPackages()
		if instruction == None:
			instruction = self.chooseMove()
	
		self.calculateBid(instruction)

		return instruction
		
	#
	# Methods
	#
	def calculateBid(self, instruction):
		instruction.bid = 1
		if instruction.op == None:
			return
		
		x = self.robot.x
		y = self.robot.y
		
		adjacent = [[x, y+1], [x+1, y], [x-1, y], [x, y-1]]
	
		for i in adjacent:
			if self.world.queryRobotsAt(i[0], i[1]):
				if self.world.gen.random() < COWARDICE:
					next = int(self.world.gen.random() * 4)
					if self.world.world[adjacent[next][1]][adjacent[next][0]] == '.' or self.world.world[adjacent[next][1]][adjacent[next][0]] == '@':
						instruction.op = next
				return 2 + int(self.world.gen.random() * 3) 
		return 

	def distanceFunc(self, distance):
		return FARSIGHTEDNESS + DISTANCE_COST * distance
	
	# returns a priority adjusted by factors such as distance 
	def weighPickupPriority(self, package):
		remainingCapacity = self.robot.remainingCapacity()
	
		if package.hypothetical == REAL_ONLY:
			if package.weight > remainingCapacity:
				return 0.0

			multiplier 	= PRIORITY_PICKUP_R
			bonus		= PRIORITY_PICKUP_R_ADD
			weightPerDistance = package.weight / (1.0 + self.router.distance(package, (package.destination_x, package.destination_y)))
		
		else:
			multiplier 	= PRIORITY_PICKUP_H
			bonus		= PRIORITY_PICKUP_H_ADD
			weightPerDistance = 0.1 


		multiplier = multiplier * remainingCapacity / self.robot.capacity
		

		return bonus + multiplier * weightPerDistance / self.distanceFunc(self.router.distance(package))
	
	# returns a priority adjusted by factors such as distance 
	def weighDropoffPriority(self, package):
		
		multiplier = PRIORITY_DROPOFF

		burden = 0.0	
		for i in self.robot.packages:
			burden += i.weight
	
		multiplier = multiplier * burden / self.robot.capacity

		return PRIORITY_DROPOFF_ADD + multiplier * package.weight / self.distanceFunc(self.router.distance( (package.destination_x, package.destination_y) ))
	
	# returns a priority adjusted by factors such as distance 
	def weighBaseReconPriority(self, base):
		if base.hasBeenVisited(self.robot):
			return 0.0
		
		return PRIORITY_BASE_RECON_ADD + PRIORITY_BASE_RECON / self.distanceFunc(self.router.distance(base))


	# returns a fully formed instruction for moving towards the destination
	# assigned the highest priority by weighPriority()
	def chooseMove(self):
		instruction 		= None
		bestPriority		= None
		priorities			= {}
		finalists			= []
		
		# packages to pick up
		for p in self.world.queryPackages(kind=REAL_AND_HYPOTHETICAL):
			if p.carrier != None:
				continue
			hashstr 		= self.world.hashstr(p.x, p.y)
			thisPriority 	= self.weighPickupPriority(p)
	
			try:
				priorities[hashstr] += thisPriority
			except:
				priorities[hashstr] = thisPriority
		
		# packages to drop off
		for p in self.robot.packages:
			hashstr 		= self.world.hashstr(p.destination_x, p.destination_y)
			thisPriority 	= self.weighDropoffPriority(p)
	
			try:
				priorities[hashstr] += thisPriority
			except:
				priorities[hashstr] = thisPriority
		
		# bases to recon
		if self.baseReconComplete == 0:
			self.baseReconComplete = 1
			
			for b in self.world.bases:
				if b.hasBeenVisited(self.robot):
					continue
				
				self.baseReconComplete = 0
				hashstr 		= self.world.hashstr(b.x, b.y)
				thisPriority 	= self.weighBaseReconPriority(b)
	
				try:
					priorities[hashstr] += thisPriority
				except:
					priorities[hashstr] = thisPriority

		for k in self.world.robot_hash.keys():
			try:
				priorities[k] = priorities[k] * 0.5
			except:
				pass

		bestPriority = max(priorities.values())
		for k in priorities.keys():
			if priorities[k] == bestPriority:
				finalists += [ k ]
	
		x, y = self.world.unhashstr( finalists[ int(self.world.gen.random() * len(finalists)) ] ) 
		instruction = icfpInstruction( 	op 			= self.world.moveToDestination(self.robot.x, self.robot.y, self.router.calculateDistances(x, y)), 	\
										bid			= 1,			\
										robot		= self.robot, 	\
										package_ids	= None			)

		return instruction


	# returns a fully formed instruction for getting as many packages as can
	# be carried, or None if no such packages exist
	def getPackages(self):
		instruction 	= None	
		uids			= []
		localPackages 	= self.world.queryPackages(self.robot.x, self.robot.y)	
		
		if len(localPackages) == 0:
			return None
			
		remainingCapacity = self.robot.remainingCapacity()	
		localPackagesWeight = 0
			
		for i in localPackages:
			if i.weight > remainingCapacity:
				localPackages.remove(i)
			localPackagesWeight += i.weight

		if len(localPackages) == 0:
			return None

		if localPackagesWeight <= remainingCapacity:
			for i in localPackages:
				uids += [ i.uid ]
		else:
			preferences = [0.0 for i in range(len(localPackages))]
			
			for i in range(len(localPackages)):
				preferences[i] += localPackages[i].weight / self.distanceFunc(self.router.distance( (localPackages[i].destination_x, localPackages[i].destination_y) ))
				for j in self.robot.packages:
					preferences[i] += PACKAGE_CLUSTER_PREFERENCE * localPackages[i].weight / self.distanceFunc(self.router.distance(j, localPackages[i]))
		
			sortedPreferences = preferences[:]
			sortedPreferences.sort()
			tmpRemainingCapacity = remainingCapacity
			for i in sortedPreferences:
				for j in range(len(preferences)):
					if i == preferences[j] and localPackages[j].weight <= tmpRemainingCapacity:
						uids += [ localPackages[j].uid ]
						tmpRemainingCapacity -= localPackages[j].weight
			
		if len(uids) == 0:
			return None
			
		instruction = icfpInstruction( 	op 			= INST_PICK, 	\
										bid			= 1,			\
										robot		= self.robot, 	\
										package_ids	= uids			)
		
		return instruction


	# returns a fully formed instruction for dropping if client is carrying
	# packages to be delivered here, otherwise returns None
	def dropPackages(self):
		uids 		= []
		
		for p in self.robot.packages:
			if p.destination_x == self.robot.x and p.destination_y == self.robot.y:
				uids += [ p.uid ]
	
		if len(uids) == 0:
			return None
			
		instruction = icfpInstruction( 	op 			= INST_DROP, 	\
										bid			= 1,			\
										robot		= self.robot, 	\
										package_ids	= uids			)
	
		return instruction

	#
	# Hooks
	#
	
	# called immediately before first turn
	def _GameStart(self):
		self.baseReconComplete = 0

#
# Create client, connect to server, and start playing
#
if len(sys.argv) > 1:
	host = sys.argv[1]
	port = atoi(sys.argv[2])

	ed = kClient(host, port, animate=10, drawDelay=0.4)

	try:
		ed.start()

	except socket.error, e:
		print "Game over.  I survived ", ed.turn-1, "turns."
else:
	print "Usage: runme host port"
