Statistics

Problem Statement for "HigherMaze"

Problem Statement

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.

Definition

Class:
HigherMaze
Method:
navigate
Parameters:
int, int, int[], int[], int[], String[]
Returns:
int
Method signature:
int navigate(int a, int p, int[] dim, int[] start, int[] finish, String[] wormholes)
(be sure your method is public)

Constraints

  • The product of all the elements of dim will be between 2 and 1000, inclusive.
  • Each element of dim will be between 2 and 20, inclusive.
  • dim will contain between 1 and 5 elements, inclusive.
  • a and p will be between 1 and 2,000,000,000, inclusive.
  • a times p will be between 1 and 2,000,000,000, inclusive.
  • start and finish will be within the hyper-box defined by dim.
  • start and finish will be both be empty space (not an asteroid, possibly a wormhole).
  • wormholes will contain between 0 and 50 elements, inclusive.
  • Each element of wormholes will be formatted as "
  • and will both be space delimited (no extra, leading or trailing spaces) lists of integers, representing a coordinate in space within the hyper-box defined by dim.
  • and will both be empty space (not an asteroid).
  • There will be no way to go back in time infinitely. (In other words, there will be no reachable cycles that take negative amounts of time. However, there may be unreachable ones, but they can not affect the return, since they are unreachable.)

Examples

  1. 138

    193

    {5,5}

    {0,0}

    {4,4}

    {}

    Returns: 6

    This input generates the following two dimensional asteroid field, where an 'X' is an asteroid, and a '.' is open space. (Here, (0,0) is the upper left corner, and (4,4) is the lower right, and (4,0) is in the lower left): ...XX XX.X. ..XXX ....X .XXX. Here is one path that takes 6 time units, where 'S' represents the start, 'F' the finish, and '*' the path. S*.XX XX*X. .*XXX ..**X .XXXF

  2. 138

    193

    {5,5}

    {0,0}

    {4,4}

    {"0 0 2 4 4"}

    Returns: 2

    While there is still a path from (0,0) to (4,4) which takes 6 time units, there is also a wormhole, which transports you directly from (0,0) to (4,4), and ahead 2 units of time.

  3. 138

    193

    {5,5}

    {0,0}

    {4,4}

    {"0 0 2 4 4","0 0 8 1 4","0 2 5 1 4","1 4 -8 4 4"}

    Returns: -1

    This is the same asteroid configuration as the previous two examples, but now there are more wormholes. The quickest way to get from (0,0) to (4,4) is to move from from (0,0) to (0,2), which takes 2 units of time. From (0,2) we should go through the wormhole to (1,4), which transports us ahead 5 units of time, for a total of 7. Then, we can take the wormhole from (1,4) to (4,4), which takes us back 8 units of time. Thus, the total time for the trip is 2 + 5 - 8 = -1, and we arrive before we left!(note that two wormholes can start at the same location, and could even start and end at the same location)

  4. 54

    73

    {20,20}

    {1,2}

    {12,12}

    {}

    Returns: 23

  5. 139

    193

    {20,20}

    {0,2}

    {18,19}

    {"0 2 -100000 0 19","4 18 -100000 7 0","8 0 1000000 19 10","19 6 -800000 13 8"}

    Returns: 21

    The only way to get all the way is to go through all 4 wormholes, in order.

  6. 138

    193

    {5,5}

    {0,0}

    {4,0}

    {"0 0 -6 4 4"}

    Returns: -2

  7. 139

    193

    {20}

    {2}

    {19}

    {}

    Returns: 2147483647

  8. 19

    37

    {20,20}

    {0,1}

    {19,18}

    {"0 1 10 19 18","0 1 -10 19 18"}

    Returns: -10

  9. 19

    37

    {20,20}

    {0,1}

    {19,18}

    {"0 1 -10 19 18","0 1 10 19 18"}

    Returns: -10

  10. 139

    193

    {10,10,10}

    {0,0,2}

    {3,0,7}

    {}

    Returns: 7

  11. 16249

    78901

    {5,3,4,4,4}

    {1,0,1,0,0}

    {4,2,3,3,2}

    {}

    Returns: 3

  12. 3

    3

    {20,20}

    {0,0}

    {0,0}

    {}

    Returns: 0

  13. 3

    3

    {10,10,10}

    {9,9,9}

    {0,0,0}

    {}

    Returns: 9

  14. 3

    3

    {10,10,10}

    {9,9,9}

    {0,0,0}

    {}

    Returns: 9

  15. 3

    7

    {20,20}

    {19,17}

    {0,3}

    { "18 19 -1000000 19 11", "15 19 -1000000 19 5", "12 19 -1000000 19 0", "9 19 -1000000 16 0", "6 19 -1000000 13 0", "3 19 -1000000 10 0", "0 19 -1000000 7 0", "0 15 -1000000 4 0", "0 9 -1000000 1 0" }

    Returns: -8999873

  16. 3

    5

    {20,19}

    {19,1}

    {0,18}

    { "18 0 1000000 19 5", "14 0 1000000 19 9", "10 0 1000000 19 13", "6 0 1000000 19 17", "2 0 1000000 17 18", "0 1 1000000 13 18", "0 5 1000000 9 18", "0 9 1000000 5 18", "0 13 1000000 1 18" }

    Returns: 9000090

  17. 30386

    23560

    {6}

    {4}

    {5}

    {}

    Returns: 1

  18. 21360

    17206

    {9,6,4,2}

    {1,0,1,0}

    {5,2,1,1}

    {}

    Returns: 4

  19. 35365

    36821

    {9,6,7}

    {0,0,2}

    {7,3,5}

    {}

    Returns: 7

  20. 18686

    25641

    {7,9,9}

    {0,2,8}

    {4,1,1}

    {}

    Returns: 7

  21. 10080

    39190

    {9,5}

    {0,1}

    {6,4}

    {}

    Returns: 6

  22. 36720

    26435

    {2,7,9}

    {0,2,3}

    {1,3,2}

    {}

    Returns: 1

  23. 18176

    15495

    {2,3,6,3}

    {0,0,3,1}

    {0,0,0,2}

    {}

    Returns: 3

  24. 12014

    30847

    {10,10,2}

    {6,3,1}

    {9,4,0}

    {}

    Returns: 3

  25. 25598

    11004

    {7,10}

    {4,8}

    {1,2}

    {}

    Returns: 6

  26. 5434

    32492

    {7,4,6}

    {6,1,4}

    {1,3,3}

    {}

    Returns: 5

  27. 24668

    14682

    {7,4,5}

    {6,3,4}

    {6,3,1}

    {}

    Returns: 3

  28. 4118

    4831

    {3,5}

    {1,2}

    {0,3}

    {}

    Returns: 1

  29. 38086

    33378

    {3}

    {1}

    {1}

    {}

    Returns: 0

  30. 33530

    25978

    {7}

    {2}

    {4}

    {}

    Returns: 2

  31. 17596

    33708

    {3}

    {1}

    {2}

    {}

    Returns: 1

  32. 9664

    21308

    {7,8}

    {2,2}

    {5,1}

    {}

    Returns: 3

  33. 30098

    18890

    {10}

    {4}

    {8}

    {}

    Returns: 4

  34. 14616

    20404

    {2}

    {0}

    {1}

    {}

    Returns: 1

  35. 38718

    8880

    {2,4,2,5,10}

    {1,1,1,2,0}

    {0,1,0,3,7}

    {}

    Returns: 7

  36. 32178

    7772

    {6}

    {3}

    {5}

    {}

    Returns: 2

  37. 3448

    26490

    {3,2,3,10}

    {0,0,1,5}

    {1,1,1,7}

    {}

    Returns: 2

  38. 32599

    5843

    {3,9}

    {0,0}

    {0,2}

    {}

    Returns: 2

  39. 1572

    444

    {9,8}

    {5,4}

    {3,2}

    {}

    Returns: 2

  40. 34902

    20352

    {4,8}

    {1,1}

    {2,1}

    {}

    Returns: 1

  41. 13380

    212

    {10,5,5}

    {0,0,0}

    {7,0,1}

    {}

    Returns: 7

  42. 13714

    561

    {3,4,3,3,5}

    {2,3,2,2,0}

    {0,2,1,0,1}

    {}

    Returns: 2

  43. 21078

    33077

    {8}

    {6}

    {6}

    {}

    Returns: 0

  44. 35306

    17868

    {6,2,2,8}

    {4,0,1,5}

    {0,0,0,5}

    {}

    Returns: 4

  45. 34852

    30058

    {5,5,5}

    {3,2,3}

    {0,2,0}

    {}

    Returns: 3

  46. 9088

    746

    {10}

    {9}

    {0}

    {}

    Returns: 9

  47. 8606

    38046

    {9,10}

    {6,3}

    {8,0}

    {}

    Returns: 3

  48. 1947

    28159

    {6,3}

    {3,2}

    {1,1}

    {}

    Returns: 2

  49. 32916

    33502

    {2,4}

    {0,3}

    {0,0}

    {}

    Returns: 3

  50. 31354

    25432

    {6}

    {0}

    {3}

    {}

    Returns: 3

  51. 29472

    30981

    {7,9}

    {1,0}

    {6,4}

    {}

    Returns: 2147483647

  52. 20566

    9270

    {7,7}

    {6,5}

    {6,0}

    {}

    Returns: 5

  53. 13248

    19698

    {3,2}

    {2,0}

    {2,0}

    {}

    Returns: 0

  54. 24196

    2337

    {10,3,4,6}

    {5,0,0,4}

    {0,2,3,1}

    {}

    Returns: 5

  55. 5306

    21258

    {10,2,7,3}

    {9,0,1,2}

    {2,1,5,0}

    {}

    Returns: 7

  56. 29686

    38115

    {8,2,6,6}

    {3,1,1,0}

    {0,0,5,0}

    {}

    Returns: 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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: