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.

Overview

It is your task to collect as much wool as you can by shearing the sheep. The farmland is represented by a N*N grid. The initial grid consists of trees, sheep, barns, farmers and empty locations. You have a number of farmers available that can shear your sheep, each one of the farmers can carry at most C shears of wool at a time. The sheep wander around randomly and they are not afraid of the farmers or anything else. It takes one farmer 3 shears to shear off all the layers of wool from a sheep. The sheep won't move while being sheared and the sheep won't mind if you don't shear off all their wool. You get 1000 turns to shear the sheep and deposit the wool in any of the B barns. All your farmers can move around simultaneously in each turn. A farmer can move one cell up, down, left or right. When the farmer moves into a cell that is occupied by a sheep, one layer of wool will be sheared off and the sheep and farmer will remain at their original locations for that turn. Multiple farmers can shear the same sheep at the same time. The wool needs to be brought back to a barn. The farmer will deposit all the wool he carries when moving into a barn. A farmer can pass wool to another farmer when they stand next to each other and one tries to move in the direction of the other. The wool will be passed on such that the receiving farmer will carry up to a maximum of C wool. A sheared sheep slowly grows back its wool, each at its own rate.

Here is an example solution for seed=1:

seed 1 example

Input and Output

This is an interactive problem, so your code needs to interact with the tester for each turn. Initially your code will receive as input the following values, each on a separate line:

  • N, the size of the grid.
  • C, the carry capacity of a farmer.
  • N*N lines representing the starting grid in row-major order. Each cell is either empty ('.'), a tree ('#'), a barn ('X'), a sheep ('A'..'D') or a farmer ('a'..'v'). 'A' represents a sheep with no wool, 'B' a sheep with one layer of wool, 'C' a sheep with two layers of wool and 'D' for three layers. 'a' represents a farmer that is carrying no wool, 'b' a farmer with one wool, and so forth.

The following loop repeats until 1000 turns have been performed:

  • You move farmers by writing one line of triplets, each item separated by spaces. Each triplet should be in the following format "r c m" (without the quotes), where (r,c) is the row and column of the farmer and he should be moved into the m direction. The characters allowed for m are: U (Up), D (Down), L (Left), R (Right) and N (No move). You don't have to move all the farmers in every turn. All coordinates are 0-based where coordinate (0,0) is at the top left side of the grid.
  • Sheep not sheared in the previous step grow wool according to their growth probability.
  • Sheep not sheared in the previous step move to a random orthogonal neighboring cell if it is empty.
  • The tester sends you the following, each on a separate line: the total elapsed time and the updated grid on N*N lines.

Scoring

The raw score is the amount of wool you have delivered to the barns when the simulation ends. If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

  • Moving a farmer outside the grid or into a tree.
  • Trying to move a cell that is not a farmer.
  • Trying to move the same farmer twice in the same turn.
  • Wrongly formatted moves.
  • Exceeding the time-limit.

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 normalized to 100.

Test Case Generation

Please look at the generate() method in the visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

  • The grid size N is chosen between 10 and 30, inclusive.
  • The farmer carry capacity C is chosen between 3 and 21, inclusive.
  • The number of barns B is chosen between 1 and 8, inclusive.
  • The sheep probability sheepP is chosen between 0.01 and 0.1, inclusive.
  • The farmer to sheep ratio farmerR is chosen between 0.1 and 0.3, inclusive.
  • The tree probability treeP is chosen between 0.05 and 0.2, inclusive.
  • For each sheep the wool growing probability growthP is chosen between 0.02 and 0.15, inclusive.
  • Each cell of the grid is filled, such that a tree is chosen with probability treeP and a sheep with probability sheepP; otherwise the cell is set to empty.
  • The barns are placed randomly on empty cells.
  • The number of farmers is determined by multiplying the number of sheep with farmerR.
  • The farmers are placed randomly on empty cells.
  • The grid generating process is repeated until all the farmers, sheep and barns form part of one connected component.
  • All 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.
  • 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 ShearTheSheep.<appropriate extension>

Sample Submissions

Here are example solutions for different languages, modified to be executed with the visualizer. Note that this solution does not produce a valid final answer. You may modify and submit these example solutions:

Tools

An offline tester is 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

Offline Tester / Visualizer

In order to use the offline tester/visualizer tool for testing your solution locally, you'll have to include in your solution the main method that interacts with the tester/visualizer via reading data from standard input and writing data to standard output.

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\ShearTheSheep.exe" or "~/topcoder/ShearTheSheep". In case your compiled solution is to be run with the help of an interpreter, for example, if your program is in Java, the command will be something like "java -cp C:\TopCoder ShearTheSheep".

Additionally you can use the following options:

  • -seed <seed> Sets the seed used for test case generation, default is seed 1.
  • -debug. Print debug information.
  • -novis. Turns off visualisation.
  • -pause. Starts the visualizer in paused mode. See more information below.
  • -noImages. Do not display images.
  • -delay <delay> Sets the delay (in milliseconds) between visualizing consecutive simulation steps, default is 100.
  • -N <N> Sets a custom size of the grid.
  • -C <C> Sets a custom carry capacity.
  • -B <B> Sets a custom number of barns.
  • -sheepP <sheepP> Sets a custom sheep spawn probability.
  • -farmerR <farmerR> Sets a custom farmer sheep ratio.
  • -treeP <treeP> Sets a custom tree probability.

The visualizer works in two modes. In regular mode, steps are visualized one after another with a delay specified with the -delay parameter. In paused mode, the next move will be visualized only when you press any key. The space key can be used to switch between regular and paused modes. The default starting mode is regular. You can use the -pause parameter to start in paused mode.

Marathon local testers have many useful options, including running a range of seeds with a single command, running more than one seed at time (multiple threads), controlling time limit, saving input/output/error and loading solution from a file. The usage of these options are described here.