#!/c/lang/python22/python -O
# #!/usr/bin/python22 -O

#This code is duplicated in source/crudebuteffective.py.
#This version is altered to suppress printing the
#"trip log" of the game.

import socket
import string
import random
import types
import copy
import sys

def toInts(line):
    ints = line.split()
    ints = map(string.strip, ints)
    ints = map(int, ints)
    return ints

def splitBy(list, int):
    chunks = []
    for i in range(len(list)):
        if (i + 1) % int == 0:
            lower = max(0, (i-int) + 1)
            upper = i + 1
            chunks.append(list[lower:upper])
    return chunks

def uniq(list):
    l2 = []
    for x in list:
        if not (x in l2):
            l2.append(x)
    return l2

def charlist(str):
    lst = []
    for c in str:
        lst.append(c)
    return lst

class Rings:

    def __repr__(self):
        return "Rings(%s, %s)" % (self.robot, self.dest)
    def __init__(self, bounds, valid, robot, dest):
        self.__dict__.update(locals())
        target = robot
        src = dest
        self.rings = [[dest]]
        self.targetDistance = None
        self.route = None
        i = 0
        #print >> sys.stderr, self
        while 1:
            ring = self.ringAtDistance(i)            
##            print >> sys.stderr, "RING(%s)" % i, len(ring), ring
            if not ring:
                raise "Huh?"
            if target in ring:
                self.targetDistance = i
            if self.targetDistance and i >= self.targetDistance:
                if self.shortestRoute():
                    break
            i += 1
        #print >> sys.stderr, "Shortest route from %s to %s: %s" % (self.robot, self.dest, self.route)

    def ringAtDistance(self, dist):
        if len(self.rings) > dist:
            return self.rings[dist]
        ring = []
        lastring = self.rings[dist - 1]
        lastlastring = dist > 1 and self.rings[dist - 2] or []
        for pt in lastring:
            zone = zone4(self.bounds, pt)
##            if dist < 5:
##                print >> sys.stderr, "Zone:", zone
            zone = filter(self.valid, zone)
            zone = filter(lambda x:not x in lastring, zone)
            zone = filter(lambda x:not x in lastlastring, zone)
            zone = filter(lambda x:not x in ring, zone)
            ring.extend(zone)
        ring = uniq(ring)
        self.rings.append(ring)
        return ring


##    def backtrack(self):
##        start = self.robot
##        ringNtx = self.targetDistance
##        closest = sys.maxint
##        closestpos = None
##        for ring in self.rings[ringNtx:]:
##            for pos in ring:
##                if pos != start:
##                    dist = distance(start, pos)
##                    if dist < closest:
##                        closest = dist
##                        closestpos = pos
##        if not closestpos:
##            print sys.stderr, "Ack! no closestpos??"
##            return None
##        assert closestpos != start
##        return Rings(self.bounds, self.board, start, closestpos).shortestRoute()
            

    def shortestRoute(self):
        if self.route:
            return self.route
        ring = self.targetDistance
        start = self.robot
        dest = self.dest
        route = [start]
        bounds = (len(self.rings), len(self.rings))
        def findRoute(point, depth, fast = 1):
##            print >> sys.stderr, "findRoute(%s, %s):" % (point, depth)
            if point == dest:
##                print >> sys.stderr, [(point,[])]
                return [(point,[])]
            zone = zone4(bounds, point)
            zone = filter(lambda x:x in self.rings[depth-1], zone)            
            if not zone:
##                print >> sys.stderr, None
                return None
            res = []
            for pt in zone:
                route = findRoute(pt, depth - 1)
                if route:
                    res.append((pt, route))
                    if fast:
                        break
            if not res:
##                print >> sys.stderr, [(point,[])]                
                return None
##            print >> sys.stderr, [(point,[])]
            return res
        route = findRoute(start, self.targetDistance)
        import pprint
##        print >> sys.stderr, "ROUTE:"
##        pprint.pprint(route, sys.stderr)
        self.route = self.shorten(route)
##        print >> sys.stderr, "FLAT ROUTE:"        
##        pprint.pprint(self.route, sys.stderr)
        return self.route

    def shorten(self, route):
        res = []
        while route:
            res.append(route[0][0])
            route = route[0][1]
        return res[:-1]

        
        
        
    
class Package:
    all_packages = {}
    def __init__(self, intlist):
        self.id = intlist[0]
        self.pos = (intlist[1], intlist[2])
        self.weight = intlist[3]
        self.live = 1
        self.all_packages[self.id] = self
    def __repr__(self):
        return "Package(%s, %s, %s)" % (self.id, self.pos, self.weight)

class Robot:
    def __init__(self, id):
        self.id = id
        self.pos = (0,0)
        self.packages = []
        self.live = 1
        self.capacity = 0
        self.lastMove = None

    def move(self, direction):
        self.pos = nextCell(self.pos, direction)
        self.lastMove = direction

    def pick(self, pkg):
        self.packages.append(pkg)
        self.capacity -= Package.all_packages[pkg].weight
        #print >> sys.stderr, "Picked up:", pkg

    def drop(self, pkg):
        try:
            self.packages.remove(pkg)
            self.capacity += Package.all_packages[pkg].weight
            #print >> sys.stderr, "Dropped:", pkg
        except:
            #print "Bot tried to drop a package it wasn't carrying"
            pass

    def __repr__(self):
        return "Robot(%s)" % self.id

    def nextTo(self, dest):
        return self.dirTo(dest.pos)

    def dirTo(self, pos):
        if self.pos[0] == pos[0]:
            return self.pos[1] > pos[1] and 'S' or 'N'
        if self.pos[1] == pos[1]:
            return self.pos[0] > pos[0] and 'W' or 'E'
        

    def distance(self, obj):
        if type(obj) != type(()):
            pos = obj.pos
        else:
            pos = obj
        return distance(self.pos, pos)

def distance(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])
        

class MyRobot(Robot):
    def __init__(self, id, capacity,  money):
        Robot.__init__(self, id)
        self.capacity = capacity
        self.money = money
        self.route = None
        self.expectNotify = None

    def __repr__(self):
        return "MyRobot(%s, %s, %s)" % (self.id, self.capacity, self.money)

class Action:
    def __init__(self, actlist):
        self.id = int(actlist[0])
        actlist = actlist[1:]
        self.actions = []
        i = 0
        while i < len(actlist):
            act = actlist[i]
            if act in 'NSWE':
                self.actions.append((act,None))
            else:
                self.actions.append((act,int(actlist[i+1])))
                i +=1
            i += 1

def cellAt(board, (x, y)):
    if x < 1 or y < 1:
        return '#'
    return board[y-1][x-1]

def nextCell((x, y), direction):
    if direction == 'N':
        return (x, y+1)
    elif direction == 'S':
        return (x, y-1)
    elif direction == 'E':
        return (x + 1, y)
    elif direction == 'W':
        return (x - 1, y)

MOVES = "NSWE"
WATER = '~'
BASE = '@'
PLAIN = '.'
WALL = '#'

NORTH = 'N'
WEST = 'W'
SOUTH = 'S'
EAST = 'E'

class Strategy:
    def __init__(self, board, conf):
        self.bounds, self.board = board
        self.conf = conf
        self.robot = MyRobot(conf[0], conf[1], conf[2])
        self.otherbots = {}
        self.history = []
        self.turn = 0
        self.homebases = []
        self.status = []
        self.maybePackages = []
        for row in range(self.bounds[1]):
            for col in range(self.bounds[0]):
                if self.board[row][col] == BASE:
                    self.homebases.append((col + 1, row + 1))
                    
    def cellAt(self, (x, y)):
        return cellAt(self.board, (x, y))

    def updateBots(self, actions):
        #print "My robot:", self.robot
        #print "update with:", actions
        myRobotUpdated = 0
        updatedbots = []
        for act in actions:
            id = act.id
##            print "ID:", id
            acts = act.actions
            if id == self.robot.id:
                bot = self.robot
                myRobotUpdated = 1
            else:
                bot = self.otherbots.get(id)
                if not bot:
                    self.otherbots[id] = bot = Robot(id)
                updatedbots.append(bot)
#            print "ACTS:", acts
##            print "Adjusting bot:", bot
            for (action, param) in acts:
                if action in MOVES:
                    bot.move(action)
                elif action == 'P':
                    bot.pick(param)
                elif action == 'D':
                    bot.drop(param)
                    if Package.all_packages[param].pos != self.robot.pos:
                        self.status.append("Rebooting")
                elif action == 'X':
                    bot.pos = (param, bot.pos[1])
                elif action == 'Y':
                    bot.pos = (bot.pos[0], param)
                else:
                    raise "Unknown action:", action
        for bot in filter(lambda x:x in updatedbots, self.otherbots.values()):
            bot.live = 0
            self.maybePackages.append(bot.pos)
#        if self.robot.expectNotify and not myRobotUpdated:
            #print >> sys.stderr, "Hey, expected: %s" % self.robot.expectNotify
        #self.displayMap()

    def displayMap(self):
        map = copy.deepcopy(self.board)
        for pkg in self.maybePackages:
            map[pkg[1] -1][pkg[0]-1] = '?'
        for robot in self.otherbots.values():
            if robot.live:
                map[robot.pos[1]-1][robot.pos[0]-1]='R'                
        robot = self.robot
        map[robot.pos[1]-1][robot.pos[0]-1]='M'
        map.reverse()
        for row, i in zip(map, range(len(map))):
            maprow = "".join(row)
            #print maprow + (len(self.status) > i and "\t" + self.status[i] or "")
        del self.status[:]
        
    def playTurn(self, actions, packages):
        self.updateBots(actions)
        self.turn += 1
        return self._turn(actions, packages)

    def percentMax(self, percent, maxPoints):
        points = min(maxPoints, int(self.robot.money * (percent/100.0)))
        return points

    def cmdMove(self, bid, direction):
        assert type(direction) is type("") and len(direction) == 1, repr(direction)
        self.robot.money -= int(bid)
        self.robot.expectNotify = direction
        self.history.append(self.robot.pos)
        return "%s Move %s" %(str(int(bid)), direction)

    def cmdPick(self, bid, packageIDs):
        self.robot.money -= int(bid)
        return "%s Pick %s" % (int(bid), " ".join(map(str, packageIDs)))

    def cmdDrop(self, bid, packageIDs):
        self.robot.money -= int(bid)
        return "%s Drop %s" % (str(int(bid)), " ".join(map(str, packageIDs)))

##    def zone(self, obj):
##        x, y = obj.pos
##        xmax = self.bounds[0]
##        ymax = self.bounds[1]
##        
##        zone = []
##        if x > 2:
##            zone.append((x - 1, y))
##            if y > 2:
##                zone.append((x - 1, y - 1))
##            if y < ymax:
##                zone.append((x - 1, y + 1))
##        if x > 1 and x < xmax:
##            zone.append((x + 1, y))
##            if y > 2:
##                zone.append((x + 1, y - 1))
##            if y < ymax:
##                zone.append((x + 1, y + 1))
##        if y > 2:
##            zone.append((x, y + 1))
##        if y > 1 and y < ymax:
##            zone.append((x, y - 1))
##        return zone

    def zone4(self, obj):
        return zone4(self.bounds, obj.pos)

    def valid(self, (x,y)):
        return x > 0 and y > 0 and x < self.bounds[0] and y < self.bounds[1]

def zone4(bounds, pos):
    assert type(pos) == types.TupleType, pos
    x, y = pos
    xmax, ymax = bounds
    zone = []
    if x >= 2:
        zone.append((x - 1, y))
    if x < xmax:
        zone.append((x + 1, y))
    if y >= 2:
        zone.append((x, y - 1))
    if y < ymax:
        zone.append((x, y + 1))
    return zone
    

class CrudeButEffective(Strategy):
    def __init__(self, board, conf):
        Strategy.__init__(self, board, conf)
        self.routes = {}

    def cmdMove(self, bid, dir):
        return Strategy.cmdMove(self, bid, dir)

    def cmdPick(self, bid, list):
        return Strategy.cmdPick(self, bid, list)

    def cmdDrop(self, bid, list):
        return Strategy.cmdDrop(self, bid, list)
    
    def checkForKillableBots(self):
        return self.checkForPushableBots(homicidal = 1)

    def checkForPushableBots(self, homicidal = 0):
        best_pkgs = 0
        kill = None
        for bot in self.otherbots.values():
            direction = self.robot.nextTo(bot)
            if direction:
                next = nextCell(bot.pos, direction)
                if self.valid(next):
                    if (not homicidal) or self.cellAt(next) == WATER:
                        if (not goodbot) or len(bot.packages) > best_pkgs:
                            kill = direction
        return kill

    def seek(self):
        direction = None
        base = self.nearestBase()
        if base:
            direction = self.planRoute(base)
        if direction:
            self.status.append("Going to base at %s" % (base,))
            return direction
        nearby = self.zone4(self.robot)
##        print "--nearby:", nearby
        contents = map(lambda x:(x, self.cellAt(x)), nearby)
##        print "--contents:", contents
        viable = filter(lambda t:t[1] in (PLAIN, BASE), contents)
##        print "--viable:", viable
        self.status.append("Moving randomly, no goal.")
        if viable:
            dest = random.choice(viable)
            direction = self.robot.dirTo(dest[0])
            if self.robot.lastMove and direction == opposite(self.robot.lastMove):
                if len(viable) > 1:
                    viable.remove(dest)
                    dest = random.choice(viable)
                    direction = self.robot.dirTo(dest[0])
            return direction
        else:
            return None

    def nearestBase(self):
        nearest = sys.maxint
        nearbase = None
        for base in self.homebases:
            dist = self.robot.distance(base)
            if dist > 0 and dist < nearest:
                nearest = dist
                nearbase = base
        return nearbase

    def planRoute(self, dest):
        rt = self.routes.get(dest)
        if rt:
            if self.robot.pos in rt:
                ntx = rt.index(self.robot.pos)
                if ntx + 1 < len(rt):
                    #print >> sys.stderr, "Using cached route"
                    return self.robot.dirTo(rt[ntx + 1])
        rings = Rings(self.bounds, lambda x:cellAt(self.board, x) in (PLAIN, BASE), self.robot.pos, dest)
        route = rings.shortestRoute()
        #print >> sys.stderr, "Using route", route
        self.routes[dest] = route
        return self.robot.dirTo(route[0])
        
    def _turn(self, actions, packages):
        bid = 1
        if self.cellAt(self.robot.pos) == BASE:
            if not packages:
                try:
                    self.homebases.remove(self.robot.pos)
                except:
                    pass
                    #print >> sys.stderr, "Couldn't remove %s from %s" % (self.robot.pos, self.homebases)
        #If there's a vulnerable bot nearby, kill it.
        try:
            direction = self.checkForKillableBots()
            if direction:
                self.status.append("Trying to kill!")
                return self.cmdMove(self.percentMax(20,100), direction)
            direction = self.checkForPushableBots()
            danger = not not direction
            if danger:
                bid  = 5
            if self.robot.packages:            
                drops = []
                for package in map(Package.all_packages.get, self.robot.packages):
                    if package.pos == self.robot.pos:
                        drops.append(package.id)
                if drops:
                    self.status.append("Dropping")
                    return self.cmdDrop(1, drops)
            if packages:
                available = self.robot.capacity
                picks = []
                packages.sort(lambda x, y: cmp(y.weight, x.weight))
                self.status.append("Package weights " + repr(map(lambda x:x.weight, packages)))
                for pkg in packages:
                    if pkg.weight < available:
                        self.status.append(repr(pkg))
                        picks.append(pkg.id)
                        available -= pkg.weight
                self.robot.newpackages = 1
                if picks:
                    self.status.append("Pickup")
                    return self.cmdPick(self.percentMax(1,10), picks)
            if self.robot.packages:
                self.status.append("Carrying " + repr(self.robot.packages))
                closest = -1
                for pkgID in self.robot.packages:
                    package = Package.all_packages[pkgID]
                    package.distance = self.robot.distance(package)
                    if closest < 0 or package.distance < closest:
                        closest = package
                nextStep = self.planRoute(closest.pos)
            else:
                nextStep = self.seek()
            direction = self.avoidNearbyBots(nextStep)
            if direction:
                self.status.append("Trying to avoid")
                bid, nextStep = direction
            return self.cmdMove(bid, nextStep)
        except:
            self.status("Error occurred, ignoring")
            self.cmdDrop(bid, [])
        
    def avoidNearbyBots(self, dir):
        target = nextCell(self.robot.pos, dir)        
        for bot in self.otherbots.values():
            if bot.pos == target:
                dirs = flank(dir)
                if self.cellAt(nextCell(self.robot.pos, dirs[0])) in (PLAIN, HOME):
                    return 1, dirs[0]
                if self.cellAt(nextCell(self.robot.pos, dirs[1])) in (PLAIN, HOME):
                    return 1, dirs[1]
            return self.percentMax(2,20), dir
                 
_opposites = {'N':'S',
              'S':'N',
              'E':'W',
              'W':'E',
              None:None}

def opposite(dir):
    return _opposites[dir]
    
def flank(dir):
    return filter(lambda x:not (x in dir, opposite(dir)), MOVES)

    
def playGame(host, port, strategyfunc):
    def receiveBoard():
        dimensions = toInts(sockfile.readline())
        width, height = dimensions[0], dimensions[1]
        rows = []
        for i in range(height):
            rows.append(charlist(sockfile.readline())[:width])
        assert height == len(rows)
        return ((width, height), rows)
        
    def receiveConf():
        id, capacity, money = toInts(sockfile.readline().strip())
        #print "CONF:", id, capacity, money
        return id, capacity, money

    def receiveResponse():
        actions = filter(None, sockfile.readline().strip().split("#"))
        if strategy:
            strategy.status.append("ACTIONS:" + repr(actions))
        for i in range(len(actions)):
            playerParts = actions[i].split()                
            actions[i] = Action(playerParts)
        return actions

    def receivePackages():
        packageData = toInts(sockfile.readline().strip())
        packageData = splitBy(packageData, 4)
        packages = map(Package, packageData)
        strategy.status.append("PACKAGES" + repr(packages))
        return packages
        
    strategy = None
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.connect((host,port))
    sock.send('Player\n')
    sockfile = sock.makefile('r', 1024)
    board = receiveBoard()
    conf = receiveConf()
    actions = receiveResponse()
    strategy = strategyfunc(board, conf)
    global STRATEGY
    STRATEGY = strategy
    while 1:
        packages = receivePackages()
        cmd = strategy.playTurn(actions, packages).strip() + "\n"
        strategy.status.append("Command:" + cmd.strip())
        sys.stderr.write(cmd)
        sock.send(cmd)
        actions = receiveResponse()
    sock.shutdown()
    
    

if __name__ == '__main__':
    import sys
    host, port = sys.argv[1:3]
#    print "Connecting to %s:%s" % (host, port)
    playGame(host, int(port), CrudeButEffective)
    
    
