TweetFollow Us on Twitter

Feb 00 Challenge

Volume Number: 16 (2000)
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)
extern "C" {

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)

For example, 


is a Latin Square with the value 1234234141233412. It is not the minimal Latin Square of order 4, however, since the following Latin Square,


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 C++
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:

Copyright © 1999 Tom Saxton

#include "PuttingGreen.h"

#include <stdlib.h>
#include <math.h>

	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;			// 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);
static double _DotVec(VEC vec1, VEC vec2);
static double _LenVec(VEC vec);
static void _ScaleVec(VEC vec, double s, VEC *pvecResult);

// triangle utilities

static void _GetMidTriPos(int itri, Point3DDouble *ppos);

// Entry Points
#if 0
static void ___Entry_Points(){}


void InitGreen(
	Point3DDouble paposGrid[],	/* green terrain description */
	long cposGrid,	/* number of points */
	MyTriangle patri[],	/* triangles comprising the green */
	int ctri,	/* number of triangles */
	long itriPin,	/* index in triangles[] of the pin on this green */
	long cholePractice,	/* number of unscored (but timed) holes to 			   practice on this green */
	long choleScored	/* number of holes to be scored on this green */

	s_paposGrid = paposGrid;
	s_cposGrid = cposGrid;
	s_patri = patri;
	s_ctri = ctri;
	s_itriPin = itriPin;
	s_cholePractice = cholePractice;
	s_choleScored = choleScored;
	_GetMidTriPos(itriPin, &s_posPin);
	s_ihole = 0;
#pragma warn_unusedarg off


void StartHole(	/* called to start play on this hole */
	Point3DDouble posStart, 	/* initial ball position on the green */
	Boolean fPractice	/* TRUE if this hole is practice */
	s_posCur = posStart;
	s_cputt = 0;
	s_fPractice = fPractice;

#pragma warn_unusedarg reset

#define cputtPractice 10
#define cputtScore    10

typedef struct SD SD;
struct SD
	double speed;
	double dist;
static SD s_asd[cputtPractice];
static int s_csd;


Boolean 		/* quit */ MakePutt(
	Velocity2DDouble *pvXY		/* return initial ball velocity in the z==0 plane */
	double dist;
	Point3DDouble vXY;
	if (s_cputt >= (s_fPractice ? cputtPractice : cputtScore))
		if (s_fGetDrag)
			int isd;
			double sumX, sumY, sumXY, sumXX;
			Assert(s_csd > 0);

			// do linear regression on the data

			sumX = sumY = sumXY = sumXX = 0;
			for (isd = 0; isd < s_csd; ++isd)
				SD *psd = &s_asd[isd];
				double y = psd->dist;
				double x = fabs(psd->speed);
				sumXX += x * x;
				sumXY += x * y;
				sumX += x;
				sumY += y;
			mDrag = (sumX*sumY - s_csd*sumXY)/(sumX*sumX - s_csd*sumXX);
			bDrag = (sumY - mDrag*sumX)/s_csd;
			Assert(0.0 <= mDrag && mDrag <= 5.0);
			Assert(-5.0 <= bDrag && bDrag <= 5.0);

			s_fGetDrag = fFalse;
		// give up

		return fTrue;
	// just give up after we've finished with practice shots

	if (s_fPractice && !s_fGetDrag)
		return fTrue;

	_SubVec(s_posPin, s_posCur, &vXY);
	vXY.z = 0;
	dist = _LenVec(vXY);
	if (s_fGetDrag)
		s_svInitial = 3.0*(1.0 + s_cputt/2);
		if (s_cputt % 2)
			s_svInitial = -s_svInitial;
		s_svInitial = (dist + 0.03 - bDrag) / mDrag;
		s_distExpect = dist;
	_ScaleVec(vXY, s_svInitial/dist, &vXY);
	pvXY->x = vXY.x;
	pvXY->y = vXY.y;

	return fFalse; // keep going


void BallMovement(
	BallPosition papos4[],	/* provides ball movement in response to MakePutt */
	int cpos,	/* number of ball positions provided */
	Boolean fInHole	/* true if the ball went into the hole */
	Point3DDouble posNew;
	posNew = papos4[cpos-1].pt;
	if (!fInHole)
		double dist;
		Point3DDouble vecMove;
		_SubVec(posNew, s_posCur, &vecMove);
		dist = _LenVec(vecMove);

		if (s_fGetDrag)
			Assert(0 <= s_csd && s_csd < DIM(s_asd));
			s_asd[s_csd].speed = fabs(s_svInitial);
			s_asd[s_csd].dist = dist;

	s_posCur = posNew;

// Vector Functions

#if 0
static void ___Vector_Functions(){}


static void _SubVec(VEC pos1, VEC pos2, VEC *pposResult)
	pposResult->x = pos1.x - pos2.x;
	pposResult->y = pos1.y - pos2.y;
	pposResult->z = pos1.z - pos2.z;


static double _DotVec(VEC vec1, VEC vec2)
	return vec1.x * vec2.x + vec1.y * vec2.y + vec1.z * vec2.z;


static double _LenVec(VEC vec)
	return sqrt(_DotVec(vec, vec));

static void _ScaleVec(VEC vec, double s, VEC *pvecResult)
	pvecResult->x = s * vec.x;
	pvecResult->y = s * vec.y;
	pvecResult->z = s * vec.z;



static void _GetMidTriPos(int itri, Point3DDouble *pposMid)
	MyTriangle tri;
	int iipos;
	Assert(0 <= itri && itri < s_ctri);
	tri = s_patri[itri];
	*pposMid = s_vecZero;
	for (iipos = 0; iipos < DIM(tri.pointIndices); ++iipos)
		Point3DDouble *ppos;
		Assert(0 <= tri.pointIndices[iipos] && 
										tri.pointIndices[iipos] < s_cposGrid);
		ppos = &s_paposGrid[tri.pointIndices[iipos]];
		pposMid->x += ppos->x;
		pposMid->y += ppos->y;
		pposMid->z += ppos->z;
	pposMid->x *= 1.0/3.0;
	pposMid->y *= 1.0/3.0;
	pposMid->z *= 1.0/3.0;

Community Search:
MacTech Search:

Software Updates via MacUpdate

World of Tanks Generals guide - Tips and...
World of Tanks Generals is a brand new card game by the developer behind the World of Tanks shooter franchise. It plays like a cross between chess and your typical card game. You have to keep in consideration where you place your tanks on the board... | Read more »
TruckSimulation 16 guide: How to succeed...
Remember those strangely enjoyable truck missions in Grand Theft Auto V whereit was a disturbing amount of fun to deliver cargo? TruckSimulation 16 is reminiscent of that, and has you play the role of a truck driver who has to deliver various... | Read more »
The best GIF making apps
Animated GIFs have exploded in popularity recently which is likely thanks to a combination of Tumblr, our shorter attention spans, and the simple fact they’re a lot of fun. [Read more] | Read more »
The best remote desktop apps for iOS
We've been sifting through the App Store to find the best ways to do computer tasks on a tablet. That gave us a thought - what if we could just do computer tasks from our tablets? Here's a list of the best remote desktop apps to help you use your... | Read more »
Warhammer 40,000: Freeblade guide - How...
Warhammer 40,000: Freebladejust launched in the App Store and it lets you live your childhood dream of blowing up and slashing a bunch of enemies as a massive, hulking Space Marine. It's not easy being a Space Marine though - and particularly if... | Read more »
Gopogo guide - How to bounce like the be...
Nitrome just launched a new game and, as to be expected, it's a lot of addictive fun. It's called Gopogo, and it challenges you to hoparound a bunch of platforms, avoiding enemies and picking up shiny stuff. It's not easy though - just like the... | Read more »
Sago Mini Superhero (Education)
Sago Mini Superhero 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: KAPOW! Jack the rabbit bursts into the sky as the Sago Mini Superhero! Fly with Jack as he lifts impossible weights,... | Read more »
Star Wars: Galaxy of Heroes guide - How...
Star Wars: Galaxy of Heroes is all about collecting heroes, powering them up, and using them together to defeat your foes. It's pretty straightforward stuff for the most part, but increasing your characters' stats can be a bit confusing because it... | Read more »
The best cooking apps (just in time for...
It’s that time of year again, where you’ll be gathering around the dinner table with your family and a huge feast in front of you. [Read more] | Read more »
Square Rave guide - How to grab those te...
Square Rave is an awesome little music-oriented puzzle game that smacks of games like Lumines, but with its own unique sense of gameplay. To help wrap your head around the game, keep the following tips and tricks in mind. [Read more] | Read more »

Price Scanner via

Cyber Monday: Apple MacBooks on sale for up t...
Apple resellers have MacBook Pros, MacBook Airs, and MacBooks on sale for up to $250 off MSRP for Cyber Monday 2015. The following is a roundup of the lowest prices available for new models from any... Read more
Cyber Monday: 15% off Apple products, and sto...
Use code CYBER15 on Cyber Monday only to take 15% on Apple products at Target, and store-wide. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-... Read more
iPad Air 2 And iPad mini Among Top Five Black...
Adobe has released its 2015 online shopping data for Black Friday and Thanksgiving Day. The five best selling electronic products on Black Friday were Samsung 4K TVs, Apple iPad Air 2, Microsoft Xbox... Read more
All-in-one PC Shipments Projected To Drop Ove...
Digitimes’ Aaron Lee and Joseph Tsai report that all-in-one (AIO) PC shipments may drop a double-digit percentage on-year in 2015 due to weaker-than-expected demand, although second-largest AIO make... Read more
Sprint Offers iPad Pro
Sprint now offers Apple’s new iPad Pro with Wi-Fi + Cellular, featuring a 12.9-inch Retina display with 5.6 million pixels. Customers can pick up iPad Pro at select Sprint retail locations. It can... Read more
Cyber Monday: Target offers 15% discount on A...
Target has discounted Apple Watches by 15% for Cyber Monday. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary: - Apple... Read more
Sunday roundup of Holiday weekend Mac sales:...
Take up to $500 off MSRP on the price of a new Mac at B&H Photo today as part of their Black Friday/Holiday weekend sale. Shipping is free, and B&H charges NY tax only. These prices are... Read more
Holiday weekend: Apple Watch on sale for $50-...
B&H Photo has the Apple Watch on sale today for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - Apple Watch Sport: $50 off - Apple Watch: $50-$100 off Read more
Holiday weekend: iPad Air 2s on sale for up t...
B&H Photo has iPad Air 2s on sale for up to $80 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $459 $40 off - 64GB iPad Air 2 WiFi: $569 $30 off - 128GB iPad Air... Read more
Holiday weekend Mac sales roundup: B&H Ph...
B&H Photo continues to have all new Macs on sale for up to $500 off MSRP as part of their Black Friday/Holiday weekend sale. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina... Read more

Jobs Board

Technical Program Manager, Strategic Merchant...
# Technical Program Manager, Strategic Merchants - Apple Pay Job Number: 44001177 Santa Clara Valley, Califo ia, United States Posted: Oct. 30, 2015 Weekly Hours: 40.00 Read more
Frameworks Engineer, *Apple* Watch - Apple...
# Frameworks Engineer, Apple Watch Job Number: 41403122 Santa Clara Valley, Califo ia, United States Posted: Jul. 1, 2015 Weekly Hours: 40.00 **Job Summary** Join the Read more
Software Engineer - *Apple* Pay - Apple (Un...
# Software Engineer - Apple Pay Job Number: 44003246 Santa Clara Valley, Califo ia, United States Posted: Nov. 16, 2015 Weekly Hours: 40.00 **Job Summary** Apple Pay Read more
Merchant Operations Manager: *Apple* Pay -...
# Merchant Operations Manager: Apple Pay Job Number: 43593822 Santa Clara Valley, Califo ia, United States Posted: Nov. 10, 2015 Weekly Hours: 40.00 **Job Summary** The Read more
Product Design Engineer - *Apple* Watch - A...
# Product Design Engineer - Apple Watch Job Number: 41727161 Santa Clara Valley, Califo ia, United States Posted: Jul. 22, 2015 Weekly Hours: 40.00 **Job Summary** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.