Fences (also known as Slitherlink) is a classic type of diagram puzzles.
The rules of Fences are as follows:
- You're given a rectangular grid of lattice points.
- Your task is to create a loop. The loop consists of segments connecting the neighboring points and those segments can only go vertically or horizontally.
- Some of the cells (squares formed by 4 neighboring points) can contain numbers. Each number represents the amount of loop's segments that must touch this number.
- The loop cannot cross or touch itself - this means that you cannot visit the same point twice.
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:
- size is randomly generated in [15, 100] range.
- fillRatio is randomly generated in [0.1, 1.0) range.
- weights array is created as 4 independent random numbers. The weights for numbers 0, 1 and 2 are in [0.0, 1.0) range, and the weight for number 3 is in [0.0, 0.5) range.
- size x size diagram is generated as follows. The probability that a cell contains a number is fillRatio. If a cell contains a number then it's chosen as 0, 1, 2 or 3, where the probability of choosing number X is proportional to weights[X].
- In a rare case, where the generated diagram contains no numbers, the whole process is restarted from scratch.
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.
The offline tester/visualizer is available. You can use it to test your solution locally.