TweetFollow Us on Twitter

Mar 97 Challenge

Volume Number: 13 (1997)
Issue Number: 3
Column Tag: Programmer's Challenge

Programmer's Challenge

By Bob Boonstra, Westford, MA

Hex

This month features another round-robin tournament competition, this time with the game of Hex. You might have encountered Hex through one of Marvin Gardner's columns in Scientific American. The game is played on an NxN rhombus of hexagons, with one player attempting to occupy an unbroken chain of hexagons connecting the top and the bottom, and the other player the left with the right. Players alternate occupying hexagons, and the first to complete an unbroken chain is the winner. The prototype for the code you should write is:

Boolean /*legalMove*/ Hex (
 long boardSize, /* number of rows/columns in the game board */
 long oppRow,    /* row where opponent last moved, 0 .. boardSize-1 */
 long oppCol,    /* column where opponent last moved, 0 .. boardSize-1 */
 long *moveRow,  /* return your move - row, 0 .. boardSize-1 */
 long *moveCol,  /* return your move - column, 0 .. boardSize-1 */
 void *privStorage,/* preallocated storage for your use */
 Boolean newGame,/* TRUE if this is your first move in a new game */
 Boolean playFirst /* TRUE if you play first (vertically) */
);

For your first move, Hex will be called with newGame set to TRUE. The size of the board, a number between 8 and 64, inclusive, will be provided in boardSize. If playFirst is TRUE, your objective is to form a vertical connection across the rows of the board, and you make the first move. Otherwise you are playing second and the objective is to form a horizontal connection across the columns. Your code and the code of an opponent will alternate play. Your opponent's move will be provided in (oppRow, oppCol), which will be set to (-1, -1) if you are moving first. When your code is called, you should evaulate your opponents move, calculate your own move, and store it in (*moveRow, *moveCol). If for any reason you believe your opponent has moved into an occupied hexagon, Hex should return a legalMove value of FALSE, otherwise it should return TRUE.

A key to winning at Hex is to form "2-bridges" of hexagons that can be connected regardless of what move your opponent makes. For example, examine this 9x9 board, with the horizontal ("H") player to move:

   0 1 2 3 4 5 6 7 8
 0  . . . . . . . . .
  1  . . . . . . . V .
   2  . . V . . . . V .
    3  . . . V . . . . .
     4  . . . . . . V . .
      5  . . V H H H V . .
       6  . . . . . . H . .
        7  . H . V . H . . .
         8  . H . . . . . . .

In this example, V can force a win. H can block one of the (row,col) positions (6,2) or (6,5), but not both. If, for example, H occupies (6,2), then V can occupy (6,5), with a guaranteed "2-bridge" connection to (7,3) via (6,4) or (7,4). A similar bridge exists if H occupies (6,5). V is therefore unstoppable from this position.

For some additional strategy, see <http://www.daimi.aau.dk/~tusk/pbmserv/hex/hex.faq.html>, or <http://www.cs.cmu.edu/People/hde/hex/hexfaq>. There is a "proof" that the first player can always win, but the proof is a nonconstructive proof by counterexample that does not divulge the winning strategy.

Your code will be provided with 1MB of preallocated storage pointed to by privStorage. This storage will be preinitialized to zero before your first move and will persist between moves. You should not allocate any additional dynamic storage beyond that provided by privStorage. Small amounts of static storage are permitted.

The Challenge will be scored by a tournament where each entry plays against each other entry twice for each of a number of board sizes, once playing first and once playing second. Another fair tournament schedule might be used if a large number of entries are received. For each game, the winner will earn game points for the victory, minus an amount based on the execution time used to compute the moves, as follows:

game points = 10 - (execution time in seconds)/boardSize

The loser will earn zero points and will not be penalized for the execution time expended in defeat. The player with the most total points for all games in the tournament will be the winner.

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

The December Tangram Challenge was a difficult one, so difficult that no entries were submitted by the Challenge deadline. Three people (Alan Hart, Ernst Munter, and George Warner) responded with entries after I notified the Programmer's Challenge mailing list of a one-week extension, but none of those entries passed my test cases. As a result, there is no winner for the Challenge this month.

The problem was to reassemble a two-dimensional shape that has been cut into a number of smaller shapes. Each piece was to be transformed to its correct position by optionally flipping it about a vertical axis, rotating it, and translating it, in that order. A simple tangram can be created by curring a square into five right triangles of three different sizes, a smaller square, and a rhomboid. The problem statement also allowed for zero or more holes in the assembled shape, a fact which complicated the problem significantly. The submitted solutions all had problems with shapes that did not include holes, and I was unable to select one as being more correct than the rest. I have awarded 4 contest points to each of the entrants for their efforts, and selected one of them for publication.

Dave Bayer wrote to point out that the Tangram Challenge is theoretically as well as practically difficult, in that it is one of a class of problems called "NP-hard". The conjecture is that these problems cannot be solved in time that is a polynomial function of the problem size, and the problems in this class are equivalent in the sense that a polynomial time solution for one of them would provide a solution for the others. The best known problem in this class is the traveling salesperson problem.

To demonstrate that the Tangram Challenge is NP-hard, Dave transforms another NP-hard problem, the Partition Problem, into a tangram. The partition problem is to determine, given a sequence of integers i1, i2, ik, whether there exists a subset whose sum is exactly half of the sum of the entire sequence. For example, given the sequence 4,4,5,7,9,11,14,14,14,18, which sums to 100, the Partition Problem would be to find a subset (e.g., 4,7,11,14,14) that sums to 50. Dave converts the sequence into a tangram with one hole by constructing pieces of a rod whose length is a number from the Partition Problem sequence, marking one half the length of the rod with a hole in the tangram. The tangram would be constructed with 3xN pieces, where N is in the sequence. Using the shorter sequence 1,2,3 to illustrate this, the tangram would be as follows:

XXX  XXXXXX  XXXXXXXXX                   XXXXXXXXXXXXXXXXXXX
XXX  XXXXXX  XXXXXXXXX                   XXXXXXXXX XXXXXXXXX
XXX  XXXXXX  XXXXXXXXX                   XXXXXXXXXXXXXXXXXXX

1       2       3       assembled into       1  +  2  =  3


This construction shows that a solution to the Partition Problem would solve this tangram puzzle, and conversely, which demonstrates that the tangram problem is NP-hard. Readers interested in complexity theory can refer to Computers and Intractability, a Guide to the Theory of NP-Completeness, by Garey and Johnson, or to Introduction to Automata Theory, Languages, and Computation, by Hopcroft and Ullman. Thanks to Dave Bayer for these insights, and also for suggesting this month's Hex Challenge.

TOP 20 CONTESTANTS

Here are the Top Contestants for the Programmer's Challenge. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points Rank Name Points

1. Munter, Ernst 189 11. Cutts, Kevin 21

2. Gregg, Xan 114 12. Nicolle, Ludovic 21

3. Larsson, Gustav 87 13. Picao, Miguel Cruz 21

4. Lengyel, Eric 40 14. Brown, Jorg 20

5. Lewis, Peter 32 15. Gundrum, Eric 20

6. Boring, Randy 27 16. Studer, Thomas 20

7. Cooper, Greg 27 17. Karsh, Bill 19

8. Antoniewicz, Andy 24 18. Mallett, Jeff 17

9. Beith, Gary 24 19. Nevard, John 17

10. Kasparian, Raffi 22 20. Hart, Alan 14

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   5th place             2 points
2nd place  10 points   finding bug           2 points
3rd place   7 points   suggesting Challenge  2 points
4th place   4 points

Here is Alan Hart's solution:

Tangrams.cp

© 1996 Alan Hart

/*
NOTES

1.Translate all the Polygons into relative vector sequences
    to do the manipulations and tests.
    Once we have a solution, convert the final positions back into
    transformations for return to the caller.
    
2.Holes are almost the same as pieces. Exceptions:
    - We don't need to return their transformations - They probably can't be flipped,
    - They probably can't lie along the edges of the shape.

3.The process will be recursive trial and error:

    Where pieces are used, Holes can also be included in the process,
    taking into account that they can't be flipped or deployed at the edge of the shape.

    - Put the first vertex of the first piece at the first vertex of the shape.
    - Align the first side of the piece with the first side of the shape.
    - If the piece is not entirely inside the shape, try the piece's next vertex.
    - If the piece is inside the shape modify the shape to remove the piece
    and recurse to try to place the remaining pieces.
    - If the pieces are placed successfully, return
    - When all vertices of the piece have been tried unsuccesfully, flip it and repeat
    - When both flips of the piece have been tried,
    move it to the next vertex of the shape and repeat
    - When all vertices of the shape have been tried, flip the shape and repeat

4.We need a slick procedure for testing whether one polygon lies entirely inside another. */

#include "Tangrams.h"

void SolveTangram(
 MyPolygon*theShape,
 long   numHoles,
 MyPolygon*theHoles[],
 long   numPieces,
 MyPolygon*thePieces[],
 MyTransform*theXForms[]
)

{
/* Initialise the Tangram instance      */
 TTangram theTShape;
 theTShape.ITangram (theShape,
 numHoles, theHoles,
 numPieces, thePieces,
 theXForms);
 
/* Fill The Shape     */
 theTShape.solve();

 return;
}

TTangram.cp

/* Class TTangram methods   */

#include "Tangrams.h"
#include "Debug.h"

TTangram::TTangram ()
{
 xForms = 0;
}

TTangram::TTangram (TTangram& aShape)
{
 unplaced = aShape.unplaced;
 placed = aShape.placed;
 xForms = aShape.xForms;
}

void  TTangram::ITangram (MyPolygon *theShape,
 long numHoles, MyPolygon *theHoles[],
 long numPieces, MyPolygon *thePieces[],
 MyTransform*theXForms[])
{
 long i;
 TPiece *aPiece;
 TShape *aHole;
 
 IPolygon (theShape);
 
 for (i = 0; i < numPieces; i++)
 {
 aPiece = new TPiece;
 if (aPiece)
 {
 aPiece->IPiece (thePieces, i);
 unplaced.insert (aPiece);
 }
 else
 MyError("\pCan't make a Piece");
 }

 for (i = 0; i < numHoles; i++)
 {
 aHole = new TShape;
 if (aHole)
 {
 aHole->IShape (theHoles[i]);
 unplaced.insert (aHole);
 }
 else
 MyError("\pCan't make a Hole");
 }
 
 xForms = theXForms;
}

void  TTangram::solve (void)
{
 fill (&unplaced, &placed);
 
/* Get the transform for each piece */
 TShape *aPiece = (TShape *)placed.first();
 while (aPiece)
 {



    /*   Leave out the Holes */
 if (aPiece->canFlip())
  aPiece->getTransform (xForms);
 aPiece = (TShape *)placed.next(aPiece);
 }
}

TPolygon.cp

/* TPolygon Class methods */

#include "Tangrams.h"
#include "Debug.h"

#include <QuickDraw.h>

TPolygon::TPolygon () {;}

TPolygon::TPolygon (TPolygon& p)
{
 *(TVector *)this = p;
 sides.IList(p.sides);
}


void TPolygon::IPolygon (TPolygon *p)
{
 *(TVector *)this = *p;
 sides.IList(p->sides);
}

void TPolygon::IPolygon (MyPolygon *theData)
{
/* Create a TPolygon using cartesian input data */
 long i;
 TVector*aSide, previousSide;
 
/* The origin defines the vector position
    of the first vertex      relative to the origin and the h=0 axis */
 setHV (theData->vertex[0].h, theData->vertex[0].v);
 for (i = 0; i < theData->numVertices ; i++)
 {
 aSide = new TVector;
 if (!aSide)
 MyError("\pIPolygon: Failed to create a new side vector");
   sides.insert (aSide);
    /*   Convert each vertex to a vector from the previous vertex */
   if (i == theData->numVertices -1)
           /*   The last vector is relative to the origin      */
 aSide->setHV (theData->vertex[0].h 
 - theData->vertex[i].h,
   theData->vertex[0].v - theData->vertex[i].v);
   else
 aSide->setHV (theData->vertex[i+1].h 
 - theData- >vertex[i].h,
   theData->vertex[i+1].v - theData->vertex[i].v);
 }
}

/* Access */
TVector TPolygon::getOrigin (void)
{
 return *this;
}

TVector* TPolygon::firstSide (void)
{
 return sides.first();
}

TVector* TPolygon::nextSide (TVector *aSide)
{
 TVector *v = sides.next(aSide);
 if (v)
 return v;
 else
 return sides.first();
}

TVector* TPolygon::lastSide (void)
{
 return sides.last();
}

float TPolygon::getRotation (void)
{
 return sides.first()->getAngle();
}

void  TPolygon::rotate (float anAngle)
{
 TVector*theSide, *firstSide;


 firstSide = sides.first();
 if (firstSide)
 { 
 theSide = firstSide;
 do {
 theSide->rotate(anAngle);
 theSide = sides.next(theSide);;
 } while (theSide);
 }
}
 
void  TPolygon::translateTo (TVector *where)
{
 if (where)
 {
 *(TVector *)this = *where;
 }
 else
 set(0,1);
}
 
void  TPolygon::rotateTo (float direction)
{
 rotate (direction - getRotation());
}
 
Boolean TPolygon::fill (TList *unplaced, TList *placed)
{
 Booleanresult = false;
 TShape *thePiece, *previousPiece = 0;
 TPolygon *newSpace;

 thePiece = (TShape *)unplaced->first();
 if (thePiece)
 {
 do { /*   Try all unplaced pieces */
 
    /*   Transfer the current piece to the placed list */
 unplaced->remove (thePiece);
 placed->insert(thePiece);
 
    /*   Align thePiece with the first side of the Shape */
 align(thePiece);
 do { /*   Try each flip state */
 do { /*   Try all orientations */
 if (this->contains (thePiece))
 {
    /*   Copy the Shape */
 newSpace = new TPolygon (*this);
    /*   Modify the copy to remove the area of thePiece. */
 newSpace->subtract (thePiece);
    /*   Try to place remaining pieces in this shape. */
 result = newSpace->fill (unplaced, placed);
 
    /*   Discard the modified shape. */
 delete newSpace;
 
 if (result) return true;
 }
 } while (thePiece->turn());
 } while (thePiece->flip());
 
    /*   Move the current piece back to the unplaced list*/
 placed->remove (thePiece);
 unplaced->insert (thePiece, previousPiece);
 
    /*   Next unplaced piece */
 previousPiece = thePiece;
 thePiece = (TShape *)unplaced->next (thePiece);
 } while (!result && thePiece);
 }
 else
    /*   No pieces left to place - job done */
 result = true;
 return result;
}



void TPolygon::align (TPolygon *p)
{
 p->translateTo(this);
 p->rotateTo (getRotation());
}

void TPolygon::subtract (TPolygon *thePiece)
{
 TVector*firstPieceSide, *pieceSide, 
 *firstShapeSide, *shapeSide,
 *aSide, difference;

/* The origins of the Shape and thePiece should be congruent */
 Assert(TVector(*this) == thePiece->getOrigin(),
 "\pSubtract: thePiece is not placed at the origin of          
 the Shape");
 
/* Start at the first sides */
 firstPieceSide = pieceSide = thePiece->firstSide();
 firstShapeSide = shapeSide = firstSide();
 
/* Calculate the difference */
/* Delete all consecutive sides of the shape that are
    congruent with sides of aPiece. */
 do {
 difference = *shapeSide;
 difference -= *pieceSide;
 if (difference.getLength() == 0)
 {
    /*   These sides are congruent */
 *this += *shapeSide;
 aSide = shapeSide;
 shapeSide = nextSide(aSide);
 sides.remove (aSide);
 delete aSide;
 pieceSide = thePiece->nextSide(pieceSide);
 if (pieceSide == firstPieceSide)
 {
    /*   We've gone right round thePiece
    All piece sides congruent.
    We have filled an enclosed space in the shape.
    So just return */
 return;
 }
 else if (*shapeSide || *pieceSide)
    /*   The next sides are parallel
    Loop to check if they are equal */
 ;
 else
    /*   The next sides are not concurrent */
 break;
 }
 else
 {
    /*   These sides are concurrent but have different lengths
    Reduce the shape side to the length and direction of the residue,
    put the origin here, and move to the next piece side */
 *shapeSide = difference;
 *this += *pieceSide;
 
 pieceSide = thePiece->nextSide(pieceSide);
 break;
 }

 } while (true);
 
/* pieceSide is the first non-congruent side of thePiece.
    Make a new list of the rest of the pieceSides in reverse order */
 
 TList *newSides = new TList();
 while (pieceSide != thePiece->firstSide())
 {
 aSide = new TVector(*pieceSide);
 newSides->insert(aSide, 0);
 pieceSide = thePiece->nextSide(pieceSide);
 } 
 



/* Scan the list of newSides
    and compare them with the last sides of the shape.
    Eliminate duplicated or concurrent sides */
 pieceSide = newSides->first();
 while (pieceSide)
 {
 shapeSide = lastSide();
 if (*pieceSide == *shapeSide)
    /*   Sides are congruent so remove from the shape and loop */
 sides.remove (shapeSide);
 else if (*pieceSide || *shapeSide)
 {
    /*   Sides are parallel but different lengths */
 shapeSide->setLength (shapeSide->getLength() 
 - pieceSide->getLength());
 pieceSide = newSides->next(pieceSide);
 break;
 }
 else
 break;
 pieceSide = newSides->next(pieceSide);
 }
/* Reverse the rest of the pieceSides and append to the shape */
 while (pieceSide)
 {
 newSides->remove (pieceSide);
 shapeSide = (TVector *)newSides->next(pieceSide);
 sides.insert (pieceSide);
 pieceSide->reverse();
 pieceSide = shapeSide;
 }
/* Destroy the temporary List */
 delete newSides;
}

Boolean TPolygon::contains (TPolygon *p)
{
/* Test if *this contains (is wholly outside) p  */
 Booleanresult = true;
 TVector*inside, *firstInside,
 *outside, *firstOutside,
 outStart, inStart, relative;
// minAngle, maxAngle;
 
 inStart = p->getOrigin();
 inside = firstInside = p->firstSide();
 do { /* for each side of *p */
 outStart = (TVector)*this;
 outside = firstOutside = firstSide();
/*       relative = outStart;
    relative -= inStart;
    minAngle = maxAngle = relative; */
    do   /*  for each side of *this */
 {
    /*   Check if sides of *p and *this intersect */
 if (*inside || *outside)
    /*   Parallel lines don't intersect */
 ;
 else if (Intercept (&inStart, inside, &outStart, outside))
 {
    /*   These sides intersect */
 result = false;
 break;
 }
 
    /*   update the subtended angles
    relative += *outside;
    if (relative > maxAngle) maxAngle = relative;
    else if (relative < minAngle) minAngle = relative; */
 
    /*   next side of *this */
 outStart += *outside;
 outside = nextSide (outside);
 } while (outside != firstOutside);
 
 if (!result) break;
 




    /*   If max and min subtended angles are not parallel
    the start point of *p side is outside *this
    if (!(maxAngle || minAngle))
    {
    result = false;
    break;
    } */
    /*   next side of *p */
 inStart += *inside;
 inside = p->nextSide (inside);
 } while (inside != firstInside);
 
 return result;
}

TList.cp

/* TList Class Methods      */

/* TList implements a singly-linked List of pointers
    The TList has pointers to the start and end nodes.
    Each node has a pointer to the next TVector in the list
 
    start -> node1 -> node2 ->....-
                                     |-> nodeN -> 0
                              end -
          
    New nodes are added by inserting them after a specific node
    using insert (TVector *aVector, TVector *afterVector)
    or by adding them after the end node using insert (TVector *aVector). */

#include "Tangrams.h"

TList::TList()
{
 start = 0;
 end = 0;
}

void TList::IList(TList& aList)
{
 TVector *v1, *v2;
 v1 = aList.start;
 while (v1) {
 v2 = new TVector (*v1);
 insert(v2);
 v1 = v1->next;
 }
 return;
}

TList::~TList()
{
 TVector*n1, *n2;
 
 n1 = start;
 while (n1 != 0)
 {
 n2 = n1->next;
 delete n1;
 n1 = n2;
 }
}

void TList::insert (TVector *aVector)
{
/* Append TVector as the last item in the list */
 if (end)
 insert (aVector, end);
 else
 {
 aVector->next = 0;
 start = end = aVector;
 }
}


void TList::insert (TVector *aVector, TVector *afterVector)
{
/* Insert TVector after afterVector */
 if (afterVector)
 {
 aVector->next = afterVector->next;
 afterVector->next = aVector;
 }
 else
 {
 aVector->next = start;
 start = aVector;
 }
 if (end == afterVector)
 end = aVector;
}
void TList::remove (TVector *aVector)
{
 if (start)
 {
 if (aVector == start)
 {
 start = start->next;
 if (end == aVector)
 end = 0;
 }
 else
 {
 TVector* n = start;
 while (n)
 {
 if (n->next == aVector)
 {
 n->next = aVector->next;
 if (aVector == end)
 end = n;
 break;
 }
 else
 n = n->next;
 }
 }
 }
}

TVector*TList::first (void)
{
 return start;
}

TVector*TList::next (TVector *aVector)
{
/* Return the next node in the list. */
 return aVector->next;
}

TVector*TList::last (void)
{
 return end;
}

Boolean TList::valid (TVector *aVector)
{
 TVector*n;
 n = start;
 if (aVector)
 while (n)
 if (aVector == n)
 return true;
 else
 n = n->next;
 return false;
}

TPiece.cp

/* TPiece Class Methods */

#include "Tangrams.h"

void TPiece::IPiece (MyPolygon *theData[], long i)
{
 IShape (theData[i]);
 index = i;
 firstOrigin = *this;
 firstDirection = *firstDefinedSide;
}

void TPiece::getTransform (MyTransform *theTransform[])
{
 MyVertex v;
 MyTransform*tf = theTransform[index];

 firstOrigin.getHV (&v);
 tf->doFlip = flipped;
 if (flipped)
 {
 tf->flipH = v.h;
 firstDirection.flip(pi/2);
 firstOrigin -= firstDirection;
 }
 else
 tf->flipH = 0;

 firstOrigin.getHV (&v);
 tf->rotateCenterH = v.h;
 tf->rotateCenterV = v.v;

 tf->rotateClockwise = firstDefinedSide->getAngle() - firstDirection.getAngle();
 
 TVector offset = getOrigin();
 offset -= firstOrigin;
 TVector *side = firstSide();
 while (side != firstDefinedSide)
 {
 offset += *side;
 side = nextSide (side);
 }
 offset.getHV (&v);
 tf->translateH = v.h;
 tf->translateV = v.v;
}

TShape.cp

/* TShape Class methods */

#include "Tangrams.h"
#include "Debug.h"

TShape::TShape()
{
 flipped = false;
}

void TShape::IShape (MyPolygon *theData)
{
 IPolygon (theData);
 flipped = 0;
 firstDefinedSide = firstSide();
}

Boolean TShape::flip(void)
{
 Boolean result = false;
 
 if (canFlip())
 {
 TVector*firstSide;
 
 firstSide = sides.first();
 if (firstSide)
 {
 float  base = firstSide->getAngle();
 TVector*theSide, *nextSide;
 theSide = sides.next(firstSide);
 while (theSide) {
 theSide->flip(base); /* Flip each subsequent side round the first */
 nextSide = sides.next(theSide);
 sides.remove(theSide); /* and reverse its order */
 sides.insert(theSide, firstSide);
 theSide = nextSide;
 }
 }
 result = flipped = !flipped;
 }
 return result;
}
 
Boolean TShape::turn ()
{
 TVector *s1 = sides.first();
 sides.remove(s1);
 sides.insert(s1);
 TVector *s2 = sides.first();
 rotate (s1->getAngle() - s2->getAngle());
 return (s2 != firstDefinedSide);
}

void TShape::getTransform (MyTransform *theTransform[])
{
 theTransform = theTransform;
}

TVector.cp

/* TVector Class methods       */

#include "Tangrams.h"

/* DEFINITIONS */
#define k_ZeroError (0.001) /* Needs to be dynamic */

/* TVector is a polar vector
    Angle is measured in clockwise radians
    Absolute angles are measured relative to the h=0 axis */

float zeroCorrect (float q);
float zeroCorrect (float q)
{
 return (q > -k_ZeroError && q < k_ZeroError) ? 0: q;
}

float angleCorrect (float q);
float angleCorrect (float q)
{
 while (q > pi)
 q = q - 2 * pi;
 while (q < - pi)
  q = q + 2 * pi;
 return zeroCorrect (q);
}

TVector::TVector()
{
 next = 0;
 set (0,0);
}

TVector::TVector(TVector& v)
{
 *this = v;
}

TVector::TVector(float dir, float len)
{
 set (dir, len);
}

/* Polar Vector assignment
    Only assigns direction and length */
TVector& TVector::operator = (TVector& aVector)
{
 angle = aVector.angle;
 length = aVector.length;
 return (*this);
}





/* Polar Vector addition */
TVector& TVector::operator += (TVector& aVector)
{
 MyVertex p1, p2;
 
 getHV (&p2);
 aVector.getHV (&p1);
 p2.h += p1.h;
 p2.v += p1.v;
 p2.h = zeroCorrect(p2.h);
 p2.v = zeroCorrect(p2.v);
 setHV (&p2);
 return (*this);
}

/* Polar Vector subtraction */
TVector& TVector::operator -= (TVector& aVector)
{
 MyVertex p1, p2;
 
 getHV (&p2);
 aVector.getHV (&p1);
 p2.h -= p1.h;
 p2.v -= p1.v;
 p2.h = zeroCorrect(p2.h);
 p2.v = zeroCorrect(p2.v);
 setHV (&p2);
 return (*this);
}

/* Polar Vector equality */
Boolean TVector::operator == (TVector& aVector)
{
 if (0 == zeroCorrect (aVector.length - length))
 if (0 == angleCorrect (aVector.angle - angle))
 return true;
 return false;
}

/* Polar Vector angle compare */
Boolean TVector::operator > (TVector& aVector)
{
 if (0 != zeroCorrect (aVector.length - length))
 if (0 < angleCorrect (aVector.angle - angle))
 return true;
 return false;
}

/* Polar Vector angle compare */
Boolean TVector::operator < (TVector& aVector)
{
 if (0 != zeroCorrect (aVector.length - length))
 if (0 < angleCorrect (aVector.angle - angle))
 return true;
 return false;
}
/* Test if parallel */
Boolean TVector::operator || (TVector& aVector) 
{
 float diff = angleCorrect (aVector.angle - angle);
 if (0 == diff)
 return true;
 else if (0 == angleCorrect (diff + pi))
 return true;
 else return false;
}

void TVector::set (float dir, float len)
{
 angle = dir; length = len;
}

void TVector::setLength (float len)
{
 length = len;
}



void TVector::setAngle (float dir)
{
 angle = dir;
}

void TVector::setNext (TVector *aVector)
{
 next = aVector;
}

/* Transformation */
void TVector::rotate (float anAngle)
{
 angle += anAngle;
 if (angle > pi)
 angle -= 2*pi;
 else if (angle < -pi)
 angle += 2*pi;
 angle = zeroCorrect (angle);
}

void TVector::reverse (void)
{
 if (angle > 0)
 angle = zeroCorrect (angle - pi);
 else
 angle = zeroCorrect (angle + pi);
}

void TVector::flip (float around)
{
 angle = angleCorrect (2 * around - angle);
}

/* Access */
float TVector::getLength (void)
{
 return length;
}

void TVector::setLength (float len)
{
 length = len;
}

float TVector::getAngle (void)
{
 return angle;
}

TVector*  TVector::getNext (void)
{
 return (TVector *)next;
}

/* Cartesian/Polar conversion */
void TVector::getHV (MyVertex *pt)
{
 pt->h = zeroCorrect(length * sinf(angle));
 pt->v = zeroCorrect(length * cosf(angle));
}

void TVector::setHV (MyVertex *pt)
{
 setHV (pt->h, pt->v);
}
void TVector::setHV (float h, float v)
{
 if (zeroCorrect(v))
 {
    /*   |v| != 0 */
 angle = zeroCorrect(atanf(h/v));
    /*   We have an angle between -pi/2 and pi/2
    If v < 0 we need to put the angle in the opposite quadrant */
 if (v < 0)
 if (angle < 0)
 angle += pi;
 else
 angle -= pi;
 }
 else if (h < 0)
 angle = -pi/2;
 else
 angle = pi/2;

 length = sqrtf(h*h + v*v);
}

/* Test for Intersection */
Boolean Intercept (TVector *p1start, TVector *p1,
 TVector *p2start, TVector *p2)
{
/* p1start is the first point on the inside vector p1
    p2start is the first point on the outside vector p2 */
 
 Boolean result = false;

/* x1 and x2 are the start and end points of the inside vector */
 TVector x1 = *p1start;
 TVectorx2 = *p1;
 x2 += x1;
 
/* Transform the inside vector so that the outside vector
    lies along the positive h=0 axis */
 x1 -= *p2start; /* translate inside points so that outside start point = 0,0 */
 x2 -= *p2start;
 x1.length = zeroCorrect (x1.length);
 float  a1 = angleCorrect(x1.angle - p2->angle); /* rotate so that outside lies along 
the axis */
 float  a2 = angleCorrect(x2.angle - p2->angle);
 
/* Inside can get outside by being concurrent with it and longer */
 if (a1 == 0 && a2 == 0)
 if (x1.length < 0 || zeroCorrect (x2.length - p2->length) > 0)
 return true;
 
/* Inside can get outside by starting at axis and going in the wrong direction */
 if ((x1.length == 0 || a1 == 0) && a2 < 0)
 return true;  

 if ( (a1 > 0 != a2 > 0) && 
/* The endpoints are on opposite sides of the h=0 axis, */
 a1 != 0 && x1.length != 0 &&
 a2 != 0 && x2.length != 0 &&  /* neither is on the axis, */
 (a1 < pi || a2 < pi)) /* and at least one end is above the v=0 axis */

 {
 float  denom = ((sinf(a1) * x1.length) - (sinf(a2) * x2.length));
 if (denom > k_ZeroError || denom < - k_ZeroError)
 {
 float diff = p2->length - sinf(a1 - a2) * x1.length * x2.length /denom;
 
 if (diff > k_ZeroError)
 result = true;
 }
 else
 result = false;
 }
 return result;
}

Debug.h

#ifndef __DEBUG__

 #define __DEBUG__
 
 void _Assert(const Boolean condition, ConstStr255Param msg);

 void _MyError(ConstStr255Param msg);

 #ifdef DEBUG

 #define Assert(c, msg)  _Assert (c, msg);
 #define MyError(msg)  _MyError (msg);
 
 #else
 
 #define Assert(c, msg) { /* Nothing */ }
 #define MyError(msg)  ExitToShell();
 
 #endif

#endif

Tangram.h

/* Tangrams.h   */

#pragma mark Problem Specification

typedef struct MyVertex {
 float  h;/* horizontal coordinate of vertex */
 float  v;/* vertical coordinate of vertex */
}MyVertex;

#define kMaxVertices 10

typedef struct MyPolygon {
 long   numVertices; /*the number of vertices*/
 MyVertex vertex[kMaxVertices];  /*the vertices*/
}MyPolygon;

typedef struct MyTransform {
 float  flipH; /* If doFlip - flip polygon about this horiz.coord.*/
 float  rotateClockwise;  /* radians to rotate - */
 float  rotateCenterH;    /* - around this horiz coord - */
 float  rotateCenterV;    /* - and this vert coord */
 float  translateH;/* translate this far horiz */
 float  translateV;/* translate this far vert */
 BooleandoFlip;  /* Flip if true */
}MyTransform;
void SolveTangram(



 MyPolygon*theShape, /* shape to be assembled */
 long   numHoles,/* number of holes in theShape (>=0) */
 MyPolygon*theHoles[],  /* holes in theShape (>=0) */
 long   numPieces, /* number of pieces in theShape */
 MyPolygon*thePieces[], /* pieces in theShape */
 MyTransform*theXForms[]  /* transform for each piece */
);

/* INCLUDES */

#include <math.h>

#define MyError(msg)  ExitToShell();

/* CLASSES */

class TVector
{
/* A vector expressed in polar coordinates */
 friend class TList;
 protected:
 float  angle; // clockwise radians
 float  length;  // length
 TVector*next;
 public:
 //     Constructors
 TVector();
 TVector(TVector& v);
 TVector(float dir, float len);
 //     Operators
 TVector& operator = (TVector& aVector);
 TVector& operator += (TVector& aVector);
 TVector& operator -= (TVector& aVector);
 Boolean operator == (TVector& aVector);
 Boolean operator > (TVector& aVector);
 Boolean operator < (TVector& aVector);
 Boolean operator || (TVector& aVector); /* parallel */
    //    Access
 float  getLength ();
 float  getAngle ();
 TVector* getNext ();
 void set (float dir, float len);
 void setLength (float len);
 void setAngle (float dir);
 void setNext (TVector *aVector);
 //     Transformation
 void rotate (float anAngle);
 void reverse ();
 void flip (float around);
    //    Cartesian/Polar conversion
 void setHV (float h, float v);
 void setHV (MyVertex *pt);
 void getHV (MyVertex *pt);
    //    Is Intercept of the line from p1 to p2 on h=0 < distance?
 friend Boolean Intercept (TVector *p1start, TVector *p1,
 TVector *p2start, TVector *p2);
};

class TList
{
/* A list of TVector instances */
 protected:
 TVector*start;
 TVector*end;
 public:
 TList();
 ~TList();
 void IList(TList& aList);
 void insert (TVector *aVector); /* add aVector to the end */
 void insert (TVector *aVector, TVector *afterVector);
 void remove (TVector *aVector);
 TVector* first (void); /* return first node */
 TVector* next (TVector *aVector);
 TVector* last (void); /* return last node */
 Booleanvalid (TVector *aVector);
};

class TPolygon : public TVector
{
/* A Polygon can be rotated and translated.
    "Align" places the polygon with its first side along the first side of the input polygon
    "Rotate" turns the polygon through an angle about its origin
    "Translate" moves the polygon along a vector */
 protected:
 TList  sides;
    /*   A list of Vectors defining the direction and distance
    of each vertex from its predecessor.
    The Vector in the base class stores direction and
    distance from the origin to the start point. */
 
 public:
    /*   Constructors */
 TPolygon ();
 TPolygon (TPolygon& p);
 void IPolygon(TPolygon *shape);
 void IPolygon(MyPolygon *shape);
    /*   Access */
 TVectorgetOrigin (void);
 TVector* firstSide (void);
 TVector* nextSide (TVector *aSide);
 TVector* lastSide (void);
 float  getRotation (void);
    /*   Transformations */
 void rotate (float angle);
 void rotateTo (float direction);
 void translate (TVector *where);
 void translateTo (TVector *where);
 
 Booleanfill (TList *unplaced, TList *placed);
 Booleancontains (TPolygon *p);
 void align (TPolygon *thePiece);
 void subtract (TPolygon *aPiece);
};

class TShape : public TPolygon
{
/* A Shape is a Polygon used to fill a Tangram.
    It may be flipped and turned.
    It remembers its first defined side and flipped state
    "Flip" turns the shape over about the perpendicular
    bisector of its current first side
    "Turn" moves the shape so that its next side and vertex take
    the start point and direction of its current first side and vertex */
 protected:
 Booleanflipped;
    /*   Is this Shape currently flipped? */
 TVector* firstDefinedSide;
    /*   Stores a pointer to the first side */
 public:
 TShape();
 void IShape (MyPolygon *theData);
 virtualBoolean canFlip(void) {return false;}
    /*   The base class cannot be flipped and always returns false */
 Booleanflip(void);
    /*   Flip the Shape if canFlip()
    Return false if it is not now flipped. */
 Booleanturn ();
    /*   Change the current first side.
    Return false if the next side is the firstDefinedSide */
 virtualvoid getTransform (MyTransform *theTransform[]);
};

class TPiece : public TShape
{
/* A Piece is a Shape that can really be flipped, and
    It remembers the index of the input data that defined it,
    and the direction and relative position of the first defined side for recovery
    of its transform into the MyTransform structure at that index */
 private:
 long index;
 TVectorfirstOrigin;
 TVectorfirstDirection;
 public:
 void IPiece (MyPolygon *theData[], long i);
 virtualBoolean canFlip(void) {return true;}
 virtualvoid getTransform (MyTransform *theTransform[]);
};


 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Spotify 1.2.0.1165 - Stream music, creat...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Thunderbird 102.5.1 - Email client from...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
Pinegrow 7.03 - Mockup and design web pa...
Pinegrow (was Pinegrow Web Designer) is desktop app that lets you mockup and design webpages faster with multi-page editing, CSS and LESS styling, and smart components for Bootstrap, Foundation,... Read more
Adobe After Effects 2022 23.1 - Create p...
The new, more connected Adobe After Effects can make the impossible possible. Get powerful new features like a Live 3D Pipeline that brings CINEMA 4D scenes in as layers - without intermediate... Read more
SteerMouse 5.6.7 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Wireshark 4.0.2 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
Adobe Premiere Pro 2022 23.1 - Digital v...
Adobe Premiere Pro is available as part of Adobe Creative Cloud for as little as $54.99/month. The price on display is a price for annual by-monthly plan for Adobe Premiere Pro only. Adobe Premiere... Read more
1Password 8.9.10 - Powerful password man...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
FotoMagico 6.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Affinity Photo 1.10.6 - Digital editing...
Affinity Photo - redefines the boundaries for professional photo editing software for the Mac. With a meticulous focus on workflow it offers sophisticated tools for enhancing, editing and retouching... Read more

Latest Forum Discussions

See All

‘Awaken Legends: Idle RPG’ Celebrates th...
Awaken Legends: Idle RPG is adding its first update since the game was soft-launched in November, letting players get their hands on a new hero “Hera Valen". Players can also look forward to the Covenant of the Dark Knight event and the Wishing Well... | Read more »
‘Horizon Chase 2’ Japan World Tour Expan...
Horizon Chase 2 () from Aquiris is getting a major expansion today on Apple Arcade. The Japan World Tour expansion brings in 11 new races across 9 cities and it should be rolling out now as of this writing. I expect it to be available worldwide... | Read more »
Dark Fantasy Visual Novel ‘The 13th Mont...
Originally announced for release in August, The 13th Month from Japanese developer Kobayashimaru and publisher Kodansha released on PC via Steam worldwide this month. The dark fantasy visual novel that reimagines the classic Sleeping Beauty tale, is... | Read more »
Tom Clancey’s The Divison Resurgence ann...
Ubisoft has announced the latest Live Test dates for Tom Clancy’s The Division Resurgence, the hotly anticipated mobile entry in the Divison series. Starting December 8th and ending on the 22nd, the test will offer a huge amount of content for the... | Read more »
‘Easy Come Easy Golf’ New Update Adds St...
Easy Come Easy Golf () from Clap Hanz is one of my favorite games on Apple Arcade. It has been updated quite a bit since launch bringing in new modes and improvements. It recently launched on Nintendo Switch as well. | Read more »
Out Now: ‘Magic vs Metal’, ‘Suzerain’, ‘...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 7th, 2022. Today can be accurately described as Mikhail Madness, with a whopping four reviews from our pal-est of pals. Football Manager 2023 Touch, Wobbledogs, Soccer Story... | Read more »
Alchemy Stars celebrates 1 and a half ye...
It has been one and a half years since Alchemy Stars launched, and Level Infinite is celebrating in style with a host of new content. There will be a new story mission and even a store to explore, and a whole new mode for those budding idol... | Read more »
Fighting Game ‘Art of Fighting 2’ ACA Ne...
Last week, side-scrolling shooter Pulstar hit mobile platforms as the newest ACA NeoGeo series release from Hamster and SNK. Read Shaun’s review of it here. Today, fighting game Art of Fighting 2 has launched on iOS and Android. Art of Fighting 2... | Read more »
‘Genshin Impact’ Version 3.3 Update Now...
HoYoverse recently revealed the next major update for Genshin Impact (Free) in the form of version 3.3 ‘All Senses Clear, All Existence Void’. | Read more »

Price Scanner via MacPrices.net

New! Details on Verizon’s Christmas/Holiday p...
Verizon is offering discounts on iPhones, Apple Watch models, and iPads with specific promo codes as part of their Christmas/Holiday 2022 offerings. Codes are valid when adding a new line of service... Read more
Apple MagSafe accessories are back on Holiday...
Amazon has Apple MagSafe Chargers and Apple’s MagSafe Battery on sale for up to 24% off MSRP again as part of their Christmas/Holiday sale. Shipping is free, and all models are in stock: – MagSafe... Read more
13″ M2 MacBook Airs on sale again for the low...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $150 off MSRP as part of their Christmas/Holiday Sale, prices start at $1049. Shipping is free. They are the lowest prices... Read more
Get an Apple 16″ MacBook Pro for $400 off MSR...
16″ MacBook Pros with Apple’s M1 Pro CPUs are in stock and on sale today at B&H Photo for $300-$400 off Apple’s MSRP for a limited time. Prices start at $2099 for M1 Pro models with 512GB or 1TB... Read more
Holiday clearance sale! Previous-generation A...
Amazon has 2nd generation 32GB and 64GB 4K Apple TVs with Siri remotes and 32GB Apple TV HDs on clearance sale for $80-$90 off original MSRP. Shipping is free, and delivery is available in time for... Read more
Christmas sale at Verizon: Apple AirPods Pro...
Verizon has first-generation Apple AirPods Pro on sale for $159.99 on their online store as part of their continuing Christmas/Holiday sale. Their price is $90 off Apple’s original MSRP, and it’s the... Read more
New Christmas/New Years promo at Xfinity Mobi...
Switch to Xfinity Mobile and open a new line of service, and take $400 off the price of a new iPhone, no trade-in required, through January 10, 2023. The $400 is applied to your account as credits... Read more
Apple iPad Smart Keyboard Folio prices drop u...
Apple iPad Smart Keyboard Folio prices have dropped up to $60 off MSRP at Amazon and Walmart as part of their Christmas/Holiday sales. These are the cheapest prices currently available for these iPad... Read more
Today is the final day for Xfinity Mobile’s $...
If you switch to Xfinity Mobile and open a new line of service, they will take $500 off the price of a new iPhone, no trade-in required. This is the best no trade-in Cyber Monday Apple iPhone 14 deal... Read more
Amazon restocks 10.2″ 64GB 9th-generation iPa...
Amazon has Apple’s 9th generation 10.2″ 64GB WiFi iPads (Silver) in stock and on sale for $269.99 shipped as part of their Christmas/Holiday Sale. Their price is $60 off Apple’s MSRP. Free delivery... Read more

Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Sephora Beauty Advisor - *Apple* Blossom Ma...
Sephora Beauty Advisor - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.