|
March 2000 Programmer's Challenge
Sum of the Powers
(Revised Problem Statement)
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Wednesday, 1 March 2000
A year or so back, Ken Slezak wrote me to say: "Recently my 7th grade son showed me an extra credit math problem. Given a number from 1 to 100, create that number from one, two, or three squared numbers added or subtracted together…. It turned out to be more difficult than I thought! Might this make an interesting programming challenge?" Well, Ken, we’re about to find out.
First, though, we need to spice up the problem a bit. I’ve been trying to make the problems a little easier of late, but the 7th grade level, even the 7th grade extra credit level, would be a bit too easy. First, we’ll expand the problem domain to include any positive number that fits into a signed 32-bit long integer. Second, we’ll expand the number of terms allowed. And third, instead of limiting the problem to only squared numbers, we’ll allow any positive exponent greater than 1.
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
