Mar 00 Challenge
Volume Number: 16
Issue Number: 3
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Sum of Powers
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 */
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.
The winner will be the solution that forms the desired results with the minimum
number of 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.
Three Months Ago Winner
Congratulations to Jonathan Taylor (Blandford, Dorset, U.K.) for winning the
December, 1999, Costas Array Challenge. The Costas Challenge required contestants to
produce all of the arrays of a given dimension that satisfied two criteria. First, each
row and each column of the array must have exactly one "1", with the remaining
entries being zeros. Second, the line connecting a pair of "1"s in an array may not have
the same slope as the line connecting any other pair of "1"s. Costas arrays have
properties that make it an ideal discrete waveform for some sensor applications. The
number of Costas arrays of order N increases until N==17, after which it decreases at
least until N==23. This Challenge attracted 16 entries, 13 of which worked correctly.
Jonathan's solution is recursive for array sizes greater than 17, but he gains speed by
unrolling the code for smaller orders. He also took advantage of the fact that assembly
language was permitted for this Challenge. For these smaller arrays, he maintained the
position of the "1"s in each row in separate registers, eliminating a significant
number of memory accesses. This optimization allowed Jonathan's entry to run
approximately 15% faster than the second place entry by Ernst Munter. Jonathan
included a nice description of the recursive and unrolled algorithms in the preface to
his code, so I won't repeat his description here.
I evaluated every entry by having them calculate the Costas arrays of orders 5 through
13, inclusive. I then extended the tests to include arrays of orders through 15.
Finally, I tested the top entries with arrays of orders through 17. In evaluating the
correctness of the arrays generated, I made use of some code provided by Ludovic
Nicolle. Ludo's code verified that each array produced met the criteria for a Costas
array, and that each array was distinct from any other array. Solutions were judged
correct if the number of valid, unique Costas arrays produced equaled the known
number of Costas arrays of a given order. Judging correctness would have been more
difficult if any of the solutions had completed problems where the number of Costas
arrays is unknown; fortunately (or unfortunately, depending on your point of view),
none of the entries completed problems of that size. Several contestants observed that
execution time increased by a factor of ~5.3 from one order to the next, and some
estimated that 1000 fast PowerMacs should be able to calculate the arrays of order 24
in a couple of weeks. Perhaps we should turn this over to the distributed.net folks.
The table below lists, for each of the solutions submitted, the cumulative time
required to calculate the Costas arrays up to orders 13, 15, and 17. It also indicates
the code size, data size, and programming language used by each solution. As usual, the
number in parentheses after the entrant's name is the total number of Challenge points
earned in all Challenges prior to this one.
Name Time (13) (secs) Time (15) (secs) Time (17) (secs) Errors
Code Size Data Size Lang
Jonathan Taylor (4) 7.69 228.79 1246.12 0 21334
200 C/asm
Ernst Munter (547) 9.31 270.32 1477.03 0 4668
8608 C++/asm
Ludovic Nicolle (48) 10.02 289.08 N/A 0 2612 24
Xan Gregg (116) 12.06 340.65 N/A 0 4428 8
Rob Shearer (41) 12.06 346.45 N/A 0 158720 10300
Willeke Rieken (61) 19.36 540.05 N/A 0 2420 8
Tom Saxton (158) 33.16 1011.24 N/A 0 1500 8 C
Greg Sadetsky (2) 40.74 1122.02 N/A 0 2044 8 C
Michael Lewis 51.94 1592.36 N/A 0 1528 72 C
Randy Boring (112) 57.32 1801.37 N/A 0 1516 24
Sebastian Maurer (77) 59.83 1927.93 N/A 0 1216 74
Brian Hall 125.35 3642.11 N/A 0 2880 412 C
Brady Duga (10) 130.50 N/A N/A 0 4152 371
D. L. N/A N/A N/A 1
C. L. N/A N/A N/A 1
B. B. N/A N/A N/A 1
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 or more points during the past two years. The
numbers below include points awarded over the 24 most recent contests, including
points earned by this month's entrants.
Rank Name Points
1. Munter, Ernst 247
2. Saxton, Tom 139
3. Maurer, Sebastian 67
4. Rieken, Willeke 51
5. Heithcock, JG 43
6. Shearer, Rob 43
7. Boring, Randy 39
8. Taylor, Jonathan 24
9. Brown, Pat 20
10. Jones, Dennis 12
11. Hart, Alan 11
12. Duga, Brady 10
13. Hewett, Kevin 10
14. Murphy, ACC 10
15. Selengut, Jared 10
16. Strout, Joe 10
17. Varilly, Patrick 10
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the
first person to suggest a Challenge that I use. The points you can win are:
1st place ›20 points
2nd place ›10 points
3rd place ›7 points
4th place ›4 points
5th place ›2 points
finding bug ›2 points
suggesting Challenge ›2 points
Here is Jonthan Taylor's winning Costas solution:
Costas.c
Copyright © 1999 Jonathan Taylor
/*
The algorithm works by attempting to find a position for a '1' in the
first row of the array, and then to work down the array attempting to
fill each row in turn until there is no permissible move, in which
case the program backtracks to the previous row and tries the next
permissible position. At the beginning of each row, it calculates a
bit-mask which shows which positions have been forbidden by the choice
of position on the previous rows.
There are two conditions that are detected:
1. A '1' is already in the column
2. Putting a '1' in this position would create three in a row:
Let a A and B be the x position of the '1' in two previous rows. Every
existing combination of A and B is checked in turn. C is another row's
x position. This row is the one which, when combined with B and C will
cause one of the positions in the current row to be forbidden. For
example:
1000 0000 row described by A
0000 0010
0010 0000 row described by B
0100 0000 row described by C
0001 0000
(the next row is the one currently being determined)
the '1' in row B is two right and two down of the one in A, so the
position two right and two down from the '1' in row C is forbidden.
The program will record this information appropriately
The program was a recursive function which stores the position of the
1 in each row (rowPos) in RAM, as well as the bitField for each row.
The bitField is a long where each bit represents one of the positions
that the '1' could be placed in the current row. If a bit is set, that
position is forbidden by the rules as applied to the rows that have
already been decided. Unused bits are also one. Note that each level
of recursion has its own bitField variable, each of which will be very
different.
In each recursion, it sets bitField to the appropriate value. If
bitField is now equal to
-1, there are no permissible places to put the '1' on this row, and
the function returns to the previous recursion. If it does not return,
it then checks each bit in bitField to see if it is a zero. If it is,
that is a permissible place for the '1'. It records this selection and
calls the next level of recursion (when that level returns, execution
will resume by trying the next bit in bitField).
If by placing a '1' at this level the array has been successfully
filled, the array has the correct values entered in it, and the
function then returns to the previous level of recursion in order to
continue the search for the next solution. It should be noted that if
an array is a valid solution, then its horizontal reflection is also a
different, valid solution (for 2 or more rows). That is also recorded
in the solution list. This allows the running time to be roughly
halved, because once the first row has been half traversed, all the
solutions will have been found.
The problem with that is that the program must be stopped halfway
through the arrays in order to prevent there being repeats. The
condition is slightly different for even- and odd-sized arrays, so one
of two different tests is used depending on the array size.
This version was used for cases of n>17. Version 2 handles smaller
cases (much faster!). The underlying algorithm is the same, though. It
could easily be extended to higher ones by writing more code.
Version 2
I suspected that the limiting factor for the speed of the previous
example was probably memory accesses. In calculating bitField, the
positions of the '1's in previous rows are used over and over again.
However, they are not used in order, and neither I nor the complier
could find any effective way of caching the values in registers to
save on RAM accesses. However, I realised there were in fact enough
registers to fit them all into registers.
This strategy is extremely fast, as it requires only one write to RAM
when calling the next recursion level, and one read when returning.
However there is a problem. I have been unable to discover a way of
indirectly addressing a register. It is not possible to design a loop
that will access, say, row_position[n] if it is stores in register n.