Key Information

Register
Submit
The challenge is finished.

Challenge Overview

Important Links

  • Submission-Review You can find your submissions artifacts here. Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores. 
  • Other Details For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution etc.  

Problem Statement

You are given a NxN grid containing pegs and target squares. Your task is to move every peg to a target square in the least number of moves. Pegs can use two types of moves: slide and jumps. A peg can slide into one of the neighbouring (4-connected) empty cells. Alternatively, it can make a series of consecutive jumps, each time jumping over another peg or a wall. Both move types are counted as a single move for scoring purposes.

 

Here is an animation showing a solution for seed=1. Targets are shown in green, walls are shown in grey, while pegs are shown as blue circles. This solution requires 9 moves to transfer all the pegs to target squares, hence it obtains a raw score of 9. Note that if one was to terminate the solution earlier then the score would be higher as there is a penalty for each uncovered target square (explained in the Scoring section).

 

 

Implementation

Your code will receive as input the following values:
  • N, the size of the grid.
  • NumPegs, the number of pegs and targets on the grid.
  • N*N single-character lines describing the input grid, where line r*N+c represents the cell in row r and column c. Empty cells are '.', walls are '#', pegs are 'P' and targets are 'X' (without the '').
Your code should write to output the following:
  • On the first line, the number of peg moves M you want to perform. M cannot be greater than NumPegs*N.
  • M lines, where each line desribes the move of a single peg.

     

    Slide moves must be formatted as "ROW COL S DIR" (without the ""). ROW and COL are the 0-based row and column locations of the peg you want to move. The top left corner of the board corresponds to row and column zero. DIR denotes the direction of the move:

     

    • U: Up, slides the peg to location (ROW-1, COL).
    • D: Down, slides the peg to location (ROW+1, COL).
    • L: Left, slides the peg to location (ROW, COL-1).
    • R: Right, slides the peg to location (ROW, COL+1).

     

    Jump moves must be formatted as "ROW COL J [DIR]" (without the ""). ROW and COL are the 0-based row and column locations of the peg you want to move. [DIR] is a list of one or more characters representing the direction of each jump in the sequence:

     

    • U: Up, jumps the peg to location (ROW-2, COL).
    • D: Down, jumps the peg to location (ROW+2, COL).
    • L: Left, jumps the peg to location (ROW, COL-2).
    • R: Right, jumps the peg to location (ROW, COL+2).

     

    For example, the first move in the animation is "1 4 S U", while the 7th move is "1 0 J DR".

Scoring

Your raw score for a test case is the total number of moves in your return plus a penalty of 2*N for each target that remains uncovered at the end of the simulation. If your return was invalid (more than NumPegs*N elements, illegal characters used, moves outside the grid, illegal moves, etc.) then your raw score on this test case will be -1.

 

If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is MIN/YOUR, where YOUR is your raw score and MIN is the smallest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalised to 100.

 

Test Case Generation

Please look at the visualizer source code for the exact details about test case generation. Each test case is generated as follows:
  • The grid size N is randomly chosen between 5 and 50, inclusive.
  • The number of pegs and targets NumPegs is randomly chosen between N and (N*N)/4, inclusive.
  • The wall probability wallP is randomly chosen beetween 0 and 0.5, inclusive.
  • Randomly place all pegs and targets in different cells.
  • For the remaining cells, randomly place walls with probability wallP.
  • All generated values are chosen uniformly at random.

Notes

  • The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
  • There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
  • The compilation time limit is 30 seconds.
  • There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
  • The match is rated.

Languages Supported

C#, Java, C++ and Python

Submission Format

Your submission must be a single ZIP file not larger than 500 MB, with your Source Code only:
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.

Make sure you name your Source Code file as JumpAround.<appropriate extension>

- Java Source Code - JumpAround.java
- C++ Source Code - JumpAround.cpp
- Python3.6 Source Code - JumpAround.py
- C# Source Code - JumpAround.cs

Sample Submissions

Tools

Submission format and an offline tester are available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.

DOWNLOADS

HELPFUL INFORMATION

OFFLINE TESTER / VISUALIZER

In order to use the offline tester/visualizer tool for testing your solution locally, you'll have to modify your solution by adding the main method that interacts with the tester/visualizer via reading data from standard input and writing data to standard output. As long as you do not change the implementation of method findSolution, this doesn't affect the way your solution works when submitted to our server.

Here are example solutions for different languages, modified to be executed with the visualizer. They all implement the same approach: slide pegs to adjacent target cells. To run the tester with your solution, you should run: 
java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation. If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\solution.exe" or "~/topcoder/solution". In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder Solution".

Additionally you can use the following options:
  • -seed <seed>. Sets the seed used for test case generation, default is seed 1.
  • -novis. Turn off visualization.
  • -debug. Print debug information.
  • -size <cell size>. Use custom grid size, default is 20 pixels.
  • -delay <delay>. Sets the delay (in milliseconds) between visualizing consecutive simulation steps, default is 100.
  • -pause. Starts visualizer in paused mode. See more information below.
The visualizer works in two modes. In regular mode, steps are visualized one after another with a delay specified with -delay parameter. In paused mode, the next turn will be visualized when you press any key (except space). The space key can be used to switch between regular and paused modes. The default starting mode is regular. You can use -pause parameter to start in paused mode.

 

Finally, you can print any debug information of your solution to standard error, and it will be forwarded to the standard out of the tester.

SHARE:

ID: 30103195