#!/usr/bin/env ruby
# icfp2002 - flu@iki.fi
# crude and unfinished, but mostly working

require 'socket'

# ------------------------------------------
module Enumerable
  def inject(a)
    each do |i| a = yield(a, i) end
    a
  end
end

# ------------------------------------------
class Array
  def x() self[0] end
  def y() self[1] end
  def x=(value) self[0] = value end
  def y=(value) self[1] = value end
end

# ------------------------------------------
class Map
  attr_accessor :height
  attr_accessor :base_locations

  def initialize(server)
    @map = []
    @width, @height = server.getlist
    @height.times do @map << server.gets.strip end
    @base_locations = []
    @height.times do |y|
      @width.times do |x|
        case @map[y][x]
        when ?@ then @base_locations << [x, y]
        end
      end
    end
  end

  def is_valid(x, y)
    x.between?(0, @width-1) and
    y.between?(0, @height-1) and
    ".@".include?(@map[y][x])
  end

  def show
    map = []
    for row in @map
      map << row.clone
    end
    Robot.each do |id, r|
      x, y = r.location
      map[y][x] = id.to_s
    end
    for line in map.reverse
      puts line
    end
  end
end

# ------------------------------------------
class Package
  attr_accessor :location, :weight, :destination, :pid

  @@pidtable = {}
  @@locationtable = {}

  def self.get(pid)
    @@pidtable[pid] ||= self.new(pid)
  end

  def self.at(location)
    @@locationtable[location] or []
  end

  def location=(value)
    (@@locationtable[@location] || []).delete(self)
    @location = value
    (@@locationtable[@location] ||= []) << self
  end

  def initialize(pid)
    @pid = pid
  end

  def to_s
    @pid.to_s
  end
end

# ------------------------------------------
class Robot
  attr_accessor :capacity, :money, :location, :destination, :packages, :rid

  @@ridtable = {}
  @@locationtable = {}

  def self.get(rid)
    @@ridtable[rid] ||= self.new(rid)
  end

  def self.at(location)
    @@locationtable[location] or []
  end

  def self.each
    @@ridtable.each do |k, v| yield k, v end
  end

  def Robot.default(capacity, money)
    @@capacity, @@money = capacity, money
  end

  def initialize(rid)
    @rid = rid
    @capacity, @money = @@capacity, @@money
    @location = []
    @packages = []
  end

  def location=(value)
    (@@locationtable[@location] || []).delete(self)
    @location = value
    (@@locationtable[@location] ||= []) << self
  end

  def empty?
    @packages.empty?
  end

  def move(dx, dy)
    @location.x += dx
    @location.y += dy
  end

  def pick(pid)
    package = Package.get(pid)
    package.location = nil
    @packages << package
    @capacity -= package.weight
  end

  def drop(pid)
    package = Package.get(pid)
    package.location = @location if package.destination != @location
    @packages.delete(package)
    @capacity += package.weight
  end

  def to_s
    @rid.to_s
  end
end

# ------------------------------------------
class Server < TCPSocket
  def getlist
    gets.split.map do |s| s =~ /^\d/ and s.to_i or s end
  end
  
  def getresponselist
    gets.split(/#/)[1..-1].map do |response|
      response.split.map do |s| s =~ /^\d/ and s.to_i or s end
    end
  end
end

# ------------------------------------------
class Command
  attr_accessor :bet, :cmd, :arg

  def to_s
    "%s %s %s" % [@bet, @cmd, @arg]
  end
end

# ------------------------------------------
class Client
  def initialize(args)
    @server = Server.open(*args)
    @server.puts 'Player'
    @map = Map.new(@server)
    rid, capacity, money = @server.getlist
    Robot.default(capacity, money)
    @myrobot = Robot.get(rid)
    @state = :travel
    @specialbet = 3
    @command = Command.new
    @packages_to_pick = []
    @maxcapacity = capacity
    @picked = false
  end

  def find_unvisited(previous, old)
    unvisited = []
    for x, y in previous
      unvisited.push([x+1, y], [x, y+1], [x-1, y], [x, y-1])
    end
    unvisited -= old
    unvisited.reject do |x, y| not @map.is_valid(x, y) end
  end

  def dijkstra(source, target)
    m = Array.new(@map.height).map do [] end
    m[source.y][source.x] = distance = 0
    visited = previous = old = [source]
    while distance += 1
      for x, y in unvisited = find_unvisited(previous, old)
        m[y][x] = distance
      end
      return if unvisited.empty?
      break if unvisited.include?(target)
      old = previous
      previous = unvisited
      visited |= unvisited
    end
    dir = nil
    current = target.clone
    while current != source
      case distance -= 1 
      when m[current.y+1][current.x] then current.y += 1; dir = "S"
      when m[current.y][current.x+1] then current.x += 1; dir = "W"
      when m[current.y-1][current.x] then current.y -= 1; dir = "N"
      when m[current.y][current.x-1] then current.x -= 1; dir = "E"
      end
    end
    dir
  end

  def select_bet
    x, y = @myrobot.location
    Robot.at([x+1, y]).empty? and
    Robot.at([x-1, y]).empty? and
    Robot.at([x, y+1]).empty? and
    Robot.at([x, y-1]) ? 1 : @specialbet
  end

  def drop_packages
    if @myrobot.location == @myrobot.destination
      @command.cmd = "Drop"
      @command.arg = @myrobot.packages.reject do |p|
        p.destination != @myrobot.location
      end.join(" ")
      return true if @command.arg.length > 0
    end
    false
  end

  def select_packages_and_route
    if not @packages_to_pick.empty?
      @command.cmd = "Pick"
      @command.arg = @packages_to_pick.join(" ")
      @myrobot.destination = @packages_to_pick.first.destination
      @packages_to_pick = []
      @picked = true
      return true
    end
    if @picked
      @picked = false
      return false
    end
    if not (all = Package.at(@myrobot.location)).empty?
      all += @myrobot.packages
      x, y = @myrobot.location
      mx = all.inject(x) do |a, i| a+i.destination.x end / (all.length+1)
      my = all.inject(y) do |a, i| a+i.destination.y end / (all.length+1)
      all.sort! do |a, b|
        ((mx-a.destination.x).abs + (my-a.destination.y).abs) <=>
        ((mx-b.destination.x).abs + (my-b.destination.y).abs)
      end
      total = all.inject(0) do |a, i| a+i.weight end
      while total > @maxcapacity
        p = all.pop
        total -= p.weight
      end
      @packages_to_pick = all - @myrobot.packages
      return false if @packages_to_pick.empty?
      if not (packages_to_drop = @myrobot.packages - all).empty?
        @command.cmd = "Drop"
        @command.arg = packages_to_drop.join(" ")
        return true
      else
        @command.cmd = "Pick"
        @command.arg = @packages_to_pick.join(" ")
        @packages_to_pick = []
        @myrobot.destination = all[rand(all.length)].destination
        @picked = true
        return true
      end
    end
    false
  end

  def select_next_base
    if @myrobot.empty?
      # - find best base/destination with distance != 0
      l = @map.base_locations
      @myrobot.destination = l[rand(l.length)]
    end
  end

  def make_decision
    @command.bet = select_bet
    return if drop_packages
    return if select_packages_and_route
    select_next_base
    @command.cmd = "Move"
    @command.arg = dijkstra(@myrobot.location, @myrobot.destination)
    if @command.arg == nil
      #puts "No route to destination!"
      # - remove package with this destination
      @command.cmd = "Drop"
    end
  end

  def process_response
    for response in @server.getresponselist
      #puts "processing %s" % response.join(" ")
      robot = Robot.get(response.shift)
      while op = response.shift
        case op
        when "N" then robot.move(0,1)
        when "S" then robot.move(0,-1)
        when "E" then robot.move(1,0)
        when "W" then robot.move(-1,0)
        when "P" then robot.pick(response.shift)
        when "D" then robot.drop(response.shift)
        when "X" then robot.location.x = response.shift-1
        when "Y" then robot.location.y = response.shift-1
        end
      end
    end
  end

  def process_packages
    line = @server.getlist
    while line.length > 0
      pid, x, y, w, *line = line
      package = Package.get(pid)
      package.location = @myrobot.location
      package.destination = [x-1, y-1]
      package.weight = w
    end
  end

  def debug
    @map.show
    STDIN.gets
    STDOUT.puts @command
  end

  def run
    while true
      process_response
      process_packages
      make_decision
      #debug
      @server.puts @command
      @myrobot.money -= @command.bet.abs
    end
  end
end

# ------------------------------------------
Client.new(ARGV).run
