A polyomino is a set of simply connected squares whose edges are fully adjacent to one another. As a simple example, the classic game Tetris uses polyominoes of order 4, meaning they are composed of four squares each.
You are given a partially covered board of size width-by-height. Two int[]s, x and y indicate the locations that are already covered (by 'X' in the examples). The tester will call your method, fillBoard, and will provide as parameters the size of the board, and the covered locations (corresponding elements of x and y indicate a covered cell).
The goal of the game is to completely cover the board with polyominoes of various sizes, leaving as few polyominoes unused as possible. No two polyominoes may overlap, no polyonimo may cover any cell that was covered to start with, or go beyond the edges of the game board.
Two library functions, getNext and placeNext, are provided. getNext should be called with a single parameter indicating the size (order) of the polyomino you wish to receive, which may be from 3 to 1000, inclusive. The returned String[] will represent the generated polyomino, where each 'X' character is a square composing the polyomino (the other characters are spaces). The String[] will represent the minimal rectangular bounding box encapsulating the polyomino. Each polyomino requested is assigned an index: the first is index 0, the second is index 1, etc. You may request up to 10,000 polyominoes throughout the game, holding as many of them at a time as you like (i.e. you need not place a polyomino as soon as you receive it). When you want to place a tile, you should call Polyomino.placeNext with four parameters: the index of the polyomino you are placing, the x and y coordinates of the upper-left corner of the bounding box, and the rotation. For the rotation, 0 = no rotation, 1 = 90 degrees counter-clockwise, 2 = 180 degrees counter-clockwise, 3 = 270 degrees counter-clockwise.
Your program will have 30 seconds to execute. Every time you place a tile, you will score x2 points, where x is the size of the tile. (After calling placeNext, the return value will indicate your total score so far.) Once you are done filling the board, any requested tiles that have been unused will count against your score in the same fashion. (If this penalty results in a negative score, you will receive a 0 for the test case.) Any calls to getTile with an invalid size, or that would exceed 10,000 tiles will result in scoring a 0 for the test case. Calling placeNext with an invalid index, or invalid rotation, will result in a 0 for the test case. Also, if the position to place the tile would cause it to cover a previously covered cell, or go off the edge of the board (partly or entirely), it will result in a 0 for the test case. Once your method returns, a time penalty of 1% per second will be deduced from your score. Thus, if you score 200 points by placing tiles, and use 10 seconds of processor time, you will end up with a score of 180.
The total score will be the sum of the relative scores for each test case. Each relative score will be the raw score for that test case proportional to the best score anyone achieved for that case. For instance, if you score 50 on a test case, and the best score is 200, that equates to a relative score of 0.25 for that case. (Thus, the maximum possible total score is equal to the number of test cases.)
When you request a new tile, it will be randomly generated. Generation will start with a single square. Then, an additional square will be chosen randomly among all squares adjacent to the current polyomino, and added to the tile, repetetively, until the desired size has been reached. Note that this generation does not produce all polyominoes with equal probability. For example, of the two size 3 polyominoes {"XX","X "} is twice as likely as {"XXX"} (taking into account the isomorphisms from rotation).
Test cases are generated as follows: width and height are selected uniformly at random, between 20 and 200. Then, the number of covered cells is chosen randomly between height * width * 0.1 and height * width * 0.7. The locations of the covered cells are chosen uniformly at random.
|