Challenge Overview
Problem Statement | |||||||||||||
Fences (also known as Slitherlink) is a classic type of diagram puzzles. The rules of Fences are as follows:
In this problem your task is to create a program that gets a fences puzzle as an input and finds a valid loop that satisfies as many clues (numbers) as possible. Please note that those puzzles are most probably not valid. This means that in most cases it won't be possible to satisfy all of the numbers and even if it's possible, most likely there will be several ways of doing it. Test case generation:
Implementation and Scoring: You have to implement findLoop method, that takes a String[] diagram and returns a valid loop as a String. The diagram is formatted as follows. Each element describes one row of cells. And each character in a row describes one cell. That means that diagram[r][c] describes the cell at row r and column c. Empty cells are represented by "-" (dash) character and numbers are represented by "0", "1", "2" and "3". Your return value should be formatted as "Row Column Loop". Row and Column describe the 0-indexed position of some lattice point on your loop, where (0, 0) corresponds to the upper-left corner. Loop should describe the path that traverses your loop around (in any direction) starting from (Row, Column) point. Loop should be a string that consists only of "U", "D", "L" and "R" characters, which stand for Up, Down, Left and Right. Since the task is to find a closed loop, your path should end in the same place where it started. Raw score for each test case is simply the number of correct (satisfied) clues divided by the total number of clues. This is the score you will see in the example submission and in the visualizer. If your return was invalid or you exceeded time limit then your raw score for that test case is 0. In this contest we are using relative scoring. This means that your score for each test case will be divided by the current best solution for this test case (among all competitors). So normalizedScore = rawScore / bestRawScore. Your overall score will be equal to 1000000 * (the arithmetic average of your normalized scores for all test cases). This is the score you will see on the standings page. Tools The offline tester/visualizer is available. You can use it to test your solution locally. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | The memory limit is 1024 MB and the time limit is 10 seconds (which includes only time spent in your code). | ||||||||||||
| - | 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. You can find information about compilers that we use and compilation options here. | ||||||||||||
| - | There are 10 example test cases and 100 full submission test cases. | ||||||||||||
| - | By default all random variables are generated from uniform distribution. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
| 5) | |||||||||||||
| |||||||||||||
| 6) | |||||||||||||
| |||||||||||||
| 7) | |||||||||||||
| |||||||||||||
| 8) | |||||||||||||
| |||||||||||||
| 9) | |||||||||||||
| |||||||||||||
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)2020, TopCoder, Inc. All rights reserved.