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" {
#endif

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

PuttingGreen.c
Copyright © 1999 Tom Saxton

#include "PuttingGreen.h"

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

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;			// 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(){}
#endif

InitGreen

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

StartHole

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_ihole;
	
	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;

MakePutt

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;
	}
	else
	{
		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
}

BallMovement

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_csd;
		}
	}

	s_posCur = posNew;
		
	++s_cputt;
}

//
// Vector Functions
//

#if 0
static void ___Vector_Functions(){}
#endif

_SubVec

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;
}

_DotVec

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

_LenVec

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

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

}

_GetMidTriPos

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;
}
 
AAPL
$118.93
Apple Inc.
-0.07
MSFT
$47.81
Microsoft Corpora
+0.06
GOOG
$541.83
Google Inc.
+1.46

MacTech Search:
Community Search:

Software Updates via MacUpdate

Adobe Photoshop Elements 13.0 - Consumer...
Adobe Photoshop Elements 12--the #1 selling consumer photo editing software--helps you edit pictures with powerful, easy-to-use options and share them via print, the web, Facebook, and more.Version... Read more
Skype 7.2.0.412 - Voice-over-internet ph...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
HoudahSpot 3.9.6 - Advanced file search...
HoudahSpot is a powerful file search tool built upon MacOS X Spotlight. Spotlight unleashed Create detailed queries to locate the exact file you need Narrow down searches. Zero in on files Save... Read more
RapidWeaver 6.0.3 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
iPhoto Library Manager 4.1.10 - Manage m...
iPhoto Library Manager lets you organize your photos into multiple iPhoto libraries. Separate your high school and college photos from your latest summer vacation pictures. Or keep some photo... Read more
iExplorer 3.5.1.9 - View and transfer al...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
MacUpdate Desktop 6.0.3 - Discover and i...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
SteerMouse 4.2.2 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. It also supports Apple Mighty Mouse very well. SteerMouse can assign various functions to buttons that Apple's software does not allow,... Read more
iMazing 1.1 - Complete iOS device manage...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
PopChar X 7.0 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more

Latest Forum Discussions

See All

Mystery Case Files: Dire Grove, Sacred G...
Mystery Case Files: Dire Grove, Sacred Grove HD Review By Jennifer Allen on November 28th, 2014 Our Rating: iPad Only App - Designed for the iPad A decent new installment for the popular Mystery Case Files series.   | Read more »
Castaway Paradise – Tips, Tricks, and St...
Ahoy there, castaways: Were you curious about our own thoughts regarding this pristine shipwreck? Check out our Castaway Paradise review! Castaway Paradise is out for iOS, finally giving mobile gamers the opportunity to enjoy the idyllic lifestyle... | Read more »
Castaway Paradise VIP Subs are on Sale f...
Castaway Paradise VIP Subs are on Sale for a Limited Time, and a Special Holiday Update is Coming Soon Posted by Rob Rich on November 28th, 2014 [ | Read more »
Primitive Review
Primitive Review By Jordan Minor on November 28th, 2014 Our Rating: :: FOLK ARTUniversal App - Designed for iPhone and iPad True to its name, Primitive is about as straightforward as runners get.   | Read more »
7 tips to get ahead of the competition i...
7 tips to get ahead of the competition in Dynasty of Dungeons Posted by Simon Reed on November 28th, 2014 [ permalink ] Playcrab has launched their action-packed new dungeon crawler, Dynasty of Dungeons, today. | Read more »
Master of Tea Kung Fu Review
Master of Tea Kung Fu Review By Jordan Minor on November 28th, 2014 Our Rating: :: ONE DROP RULESUniversal App - Designed for iPhone and iPad Master of Tea Kung Fu is a creative and complex caffeinated brawler.   | Read more »
Monster Strike Review
Monster Strike Review By Campbell Bird on November 28th, 2014 Our Rating: :: BILLIARD STRATEGYUniversal App - Designed for iPhone and iPad Collect monsters and battle by flinging them across the battlefield in this strangely... | Read more »
Proun+ Review
Proun+ Review By Jennifer Allen on November 28th, 2014 Our Rating: :: TWITCHY RACINGUniversal App - Designed for iPhone and iPad Twitchy racing aplenty in Proun+, an enjoyably tricky title.   | Read more »
Lucha Amigos (Games)
Lucha Amigos 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Forget Ninja Turtles, and meet Wrestlers Turtles! Crazier, Spicier and…Bouncier! Sling carapaces of 7 Luchadores to knock all... | Read more »
Record of Agarest War Zero (Games)
Record of Agarest War Zero 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: HyperDevbox Holiday Turkey Black Friday Special Pricing! To celebrate the opening of the holiday season HyperDevbox... | Read more »

Price Scanner via MacPrices.net

Up To 75% Off Infovole Text Apps Over Black F...
Infovole’s entire range of apps, including the Textkraft family of word processors for iPads and iPhones, is being offered at 50-75% off over the Black Friday and Cyber Monday weekend. The five-day... Read more
Black Friday: Up to $60 off Mac minis, NY tax...
 B&H Photo has new 2014 Mac minis on sale for up to $60 off MSRP as part of their Black Friday sale. Shipping is free, and B&H charges NY sales tax only: - 1.4GHz Mac mini: $449.99 $50 off... Read more
Black Friday: 27-inch 5K iMac for $2299, save...
 B&H Photo continues to offer Black Friday sale prices on the 27″ 3.5GHz 5K iMac, in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP... Read more
Karalux Announces 24K Gold-Plated iPhone 6
Karalux, a Vietnam-based jewellery firm, has launched a unique 24 karat gold-plated iPhone 6 version with gold-cast monolithic dragon on its back panel. The real 24 karat gold plated enclosure doesn’... Read more
Black Friday: 13-inch 2.6GHz Retina MacBook P...
 B&H Photo has lowered their price for the 13″ 2.6GHz/128GB Retina MacBook Pro to $1159 for Black Friday. That’s $140 off MSRP, and it’s the lowest price for this model (except for Apple’s $1099... Read more
View all the Black Friday sales on our Mac Pr...
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. View Black Friday sale prices at a... Read more
Black Friday: 11-inch MacBook Air for $779, s...
 Best Buy has lowered their price for the 2014 11″ 1.4GHz/128GB MacBook Air to $779.99 for Black Friday. That’s $120 off MSRP. Choose free shipping or free local store pickup (if available). Sale... Read more
Apple Store Black Friday sale for 2014: $100...
BLACK FRIDAY The Apple Store has posted their Black Friday deals for 2014. Receive a $100 PRODUCT(RED) branded iTunes gift card with the purchase of select Macs, $50 with iPads, and $25 with iPods,... Read more
Black Friday: 15% off iTunes Gift Cards
Staples is offering 15% off $50 and $100 iTunes Gift Cards on their online store as part of their Black Friday sale. Click here for more information. Shipping is free. Best Buy is offering $100... Read more
BEVL Releases Dock Tailored for iPhone 6 and...
Seattle based BEVL has released their first product: an iPhone dock that is divergent in build quality, rock-solid function and visual simplicity to complement the iPhone. BEVL is now accepting... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.