# ICFP 2002 entry for OaSys
# see http://icfpcontest.cse.ogi.edu/ for details of contest
# Contact: Terry Stewart at tcstewar@connect.carleton.ca
# Version 2 (non-lightning round submission)
#
# Overview:
#  A fairly simple little program.  Here's the basic logic:
#     if we can drop packages to get points, do so
#     if we can pick up packages, pick up groups that go to the same
#         destination, if possible.  Choose the optimal group for the most weight, and bias selection
#         to choose lots of small boxes rather than a fex large ones.
#     if we have packages, go towards the closest one's destination
#     otherwise, go to the nearest base (ignoring ones we are pretty sure are empty)
#  When going towards a particular location, it will try to avoid running
#    into or near other robots and going near water (as long as that doesn't slow it down getting to its target).
#    it also has a 75% chance of running away if its path is blocked by another robot.  This is to
#    avoid deadlocks.
#  Finding a path to a location is done by determining the distance from every point on the map to
#    the target (up to as far as the needed point), and caching this data, of course.
#

import random
import socket
import sys


# ------------------------------------
# COMMUNICATIONS functions
# ------------------------------------


# initialize socket
s=socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((sys.argv[1],int(sys.argv[2])))

def sendLine(text):
  "Adds a \\n and sends the text to the server"
  print '--->'+text
  text=text+'\n'
  v=s.send(text)
  while v!=len(text):
    text=text[v:]
    v=s.send(text)
    

extra=''
def readLine():
  "Returns one line from the server"
  global extra
  while '\n' not in extra:
    extra=extra+s.recv(1024)
  i=extra.find('\n')
  res=extra[:i]
  extra=extra[i+1:]
  print '<---',res
  return res

def sendMove(bid,dir):
  "requests a move in a given direction"
  if dir not in ('N','S','E','W'):
    print 'ERROR! tried to move',dir
  sendLine('%d Move %s' % (bid,dir))
  
def sendPick(bid,packs):
  "attempts to pick up packages"
  m='%d Pick' % bid
  for p in packs:
    m=m+' '+`p`
  sendLine(m)
  
def sendDrop(bid,packs):
  "attempts to drop packages"
  m='%d Drop' % bid
  for p in packs:
    m=m+' '+`p`
  sendLine(m)




def pointsAround((x,y)):
  return ((x,y+1),(x,y-1),(x+1,y),(x-1,y))


class DistMap:
  def __init__(self,center,board):
    self.b=board
    self.c=center
    self.map=[]
    for i in range(0,board.h): self.map.append([9999999]*board.w)
    self.map[center[1]][center[0]]=0
    self.unprocessed=[center]
  def getDistanceTo(self,p):
    if self.b.getMapData(p) in ('#','~'):
      return 9999999
    (x,y)=p
    while self.map[y][x]==9999999 and len(self.unprocessed)>0:
      (lx,ly)=self.unprocessed.pop(0)
      value=self.map[ly][lx]+1
      for (nx,ny) in pointsAround((lx,ly)):
        if self.map[ny][nx]==9999999 and self.b.getMapData((nx,ny)) not in ('#','~'):
          self.map[ny][nx]=value
          self.unprocessed.append((nx,ny))
    return self.map[y][x]
      
      
    
    
      

# ------------------------------------
# Board data
# ------------------------------------

class Board:
  def __init__(self):
    self.distMaps={}           # cached distance maps for path finding
    self.packWeight={}   # known weights of packages
    self.packWeightTotal=0 # total weight of seen packages
    self.packCount=0       # total number of seen packages
    self.packDest={}     # known destinations of packages
    self.bases=[]        # list of bases that may have packages
    self.score={}        # best guesses for all players' scores
    
    self.w=-1            # width of board (after adding walls all around)
    self.h=-1            # height of board (after adding walls all around)
    self.map=[]          # map of the world (with walls added all around).  Access with map[y][x].
    self.id=''           # id of the robot (of the form '#3')
    self.strength=-1     # how much the robot can carry
    self.money=-1        # the amount of money the robot has
    self.loc={}          # location and carry list of all known robots.  loc['#1']=[x,y,[p1,p2,p3]]       
    
  def getMapData(self,(x,y)):
    return self.map[y][x]
    
  def getDistanceTo(self,x,y,exact=0):
    """returns the length of the best path from the current location to (x,y).
       If exact is zero, then it modifies this to add one to a distance if
       a robot is there or one step away."""
    (fx,fy,p)=self.loc[self.id]
    return self.getDistanceToFrom(x,y,fx,fy,exact)

  def getDistanceToFrom(self,x,y,fx,fy,exact=0):
    """returns the length of the best path from (fx,fy) to (x,y).
       If exact is zero, then it modifies this to add 3 or 1 to a distance if
       a robot is there or one step away."""
    if ((x,y)) not in self.distMaps:
      self.distMaps[(x,y)]=DistMap((x,y),self)
    dm=self.distMaps[(x,y)]
    r=dm.getDistanceTo((fx,fy))
    if not exact and r<9999999:
      if self.isOtherAt(fx,fy) and random.random()<0.75:
        r=r+3
      elif self.isOtherNear(fx,fy) or self.isWaterNear(fx,fy):
        r=r+1
    return r

  def isOtherAt(self,xx,yy,ignore='myself'):
    "checks if there is a robot other than me at (xx,yy)"
    if ignore=='myself': 
      ignore=self.id
    for id in self.loc.keys():
      (x,y,p)=self.loc[id]
      if (x,y)==(xx,yy) and id!=ignore:
        return 1
    return 0

  def isOtherNear(self,x,y,ignore='myself'):
    "checks if there is a robot other than me anywhere around (x,y)"
    return self.isOtherAt(x+1,y,ignore) or self.isOtherAt(x-1,y,ignore) or self.isOtherAt(x,y+1,ignore) or self.isOtherAt(x,y-1,ignore)
    
  def isWaterNear(self,x,y):
    "checks is there is water around (x,y)"
    for (xx,yy) in pointsAround((x,y)):
      if self.map[yy][xx]=='~': return 1
    return 0
  
  def getCarriedWeight(self):
    "returns the amount of weight of packages the robot is currently carrying"
    total=0
    for i in self.loc[self.id][2]:
      total=total+self.packWeight[i]
    return total

  def findBases(self):
    "scans the map for bases"
    self.bases=[]
    for y in range(0,len(self.map)):
      x=-1
      while 1:
        x=self.map[y].find('@',x+1)
        if x==-1:
          break
        else:
          self.bases.append((x,y))
  
  
# ------------------------------------
# Game functions
# ------------------------------------
  
def readBoard():
  "reads the initialization data from the server and sets up the board"  
  b=Board()
  dim=readLine().split()
  (b.w,b.h)=(int(dim[0])+2,int(dim[1]))
  b.map=['#'*b.w]
  for i in range(0,b.h):
    b.map.append('#'+readLine()+'#')
  b.map.append('#'*b.w)
  b.h=b.h+2
  b.findBases()
  
  me=readLine().split()
  (b.id,b.strength,b.money)=('#'+me[0],int(me[1]),int(me[2]))
  
  b.loc={}
  loc=readLine().split()
  while len(loc)>0:
    (id,xn,x,yn,y)=loc[:5]
    loc=loc[5:]
    b.loc[id]=[int(x),int(y),[]]
  return b

def readPackageList(b):
  "reads the list of packages at the current location"
  p=readLine().split()
  l={}
  while len(p)>0:
    (id,x,y,w)=p[:4]
    p=p[4:]
    id=int(id)
    x=int(x)
    y=int(y)
    w=int(w)
    l[id]=(x,y,w)
    b.packWeight[id]=w
    b.packDest[id]=(x,y)
    b.packWeightTotal=b.packWeightTotal+w
    b.packCount=b.packCount+1
  return l

def readUpdate(b):
  "reads the data from the server about what happened last turn, and updates the board"
  com=readLine().split()
  ids=[]
  while len(com)>0:
    id=com.pop(0)
    ids.append(id)
    acts=[]
    while len(com)>0 and com[0][0]!='#':
      acts.append(com.pop(0))
    while len(acts)>0:
      act=acts.pop(0)
      if act=='N':
        b.loc[id][1]=b.loc[id][1]+1
      elif act=='S':
        b.loc[id][1]=b.loc[id][1]-1
      elif act=='E':
        b.loc[id][0]=b.loc[id][0]+1
      elif act=='W':
        b.loc[id][0]=b.loc[id][0]-1
      elif act=='P':
        p=int(acts.pop(0))
        b.loc[id][2].append(p)
      elif act=='D':
        p=int(acts.pop(0))
        if p in b.packDest.keys():
          if b.packDest[p]==(b.loc[id][0],b.loc[id][1]):
            if id not in b.score.keys(): b.score[id]=0
            b.score[id]=b.score[id]+b.packWeight[p]
        elif not b.isOtherNear(b.loc[id][0],b.loc[id][1],ignore=id) and b.packCount>0:
          # guess that the robot delivered a package, and guess at its score
          if id not in b.score.keys(): b.score[id]=0
          b.score[id]=b.score[id]+b.packWeightTotal/b.packCount
        if p in b.loc[id][2]:
          b.loc[id][2].remove(p)
      elif act=='X':
        if id not in b.loc.keys():
          b.loc[id]=[-1,-1,[]]
        x=int(acts.pop(0))
        b.loc[id][0]=x
      elif act=='Y':
        if id not in b.loc.keys():
          b.loc[id]=[-1,-1,[]]
        y=int(acts.pop(0))
        b.loc[id][1]=y
  for i in b.loc.keys():
    if i not in ids:
      del b.loc[i]
      if i in b.score.keys():
        del b.score[i]        

def listPossibleDrop(b):
  "return all the held packages that have the current square as their location"
  (x,y,p)=b.loc[b.id]
  return filter(lambda id,b=b,x=x,y=y: b.packDest[id]==(x,y),p)
  
def getDest(b):
  "return the closest destination for a package I'm holding.  Returns None if there are no packages."
  (x,y,p)=b.loc[b.id]
  best=None
  dist=9999999
  for id in p:
    (x,y)=b.packDest[id]
    d=b.getDistanceTo(x,y,exact=1)
    if d<dist:
      best=(x,y)
      dist=d
  return best  
  
def listPossiblePackages(b,pack):
  """returns a list of packages we can pick up.  First it groups packages by
     destination.  These destinations are then sorted by distance, and the 
     packages for each group are sorted from smallest to largest.  Now we
     consider each group in order, from closest to farthest.  For each group,
     we call findBestFit to grab the optimal set of packages.  We only go on
     to the next group if either we've grabbed everything from the last
     group, or if the point ratio (score/(2*dist)) is at least as good."""
  max=b.strength-b.getCarriedWeight()
  r=[]
  
  dests={}
  for id in pack.keys():
    d=b.packDest[id]
    (x,y)=d
    if d not in dests:
      dests[d]=(b.getDistanceTo(x,y,exact=1),[])
    dests[d][1].append((id,b.packWeight[id]))
  l=[]
  for (dist,p) in dests.values():
    if dist<9999999:
      p.sort(lambda a,b: cmp(a[1],b[1]))
      l.append((dist,p))
  l.sort(lambda a,b: cmp(a[0],b[0]))  
  
  oldratio=-1
  for (dist,p) in l:
    (best,amount)=findBestFit(p,max)
    ratio=float(amount)/(2*dist)
    if len(best)<len(p):
      if oldratio==-1:
        oldratio=ratio
    if oldratio>=0 and ratio<oldratio:
      break
    max=max-amount
    for (id,w) in best:
      r.append(id)
  print 'allpacks:',l
  print 'chosen',r
  return r
  
def findBestFit(p,max):
  """finds the best fit for which packages to pick up (i.e. the maximum
   weight possible).  This algorithm prefers larger sets of packages (since
   we only lose one when pushed by another robot)."""

  if p[0][1]>max:       # if the smallest item is too big, ignore this group
    return ([],0)
  c=[]
  space=max
  for index in range(0,len(p)):
    (id,w)=p[index]
    if space==0:        # if we're packed completely, stop looking for more
      break
    if w>max:           # if we're now looking at way too big objects, stop
      break             
    if w<=space:        # if there's room for this one, add it
      c.append((id,w))
      space=space-w
    elif w<=max:               # otherwise, see if we can make room by deleting everything else and doing some recursion
      improvedSpace=max-w
      (sub,amount)=findBestFit(p[:index],improvedSpace)
      improvedSpace=improvedSpace-amount
      
      if improvedSpace<space:
        c=sub
        c.append((id,w))
        space=improvedSpace
  return (c,max-space)
      
      


def goTo(b,x,y,bid=1):
  """moves towards (x,y).  Checks to see which direction will make it closest to
     the target.  Randomly chooses among equal distances.  Since getDistanceToFrom
     increases by one the distance measurement if there's another robot near that spot,
     it will tend to avoid other robots if there is another equally good route.  It
     will also avoid water in this manner.  Also, there is a 75% chance that it will
     not try to run into a robot if there is one in the way (it will go around or back up,
     due to increasing the distance count by 3)."""
  (sx,sy,p)=b.loc[b.id]
  n=b.getDistanceToFrom(x,y,sx,sy+1)
  s=b.getDistanceToFrom(x,y,sx,sy-1)
  e=b.getDistanceToFrom(x,y,sx+1,sy)
  w=b.getDistanceToFrom(x,y,sx-1,sy)
  best=min(n,s,e,w)
  l=filter(lambda (v,s),best=best: v==best,((n,'N'),(s,'S'),(e,'E'),(w,'W')))
  (value,symbol)=random.choice(l)
  sendMove(bid,symbol)


def doAI(b,pack):
  "Does the AI for a turn."
  
  # if I'm at a base, and there's nothing here, remove it from my list of bases.
  (sx,sy,p)=b.loc[b.id]
  if len(pack)==0 and b.map[sy][sx]=='@' and (sx,sy) in b.bases:
    print 'Removing base at (%d,%d) from list' % (sx,sy)
    b.bases.remove((sx,sy))

  print 'id:',b.id,'money:',b.money,'scores:',b.score    
  print b.loc
  print 'Robot at (%d,%d)' % (b.loc[b.id][0],b.loc[b.id][1])
  
  # try to drop packages if we're at the destination
  drop=listPossibleDrop(b)
  if len(drop)>0:
    print 'Dropping packages at target:',drop
    sendDrop(1,drop)
  else:

    # try to grab packages if we can and no one else is around (don't get into
    # fights with other robots for packages)
    grab=listPossiblePackages(b,pack)
    if len(grab)>0 and not b.isOtherNear(sx,sy):
      print 'Picking up packages:',grab
      sendPick(1,grab)

    else:
      # go towards the closest destination for a package we have
      dest=getDest(b)
      if dest!=None:
        print 'Delivering package to (%d,%d)'%(dest[0],dest[1])
        goTo(b,dest[0],dest[1])

      else:
        # go towards the nearest base
        bbd=9999999
        if len(b.bases)==0:
          b.findBases()
        for base in b.bases:
          d=b.getDistanceTo(base[0],base[1])
          if d<bbd:
            bbd=d
            bb=base
        print 'Going to base at (%d,%d)' % (bb[0],bb[1])
        goTo(b,bb[0],bb[1])   
  b.money=b.money-1    #we always bid 1
      
      
      
 

#play the game
sendLine('Player')
b=readBoard()
while 1:
  pack=readPackageList(b)
  doAI(b,pack)
  readUpdate(b)