JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 10
Problem: DiscretizedContinuousPacMan

Problem Statement

    

In this problem you'll play a continuous PacMan that fights against 4 evil ghosts. Ghosts outnumber you, but are silly, and each of them has a predefined strategy to follow in order to capture you (they do not do any team work as they should). There can also be a fruit that can be eaten by you or the ghosts. You, the ghosts and the fruit form the set of objects of the game. All objects except the fruit form the set of characters.

The board in which the game is played is a rectangle of 10000 by 10000 units and at each instant you and the ghosts are at some point with integer coordinates (X,Y) where 0 <= X,Y <= 10000. If two objects are within 75 from each other (meaning their distance is less than or equal to 75) we say they touch each other. At each instant, each object decides its move, and after that each move is performed in the following order (keep reading for a description of each item):

  1. You are moved
  2. Score and death calculations are made
  3. Ghosts and the fruit are moved
  4. Score and death calculations are made
  5. Dead characters are respawned
If an object dies or disappears during a phase, it is gone until phase 5, so it cannot move nor eat or kill anything.

In phase 1 your position becomes the new one.

In phase 3 all ghosts and the fruit positions become the new ones.

In phases 2 or 4, zero or more of these things can happen:

  • If you touch a ghost, you are said to be dead, and get -10 points.
  • If some ghost touches some other ghost, then it is said to be dead and you get +1 points for each dead ghost.
  • If any character touches a fruit it eats it and the fruit disappears. If you eat the fruit you get +10 point, if any number of ghosts eat the fruit you get -10 point. If you and any number of ghosts eat the fruit during the same phase, the fruit disappears and no points are added nor substracted to your score.
Dead characters and disappearing fruit are not removed until the end of the phase. For instance, you might eat the fruit, and also be killed by two ghosts who also kill eachother.



In phase 5 dead characters respawn randomly on the board, and no randomly placed object will have some other object at a distance of 150 or less. Also, if there is no fruit on the board (because it wasn't one at the beginning of the turn or because it was recently eaten) with a probability of 0.1, one fruit is placed randomly on the board (more than 150 away from any other object). Note that there will be no fruit before the initial movement of the characters.

You and each of the ghosts can move in steps of at most 100, which means the Euclidean distance between the current position and the position to where any character is moving must be less than or equal to 100. Moves outside the board are prohibited. The fruit can move to a distance of at most 50 units, but it moves randomly and always to a far location (the exact algorithm is given at the end of the problem statement).

The strategies for each ghost, numbered from 1 to 4, are (suppose your position is x,y and the ghost position is gx,gy, and let dx=abs(gx-x) and dy=abs(gy-y)):

  • Move to the position that minimizes dx, and in case of ties, the one that minimizes dy
  • Move to the position that minimizes dy, and in case of ties, the one that minimizes dx
  • Move to the position that minimizes dx2+dy2 (minimize Euclidean distance)
  • Move to the position that minimizes dx+dy (minimize manhattan distance)
For all ghosts, in case of further ties, it is decided randomly between the tied positions.

You only need to implement a method nextStep which takes as input two int[]s x and y representing the coordinates of each object in play and both contain exactly 6 elements. The 0th elements represent your coordinates, the 1st, 2nd, 3rd and 4th elements represent the 4 ghosts, in the order that was mentioned in the strategy description. If there is a fruit in play, its coordinates are described in both 5th elements, if there is not, both 5th elements are -1. This method has to return a int[] with exactly two elements, the x and y coordinate, in that order, to which you want to move next. If you return an invalid number of elements, or an invalid move (numbers outside valid range or a position too far away from your current location), it is assumed that you want to stay still (move to your current location) and then end the test case (see below).

Each test case will consist of up to 10000 calls to nextStep method, up to 30 seconds of execution in total, until a runtime error is produced or until you return an invalid move, whichever comes first. After each of the calls, every calculation is made. If your time is up, you give a runtime error, or return an invalid move, the last call will be assumed to return the same position you were in, the calculations will be made and then the test case will be over, even if the full 10000 steps haven't been executed. Your total score will be simply the sum of the score of each individual test case. If this total is negative, it will be increased to 0. There will be 20 system test cases.

The algorithm for the fruit movement is:

double theta = nextAngle();  //this selects a uniform value between 0 and 2*PI
newX := fix(oldX + trunc(cos(theta)*50)) 
newY := fix(oldY + trunc(sin(theta)*50))

fix(x) is max(0,min(x,10000))
trunc(x) is the integral part of x
For your convenience, a visualization tool is being made available, which may interact with your program via stardard in/out. You may download it here. You may also play manually here.
 

Definition

    
Class:DiscretizedContinuousPacMan
Method:nextStep
Parameters:int[], int[]
Returns:int[]
Method signature:int[] nextStep(int[] x, int[] y)
(be sure your method is public)
    
 

Notes

-When "randomly" is mentioned without further clarification anywhere in the statement, it means uniformly between every valid choice.
-The memory limit is 64M.
 

Examples

0)
    
 
You should use system out to print whatever information you want about the example test cases.
1)
    
 
2)
    
 
3)
    
 
4)
    
 

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.