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

Community Search:
MacTech Search:

Software Updates via MacUpdate

MacFamilyTree 7.3.4 - Create and explore...
MacFamilyTree gives genealogy a facelift: it's modern, interactive, incredibly fast, and easy to use. We're convinced that generations of chroniclers would have loved to trade in their genealogy... Read more
Yummy FTP 1.10.2 - FTP/SFTP/FTPS client...
Yummy FTP is an FTP + SFTP + FTPS file transfer client which focuses on speed, reliability and productivity. Whether you need to transfer a few files or a few thousand, schedule automatic backups, or... Read more
VueScan 9.5.08 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Iridient Developer 3.0.1 - Powerful imag...
Iridient Developer (was RAW Developer) is a powerful image conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more
Air Video Server HD 2.1.0 - Stream video...
Air Video Server HD streams videos instantly from your computer on your iPhone, iPad, iPod touch or Apple TV. No need to worry about converting or transferring files. We took everything that was... Read more
Duplicate Annihilator 5.7.5 - Find and d...
Duplicate Annihilator takes on the time-consuming task of comparing the images in your iPhoto library using effective algorithms to make sure that no duplicate escapes. Duplicate Annihilator... Read more
BusyContacts 1.0.2 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
Capture One Pro 8.2.0.82 - RAW workflow...
Capture One Pro 8 is a professional RAW converter offering you ultimate image quality with accurate colors and incredible detail from more than 300 high-end cameras -- straight out of the box. It... Read more
Backblaze 4.0.0.872 - Online backup serv...
Backblaze is an online backup service designed from the ground-up for the Mac.With unlimited storage available for $5 per month, as well as a free 15-day trial, peace of mind is within reach with... Read more
Little Snitch 3.5.2 - Alerts you about o...
Little Snitch gives you control over your private outgoing data. Track background activity As soon as your computer connects to the Internet, applications often have permission to send any... Read more

Pie In The Sky: A Pizza Odyssey (Games)
Pie In The Sky: A Pizza Odyssey 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: A game about delivering pizza. In space. | Read more »
Chosen Gives Hopeful Singers, Songwriter...
If YouTube videos and reality TV shows like The Voice have taught us one thing, it’s that there are a lot of people out there who are anxious to show the world their talents. And if they’ve taught us a second thing, it’s that there’s an almost... | Read more »
Android's Popular OfficeSuite Now A...
Once only available for Android devices, OfficeSuite has finally landed on the app store. The Mobile Systems app lets you view, edit, create, and share Word, Excel, and PowerPoint documents as well as convert them to/from PDFs. It's touted as being... | Read more »
Warhammer: Arcane Magic is Coming Soon,...
Turbo Tape Games has announced that they're joining forces with Games Workshop to bring the turn-based strategy board game, Warhammer: Arcane Magic, to life on the iOS. | Read more »
Fast & Furious: Legacy's Creati...
| Read more »
N-Fusion and 505's Ember is Totally...
| Read more »
These are All the Apple Watch Apps and G...
The Apple Watch is less than a month from hitting store shelves, and once you get your hands on it you're probably going to want some apps and games to install. Fear not! We've compiled a list of all the Apple Watch apps and games we've been able to... | Read more »
Appy to Have Known You - Lee Hamlet Look...
Being at 148Apps these past 2 years has been an awesome experience that has taught me a great deal, and working with such a great team has been a privilege. Thank you to Rob Rich, and to both Rob LeFebvre and Jeff Scott before him, for helping me... | Read more »
Hands-On With Allstar Heroes - A Promisi...
Let’s get this out of the way quickly. Allstar Heroes looks a lot like a certain other recent action RPG release, but it turns out that while it’s not yet available here, Allstar Heroes has been around for much longer than that other title. Now that... | Read more »
Macho Man and Steve Austin Join the Rank...
WWE Immortals, by Warner Bros. Interactive Entertainment and WWE, has gotten a superstar update. You'll now have access to Macho Man Randy Savage and Steve Austin. Both characters have two different versions: Macho Man Randy Savage Renegade or Macho... | Read more »

Price Scanner via MacPrices.net

Apple offering refurbished 27-inch 5K iMacs f...
The Apple Store is offering Apple Certified Refurbished 27″ 3.5GHz 5K iMacs for $2119 including free shipping. Their price is $380 off the price of new models, and it’s the lowest price available for... Read more
16GB iPad mini on sale for $199, save $50
Walmart has 16GB iPad minis (1st generation) available for $199.99 on their online store, including free shipping. Their price is $50 off MSRP. Online orders only. Read more
New 128GB MacBook Airs on sale for $50 off MS...
 B&H Photo has 128GB 11″ and 13″ 2015 MacBook Airs on sale today for $50 off MSRP including free shipping plus NY sales tax only: - 11″ 1.6GHz/128GB MacBook Air (Model #MJVM2LL/A): $849 $50 off... Read more
13-inch 2.6GHz Retina MacBook Pro (refurbishe...
The Apple Store has Apple Certified Refurbished 13″ 2.6GHz/128GB Retina MacBook Pros available for $979 including free shipping. Original MSRP for this model was $1299. Read more
Save up to $600 with Apple refurbished Mac Pr...
The Apple Store is offering Apple Certified Refurbished Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Samsung Galaxy S 6 and Galaxy S 6 edge U.S. P...
Samsung Electronics America, Inc. has announced the Galaxy S 6 and Galaxy S 6 edge will be available in the U.S. beginning April 10, with pre-orders being accepted now. “We have completely reimagined... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
The Apple Store has Apple Certified Refurbished 13″ 2.5GHz MacBook Pros available for $829, or $270 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.... Read more
Save up to $80 on iPad Air 2s, NY tax only, f...
 B&H Photo has iPad Air 2s on sale for $80 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469.99 $30 off - 64GB iPad Air 2 WiFi: $549.99 $50 off - 128GB iPad... Read more
iMacs on sale for up to $205 off MSRP
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1019 $80 off - 21″ 2.7GHz iMac: $1189 $110 off - 21″ 2.9GHz... Read more
Färbe Technik Offers iPhone Battery Charge LI...
Färbe Technik, which manufactures and markets of mobile accessories for Apple, Blackberry and Samsung mobile devices, is offering tips on how to keep your iPhone charged while in the field: •... Read more

Jobs Board

DevOps Software Engineer - *Apple* Pay, iOS...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring 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
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Lead *Apple* Solutions Consultant - Retail...
**Job Summary** Job Summary The Lead ASC is an Apple employee who serves as the Apple business manager and influencer in a hyper-business critical Reseller's store Read more
*Apple* Pay - Site Reliability Engineer - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.