The prototype for the code you should write is:
typedef struct IntegerPower {
long value; /* term is sign*value^power */
short power; /* power = 2,3,4,... */
short sign; /* +1 or -1, -1 disallowed if power==2 */
} IntegerPower;
long /* number of factors */ SumOfPowers (
long result, /* terms need to sum to this result */
IntegerPower terms[], /* return terms sign*value^power here */
long maxTerms /* maximum number of terms allowed */
);
Your SumOfPowers routine will be called a number of times. Each time, you must identify a set of terms which sum to the specified result. Each term is a value raised to an integer power greater than 1, multiplied by a sign value. You should return the number of terms used to form the result, or zero if the result cannot be formed with maxTerms terms.
To prevent a trivial solution, a negative sign is prohibited for values raised to a power==2. Furthermore, all intermediate results must fit into a 32-bit long integer.
The winner will be the solution that forms the desired result in the shortest time with the fewest terms. A time penalty of one term will be added per 100 milliseconds of execution time. All solutions must be calculated at execution time; any entry that precalculates a solution will be disqualified.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C, C++, or Pascal. Solutions in Java will also be accepted, but Java entries must be accompanied by a test driver that uses the interface provided in the problem statement.
Ken Slezak earns 2 Challenge points for suggesting this month’s Challenge.
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 12th 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".
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
