#!/usr/bin/perl -w

# Copyright (c) 2002 Joerg Rathlev
# 
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

use IO::Socket;
use strict;

my $debug =  0;  # debuglevel bitmask
                 #  1 = print board, id, capacity and money after connecting
                 #  2 = print messages received from server
                 #  4 = print messages sent to server
                 #  8 = print status every turn
                 # 16 = print what the robot will do next (doesn't work with moving_strategy_2)
                 # 32 = print the path the robot will take (doesn't work with moving_strategy_2)

my $server;      # the server connection socket

my $board;       # function returning the tile at (x, y)
my $cost;        # function returning the cost of moving to (x, y)
my $width;       # the board's width
my $height;      # the board's height
my @board_data;  # the board data

my $playercnt = 0;      # number of players

my $cost_default = 100; # default cost
my $cost_water = 20;    # extra cost per opponent for each adjacent water field
my $cost_narrow = 5;    # extra cost per opponent for narrow fields

my $id;          # this robot's id
my $money;       # this robot's money
my $max_weight;  # how much weight can we carry?
my @payload;     # what packets are we carrying?
my $weight = 0;  # how much weight this robot carries
my $dropped = 0; # true if we dropped packets in the last turn
my $picked = 0;  # true if we picked up packets in the last turn
my $moved = 0;   # true if we moved in the last turn

my %packets;     # packets available at the current position
my %positions;   # positions of the robots


# initializes the connection and gets the board and robot information
# from the server
sub init {
    $server = IO::Socket::INET->new(Proto => "tcp",
				    PeerAddr => $_[0],
				    PeerPort => $_[1])
	or die "Could not initialize connection:\n$!\n";

    # send initialization
    print $server "Player\n";

    # get board dimensions
    ($width, $height) = split(' ', <$server>);
    $width += 2; $height += 2;

    # get the board
    $board_data[0] = '#' x ($width);          # the first line is a wall,
    $board_data[$height-1] = $board_data[0];  # the last line is also a wall
    for (my $i = 1; $i < $height-1; $i++) {
	my $str = <$server>;
	chomp($str);
	$board_data[$i] = '#' . $str . '#';
    }

    $board = make_board_function();
    $cost = make_cost_function();

    # get our id, capacity and money
    ($id, $max_weight, $money) = split(' ', <$server>);

    if ($debug & 1) {
	for (my $y = 0; $y < $height; $y++) {
	    for (my $x = 0; $x < $width; $x++) {
		print $board->($x, $y);
	    }
	    print "\n";
	}
	print "Id: $id\nmax_weight: $max_weight\nmoney: $money\n";
    }
}


# creates the board function.  the board function, when called with
# arguments (x, y), will return the tile at board position (x, y)
sub make_board_function {
    return sub {
	return substr($board_data[$_[1]], $_[0], 1);
    }
}


# prints our current status.  for debugging
sub print_status {
    print "Status: (($positions{$id}[0], $positions{$id}[1]), $weight, $money)\n";
    foreach (@payload) {
	print "Packet: $_->{'id'} dest ($_->{'dest'}[0], $_->{'dest'}[1]) weight $_->{'weight'}\n";
    }
}


# removes a homebase from the board
sub remove_homebase {
    substr($board_data[$_[1]], $_[0], 1) = '.';
}


# returns coordniates north, south etc. of given position
sub north {
    return ($_[0], $_[1] + 1);
}
sub south {
    return ($_[0], $_[1] - 1);
}
sub east {
    return ($_[0] + 1, $_[1]);
}
sub west {
    return ($_[0] - 1, $_[1]);
}


# returns true if there is a wall/water/homebase
sub wall {
    return ($board->(@_) eq '#');
}
sub water {
    return ($board->(@_) eq '~');
}
sub homebase {
    return ($board->(@_) eq '@');
}


# returns true if the tile is occupied by a robot
sub occupied {
    foreach (values %positions) {
	if ($_->[0] == $_[0] && $_->[1] == $_[1]) {
	    return 1;
	}
    }
    return 0;
}


# returns true if the position is "narrow", i.e. there is a wall or
# water both north and south or both west and east of the given
# position
sub narrow {
    return (wall(north(@_)) && wall(south(@_)))
	|| (wall(west(@_)) && wall(east(@_)));
}


# returns the number of adjacent tiles of the type identified by the
# function passed as first argument, e.g. adjacent(wall, x, y)
sub count_adjacent {
    my $cnt = 0;
    my $f = shift;
    if ($f->(north(@_))) { $cnt++; }
    if ($f->(south(@_))) { $cnt++; }
    if ($f->(east(@_)))  { $cnt++; }
    if ($f->(west(@_)))  { $cnt++; }
    return $cnt;
}

# returns the adjacent positions that are of the type identified by
# the function passed as the first argument, e.g. adjacent(wall, x, y)
sub adjacent {
    my @p = ();
    my $f = shift;
    if ($f->(north(@_))) { push(@p, [north(@_)]); }
    if ($f->(south(@_))) { push(@p, [south(@_)]); }
    if ($f->(east(@_))) { push(@p, [east(@_)]); }
    if ($f->(west(@_))) { push(@p, [west(@_)]); }
    return @p;
}


# makes the cost function. the cost function is like the board
# function, but will return the cost of moving at a certain position.
# the cost function is used by the function that calculates the
# shortest path.
sub make_cost_function {
    my @costmap;
    for (my $y = 0; $y < $height; $y++) {
	for (my $x = 0; $x < $width; $x++) {
	    if (wall($x, $y) || water($x, $y)) {
		$costmap[$x][$y] = 0;
	    }
	    else {
		$costmap[$x][$y] = $cost_default
		    + ($cost_water * count_adjacent(\&water, $x, $y) * ($playercnt - 1))
		    + ((narrow($x, $y) ? $cost_narrow : 0) * ($playercnt -1));
	    }
	}
    }
    return sub {
	return $costmap[$_[0]][$_[1]];
    }
}


# because the robot cannot move diagonally, the minimum distance from
# (x1, y1) to (x2, y2) is |x1-x2| + |y1-y2|
sub min_distance {
    return abs($_[0] - $_[2]) + abs($_[1] - $_[3]);
}


# the minimum costs from (x1, y1) to (x2, y2) is the minimum distance
# multiplied with the minimum (i.e. default) costs
sub min_costs {
    return min_distance(@_) * $cost_default;
}


# (x1, y1, x2, y2) -> ((x2, y2), ...)
#
# get the shortest path from (x1, y1) to (x2, y2) using the A*
# algorithm
sub shortest_path {

    my $pos = sub {
	return $_[1] * $width + $_[0];
    };

    my $coord = sub {
	return ($_[0] % $width, ($_[0] - ($_[0] % $width)) / $width);
    };

    (my $x1, my $y1, my $x2, my $y2) = @_;

    my $dest = $pos->($x2, $y2);

    # the list of open positions.  the hash key is the position, the
    # value is an array containing: the previous position or undef,
    # the length of the path from the start to the position, and the
    # minimum length from the position to the destination.

    # the starting position is inserted into open
    my %open = ($pos->($x1, $y1) => [undef, 0, min_costs($x1, $y1, $x2, $y2)]);
    my %closed = ();

    while(1) {

	# there is no solution (this is bad, because it isn't handeled)
	if (!keys(%open)) {
	    return ();
	}

	# find the best position in open and move it into closed
	my $best_pos = (sort { $open{$a}->[2] <=> $open{$b}->[2] } keys %open)[0];
	$closed{$best_pos} = $open{$best_pos};
	delete($open{$best_pos});

	# have we reached the destination?
	if ($best_pos == $dest) {
	    my @path = (); #([$x2, $y2]);
	    for ( ; defined $closed{$best_pos}->[0];
		  $best_pos = $closed{$best_pos}->[0]) {
		push(@path, [$coord->($best_pos)]);
	    }
	    return @path;
	}

	# get the successors
	my @successors = adjacent(sub { return !(wall(@_) || water(@_)); },
				  $coord->($best_pos));

	foreach (@successors) {
	    my $g = $closed{$best_pos}->[1]
		    + $cost->($coord->($best_pos), @$_);
	    my $f = $g + min_costs(@$_, $x2, $y2);
	    if (exists($open{$pos->(@$_)})) {
		if ($f < $open{$pos->(@$_)}->[2]) {
		    $open{$pos->(@$_)} = [$best_pos, $g, $f];
		}
	    }
	    elsif (exists($closed{$pos->(@$_)})) {
		if ($f < $closed{$pos->(@$_)}->[2]) {
		    $open{$pos->(@$_)} = [$best_pos, $g, $f];
		    delete($closed{$pos->(@$_)});
		}
	    }
	    else {
		$open{$pos->(@$_)} = [$best_pos, $g, $f];
	    }
	}
    }
}


# finds the nearest homebase for a given position (x, y)
sub find_nearest_homebase {
    my @homebase = ();
    my $best = 0;
    for (my $x = 1; $x < $width-1; $x++) {
	for (my $y = 1; $y < $height-1; $y++) {
	    if (homebase($x, $y)
		    && !($x == $positions{$id}[0] && $y == $positions{$id}[1])) {
 		if (!@homebase || min_costs($_[0], $_[1], $x, $y) < $best) {
		    @homebase = ($x, $y);
		    $best = min_costs($_[0], $_[1], $x, $y);
		}
	    }
	}
    }
    return @homebase;
}


# reads from the server the moves that were made in the last turn
sub get_moves() {
    my $moves = <$server>;
    if ($debug & 2) { print "recv: $moves"; }
    if (!$moves) {
	# this might happen... when we die?
	print STDERR "Didn't receive reply from server.\n";
	exit();
    }
    chomp($moves);

    my %old_positions = %positions;
    %positions = ();
    $moved = $picked = $dropped = 0;

    while (length($moves) > 0) {
	$moves =~ /^#([^#]+).*/;
	if (!$1) {
	    # this might happen if we die
	    print STDERR "Syntax error in server reply.\n";
	    print "$moves\n";
	    print while(<$server>);
	    exit();
	}
	(my $robot, my @fields) = split(' ', $1);

	$positions{$robot} = $old_positions{$robot};
	for (my $i = 0; $i < @fields; $i++) {
	    if ($fields[$i] eq 'N') {
		$positions{$robot} = [north(@{$positions{$robot}})];
		if ($robot == $id) {
		    $moved = 1;
		}
	    }
	    elsif ($fields[$i] eq 'S') {
		$positions{$robot} = [south(@{$positions{$robot}})];
		if ($robot == $id) {
		    $moved = 1;
		}
	    }
	    elsif ($fields[$i] eq 'E') {
		$positions{$robot} = [east(@{$positions{$robot}})];
		if ($robot == $id) {
		    $moved = 1;
		}
	    }
	    elsif ($fields[$i] eq 'W') {
		$positions{$robot} = [west(@{$positions{$robot}})];
		if ($robot == $id) {
		    $moved = 1;
		}
	    }
	    elsif ($fields[$i] eq 'X') {
		my $x = $fields[++$i]; # the new X coordinate
		++$i;                  # skip the "Y" character
		my $y = $fields[++$i]; # the new Y coordinate
		$positions{$robot} = [$x, $y];
		if ($robot == $id) {
		    $moved = 1;
		}
	    }
	    elsif ($fields[$i] eq 'P') {
		# don't watch other robots
		if ($robot == $id) {
		    push(@payload, $packets{$fields[$i + 1]});
		    $weight += $packets{$fields[$i + 1]}{'weight'};
		    $picked = 1;
		}
		$i++;
	    }
	    elsif ($fields[$i] eq 'D') {
		# don't watch other robots
		if ($robot == $id) {
		    for (my $p = 0; $p < @payload; $p++) {
			if ($payload[$p]{'id'} == $fields[$i + 1]) {
			    $weight -= $payload[$p]{'weight'};
			    delete($payload[$p]);
			    my @new_payload;
			    foreach (@payload) {
				if (defined $_) {
				    push(@new_payload, $_);
				}
			    }
			    @payload = @new_payload;
			    last;
			}
		    }
		    $dropped = 1;
		}
		$i++;
	    }
	}
	$moves =~ s/^#[^#]+(.*)/$1/;
    }

    if ($playercnt != (keys %positions)) {
	$playercnt = keys %positions;
	if ($debug & 16) { print "Number of players is now $playercnt.\n"; }
    }

    if ($debug & 8) {
	print_status();
    }
}


# reads the list of available packets from the server
sub get_available_packets {
    my $packets = <$server>;
    if ($debug & 2) { print "recv: $packets"; }
    chomp($packets);

    %packets = ();
    if ($packets ne '') {
	my @fields = split(' ', $packets);
	for (my $i = 0; $i < @fields; $i += 4) {
	    $packets{$fields[$i]} = { 'id'     => $fields[$i],
				      'dest'   => [$fields[$i+1], $fields[$i+2]],
				      'weight' => $fields[$i+3] };
	}
    }
}


# returns a simple moving strategy function.  the simple strategy is
# that when the robot carries no packets, it will be moved to the
# nearest homebase, and when it does carry at least one packet, it
# will move to the nearest packet destination.  if there are any
# packets at the robots current position, it will pick up as many as
# possible (using a greedy, unoptimized algorithm), and if it is at a
# carried packet's destination, it will drop the packet.
sub simple_moving_strategy {

    my @destination = (0, 0); # the last move's destination
    my @path = ();            # the path we're planning to take

    return sub {

	# are there any packets at our current position?  if yes, pick
	# them up.
	if (%packets) {
	    my $remaining_capacity = $max_weight - $weight;
	    my @picklist;
	    foreach (values %packets) {
		if ($_->{'weight'} <= $remaining_capacity) {
		    push(@picklist, $_->{'id'});
		    $remaining_capacity -= $_->{'weight'};
		}
	    }

	    if (@picklist) {
		if ($debug & 16) { print "Now picking up packets.\n"; }
		pick(1, @picklist);
		return;
	    }
	}

	# do we carry any packets, and if yes, are we at one of the
	# packets' destinations?  then drop them.
	if (@payload) {
	    my @droplist;
	    foreach (@payload) {
		if ($_->{'dest'}[0] == $positions{$id}[0]
		        && $_->{'dest'}[1] == $positions{$id}[1]) {
		    push(@droplist, $_->{'id'});
		}
	    }

	    if (@droplist) {
		if ($debug & 16) { print "Now dropping packets.\n"; }
		drop(1, @droplist);
		return;
	    }
	}

	# have we been pushed to where we didn't want to go?  if yes,
	# our path is now invalid
	if ($destination[0] != $positions{$id}[0]
	        || $destination[1] != $positions{$id}[1]) {
	    if ($debug & 16) { print "We were pushed.\n"; }
	    @path = ();
	}

	# do we know where to go next?  if not, calculate a new path.
	if (!@path) {
	    # if we carry any packets, go to the next packet's
	    # destination
	    if (@payload) {
		@path = shortest_path(@{$positions{$id}}, @{$payload[0]{'dest'}});
		if ($debug & 16) {
		    print "Now going to packet $payload[0]{'id'}'s destination, ";
		    print "($payload[0]{'dest'}[0], $payload[0]{'dest'}[1]).\n";
		}
	    }
	    else {
		# if we already are at a homebase but there are no
		# packets, this position is not a homebase any longer
		if (homebase(@{$positions{$id}}) && !%packets) {
		    #remove_homebase(@{$positions{$id}});
		}

		# now go to the nearest homebase
		@path = shortest_path(@{$positions{$id}},
				      find_nearest_homebase(@{$positions{$id}}));
		if ($debug & 16) { print "Now going to the nearest homebase.\n"; }
	    }

	    if ($debug & 32) {
		print "Taking this path:\n";
		foreach (@path) {
		    print "($_->[0], $_->[1]) <- ";
		}
		print "\n";
	    }
	}

	# move the robot
	@destination = @{pop(@path)};
	move(1, @destination);
	return;
    }
}


# a better moving strategy than simple_moving_strategy
# 
# this strategy tries to make its decisions based on the following
# goals (in descending priority):
# 1. survive
# 2. deliver packets
# 3. pick up new packets
# 4. move
sub moving_strategy_2 {
    my $prev_playercnt = $playercnt;  # number of players in the last turn
    my @path = ();                    # the path we're planning to take

    my $action = 0;  # what do we want to do?
                     # 0 = don't know yet
                     # 1 = move
                     # 2 = pick
                     # 3 = drop

    my @dest = (0, 0);  # where do we want to move (this turn)?
    my @ldest = (0, 0); # where do we want to move (long-term)?
    my @drop = ();      # which packets do we want to drop?
    my @pick = ();      # which packets do we want to pick?

    # tells us if we are threated by an opponent who might push us
    # into the water at the given position, and where the opponent
    # would be coming from (1 = north, 2 = east, 3 = south, 4 = west).
    my $threat = sub {
	if (water(south(@_)) && occupied(north(@_))) { return 1; }
	if (water(west(@_))  && occupied(east(@_)))  { return 2; }
	if (water(north(@_)) && occupied(south(@_))) { return 3; }
	if (water(east(@_))  && occupied(west(@_)))  { return 4; }
	return 0;
    };

    # make a bid.
    #  2 = very high
    #  1 = slightly higher than usual
    #  0 = normal (positive)
    # -1 = normal (negative)
    # -2 = slightly lower
    # -3 = very low
    my $make_bid = sub {
	my $bid;
	if ($_[0] ==  2) { $bid =  25; }
	if ($_[0] ==  1) { $bid =   5; }
	if ($_[0] ==  0) { $bid =   1; }
	if ($_[0] == -1) { $bid =  -1; }
	if ($_[0] == -2) { $bid =  -5; }
	if ($_[0] == -3) { $bid = -25; }
	# never bid more than 10% of our remaining money
	if (abs($bid) > 0.1 * $money) {
	    $bid = ($bid < 0) ? int(0.1 * $money) : -int(0.1 * $money);
	    if ($bid == 0) { $bid = 1; }
	}
	return $bid;
    };

    # finds the nearest tile to which a packet has to be delivered
    my $find_nearest_packet_destination = sub {
	my @min_dest = undef;
	my $min = undef;
	foreach (@payload) {
	    if (!defined($min) || (min_costs(@{$positions{$id}}, @{$_->{'dest'}}) < $min)) {
		$min = min_costs(@{$positions{$id}}, @{$_->{'dest'}});
		@min_dest = @{$_->{'dest'}};
	    }
	}
	return @min_dest;
    };

    # picks as many packets as possible (this is *not* a good
    # algorithm because it is greedy)
    my $pick_packets = sub {
	# how useful is a packet?
	my $use = sub {
	    my %packet = @_;
	    return int(($packet{'weight'} * 1000)
		       / min_costs(@{$positions{$id}}, @{$packet{'dest'}}));
	};

	# create a list of all packets at current position
	my @available_packets;
	foreach (values %packets) {
	    push(@available_packets, $_);
	}

	# sort them by usefulness
	my @sorted_packets = sort { return $use->(%$a) <=> $use->(%$b) } @available_packets;

	# pick the most useful ones, until zero capacity is left
	my @result;
	my $capacity = $max_weight - $weight;
	while (my $packet = shift(@sorted_packets)) {
	    if ($capacity > $packet->{'weight'}) {
		push(@result, $packet);
		$capacity -= $packet->{'weight'};
	    }
	}

	# return the list of ids
	return map { $_->{'id'} } @result;
    };

    return sub {
	# if the number of players has changed, we recalculate the
	# costmap
	if ($prev_playercnt != $playercnt) {
	    $cost = make_cost_function();
	    @path = ();  # we must now recalculate our path as well
	}
	$prev_playercnt = $playercnt;

	# store our position in a local variable for more convienient
	# access
	my @pos = @{$positions{$id}};
	my $bid;

	# we don't yet know what to do
	$action = 0;
	@drop = ();
	@pick = ();

	# if we are now at a position other than where we expected to
	# be, or if we have both moved and dropped packets, we have
	# been pushed by an opponent
	if ($dest[0] != $pos[0] || $dest[1] != $pos[1] || ($moved && $dropped)) {
	    @path = ();
	}

	# if we're at the destination of any packets we're carrying,
	# drop them.
	if (@payload) {
	    @drop = map { $_->{'id'} } 
	            grep { ($_->{'dest'}[0] == $pos[0]) && ($_->{'dest'}[1] == $pos[1]) }
                    @payload;
	}
	if (%packets) {
	    @pick = $pick_packets->();
	}
	if (@drop) {
	    $action = 3;
	    # is there any opponent that might push us before we can
	    # drop the packets?
	    if (count_adjacent(\&occupied, @pos) > 0) {
		$bid = $make_bid->(1);
	    }
	    else {
		$bid = $make_bid->(0);
	    }
	    @path = ();
	}
	elsif (@pick) {
	    $action = 2;
	    $bid = $make_bid->(0);
	    @path = ();
	}
	else {
	    # we cannot drop or pick up packets here, so we have to
	    # move
	    if (!@path) {
		if (@payload) {
		    # move to the nearest packet destination
		    @ldest = $find_nearest_packet_destination->();
		}
		else {
		    # are we at a home base already?  then if there
		    # aren't any packets, it is not considered a
		    # homebase any longer
		    if (homebase(@pos) && !%packets) {
#			remove_homebase(@pos);
		    }

		    # move to the nearest homebase
		    @ldest = find_nearest_homebase(@pos);

		    # if there isn't any homebase any more, simply
		    # move in a random direction
		    if (!@ldest) {
			my @a = adjacent(sub { return !(wall(@_) || water(@_)); }, @pos);
			@ldest = @{$a[int(rand(@a))]};
		    }
		}
		# find the shortest path
		@path = shortest_path(@pos, @ldest);
	    }
	    $action = 1;
	    $bid = $make_bid->(0);
	    @dest = @{pop(@path)};
	}

	# if we want to move, and we would be threated by an opponent
	# at our destination, we make a low bid so that it is likely
	# that our opponent moves first.
	if ($action == 1 && $threat->(@dest)) {
	    $bid = $make_bid->(-3);
	}

	# if our robot is standing next to the water, and an opponent
	# is standing so that it could push us into the water, we must
	# escape.
	if (count_adjacent(\&water, @pos) > 0) {
	    if ($threat->(@pos) == 1 || $threat->(@pos) == 3) {
		# an opponent is threatening us from the north/south.
		# if we wanted to go west or east, check that our new
		# position would be safe, if it is not or if we wanted
		# to do something else, move towards the opponent.
		if ($action == 1 && get_direction(@pos, @dest) eq "E") {
		    # we wanted to move east, but if that isn't safe,
		    # move north instead.
		    if ($threat->(@dest)) {
			@dest = ($threat->(@pos) == 1) ? north(@pos) : south(@pos);
		    }
		}
		elsif ($action == 1 && get_direction(@pos, @dest) eq "W") {
		    if ($threat->(@dest)) {
			@dest = ($threat->(@pos) == 1) ? north(@pos) : south(@pos);
		    }
		}
		else {
		    $action = 1;
		    @dest = ($threat->(@pos) == 1) ? north(@pos) : south(@pos);
		}
		$bid = $make_bid->(2);
	    }
	    elsif ($threat->(@pos) == 2 || $threat->(@pos) == 4) {
		if ($action == 1 && get_direction(@pos, @dest) eq "N") {
		    if ($threat->(@dest)) {
			@dest = ($threat->(@pos) == 2) ? east(@pos) : west(@pos);
		    }
		}
		elsif ($action == 1 && get_direction(@pos, @dest) eq "S") {
		    if ($threat->(@dest)) {
			@dest = ($threat->(@pos) == 2) ? east(@pos) : west(@pos);
		    }
		}
		else {
		    $action = 1;
		    @dest = ($threat->(@pos) == 1) ? north(@pos) : south(@pos);
		}
		$bid = $make_bid->(2);
	    }
	}

	# execute!
	if    ($action == 1) { move($bid, @dest); }
	elsif ($action == 2) { pick($bid, @pick); }
	elsif ($action == 3) { drop($bid, @drop); }
	else                 { pick(1, 0); } # noop
    }
}


# get the direction from (x1, y1) to (x2, y2)
sub get_direction {
    (my $x1, my $y1, my $x2, my $y2) = @_;
    if ($x2 == $x1 + 1) { return "E"; }
    if ($x2 == $x1 - 1) { return "W"; }
    if ($y2 == $y1 + 1) { return "N"; }
    else { return "S"; }
}


# sends a move command to the server
sub move {
    my $bid = shift;
    $money -= abs($bid);
    my $direction = get_direction(@{$positions{$id}}, @_);
    my $msg = "$bid Move $direction\n";
    if ($debug & 4) { print "send: $msg"; }
    print $server $msg;
}


# sends a pick command to the server
sub pick {
    my $bid = shift;
    $money -= abs($bid);
    my $msg = "$bid Pick";
    $msg .= " $_" foreach (@_);
    $msg .= "\n";
    if ($debug & 4) { print "send: $msg"; }
    print $server $msg;
}


# sends a drop command to the server
sub drop {
    my $bid = shift;
    $money -= abs($bid);
    my $msg = "$bid Drop";
    $msg .= " $_" foreach (@_);
    $msg .= "\n";
    if ($debug & 4) { print "send: $msg"; }
    print $server $msg;
}


sub main {
    init(@ARGV);

    my $next_move = moving_strategy_2();

    while ($server->connected()) {
	get_moves();
	get_available_packets();
	$next_move->();
    }
}

main();
