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,
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.
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".