As those of you who are regular readers know, the ProgrammerŐs Challenge problems have become more difficult over time. Just as all scientific discoveries worth making had been made by the mid-twentieth century, so it is that all simple Challenge problems have been posed and solved by this time. Then again, as they say, maybe not. This month's problem is borrowed from http://www.polymathlove.com/, where Gary Smith posts software he uses in teaching mathematics to elementary and middle school students. One of his programs is called Area Puzzles, where students create rectangles with specified areas to cover a grid subject to certain constraints.
The prototype for the code you should write is:
void Area(
const short *cells,
/* rectangle to be covered with smaller rectangles */
/* index [row][col] as cells[row*rectWidth + col[ */
/* value N>0 means this cell must be covered by a rectangle of area N */
short rectWidth,
short rectHeight,
Rect yourRects[]
);
Your Area routine will be called with a rectangle of cells of width rectWidth and height rectHeight. Your task is to create a set of smaller rectangles (yourRect) that cover these cells. In doing so, you need to satisfy some constraints. Certain of the cells will have a nonzero value, and those cells must be covered by a rectangle with an area equal to that value. As an example, if the input cells were configured as follows É
0 0 3 0 6 0 0 0 0 8
0 6 0 0 0 0 0 0 0 0
0 0 0 0 0 0 4 0 0 0
0 0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 15 0
0 0 0 0 0 0 0 0 0 0
0 10 0 0 24 0 0 4 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 4 0 0 4 0 0 3
... you might create a set of rectangles like this, where each cell is shown with the number of the rectangle including that cell.
1 1 1 2 2 2 3 3 3 3
4 4 5 2 2 2 3 3 3 3
4 4 5 6 6 6 6 7 7 7
4 4 5 8 8 8 8 7 7 7
9 10 10 8 8 8 8 7 7 7
9 10 10 8 8 8 8 7 7 7
9 10 10 8 8 8 8 7 7 7
9 10 10 8 8 8 8 13 13 14
9 10 10 8 8 8 8 13 13 14
9 11 11 11 11 12 12 12 12 14
You should return the rectangles that cover the cell array and satisfy the constraints as yourRects. Each cell may be included in only one rectangle. If the cell has a nonzero value when Area is called, it must be included in a rectangle with an area equal to that value. Memory for the rectangles you create will be allocated for you, and there will be as many of those rectangles as there are nonzero values in the cells array. Any solution that covers the entire cells array and satisfies the constraints will be considered correct.
Scoring will be based on execution time - the winner will be the solution that correctly solves the puzzles with the smallest execution time.
This will be a native PowerPC Carbon C++ Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X. Also, when submitting you solution, please include the project file and the code you used to test your solution. Occasionally I receive a solution that will not compile and, while I always try to correct these problems, it is easier to do so if I have your entire project available.
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 15th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".