from __future__ import generators
# python imports

import re, xreadlines, string
# our imports

import IO, ICFP, defs, AStar, defs, proc


HOST = 'localhost'

PORT = 80



__version__ = "$Revision: 1.31 $"



global _world_global_

_world_global_ = None

global Jiff

Jiff = None

class Home:

  """hollow class to let home nodes be used in FindClose"""

  def __init__(self, coords):

    self.imp_loc = coords # important_loc

    self.curr_loc = coords # where it really is

    self.carrot = []

    return



class Bot:

  """The basic class to store Bot state"""

  def __init__(self, id, carry = 0, money = 0):

    self.id = id

    self.carrymax = carry

    self.carrying = 0

    self.capacity = carry

    self.startmoney = money

    self.money = money

    self.x_pos = None

    self.y_pos = None

    self.curr_loc = None

    self.last_loc = None

    self.packages = {}

    self.package_cnt = 0

    self.deliverme = None

    self.score = 0

    self.current_walk = None

    return



  def player_string(self):

    return "%d %d %d\n" % (self.id, self.carrymax, self.startmoney)



  def set_x(self, x):

    self.x_pos = x

    return



  def set_y(self, y):

    self.y_pos = y

    return



  def move(self, dir):

    """ NB, We invert the map N-S so 1,1 is NW!"""

    global _world_global_

    

    self.last_loc = (self.x_pos, self.y_pos)

    if (dir == 'E'):

      self.set_x(self.x_pos + 1)

    elif (dir == 'W'):

      self.set_x(self.x_pos - 1)

    elif (dir == 'S'):

      self.set_y(self.y_pos - 1)

    elif (dir == 'N'):

      self.set_y(self.y_pos + 1)

    else:

      raise 'Bad direction passed to Bot::mov'



    self.curr_loc = (self.x_pos, self.y_pos)

    if (self != _world_global_.bot):

      _world_global_.board.C_board.rm_player(self.last_loc)

      _world_global_.board.C_board.add_player(self.curr_loc)

    return



  def rev_move(self, oldpos, newpos):

    """return a direction for two tuples of adjacent coords"""

    if (oldpos[0] < newpos[0]):

      return 'E'

    elif (oldpos[0] > newpos[0]):

      return 'W'

    elif (oldpos[1] > newpos[1]):

      return 'S'

    elif (oldpos[1] < newpos[1]):

      return 'N'

    else:

      raise 'Bad tuple'



  def pickup(self, package):

    """A bot picked up a package"""

    self.packages[package.id] = package

    if (package.weight): # if it is known

      self.carrying += package.weight

      self.capacity -= package.weight

    self.package_cnt += 1

    # pretend we don't know where packages are when carried by others

    # if we really want to know -- do a reverse lookup

    package.curr_loc = None

    if (not self.deliverme):

      self.deliverme = package

    return



  def drop(self, package):

    global _world_global_

    if (package.weight): # if it is known

      self.carrying -= package.weight

      self.capacity += package.weight

    if (self.packages.has_key(package.id)): # we have to do this -- we might have started half way

      del self.packages[package.id]

      self.package_cnt -= 1

      if (self.deliverme == package):

        self.deliverme = None

    if (self.package_cnt):

      if (self == _world_global_.bot):

        f = FindClose(self.curr_loc, self.packages.values(), _world_global_.board.C_board)

        f.try_harder()

        if (f.found_good):

          self.deliverme = f.found_good[0][0]

        else:

          self.deliverme = f.found[0]

      else:

        self.deliverme = self.packages.values()[0]



    if (package.x_des == self.x_pos and package.y_des == self.y_pos):

      self.score += package.weight

      

    return



  def make_move(self, bid, cmd):

    self.money -= bid

    if (self.money <= 0):

      print "Outta cash, gonna die"

    return "%d %s\n" % (bid, cmd)



class Package:

  """The basic class to store package state"""

  def __init__(self, id):

    self.id = id

    self.x_des = None

    self.y_des = None

    self.weight = 0

    self.curr_loc = None

    self.imp_loc = None

    self.path_len = 100000 # replace when we know it

    self.jump_path = None # So far, just used by Home

    self.jump_to = None

    return



  def set_destination(self, x, y):

    self.x_des = x

    self.y_des = y

    self.imp_loc = (x,y)

    return



  def set_weight(self, weight):

    self.weight = weight

    return



  def myprint(self):

    print 'id %d, weight %d, x_des %d, y_des %d' % (self.id, self.weight, self.x_des, self.y_des)



class Board:

  """The board for the competition, handles state"""



  def __init__(self, width, height):

    """Intializes an empty board of width/height"""

    self.width = width

    self.height = height

    self.bases = {}

    self.d_bases = []

    self.maybe_bases = {}

    self.d_maybe_bases = []

    self.doubtful_bases = {}

    self.d_doubtful_bases = []

    self.full_init()



  def full_init(self):

    width = self.width

    height = self.height

    self.C_board = ICFP.Board(width, height)

    self.reset_extra()

    

  def reset_extra(self):

    self.xtra = {} # {X}{Y} = list of packages there

    # populating for X is a max hit of 1000, that isn't too bad

    for (i) in range(1,self.width+1):

      self.xtra[i] = {}

    self.xtra_locs = {} # {ob.id} = tuple # where a package is

    

    return



  def set_row(self, row_n, str):

    """parse and store a row string"""

    newrow = [(str[i:i+1]) for (i) in range(len(str))]

    if (len(newrow) != self.width):

      raise 'Parse error, width doesnt match expected'



    crow = []



    for (i) in range(len(newrow)):

      if (newrow[i] == '.'):

        crow.append(1)

      elif (newrow[i] == '#'):

        crow.append(2)

      elif (newrow[i] == '@'):

        self.add_base((i+1, row_n))

        crow.append(3)

      elif (newrow[i] == '~'):

        crow.append(4)

      else:

        raise 'WTF?'



    self.C_board.set_row(row_n, crow)

    return

  

  def upgrade_bases(self):

    """if no bases, upgrade mabye's to real bases

    if no maybes, doubtfuls"""



    if (len(self.d_bases)):

      return



    if (len(self.d_maybe_bases)):

      # upgrade maybes to full bases

      self.bases = self.maybe_bases

      self.d_bases = self.d_maybe_bases

      self.maybe_bases = {}

      self.d_maybe_bases = []

      return

    elif (len(self.d_doubtful_bases)):

      # game is probably over, but upgrade doubtful to bases

      self.bases = self.doubtful_bases

      self.d_bases = self.d_doubtful_bases

      self.doubtful_bases = {}

      self.d_doubtful_bases = []



    return



  def add_base_c(self, coords, mylist, mydict):

    b = Home(coords)

    mydict[b.curr_loc] = b

    mylist.append(b)

    return



  def rm_base_c(self, coords, mylist, mydict):

    b = mydict[coords]

    del mydict[coords]

    i = mylist.index(b)

    mylist.pop(i)

    return

    

  def add_base(self, coords):

    self.add_base_c(coords, self.d_bases, self.bases)

    self.upgrade_bases()

    return



  def rm_base(self, coords):

    self.rm_base_c(coords, self.d_bases, self.bases)

    if (not len(self.d_bases)):

      self.upgrade_bases()

  

  def add_maybe_base(self, coords):

    self.add_base_c(coords, self.d_maybe_bases, self.maybe_bases)

    return



  def rm_maybe_base(self, coords):

    self.rm_base_c(coords, self.d_maybe_bases, self.maybe_bases)

    return



  def add_doubtful_base(self, coords):

    self.add_base_c(coords, self.d_doubtful_bases, self.doubtful_bases)

    return



  def rm_doubtful_base(self, coords):

    self.rm_base_c(coords, self.d_doubtful_bases, self.doubtful_bases)

    return



  def from_file(self, filename):

    fob = file(filename)

    lines = []

    for (line) in xreadlines.xreadlines(fob):

      lines.insert(0,line.strip())

    fob.close()



    self.width = len(lines[0])

    self.height = len(lines)

    self.full_init()

    for (i) in range(1,self.height+1):

      self.set_row(i, lines[i-1])



    self.C_board.finalize()

    return



  def extra(self, pob, x, y):

    """Add an object to a location"""

    if (self.xtra_locs.has_key(pob.id)):

      (locx, locy) = self.xtra_locs[pob.id]

      # redo, just to make sure

      self.rm_extra(pob)

      self.extra(pob, x,y)

      return

    else:

      self.xtra_locs[pob.id] = [x,y]

      if (not self.xtra[x].has_key(y)):

        self.xtra[x][y] = []

      self.xtra[x][y].append(pob)

    return

  

  def extra_here(self, x, y):

    """return the list of stuff here"""

    if (not self.xtra[x].has_key(y)):

      return []

    else:

      return self.xtra[x][y]



  def rm_extra(self, pob):

    """Remove an object from a location"""

    if (not self.xtra_locs.has_key(pob.id)): # we didn't know about it anyway

      return 0

    (x, y) = self.xtra_locs[pob.id]

    if (pob not in self.xtra[x][y]): # seriously screwy 

      del self.xtra_locs[pob.id]

      return len(self.xtra[x][y])

    

    i = self.xtra[x][y].index(pob)

    self.xtra[x][y].pop(i) # get rid of it

    return len(self.xtra[x][y])



  def len_extra(self, x, y):

    return len(self.extra_here(x,y))



move_re = re.compile('(\w)\s*(.*)')

arg_re = re.compile('(\w)\s+(\d+)\s*(.*)')

id_re = re.compile('(\d+)\s*(.*)')

package_re = re.compile('(-?\d+)\s+(\d+)\s+(\d+)\s+(\d+)\s*(.*)')



class World:

  """the One True Singleton"""

  __single = None # our singleton reference

  # the meat of World is in __real_World



  def __init__(self, descriptor = None):

    """New a dummy object that proxys for __real_World,

       this is the instance that all other modules use to interface with World"""

        # Check whether we already have an instance

    if World.__single is None:

      # Create and remember instance

      World.__single = World.__real_World(descriptor)



    # Store instance reference as the only member in the handle

    self.__dict__['_World__single'] = World.__single



    # These are just to fool pychecker, which doesn't know

    # about the singleton trick in Python

    #    self.io = None

    #    self.bot = None # us

    #    self.board = None # state

    #    self.bots = {} # id => bot objects

    #    self.packages = {} # id => package objecs

    #    self.delivered = [] # DEBUG

    #    self.board = None

    #    self.bot = None

    

    #  def read_server_response(self) : pass

    #  def read_packages(self) : pass



  def __getattr__(self, attr):

    """Proxy to singleton"""

    return getattr(self.__single, attr)



  def __setattr__(self, attr, value):

    """Proxy to singleton"""

    setattr(self.__single, attr, value)

    return



  class __real_World:

    """The real World object

       All methods that are called on an instance of World.World() are actually

       implemented here."""



    def __init__(self, descriptor = None):

      self.io = IO.icfpIO(descriptor)

      self.bot = None # us

      self.board = None # state

      self.bots = {} # id => bot objects

      self.py_bots = {} # id(ob) => 1

      self.packages = {} # id => package objecs

      self.dropped_by_others = 0

      self.routes = {} # [((tup), (tup))] = path

      self.io.write("Player\n")

      line = self.io.readline()

      m = re.match("(\d+)\s+(\d+)", line)

      if (not m):

        raise 'Bad board dimensions!'



      global Jiff

      Jiff = proc.Jiffies()

      self.jiff = Jiff



      self.board = Board(int(m.group(1)), int(m.group(2)))

      for (i) in range(1,1+int(m.group(2))):

        line = self.io.readline()

        self.board.set_row(i, line)



      self.board.C_board.finalize()

      # self.board.C_board.print_board()

      line = self.io.readline()

      m = re.match("(\d+)\s+(\d+)\s+(\d+)", line)

      if (not m):

        raise 'Bad bot definition'



      self.bot = Bot(int(m.group(1)), int(m.group(2)), int(m.group(3)))

      self.bots[self.bot.id] = self.bot # insert ourselves

      self.py_bots[id(self.bot)] = 1



      self.read_server_response() # read and apply

      self.read_packages() # read and apply



      # get nervous if you see this used

      # (We did make it a singleton after all ...)

      global _world_global_

      _world_global_ = self

      return



    def finalize(self):

      self.C_board.finalize()



    def read_packages(self):

      """Read packages at the current location, if any"""

      global Jiff

      if (Jiff._turns > 20000):

        self.reset_extra()

        

      line = self.io.readline()

      if (line == None):

        return None

      m = package_re.match(line)

      if (m):

        if (not self.board.bases.has_key(self.bot.curr_loc)):

          # just a package on the ground, but call it a base

          self.board.add_base(self.bot.curr_loc)

        while (m):

          pkg_id = int(m.group(1))

          x_pos = int(m.group(2))

          y_pos = int(m.group(3))

          weight = int(m.group(4))

          line = m.group(5)



          pob = None

          if (self.packages.has_key(pkg_id)):

            pob = self.packages[pkg_id]

          else:

            pob = Package(pkg_id)

            self.packages[pkg_id] = pob

          # end else

          pob.set_weight(weight)

          pob.set_destination(x_pos, y_pos)

          pob.curr_loc = self.bot.curr_loc

          self.board.extra(pob, self.bot.x_pos, self.bot.y_pos)

          m = package_re.match(line)

        # end while (m)

      # end if(m)

      else: # no pacakges

        if (self.board.bases.has_key(self.bot.curr_loc)):

          self.board.rm_base(self.bot.curr_loc)

        if (self.board.maybe_bases.has_key(self.bot.curr_loc)):

          self.board.rm_maybe_base(self.bot.curr_loc)

        if (self.board.doubtful_bases.has_key(self.bot.curr_loc)):

          self.board.rm_doubtful_base(self.bot.curr_loc)

      return 1

    

    def apply_commands(self, cmds):

      """update state from the server commands"""

      seen_bots = {self.bot.id: 1}

      for (cmd) in cmds:

        if (not self.bots.has_key(cmd[0])):

          newbot = Bot(cmd[0], self.bot.carrymax, self.bot.startmoney) # assume he gets our stats

          self.bots[cmd[0]] = newbot

          self.py_bots[id(newbot)] = 1

        b = self.bots[cmd[0]]

        seen_bots[b.id] = 1 # to see who isn't dead

        # endif (initial)

        if (cmd[1] in ['N','S','E','W']):

          b.move(cmd[1])

        elif (cmd[1] == 'X'):

          b.set_x(int(cmd[2]))

          # if this was the second, place him

          if (b.x_pos and b.y_pos):

            b.curr_loc = (b.x_pos, b.y_pos)

        elif (cmd[1] == 'Y'):

          b.set_y(int(cmd[2]))

          # if this was the second, place him

          if (b.x_pos and b.y_pos):

            b.curr_loc = (b.x_pos, b.y_pos)

        elif (cmd[1] == 'P'):

          for (p_id) in cmd[2:]:

            p_id = int(p_id)

            package = None

            if (self.packages.has_key(p_id)):

              package = self.packages[p_id]

            else: # create a new package

              package = Package(p_id)

              self.packages[p_id] = package

          b.pickup(package)

          loc = (self.bot.x_pos, self.bot.y_pos)

          if (not self.board.rm_extra(package)):

            # no packages left at location

            if (self.board.bases.has_key(loc)):

              self.board.rm_base(loc)

            if (self.board.maybe_bases.has_key(loc)):

              self.board.rm_maybe_base(loc)

            if (self.board.doubtful_bases.has_key(loc)):

              self.board.rm_doubtful_base(loc)

        elif (cmd[1] == 'D'):

          if (b.id != self.bot.id):

            self.dropped_by_others += len(cmd[2:])

          for (p_id) in cmd[2:]:

            p_id = int(p_id)

            if (not self.packages.has_key(p_id)):

              package = Package(p_id)

              self.packages[p_id] = package

            package = self.packages[p_id]

            b.drop(package)

            if (b.id == self.bot.id): # we dropped it, so we know stuff about it

              if (b.x_pos != package.x_des or b.y_pos != package.y_des):

                # We might have been pushed more than once,

                # but this should put us in the right area

                self.board.add_maybe_base(b.last_loc)

              else:

                del self.packages[p_id]

            elif (b.x_pos != self.bot.x_pos or b.y_pos != self.bot.y_pos):

              # someone else probably making a delivery, add it to doubtful

              # we don't do this if it is on our current square (we'll pick it up in the package list)

              del self.packages[p_id]

              self.board.add_doubtful_base(b.curr_loc)

        elif (cmd[1] == 'NOP'):

          dummy = 1 # he was 'seen' above

        else:

          raise 'Unkown command from server'

      # for (cmd) in cmds



      # We would like to just compare the count, but

      # it could be one bot died and another joined

      for (bot_id) in self.bots.keys():

        if (not seen_bots.has_key(bot_id)):

          self.remove_bot(bot_id)



      return



    def remove_bot(self, bot_id):

      """Remove the bot from the bots list,

         from the board, and if he was carrying packages

         remove those too"""

      bob = self.bots[bot_id]

      del self.bots[bot_id]

      for (package_id) in bob.packages.keys():

        del self.packages[package_id]



      return

    

    def read_server_response(self):

      """Get a line of update info from the server"""



      line = self.io.readline()

      if (line == None):

        return None

      updates = line.split('#')

      updates.pop(0)

      all_cmds = []

      for (update) in updates:

        m = id_re.search(update)

        if (not m):

          raise 'Bad line from server'

        id = int(m.group(1))

        rest = m.group(2)

        cmds = filter(len, re.split('\s*(\w+)\s*',rest))

        if (not cmds):

          all_cmds.append([id, 'NOP'])

        while (cmds):

          cmd = cmds.pop(0)

          l = [id, cmd]

          if (cmds and re.match('\d+',cmds[0])):

            l.extend(string.split(cmds.pop(0)))

          all_cmds.append(l)

        # while (cmds)



      self.apply_commands(all_cmds)

      return 1



    def add_route(self, start, finish, steps):

      if (len(self.routes) > 2000):

        self.routes = {}

      self.routes[(start,finish)] = steps

      return



    def get_route(self, start, finish):

      if (self.routes.has_key((start,finish))):

        return self.routes.has_key((start,finish))

      elif (self.routes.has_key((finish,start))):

        return self.routes.has_key((finish,start))

      return None



    def clear_carrots(self):

      for (b) in self.board.d_bases:

        b.carrots = []

    

      

class PathFind:

  """Find your way from A to B

  caching, if any, is also done here"""

  def __init__(self):

    return

  



def sort_found(x,y):

  """used in FindClose object"""

  return - cmp(len(x[1]), len(y[1]))

    

class FindClose:

  """For a list of things, find the N best that are closest

  everything in list must have a data member imp_loc (Important Location, can be None)"""

  def __init__(self, from_here, list, CBoard):

    self.cboard = CBoard

    self.start = from_here

    self.found = list[:] # [:] is copy,  best bets [will be] in order

    self.found_good = [] # ones we know the way to

    self.ic = Jiff.avail / 4



    self.try_weakly()

    return

  

  def try_weakly(self):

    # first pass (should be quick) use heuristic1

    heur = ICFP.heuristic1

    self.found.sort(lambda x,y: cmp(heur(self.start,x.imp_loc), heur(self.start,x.imp_loc)))

    return

  

  def try_harder(self):

    # guess how many iterations we have to spend, on average, require at least 100 per

    IGUESS = 200

    self.items = self.found

    self.found = []

    global _world_global_



    boardsize = _world_global_.board.width * _world_global_.board.height;

    if (boardsize > 50000):

      self.mysort(self.items[0:min(2, len(self.items))])

    elif (len(self.items) * IGUESS > self.ic): # shorten the list to probables

      self.mysort(self.items[0:(len(self.items)/(self.ic/IGUESS))])

    else:

      self.mysort(self.items)



    if (len(self.found)):

      self.found.sort(sort_found)

    else:

      # NB, we didn't solve any of these --- might a random one be better?

      self.found = self.items # bumer, keep the first list (sorted in heuristic order)



    return self.ic



  def try_hardest(self):

    orig_ic = 200000 # enough to travel 1000+ spaces (but might be a memory concern?)

    self.ic = orig_ic

    if (len(self.items) > 2):

      self.mysort(self.items[0:2]) # just focus on a couple

    else:

      self.mysort(self.items)



  def mysort(self, items):

    """Sort to find a few locations locally"""

    ic = self.ic



    gens = []

    astar_obs = []

    for (item) in items:

      gens.append(AStar.AStar(self.start, item.imp_loc, self.cboard))



    while (ic > 0 and items):

      # give everyone a shot

      _StopIteration = StopIteration  # make local because caught a *lot*

      i = 0

      while (i < len(items)): # very un-python, but we screw with the list

        try:

          gens[i].gen.next()

        except _StopIteration:

          self.found_good.append([items[i], gens[i].solution])

          items.pop(i)

          g = gens.pop(i)

          g.done()

        ic -= 1

        i += 1

      # items list is smaller by the number that finished

      # self.found_good is larger  ""  "" ""     ""    ""



    while (len(gens)):

      g = gens.pop(0)

      g.done()



    Jiff.avail -= self.ic - ic

    self.ic = ic

    return



class FindPackage(FindClose):

  """package specific tweaks"""

  def try_weakly(self):

    global _world_global_

    global Jiff

    known = []

    unk = []

    for (p) in self.found:

      r = _world_global_.get_route(p.curr_loc, p.imp_loc)

      if (r):

        p.path_len = len(r)

        known.append(p, r)

      else:

        unk.append(p)



    self.found = unk

    self.found_good = known



  def try_harder(self):

    FindClose.try_harder(self)

    if (len(self.found_good) and Jiff.avail > 100000):

      # pick the best one and find all the ones closest to him

      best = self.found_good[0]

      newlist = []

      for (p) in self.found_good[1:]:

        newlist.append(p[0])



      self.found_good = []

      killer_list = [best]

      f = FindPackage(best[0].imp_loc, newlist, self.cboard)

      for (p) in f.found_good:

        killer_list.append(p)



      self.found_good = killer_list

    return