Feb 00 Challenge
Volume Number: 16
Issue Number: 2
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Web apps with Lasso and FileMaker Pro
Latin Squares
A Latin Square of order N is an NxN array of numbers, where each number from
0..N-1 occurs exactly once in each row and in each column. Your Challenge this month
is to construct Latin Squares that are minimal, in the sense that each must form the
smallest NxN digit base N number, where the digits are read off column by column, one
row at a time.
The prototype for the code you should write is:
#if defined(__cplusplus)
void LatinSquares(
short n, /* dimension of the Latin Square to be generated */
short *latinSquare /* set latinSquare[c + r*n] to square value row
r, col c */
);
#if defined(__cplusplus)
}
#endif
For example,
1234
2341
4123
3412
is a Latin Square with the value 1234234141233412. It is not the minimal Latin
Square of order 4, however, since the following Latin Square,
1234
2143
3412
4321
forms the number 1234214334124321.
The dimension of the squares you must generate will be less than 2**16. The winner
will be the solution that correctly computes minimal Latin Squares in the least amount
of execution time. Code size and code elegance, in that order, will be the tiebreakers, in
the event two solutions are within 1% of one another in execution time. All Latin
Squares must be computed at execution time - entries that precompute solutions will
be disqualified.
This month's Challenge was suggested by Aaron Montgomery, who earns 2 Challenge
points for making the suggestion
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.
Three Months Ago Winner
Congratulations to Tom Saxton for taking first place in the November, 1999, Putting
Green Challenge. While I'm not sure that the next Ryder Cup teams will be beating a
path to his door for his four-putting green skills, Tom did soundly beat the three other
entries.
The Putting Green Challenge required contestants to analyze a sequence of greens
described as three-dimensional points connected into adjoining triangles. Each green
had a fixed pin position, and several holes were played on each green from varying
initial ball positions. Complicating the Challenger's job was the fact that the
propagation model was unknown, available only by observing the results of a putt. For
each green, the contestants were given several practice holes that could be used to
puzzle out the propagation model. Scoring was based on an award of 100 points for each
hole successfully completed, minus 10 points for each stroke taken (not counting
practice holes), and minus 10 points for each second of execution time (including
practice time).
Two of the solutions submitted did not manage to sink a putt for any of the holes played
in my test match. One of those solutions simply hit the ball at the hole very hard,
trying to take advantage of a possible ambiguity about ball velocity in the problem
statement. I heard from enough real golfers who had rimmed the cup a few times that I
had to close the velocity loophole. Tom's winning solution is fairly straightforward. He
takes 10 practice shots on the first hole of the first green to estimate the drag
coefficients. It does not attempt to analyze the contours of the green or to model the
effect of gravity. But the drag model is good enough to put the ball in the hole with only
one putt on a level green, and with one or two putts on a flat but gently sloping green.
I used three greens in my test cases, a perfectly flat and level green, a flat but gently
sloping green, and a green with more varied terrain. Five practice holes were played
on each green, five scored holes on each of the first two greens, and 20 holes on the
final green. On the interesting terrain of the last hole, Tom's solution completed each
hole successfully, taking up to seven putts to complete the hole.
The table below lists, for each of the solutions submitted, the number of holes
successfully completed, the total number of strokes taken on nonpractice holes, total
execution time, the total score, and the size and language code parameters. 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 Holes Strokes Time Score Code Data Lang
Tom Saxton (138) 30 117 3.148 1829.969 2224
432 C
Brady Duga 10 49 2.435 509.976 1660 380 C
R. S. 0 60 0.42 -600.004 568 93
J. T. 0 210 197.47 -2101.975 2580 255 C
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 237
2. Saxton, Tom 146
3. Maurer, Sebastian 67
4. Rieken, Willeke 51
5. Heithcock, JG 43
6. Shearer, Rob 41
7. Boring, Randy 39
8. Brown, Pat 20
9. Hostetter, Mat 20
10. Jones, Dennis 12
11. Hart, Alan 11
12. Duga, Brady 10
13. Hewett, Kevin 10
14. Murphy, ACC 10
14. Selengut, Jared 10
16. Smith, Brad 10
17. Strout, Joe 10
18. 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 Tom's winning Putting Green solution:
PuttingGreen.c
Copyright © 1999 Tom Saxton
enum
{
fFalse = 0,
fTrue = TRUE
};
#define DIM(a) (sizeof(a)/sizeof((a)[0]))
// disable asserts
#define Assert(f)
// vector types and constants
typedef struct Point3DDouble VEC;
static const double epsilon = 1.0e-7;
static const VEC s_normalZ = { 0, 0, 1.0 };
static const VEC s_vecZero;
// this green
static Point3DDouble *s_paposGrid;
static int s_cposGrid;
static MyTriangle *s_patri;
static int s_ctri;
static int s_itriPin;
static Point3DDouble s_posPin;
static int s_cholePractice; [TOKEN:12079] number of practice putts
static int s_choleScored; // number of scored
putts
// computed physical constants for this green
static int s_fGetDrag = fTrue;
static double mDrag, bDrag;
// current state
static int s_ihole; // which hole are
we on?
static int s_cputt; // which putt is
this
static int s_fPractice; // is this a practice
putt?
static Point3DDouble s_posCur; // where's the ball?
// the current putt
static double s_svInitial;
static double s_distExpect;
// vector utilities
static void _SubVec(VEC pos1, VEC pos2, VEC *pposResult);