TweetFollow Us on Twitter

Aug 99 Challenge

Volume Number: 15 (1999)
Issue Number: 8
Column Tag: Programmer's Challenge

Aug 99 Prgrammer's Challenge

by Bob Boonstra, Westford, MA

3D FlyBy

Some of the people who have recently written to suggest possible Challenge problems have asked for Challenges that are more specific to the Macintosh. Well, not everyone is actually that subtle about it. One writer lamented "yet another plain-vanilla Challenge that could just as well have appeared in a Linux or Windows programming magazine". Ouch!! Since this column is based on demonstrating efficient performance, many of the problems naturally carry over to other platforms. But the writer has a point, and this month's Challenge will have more to do with the Mac OS.

Back in April, readers were asked to find a path through three-dimensional terrain that minimized elevation change. This month, you'll also be dealing with 3D terrain, but you'll be flying over it, and displaying a perspective view of that terrain. In the process, you'll have the opportunity to learn a little about QuickDraw3D.

The prototype for the code you should write is:

#include <QD3D.h>
#include <QD3DLight.h>
#include <QD3DCamera.h>
#include <Windows.h>
#if defined(__cplusplus)
extern "C" {
#endif
typedef struct MyTriangles {
	long pointIndices[3];
	TQ3ColorRGB triangleColor;
} MyTriangles;
void InitFlyBy(
	CWindowPtr theWindow,
	long numPoints,
	const TQ3Point3D thePoints[],
	long numTriangles,
	const MyTriangles theTriangles[],
	const TQ3ViewAngleAspectCameraData	perspectiveData,
		// perspectiveData.cameraData.range.hither	= 0.0;
		// perspectiveData.cameraData.range.yon 	= 1000.0
		// perspectiveData.cameraData.viewPort.origin.x = -1.0
		// perspectiveData.cameraData.viewPort.origin.y = 1.0
		// perspectiveData.cameraData.viewPort.width = 2.0
		// perspectiveData.cameraData.viewPort.height = 2.0
		// perspectiveData.fov				= 1.0
		// perspectiveData.aspectRatioXToY	=
		// 	    (float) (theWindow->portRect.right - theWindow->portRect.left) / 
		//     (float) (theWindow->portRect.bottom - theWindow->portRect.top)
	const TQ3ColorRGB backgroundColor
		// color of background
);
void GenerateView(
	TQ3CameraPlacement		viewPoint
);
void TermFlyBy(void);
#if defined(__cplusplus)
}
#endif

Your code consists of three routines: InitFlyBy. called once for each terrain map; GenerateView, called repeatedly with different view positions as you fly through the terrain; and TermFlyBy, called at the end of each flight.

InitFlyBy is given everything needed to describe the scene to be generated except the viewPoint. The terrain consists of numPoints terrain coordinates provided in thePoints. The terrain is divided into numTriangles triangles, provided in theTriangles, each of which is described by 3 pointIndices into thePoints array, plus a color for the triangle.

Each time GenerateView is called, the terrain should be displayed in theWindow from the viewPoint using the projection information provided in perspectiveData. The projection will be a perspective, as opposed to an orthographic, projection, described using the TQ3ViewAngleAspectCameraData structure. The range, viewPort, fov, and aspectRationXToY elements of that structure are guaranteed to be defined using the simplifying values shown in the prototype commentary above.

Triangles should be displayed in the triangleColor, and areas of the scene not included in theTriangles should be displayed in the backgroundColor.

To optimize your code, you can rely on the fact that the viewPoint cameraLocation provided on successive calls to GenerateView will not change very much, simulating an actual flight. Similarly, the viewPoint pointOfInterest that determines the viewing direction, and the viewPoint upVector that governs orientation will not change by large amounts. They will change as the simulated flying machine banks and turns to avoid terrain.

A more realistic FlyBy Challenge would include one or more light sources, an illumination model, and the projection of shadows. For simplicity, we'll omit those minor details. We'll also allow you to fly without worrying about intersecting the terrain ("crashing") - the test code won't do that.

TermFlyBy should deallocate any dynamically allocated memory. Remember, your solutions need to properly initialize and clean up after themselves so they can be executed repeatedly.

Information on QuickDraw3D data structures can be found at: http://developer.apple.com/techpubs/quicktime/qtdevdocs/QD3D/qd3d_book.htm

The winner will be the solution that accurately depicts multiple flights through terrain using the least amount of execution time. This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

Three Months Ago Winner

Congratulations to Ernst Munter (Kanata, Ontario) for submitting the winning solution to the May "Piper" Challenge. The Challenge, based on a TidBITS column by Rick Holzgrafe, was to map a string of characters into the smallest rectangle, placing adjacent characters in the string into adjacent positions (horizontally, vertically, or diagonally). The rules allowed (and encouraged) characters to be reused, so that a string like "How much wood would a woodchuck chuck if a woodchuck could chuck wood?" can be mapped into a compact 4x4 rectangle:

				hwhu
				oocm
				udwk
				lafi

Five people submitted entries to this Challenge, and I also evaluated a version of Rick Holzgrafe's code, modified to work with the API specified by the problem statement. Scoring was based on the area of the rectangle produced by the solution, with a 1% penalty added for each second of execution time. I evaluated the entries using 5 test cases with input strings ranging from 38 characters to 198 characters. Besides chucking wood, the entries had the opportunity to pick pickled peppers, sell sea shells by the sea shore, travel to St. Ives with the man with seven wives, and chow down on green eggs and ham with Dr. Seuss. One of the solutions, plus Rick's, outlasted my patience on the longer problems, but all of the solutions submitted (and Rick's) solved the short test cases correctly and compactly. Four solutions solved the "woodchuck" input more quickly than Rick's baseline solution, as shown in the following table:

Name Area Time (msec) Score
Ernst Munster 16 2377 16.38
Cathy Saxton 16 3621 16.58
Tom Saxton 16 4002 16.64
Sebastian Maurer 16 23551 19.77
Rick Holtzgrafe 16 145791 39.33
W. R. 16 162697 42.03

All of the entries submitted were recursive, except for the winning one. Ernst eliminated the natural recursion by placing possible moves and associated state information on the heap. Eliminating recursion probably improved the efficiency of Ernst's solutions, but his real advantage came from the fact that he generated very compact results, more compact than any other entry in three of five test cases. Ernst used two hueristics in deciding which possible move to explore first: the number of empty cells in the solution rectangle after the move, and a projection of the size of the final rectangle based on the number of unique characters yet to be placed in the box.

The next table lists, for each of the solutions submitted, the sum of the areas of the rectangles generated for all of the inputs, the total execution time, and the total score. 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 Area Time (msec) Score Code Size Data Size Lang
Ernst Munter 271 36673 298.87 6612 65632 C++
Sebastian Maurer 318 94546 390.35 5340 31 C
Tom Saxton 313 216511 515.45 5456 18177 C++
Cathy Saxton 425 216048 707.52 6148 186249 C++
W. R. n/a n/a n/a 3424 31 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 221
2. Saxton, Tom 106
3. Boring, Randy 73
4. Maurer, Sebastian 70
5. Rieken, Willeke 41
6. Heithcock, JG 37
7. Lewis, Peter 31
8. Nicolle, Ludovic 27
9. Brown, Pat 20
10. Hostetter, Mat 20
11. Mallett, Jeff 20
12. Murphy, ACC 14
13. Jones, Dennis 12
14. Hewett, Kevin 10
15. Selengut, Jared 10
16. Smith, Brad 10
17. Varilly, Patrick 10
18. Webb, Russ 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 Ernst Munter's winning Piper solution:

Piper.cpp
Copyright © 1999, Ernst Munter

/*
Problem Statement
---------
Pack the letters of a character string in the smallest possible
rectangle such that the string can be read by tracing the
characters in the box from field to adjacent field.
A penalty of 1% is added for each second of run time.
Solution Strategy
---------
Solutions are represented by the leaves of a search tree, where
each node stands for a character in the string, associated with
a particular field in the rectangle.  Each node can have up to
eight adjacent fields, and the tree grows very rapidly.
We are interested in the (or one of possibly several) trajectory
where all nodes are packed closely together, to result in the
smallest area.  Each field, with its character, can be visited
several times.
The objective then is to find the more promising trajectories
early, and cut off any search path as soon as it is clear that
it cannot lead to a better solution than the one already obtained.
In addition, the search must be cut off after a few seconds, or
the time penalty will outweigh any likely improvement in area.
Tactics
----
The search relies on two heuristics:
		at each step, all possible next moves are evaluated
		and then executed in order of the lowest "vacancy",
		that is the number of empty fields in the box after
		that move,
	-	the final size of the box at each depth is projected,
		bearing in mind the number of unique single characters
		and pairs in the remainder of the string.
The usual techniques are used to make the program as efficient
as possible, in order to execute as many moves as possible
before the timer cuts the search short.
Recursion Removal
---------
The problem by its nature suggests a recursive solution.
I chose to remove recursion by building a stack of nodes (States)
on the heap.  At each level, up to 8 child nodes ("moves" or
PartialStates) are created and stacked in the preferred order.
Then the node at the top of the stack is expanded into a full node
(with children etc), until either no more moves are possible, or
the last character of the string is reached (leaf node).
When backtracking, there will either be another move stacked on
the previous State, to be expanded; or all moves of the previous
State have been exhausted, and we step back to the previous State
from that; until the initial State is reached, at which point
all branches of the tree have been explored.
*/
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "Piper.h"
#include <lowmem.h>
typedef unsigned char 	U8;
typedef unsigned long 	U32;
typedef unsigned short	U16;
typedef unsigned short	Pair[32];
enum {
	kMaxDim		= 256,		// 256 by 256 grid
	kGridHeight	= kMaxDim,
	kGridWidth	= kMaxDim,
	kGridSize	= kGridHeight * kGridWidth,
	kBorderChar	= 0x1F,
	kWasBlank	= 0x20,
	kDefaultLoop= 0x100000,	// initial run, before timing of loops
	kTolerance	= 8			// accept up to 8 % running time penalty
};
struct Pnt
// A Point (Pnt) in the grid is represented by a short which
// can directly serve as index into the grid.
struct Pnt {
	U16	w;	// = y*256 + x
	Pnt(){}
	Pnt(U32 z):w(z){}
	Pnt(int xx,int yy) : w(xx + (yy<<8)) {}
	int X(){return w & 0xFF;}
	int Y(){return w >> 8;}
	U32 Linear(){return w;}
	void GoUp()  	{w -= 0x0100;}
	void GoDown()	{w += 0x0100;}
	void GoLeft()	{w -= 0x0001;}
	void GoRight()	{w += 0x0001;}
	void Shift(int dx,int dy){w += dx + dy*0x100;}
};
struct Rct
// A Rect (Rct) is the concatenation of two points into a long
struct Rct {
	U32 w;	// = ((top*256 + left)*256 + bottom)*256 + right
	Rct(){}
	Rct(U32 ww){w=ww;}
	Rct(Pnt & TL,Pnt & BR){w = (TL.Linear()<<16) | BR.Linear();}
	int Size()	{return Height() * Width();}
	int Top()	{return  w>>24;}
	int Left()	{return (w>>16) & 0xFF;}
	int Bottom(){return (w>>8) & 0xFF;}
	int Right()	{return  w & 0xFF;}
	int Height(){return Bottom()-Top();}
	int Width()	{return Right()-Left();}
	void ExpandTop()	{w -= (1<<24);}
	void ExpandLeft()	{w -= (1<<16);}
	void ExpandBottom()	{w += (1<<8);}
	void ExpandRight()	{w +=  1;}
};
struct Grid
// Grid is a 256 by 256 grid of characters.
// This box can hold any string up to almost 64K length, and many
// that are longer, but run time would be intolerably long anyway.
// The top, left and bottom margins are set to a border char;
// this confines the string to the box, without wrap or range checks.
static struct Grid {
 	char	g[kGridSize];
 	Grid()
 	{
 		char* gp=g;
 		memset(gp,kBorderChar,kGridWidth);
 		for (int i=1;i < kGridWidth-1;i++)
 		{
 			gp += kGridWidth;
 			memset(gp,0,kGridWidth);
 			*gp=kBorderChar;
 		}
 		memset(gp+kGridWidth,kBorderChar,kGridWidth);
 	}
 	void	Set(/*const*/ Pnt & p,const char c){g[p.Linear()]=c;}
 	int		Value(/*const*/ Pnt & p){return g[p.Linear()];}
 	Pnt &	Center(){return Pnt(kGridWidth/2,kGridWidth/2);}
}
// The grid is declared static and global.
grid;
struct PreProcess
// The PreProcess analyzes the string statically to determine for each
// string position the number of remaining unique characters, and
// the number of remaining unique pairs.  This is then summarized
// as a "tail" figure for each string index, indicating the number
// of fields (at least) that will be required for characters beyond
// the current index position.
struct PreProcess {
	U16*	indexMap;
	U16*	tail;
	char*	str;
	int		oldLen;
	int		netLen;
	PreProcess(char* s)
// All characters are reduced to the range 1 to 26, and non-alpha
// characters are removed from the string s.
// As characters are removed, an index map is created to relate
// the new character indices back to their original positions.
	{
		oldLen=strlen(s);
		indexMap=new U16[oldLen];
		str=s;
		U16* imp=indexMap;
		char* strp=str;
		for (int i=0;i<oldLen;i++)
		{
			U32 c=*s++;
			if (isalpha(c))
			{
				*imp++ = i;
				*strp++ = c & 0x1F;
			}
		}
		netLen=strp-str;
		*strp=0;
		tail=new U16[netLen];
	}
	~PreProcess()
	{
		delete [] tail;
		delete [] indexMap;
	}
	void TrivialSolution(GridPoint pt[])
// If the string is less than 4 characters long, a box of
// height 1 is optimal.
	{
		for (int i=0;i<netLen;i++)
		{
			int j=indexMap[i];
			if ((i==2) && (str[0]==str[2])) pt[j].x=0;
			else pt[j].x=i;
			pt[j].y=0;
		}
	}
	void ComputeProfile()
// Computes the tail array, just once for a given string.
	{
  		U32 cmap=0,R=0;
  		U32 link[32];
  		memset(link,0,sizeof(link));
  		int numLink[32];
  		memset(numLink,0,sizeof(numLink));
  		char* s=str;
  		int len=netLen;
  		U32 a=s[0];
  		for (int i=0;i<len;i++)
  		{
			U32 bit=1 << s[i];
 			if (0 == (cmap & bit)) {R++; cmap |= bit;}
			if (i)
			{
				int b=s[i];
				U32 bbit=1 << s[b];
				if (0 == (link[a] & bbit))
				{
					numLink[a]++;	link[a] |= bbit;
				}
				U32 abit=1 << s[a];
				if (0 == (link[b] & abit))
				{
					numLink[b]++;	link[b] |= abit;
				}
				a=b;
			}
  		}
		Pair* pair=new Pair[netLen];
  		a=s[0];
  		for (int i=0;i<len;i++)
  		{
			U32 bit=1 << s[i];
			if (cmap & bit) { R-; cmap &= ~bit;}
			tail[i]=R;
			for (int z=1;z<26;z++) pair[i][z]=numLink[z];
			if (i>0)
			{
				U32 b=s[i];
				U32 bbit=1 << s[b];
				if (link[a] & bbit)
				{
					numLink[a]-;	link[a] &= ~bbit;
				}
				pair[i][a]=numLink[a];
				U32 abit=1 << s[a];
				if (link[b] & abit)
				{
					numLink[b]-;	link[b] &= ~abit;
				}
				pair[i][b]=numLink[b];
				a=b;
			}
  		}
  		for (int i=0;i<len;i++)
     		for (a=1;a<26;a++)
				tail[i]+=(pair[i][a])/8;
		delete [] pair;
	}
	int Len(){return netLen;}
	int Index(int i){return indexMap[i];}
	char* String(){return str;}
};
struct PartialState
// The PartialState represents a child node, or a "move" forward.
// It records the bounding box , the position in the grid, and
// miscellaneous items in preparation for the move.
struct PartialState {
	Rct	corners;	// 	of rectangle in grid
	Pnt		gridPos;	// 	x-y pos of last char placed in grid
	U16		misc;		//10+1+5 bits=vacancy+wasBlank+gridChar
	void Init(
		const Rct cs,
		const Pnt gp,
		const U32 ms)
	{
		corners=cs;
		gridPos=gp;
		misc=ms;
	}
	U32 Size(){return corners.Size();}
	U32 GridChar(){return misc & 0x1F;}
	U32 WasBlank(){return misc & 0x20;}
	U32 Vacancy() {return misc >> 6;}
	void SetGrid(){grid.Set(gridPos,GridChar());}
	void ClearGrid(){grid.Set(gridPos,0);}
};
struct State:PartialState
// The State struct expands the PartialState to include a pointer
// back up the tree (previous State) and the list of children.
struct State:PartialState {
	State*			prevState;
	int				numMoves;
	PartialState	move[8];//	up to 8 possible next states
	void Init(const char* s)
	{
		prevState=0;
		numMoves=0;
		Pnt corner0=grid.Center();
		Pnt corner1=corner0;
		corner1.GoDown();corner1.GoRight();
// first character, center of grid, 0 vacancy
		PartialState::Init(Rct(corner0,corner1),corner0,*s);
		SetGrid();
	}
	State* BackTrack()
// Backtrack to immediate parent.
	{
		if (WasBlank()) ClearGrid();
		return prevState;
	}
	State* BackTrack(int & index)
// Backtrack to the first parent that has any moves left.
	{
		State* S=this;
		do
		{
			index-;
			if (S->WasBlank()) S->ClearGrid();
			S=S->prevState;
		} while (S && (0 == S->numMoves));
		return S;
	}
	State* PlaceNextChar()
// typecasts the highest numbered move (partial state) to full state
//		and places the character in the grid
	{
		if (numMoves)
		{
			State* S = (State*)(&move[-numMoves]);
			S->prevState=this;
			S->numMoves=0;
			S->SetGrid();
			return S;
		}
		return 0;
	}
	State* Add5Moves(int bestSize,int tail,char ch)
// Used only at step two, i.e. for the third letter in the string
// For the third letter, 3 moves can be eliminated because of symmetry
	{
		Add1Move(bestSize,tail,ch,0,1);
		Add1Move(bestSize,tail,ch,1,1);
		Add1Move(bestSize,tail,ch,1,0);
		Add1Move(bestSize,tail,ch,-1,-1);
		Add1Move(bestSize,tail,ch,-1,0);
	return this;
	}
// Some code sequences as macros for clarity and to save listing space
#define OVERLAY														\
	{	int spill=tail-oldVacancy;							\
		U32 newSize=oldSize;									\
		if (spill>0) newSize+=spill;						\
		if (newSize < bestSize)								\
		{																		\
			move[numMoves++].Init(corners,newPos,	\
			(oldVacancy << 6) /* | 0 */ | ch);				\
			}																\
	}
#define CHECK_LEFT												\
	if (newPos.X() <  corners.Left()) 				\
	{																			\
		newCorners.ExpandLeft();								\
		vacancy+=newCorners.Height();					\
		newSize+=newCorners.Height();					\
	}
#define CHECK_RIGHT												\
	if (newPos.X() >=  corners.Right())	 			\
	{																			\
		newCorners.ExpandRight();							\
		vacancy+=newCorners.Height();					\
		newSize+=newCorners.Height();					\
	}
#define CHECK_TOP													\
	if (newPos.Y() < corners.Top()) 					\
	{																			\
		newCorners.ExpandTop();								\
		vacancy+=newCorners.Width();						\
		newSize+=newCorners.Width();						\
	}
#define CHECK_BOTTOM											\
	if (newPos.Y() >= corners.Bottom()) 			\
	{																			\
		newCorners.ExpandBottom();							\
		vacancy+=newCorners.Width();						\
		newSize+=newCorners.Width();						\
	}
#define FINISH														\
	{	int spill=tail-vacancy;								\
		if (spill>0) newSize+=spill; 					\
	    if (newSize < bestSize) 							\
	    {																	\
		move[numMoves++].Init(newCorners,newPos,	\
		(vacancy << 6) | kWasBlank | ch);			\
		}																		\
	}
	void Add1Move(int bestSize,int tail,char ch,int dx,int dy)
// Adds a single move.
	{
		U32 oldSize=corners.Size();
		U32 oldVacancy=Vacancy();
		Pnt newPos=gridPos;
		newPos.Shift(dx,dy);
		U32 oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_LEFT else CHECK_RIGHT
			CHECK_TOP else CHECK_BOTTOM
			FINISH
		}
	}
	void Add8Moves_non_optimized(int bestSize,int tail,char ch)
// Adds all 8 possible moves.
// This function is replaced by the optimized version, below.
	{
		Add1Move(bestSize,tail,ch,0,1);
		Add1Move(bestSize,tail,ch,1,1);
		Add1Move(bestSize,tail,ch,1,0);
		Add1Move(bestSize,tail,ch,1,-1);
		Add1Move(bestSize,tail,ch,0,-1);
		Add1Move(bestSize,tail,ch,-1,-1);
		Add1Move(bestSize,tail,ch,-1,0);
		Add1Move(bestSize,tail,ch,-1,1);
	}
	void Add8Moves(int bestSize,int tail,char ch)
// Same functionality as Add8Moves_non_optimized, but inlined
//		and avoiding unnecessary box-corner tests: 35% faster
	{
		Pnt newPos=gridPos;
		U32 oldSize=corners.Size();
		U32 oldVacancy=Vacancy();
// move down
		newPos.GoDown();
		U32 oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_BOTTOM
			FINISH
		}
// move down and right
		newPos.GoRight();
		oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_BOTTOM
			CHECK_RIGHT
			FINISH
		}
// move right
		newPos.GoUp();
		oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_RIGHT
			FINISH
		}
// move up and right
		newPos.GoUp();
		oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_TOP
			CHECK_RIGHT
			FINISH
		}
// move up
		newPos.GoLeft();
		oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_TOP
			FINISH
		}
// move up and left
		newPos.GoLeft();
		oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_TOP
			CHECK_LEFT
			FINISH
		}
// move left
		newPos.GoDown();
		oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_LEFT
			FINISH
		}
// move down and left
		newPos.GoDown();
		oldC=grid.Value(newPos);
		if (oldC == ch) OVERLAY
		else if (oldC==0)
		{
			Rct newCorners=corners;
			U32 newSize=oldSize;
			U32 vacancy=oldVacancy-1;
			CHECK_BOTTOM
			CHECK_LEFT
			FINISH
		}
	}
	void SortMoves()
// Sorts by vacancy: lower vacancy moves go first (from top of stack)
	{
		for (int i=1;i<numMoves;i++)
		for (int j=0;j<i;j++)
			if (move[j].misc > move[i].misc)
			{
				double t=*((double*)(move+i));
				*((double*)(move+i))=*((double*)(move+j));
				*((double*)(move+j))=t;
			}
	}
	void CopyPoint(const int i,GridPoint pt[])
// Copies a single point to the result,
// mapping my grid's center to the result grids origin (0,0)
	{
		pt[i].x=gridPos.X()-kGridWidth/2;
		pt[i].y=gridPos.Y()-kGridHeight/2;
	}
	void CopySolution(const int len,
				/*const*/ PreProcess & pp,GridPoint pt[])
// Copies my grid point sequence to the result grid point array
// using the index mapping setup by the PreProcess object.
	{
		State* S=this;
		for (int k=len-1;k>=0;k-)
		{
			int i=pp.Index(k);
			S->CopyPoint(i,pt);
			S=S->prevState;
			if (S==0) break;	// safety catch
		}
	}
};
struct Solver
// The Solver object is the main actor to execute the tree search.
struct Solver {
	State*	states;
	int		stringLen;
	int		bestSize;
	Solver(PreProcess & pp) :
		states(new State[pp.netLen]),
		stringLen(pp.netLen),
		bestSize(pp.netLen+1)
// The constructor places the first character in the grid and
// computes the first move-list, containing only two moves
// (no need for the other possible 6 moves because of symmetry).
// Unfortunately, if one starts with the wrong one (of the two)
// one may not find the optimum solution box as quickly, but
// I have not been able to find a heuristic to make a good choice.
	{
		states[0].Init(pp.str);
		states[0].Add1Move(bestSize,pp.tail[1],pp.str[1],1,0);
		states[0].Add1Move(bestSize,pp.tail[1],pp.str[1],1,1);
	}
	~Solver(){delete [] states;}
	void GenerateSolution(const PreProcess & pp,GridPoint pt[]);
};
struct LoopTimer
// The loop timer uses LMGetTicks() to obtain an estimate of
// the average loop time, and then sets up the loop to run for
// one second at a time, until the elapsed time exceeds the
// time allowance, set by a constant (kTolerance).
struct LoopTimer {
	int loopCheck;
	int T0;
	int	elapsed;
	int	timeAllowance;
	LoopTimer() :
		loopCheck(kDefaultLoop),
		T0(LMGetTicks()),
		elapsed(0),
		timeAllowance(kTolerance*60) {}
	int AdjustLoop()
	{
		int t=LMGetTicks();
		int period=t-T0;
		T0=t;
		elapsed+=period;
		if (elapsed>timeAllowance) return 0;
		loopCheck=loopCheck*60/period;
		return loopCheck;
	}
};
Solver::GenerateSolution
void Solver::GenerateSolution(const PreProcess & 				pp,GridPoint pt[])
// The tree search function.
// Explores the solution tree until time runs out, or until
// all branches have been exhausted.
{
	int index=0;		// string index for the current state
	State* S=&states[0];
	int loopCounter=kDefaultLoop;
	LoopTimer loopTimer;
	do
	{
		if (-loopCounter == 0)
		{
			loopCounter=loopTimer.AdjustLoop();
			if (loopCounter==0)
			{
				while (S) S=S->BackTrack();
				break;// give up after kTolerance secs
			}
		}
		if (index>=stringLen-1) // have reached the end of the string
		{														// we get here only if size is better
			bestSize=S->Size();
			S->CopySolution(stringLen,
				/*added*/(PreProcess)/*end add*/pp,pt);
			S=S->BackTrack(index);
		}
		else
		{
			State* nextS=S->PlaceNextChar();
			if (nextS)
			{
				index++;
				S=nextS;
				if (index==1) // i.e. to place the 3rd character
	S->Add5Moves(bestSize,pp.tail[index+1],pp.str[index+1]);
				else
	S->Add8Moves(bestSize,pp.tail[index+1],pp.str[index+1]);
				S->SortMoves();
			}
			else S=S->BackTrack(index);// out of moves
		}
	} while (S);
}
Piper
void Piper(char *s,GridPoint pt[])
// External function published in the header file "Piper.h"
{
	PreProcess pp(s);
	if (pp.Len() <= 3) pp.TrivialSolution(pt);
	else
	{
		pp.ComputeProfile();
		Solver solve(pp);
		solve.GenerateSolution(pp,pt);
	}
}
 
AAPL
$119.00
Apple Inc.
+1.40
MSFT
$47.75
Microsoft Corpora
+0.28
GOOG
$540.37
Google Inc.
-0.71

MacTech Search:
Community Search:

Software Updates via MacUpdate

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
Carbon Copy Cloner 4.0.3 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
ForeverSave 2.1.3 - Universal auto-save...
ForeverSave auto-saves all documents you're working on while simultaneously doing backup versioning in the background. Lost data can be quickly restored at any time. Losing data, caused by... Read more

Latest Forum Discussions

See All

Make Way for Fat Chicken, from the Maker...
Make Way for Fat Chicken, from the Makers of Scrap Squad Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Relevant Games has announced they will be releasing their reverse tower defense game, | Read more »
Tripnary Review
Tripnary Review By Jennifer Allen on November 26th, 2014 Our Rating: :: TRAVEL BUCKET LISTiPhone App - Designed for the iPhone, compatible with the iPad Want to create a travel bucket list? Tripnary is a fun way to do exactly that... | Read more »
Ossian Studios’ RPG, The Shadow Sun, is...
Ossian Studios’ RPG, The Shadow Sun, is Now Available for $4.99 Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Mmmm, Tasty – Having the Angry Birds for...
The very first Angry Birds debuted on iOS back in 2009. When you sit back and tally up the number of Angry Birds games out there and the impact they’ve had on pop culture as a whole, you just need to ask yourself: “How would the birds taste... | Read more »
Rescue Quest Review
Rescue Quest Review By Jennifer Allen on November 26th, 2014 Our Rating: :: PATH BASED MATCH-3Universal App - Designed for iPhone and iPad Guide a wizard to safety by matching gems. Rescue Quest might not be an entirely original... | Read more »
You Can Play the Final Chapter of Lone W...
You Can Play the Final Chapter of Lone Wolf: Dawn Over V’taag Right Now Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Swords of Anima (Games)
Swords of Anima 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: A new tactical turn-based RPG experience. Command the Savior Rex Squad in an epic journey of courage and deception. Can you... | Read more »
Audio Defence: Zombie Arena
Audio Defence: Zombie Arena By Lee Hamlet on November 26th, 2014 Our Rating: :: DRAGS ITS FEETUniversal App - Designed for iPhone and iPad From the makers of Papa Sangre comes a defense game that forces players to listen carefully... | Read more »
Tales from the Borderland​s Will be Comi...
Tales from the Borderland​s Will be Coming to iOS by the End of the Year Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Telltale Games has announced | Read more »
Sunburn! Review
Sunburn! Review By Campbell Bird on November 26th, 2014 Our Rating: :: DON'T DIE ALONEUniversal App - Designed for iPhone and iPad Platform through the depths of space to make sure your entire crew dies together in this satisfying... | Read more »

Price Scanner via MacPrices.net

2014 1.4GHz Mac mini on sale for $449, save $...
 B&H Photo has the new 1.4GHz Mac mini on sale for $449.99 including free shipping plus NY tax only. Their price is $50 off MSRP, and it’s the lowest price available for this new model. Adorama... Read more
Early Black Friday pricing on 27-inch 5K iMac...
 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
Early Black Friday sale prices on iPad Air 2,...
 MacMall is discounting iPad Air 2s by up to $75 off MSRP as part of their Black Friday sale. Shipping is free: - 16GB iPad Air WiFi: $459 $40 off - 64GB iPad Air WiFi: $559 $40 off - 128GB iPad Air... Read more
Early Black Friday MacBook Air sale prices, $...
 MacMall has posted early Black Friday MacBook Air sale prices. Save $101 on all models for a limited time: - 11″ 1.4GHz/128GB MacBook Air: $798 - 11″ 1.4GHz/256GB MacBook Air: $998 - 13″ 1.4GHz/... Read more
Why iPhone 6 Tablet/Laptop Cannibalization Is...
247wallst.com blogger Douglas A. McIntyre noted last week that according to research posted on the Applovin blog site the iPhone 6 is outselling the iPhone 6 Plus by a wide margin . Hardly a surprise... Read more
Worldwide Tablet Growth Expected to Slow to 7...
The global tablet market is expected to record massive deceleration in 2014 with year-over-year growth slowing to 7.2%, down from 52.5% in 2013, according to a new forecast from International Data... Read more
Touchscreen Glove Company Announces New Produ...
Surrey, United Kingdom based TouchAbility specializes in design and manufacture of a wide variety of products compatible with touchscreen devices including smartphones, tablets and computers. Their... Read more
OtterBox Alpha Glass Screen Protectors for iP...
To complement the bigger, sharper displays on the latest Apple devices, OtterBox has introduced Alpha Glass screen protectors to the iPhone 6 and iPhone 6 Plus. The fortified glass screen protectors... Read more
Early Black Friday Mac Pro sale, 6-Core 3.5GH...
 B&H Photo has the 6-Core 3.5GHz Mac Pro on sale today for $3499 including free shipping plus NY sales tax. Their price is $500 off MSRP, and it’s the lowest price available for this model from... Read more
Early Black Friday sale price: 15-inch 2.2GHz...
 B&H Photo has the 2014 15″ 2.2GHz Retina MacBook Pro on sale today for $1699.99. Shipping is free, and B&H charges NY sales tax only. Their price is $300 off MSRP, equalling Best Buy’s price... 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.