#! /usr/bin/python
''' NutCracker4 - A competition squirrel that uses a TSP heuristic
for the single squirrel case, and path optimisation algorithm for
the squirrel free-for-all.
Competition squirrel by Mike Sweeney 28 Nov 04.
------------------------------------------------------------------------------
'''

import sys, time, operator
from string import *
from random import choice, shuffle
#sys.stderr = open( 'error.log', 'a' )
#dbug = sys.stderr.write
def dbug(X):pass

sqmap, nutmap = {}, {}    # Squirrel and nut counts for used locations
for line in file( sys.argv[1] ).readlines():
	line = strip(line)    # Remove leading space and new line
	if line and line[0] != '#':   # Ignore blank lines & comments (1)
		name, loc = split( line, '=' )
		xy = eval('(%s)'%loc)    # Convert string to location tuple
		if   name=='SIZE':     size = xy[0]
		elif name=='YOU':      me = xy
		elif name=='NUT':      nutmap[xy] = 1
		elif name=='SQUIRREL': sqmap[xy] = sqmap.get(xy,0)+1

adj=[ (x,y) for x in [-1,0,1] for y in [-1,0,1] ]
adj.remove( (0,0) )    # If we cannot rest, remove current square

if sqmap[me]>1: sqmap[me] -= 1 # Remove self from squirrel list
else: del sqmap[me]

def getdist(a,b): return max( abs(a[0]-b[0]), abs(a[1]-b[1]) )
def sum(L): return reduce( operator.__add__, L, 0 )

# 'Guide our squirrel onto an adjacent square aiming at destination'
def guide( dest ): return me[0]+cmp(dest[0],me[0]), me[1]+cmp(dest[1],me[1])

def mkindex( map ):
	'Return row and column indexes for this map of points'
	stripx, stripy = {}, {}
	for k,v in map.items():
		px,py = k
		stripx.setdefault( px, {} )[k] = v
		stripy.setdefault( py, {} )[k] = v
	return stripx, stripy

def mkmatrix( base, targx, targy, limit=40 ):
	'''Return a set of points from targets at each radius from the points
	in base. Each will have at least "limit" points and out to radius 5'''
	# matrix[point][range] -> { (x,y):v, ... }
	matrix, ranges = {}, {}
	for p1 in base:
		total = 0
		loc = {}
		rangecount = {}
		for radius in range( 1, size+1 ):
			if max( p1[0], size-p1[0], p1[1], size-p1[1] ) < radius : break
			loc[radius] = {}
			for dimA, index, dimB in ( [0,targx,1], [1,targy,0] ):
				for offset in ( p1[dimA]+radius, p1[dimA]-radius ):
					for p2,v2 in index.get( offset, {} ).items():
						if abs( p2[dimB] - p1[dimB] ) <= radius: 
							loc[radius][p2] = v2
			rangecount[radius] = len( loc[radius] )
			total += len( loc[radius] )
			if total > limit and radius >= 5: break
		matrix[p1] = loc
		ranges[p1] = rangecount
	return matrix, ranges

def calcvalue( moves, sqrings, nutrings ):
	'''Calculate value (int) of this nut in so many moves. Value is low
	if other squirrels are closer, 1 if further away, and very high if we
	can beat them there by one move (nasty!).'''
	penalty = 0
	for radius in range( 1, moves ):
		squirrelcount = sum( sqrings.get(radius,{}).values() )
		if squirrelcount:
			penalty += squirrelcount * (moves-radius)
	if penalty:
		value = 0.7 / penalty
	else:
		if sqrings.get(moves): 
			value = 1.5 / (1+sum( sqrings[moves].values() ))
		elif sqrings.get(moves+1): 
			value = 1. + .3 * sum( sqrings[moves+1].values() )
		else:
			value = 1.
	value *= 1 + 0.3*len(nutrings[1]) + 0.1*len(nutrings[2])
	return int( 100*value/(1+moves) )

def buildpaths( inppathlist, matrix, nsmatrix, nnmatrix ):
	'Extend paths with associated distance and reward'
	# matrix must have at least one nut
	pathlist = []
	for rew,dist,path in inppathlist :
		p = path[-1]
		nutrings = matrix[p]
		for radius in range(1,25):
			radset = nutrings.get(radius,{})
			for w in radset.keys():
				if w in path: continue
				bonus = calcvalue( dist+radius, nsmatrix[w], nnmatrix[w] )
				pathlist.append( (rew+bonus,dist+radius,path+[w]) )
	if not pathlist: pathlist = inppathlist
	pathlist.sort()
	return pathlist[-30:]

def multi():
	'Compute the best COA with this nut and squirrel configuration'
	tlim = time.clock() + 5.0
	# Return a range matrix for nut-nut, nut-sq, sq-nut:
	nutx, nuty = mkindex( nutmap )
	sqx, sqy = mkindex( sqmap )
	NNmatrix, NNcount = mkmatrix( nutmap, nutx, nuty )
	NSmatrix, NScount = mkmatrix( nutmap, sqx, sqy )
	SNmatrix, SNcount = mkmatrix( sqmap, nutx, nuty )
	meNmatrix, meNcount = mkmatrix( {me:1}, nutx, nuty )
	# Compute path options with simulation:
	pathlist = buildpaths( [(0,0,[me])], meNmatrix, NSmatrix, NNmatrix )
	while time.clock() < tlim :
		pathlist = buildpaths( pathlist, NNmatrix, NSmatrix, NNmatrix )
	# Now choose move using simulation data:
	reward, totaldist, bestpath = pathlist[-1]
	dbug( 'Path (%s) of dist=%s is %s\n' % pathlist[-1] )
	return guide( bestpath[1] ) #NOTE: [0] is self

def mknewtour( nutlist, tour=[] ):
	'Starting at "me", add each nut into the tour or on the end (lowest cost)'
	if tour:
		tour = [me] + tour
		nutstoadd = nutlist
	else:
		tour = [ me, nutlist[0] ]
		nutstoadd = nutlist[1:]
	for point in nutstoadd :
		lowest_cost = 100000
		x0,y0 = point
		for pos in range(len(tour)):
			x1,y1 = tour[pos]
			if pos < len(tour)-1 :
				x2,y2 = tour[pos+1]
				cost = max(abs(x1-x0),abs(y1-y0)) \
					 + max(abs(x2-x0),abs(y2-y0))  \
					 - max(abs(x1-x2),abs(y1-y2))
			else:
				# This is the last point on tour, so cost is adding on the end.
				cost = max(abs(x1-x0),abs(y1-y0))
			if cost == lowest_cost:
				best_pos_list.append( pos )
			elif cost < lowest_cost:
				lowest_cost, best_pos_list = cost, [pos]
		chosen_pos = choice( best_pos_list )
		tour.insert( chosen_pos+1, point )
	return tour[1:]

def tourlen( tour, start=None ):
	'Return the length of the tour'
	p1 = tour[0]
	if start: sum = getdist( start, p1 )
	else: sum = 0
	for p2 in tour[1:]:
		sum = sum + getdist( p1, p2 )
		p1 = p2
	return sum

def perm( s ):
	'Return the permutations sequences list of a sequence s'
	if len(s) == 1: return [s]
	out = []
	for i in range(len(s)):
		out.extend( [ [s[i]]+p for p in perm(s[:i]+s[i+1:]) ] )
	return out

def optimise( tour, N=6 ):
	'Return an optimised tour using a series of algorithms.'
	if len(tour) < N : return tour
	#Use a peehole optimiser with window N to improve the tour:
	for begin in (2,1,3,0):
		for i in range( begin, len(tour)-N+1, 4 ) + [len(tour)-N+2] :
			# The last iter will have N-1 points - a free right end (kewl).
			bestseg = tour[i:i+N]
			bestseglist = [bestseg]
			bestlen = tourlen( bestseg )
			for newmid in perm( bestseg[1:N-1] ) :
				newseg = bestseg[0:1] + newmid + bestseg[N-1:N]
				newlen = tourlen( newseg )
				if newlen == bestlen:
					bestseglist.append( newseg )
				elif newlen < bestlen:
					dbug( 'Window Opt: %u->%u\n' % (bestlen,newlen) )
					bestlen, bestseglist = newlen, [newseg]
			chosen_seg = choice( bestseglist )
			if chosen_seg != bestseg:
				tour[i:i+N] = chosen_seg
	return tour

def solo( fn='mytour.dat' ):
	'Return the best move for a single squirrel game'
	if len(nutmap) > 80 : think = 1.2
	else: think = 0.3
	try: 
		besttour = eval( file(fn,'r').read() )
		if len(besttour) < len(nutmap.keys()) : raise
	except: 
		besttour, think = nutmap.keys(), 9.0
	bestlen = tourlen( besttour, me )
	loop, bestc, optc = 0, 0, 0
	tlim = time.clock() + think
	while 1:
		loop += 1
		nuts = nutmap.keys()
		if len(nuts) < 3 : 
			tour = nuts
			if len(nuts)==2:
				if getdist(me,nuts[0]) > getdist(me,nuts[1]) : tour.reverse()
		else:
			shuffle(nuts)
			tour = mknewtour( nuts )
		tlen = tourlen( tour, me )
		if tlen <= (bestlen * 1.02):
			tour = optimise( [me]+tour, 6 )[1:]
			optc += 1
			optlen = tourlen( tour, me )
			if optlen < tlen:
				dbug('Total Optimised %u to %u\n' % (tlen,optlen))
			if optlen == bestlen:
				bestc += 1
			elif optlen < bestlen:
				besttour, bestlen, bestc = tour, optlen, 1
		if time.clock() > tlim: break	
	dbug('%4s(%s|%s): Best (%s) = %s\n' % (loop,optc,bestc,bestlen,besttour))
	next = guide( besttour[0] )
	# Are moving onto the nut square? Get next destination.
	if next == besttour[0] : del besttour[0]
	file(fn,'w').write( `besttour` )
	return next

if __name__ == '__main__':
	if sum(sqmap.values()) == 0: move = solo()
	else: move = multi()
	print '%d,%d' % move