Key Information

Register
Submit
The challenge is finished.
Show Deadlines

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

Problem Statement

You work as a snake charmer and you want to impress the crowd with your skilful control of the snake. The snake comes out from the middle cell of a NxN grid. At each step, you can make its head move into any of the four adjacent (horizontally and vertically) cells. The snake cannot leave the grid or run into itself. The snake is divided into sections containing numbers, where each section is one grid cell in length. You get points based on the patterns that you make with the snake's sections. In particular, you get v^(m+1) points for each section, where v is the section's value and m is the number of adjacent (horizontally and vertically) cells with value v.

Here is an example solution for seed=1, N=7, V=3, Snake="3444433322344332432434424422324243233232232424424". This solution obtains a raw score of 3339. The black line shows the path that the snake travelled. The colour of a cell indicates the number of its matching neighbours. The head and the tail of the snake are shown inside a black square. Note that the entire snake does not need to come out.

Implementation

Your code will receive as input the following values, each on a separate line:
  • N, the grid size.
  • V, the number of different section values.
  • Snake, a string of characters indicating the value of each section. The first number corresponds to the head, while the last number corresponds to the tail.
Your code should write to output the following:
  • On the first line, the number of steps S taken by the snake.
  • S lines, where the n-th line describes the n-th step taken by the snake: 'L' (left), 'U' (up), 'R' (right) or 'D' (down).

Scoring

Your raw score for a test case is the sum of points obtained by each section of the snake. If your return was invalid then your raw score on this test case will be -1. Possible reasons include:
  • Using more than N*N-1 steps.
  • Snake leaving the grid or colliding with itself.
  • Using unrecognised directions.

 

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 YOUR/MAX, where YOUR is your raw score and MAX is the largest 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:
  • Generate the grid size N, randomly chosen odd number between 7 and 49, inclusive.
  • Generate the number of section values V, randomly chosen between 2 and 8, inclusive.
  • Generate the Snake string of N*N characters representing the value of each section. Each value is randomly chosen between 2 and V+1, inclusive.

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.
  • 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 SnakeCharmer.<appropriate extension>

- Java Source Code - SnakeCharmer.java
- C++ Source Code - SnakeCharmer.cpp
- Python3.6 Source Code - SnakeCharmer.py
- C# Source Code - SnakeCharmer.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.
Here are example solutions for different languages, modified to be executed with the visualizer. 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:
  • -novis. To turn off visualization.
  • -seed <seed>. Sets the seed used for test case generation, default is seed 1.
  • -size <SZ>. Sets the size of the grid cells in pixels. If omitted, the window will take up the whole screen.
  • -debug. Print debug information.
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.

Payments

Topcoder will compensate members in accordance with our standard payment policies, unless otherwise specified in this challenge. For information on payment policies, setting up your profile to receive payments, and general payment questions, please refer to ‌Payment Policies and Instructions.