We all know that there are not necessarily three dimensions, and that there are wormholes scattered throughout the universe which will transport you through time and space. However, because it is often difficult for people to conceptualize higher dimensions, we will probably have to have computers do most of our navigation for us. Your task is to write a program that will simulate a pseudo-random asteroid field, and then navigate a ship through the asteroid field as quickly as possible.
The first step will be to generate the asteroid field. You will be given a int[], dim, that will specify how large you should make each dimension in your asteroid field. For example, if dim is {3,4,5}, the generated asteroid field will be a 3 x 4 x 5 box, with corners at (0,0,0) and (2,3,4). If dim is {3,4,5,4}, the generated asteroid field will be a 3 x 4 x 5 x 4 hyper-box (a hyper box is analogous to a regular box, but in more than three dimensions). Then, you must determine which spaces in the asteroid field actually contain asteroids. This will be done pseudo-randomly using something like the following code, where a and p are inputs (remember that there are a variable number of dimensions):
int current = 1;
for(int i0 = 0; i0<dim0; i0++)
for(int i1 = 0; i1<dim1; i1++)
... one loop per dimension
{
current = (current*a)%p;
if((current&1)==1){
//add an asteroid at (i0,i1,i2,...)
}
}
Once the asteroid field is generated, you have to navigate through it. You will be given a int[], start, and a int[], finish. You must find your way through the asteroid field, as quickly as possible without running into an asteroid. You may move from any location (a0,a1,a2...) to any other location, (b0,b1,b2...) so long as for all i, the differences between ai and bi is either 1 or 0, and bi is between 0 and dimi-1, inclusive. Each such movement takes one unit of time. For example, if you were at the S below, you could move to any of the locations marked with T, where '.' represents open space.
.....
.TTT.
.TST.
.TTT.
.....
In addition to this type of movement, you may also (but are not required to) travel through wormholes. You will be given a String[], wormholes, which specifies the origin, length of time travel, and destination of some wormholes. To go through a wormhole, you must first reach the origin of the wormhole. Then, after going through the wormhole, you will be transported to the destination of the wormhole. Additionally, wormholes transport you in time. So, each wormhole has a fixed amount of time travel associated with it, and each time you go through the wormhole, you will go forward or backward in time by that amount. Each element of wormholes will be formatted as "<origin> <time> <destination>", where <origin> and <destination> and coordinates as a space delimited list. For example, "0 0 -1 3 7" would represent a wormhole that starts at (0,0), transports you back in time 1 unit, and leaves you at (3,7) in space. Thus, if you reached (0,0) 5 units of time after you started, it would be possible to reach (3,7) from there 4 units of time after you started.
Sometimes, it will be impossible to reach finish from start. In this case return, 2^31-1 = 2147483647.
|