2015 TopCoder Open Marathon - Final

Problem Statement

Mowing the lawn in your yard with a lawnmower is a tiring task. Your yard is not level and pushing the mower up a slope, or even turning, takes a lot of effort. You are given a square map of your yard containing N by N cells. It rained a lot on your yard while you have been away for the TCO and all the grass has grown tremendously. Luckily you have a few beddings filled with plants scattered on your yard, so you don't necessary have to mow every cell. You can't mow the beddings, because they don't contain grass, and you don't want to cross over them, as you don't want to destroy the other plants. Your yard is toroidal, it wraps around at the borders.

It costs you turnCost energy to turn the mower 90 degrees left or right. Pushing the mower forward costs you forwardCost energy, while pushing the mower up a slope will cost you another slopeCost energy for every unit of height. It costs you only 20 percent of the energy (for both forward motion and slope) when performing any moves over already cut grass. The mower will only cut the grass on the current cell when it moves forward towards another cell. For every grass cell that was not mowed your score for the test case will be penalized with a cost of slopeCost*100.

Your task is to minimize the energy used in order to cut as much grass as possible and return to the cell where you have started.

Implementation Details

Your code should implement the method getMoves(String[] yard, int turnCost, int forwardCost, int slopeCost, int startCol, int startRow). Your getMoves method will be called once and should return a String containing your moves.

• yard gives you the map containing N by N cells. Each String contains a row of the yard. Any numeric character ('0'..'9') denotes the zero based height of the cell and '.' denotes a bedding.
• turnCost is the cost for every turn you make over un-cut grass. The cost will be 0.2*turnCost over already cut grass.
• forwardCost is the cost for every forward move you make over un-cut grass. The cost will be 0.2*forwardCost over already cut grass.
• slopeCost is the cost for every unit of height that you move up. For example, if your mower is on grass with the yard height at '3' and you move forward to a cell with height '7', your cost will increase with 4*slopeCost. Going down a slope does not add extra costs. The cost will be 0.2*slopeCost over already cut grass, for every unit of height going up.
• startCol gives you the zero-based starting column of your mower.
• startRow gives you the zero-based starting row of your mower.
• Your mower will always start in the direction that faces towards (startRow+1, startCol).

You must return the list of moves that you want to perform. Each character of your return must describe one move. The top left corner of the yard corresponds to row and column zero. The possible moves are:

• L : Turn Left, the mower remains on the same cell and rotates left.
• R : Turn Right, the mower remains on the same cell and rotates right.
• S : Straight, the mower is pushed forward.

Scoring

For each test case we will calculate your raw and normalized scores. If you were not able to produce a valid return value, then your raw score is -1 and the normalized score is 0. Otherwise, the raw score is equal to the sum of all costs. The normalized score for each test is 1,000,000.0 * BEST / YOUR, where BEST is the lowest cost currently obtained on this test case (considering only the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases.

You can see your raw scores on each example test case by making an example submit. You can also see total scores of all competitors on provisional test set in the match standings. No other information about scores is available during the match.

Clarifications

• Grass under the mower gets mowed only when you leave the cell.
• You may not move into a non grass cell.
• The yard wraps around (left-right and top-bottom), you can move off the edge and will appear on the other side.
• The mower must end at the location where it started.
• The top left corner of the yard corresponds to row and column zero.
• Every un-mowed cell at the end of the simulation will incur a cost of slopeCost*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 yard size N is randomly selected between 20 and 80.
• The height of each cell is between 0 and 9.
• The turn cost is chosen between 1 and 10 and then multiplied by N/4.
• The forward cost is chosen between 1 and 10.
• The slope cost is chosen between 1 and 10 and then multiplied by N.
• The starting position is selected to be on a random location with grass.
• All values are chosen uniformly and independently, at random. Ranges are inclusive.

Tools

An offline tester/visualizer is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation, simulation and score calculation.

Definition

Notes

Examples