| | You are packing shapes into a box, and wish to pack as many as possible. Each shape must be packed one at a time, in the order they are received, and cannot be moved once packed. Shapes may not overlap, and may not extend beyond the bounds of the box.
Your goal is to pack the box as fully as possible, leaving as little empty space as possible. For each call of your placeTile method, return a int[] with three elements, x, y, and r, indicating the location and rotation of the shape to place. Placing a piece at (x,y) places the upper left corner of its bounding box at that location. Return an empty int[] when you are no longer able to pack an item into the box. Both the box and item parameters are such that the first character of the first string is the upper-left (0,0) of the box/piece and the last character of the last string is the bottom right. Each 'X' character indicates part of a piece, or a location in the box that is already filled, while each '.' character represents an empty location.
The width and height of the box are chosen between 10 and 100, uniformly at random. Each shape to place is a polyomino of size 4 or 5 that can be rotated in 90 degree increments, but not flipped over. There are 7 such pieces of size 4, and 18 of size 5. Each of the 25 total pieces is equally likely to be chosen next. An example of rotating a piece is shown below:
XXX XX X.. .X
..X X. XXX .X
X. XX
r = 0 r = 1 r = 2 r = 3
Your raw score for each test case will be the amount of unused space in the box. (If your solution produces an error, makes an invalid move, etc, then all spaces are considered unused.) The total unused spaces over all cases will be summed for each submission. Your final score will be 1000 * best_sum / your_sum.
A visualization tool is available to aid you in development.
|