TweetFollow Us on Twitter

Nov 98 Prog Challenge

Volume Number: 14 (1998)
Issue Number: 11
Column Tag: Programmer's Challenge

Nov 98 Challenge

by Bob Boonstra, Westford, MA

Rendezvous and Docking

These are exciting times for space buffs like myself. We've been watching the Russian efforts to keep Mir operating, and the visits of the space shuttle to that space station. We've watched a variety of planetary gravity assist maneuvers to send the Galileo spacecraft to Jupiter and its moons and the Ulysses spacecraft into polar orbit around the sun. A satellite that did not achieve its intended geostationary orbit is being recovered using innovative gravity assist maneuvers around the moon. And over the next few years, the United States and its international partners will be launching and assembling the International Space Station.

Let's imagine that NASA has asked the Programmer's Challenge to develop some efficient software for navigating around the solar system and efficiently completing a rendezvous with another object. The prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

typedef float SimTime;     /* seconds */

typedef struct Vector3D {  /* right-handed coordinate system x-y-z */
   float x;
   float y;
   float z;
} Vector3D;

typedef enum {kDestroyed=0, kShip, kTarget, kOtherMass} BodyType;

typedef struct SimConstants {
   float G;                /* in Newtons*meters/(kg**2) */
   SimTime minTimeStep;    /* simulation timeStep will be >= minTimeStep */
   SimTime maxTimeStep;    /* simulation timeStep will be <= maxTimeStep */
   float maxAcceleration;  /* meters/(sec**2) */
   float timePenalty;      /* meters/sec per millisecond */
} SimConstants;

typedef struct Body {
   float mass;             /* mass in kg */
   float radius;           /* radius in meters */
   Vector3D   position;    /* position vector in meters */
   Vector3D   velocity;    /* velocity vector in meters */
   BodyType   bodyType;    /* (self explanatory) */
} Body;

pascal void InitSim(
   const SimConstants simConstants,    /* simulation constants */
   const SInt8 numBodies,  /* number of bodies in the simulation */
   const Body theBodies[]  /* parameters of simulation bodies */
);

pascal Boolean AdvanceTime( /* return TRUE if docking complete or giving up */
   const SimTime timeStep,  /* propagate forward this amount of time */
   Vector3D *shipAcceleration,  /* return ship acceleration vector applied */
                          /*this step */
   Body theBodies[]  /* return body parameters at the end of this time step */
);

#if defined(__cplusplus)
}
#endif

You will be given a number of Body objects moving through space. One of those objects will be a ship under your control, and another will be a target object. The rest will be objects that exert gravitational influences on one another. Your objective is to guide your ship to the target and complete a rendezvous, minimizing a cost formula that depends on the fuel expended by your ship and the time to complete the rendezvous. First, your InitSim routine will be provided with a number of parameters for the problem, and then your AdvanceTime routine will be called repeatedly to propagate all of the objects in our simulated solar system.

In order to be able to score this Challenge, we'll have to agree on the equations of motion. To the best of my recollection, the equations we will use are the non-relativistic approximations of the versions that govern the real world.

The gravitational force exerted by one object ([j]) on another object ([i]) is given by:

m[i]*r''[i] = - G* m[i]*m[j]*(r[i]-r[j]) / |(r[i]-r[j])|**3, 

where:

  • r[k] is the position vector for object k,
  • r''[k] is the acceleration vector for object k,
  • G is the gravitational constant provided in simConstants
  • m[k] is the mass of object k
  • |v| denotes the magnitude of vector v

The position (r) and velocity (r') vectors for an object at the end of timeStep t are:

   r'new = r' + r''*t
   rnew = r + + r'*t + r''*(t**2)/2

where

  • r, r' are the position and velocity vectors at the start of the timeStep
  • rnew, r'new are the position and velocity vectors at the end of the timeStep
  • t is the duration of the timeStep
  • r'' is the vector sum of all gravitational and ship accelerations acting on the object

Your InitSim routine will be given a set of simConstants that govern the simulation, the number of bodies (numBodies) included in the simulation, and a set of characteristics for each simulated Body, including mass, radius, position vector, velocity vector, and the type of body this is. Exactly one Body (kShip) will be your ship and exactly one will be your target (kTarget).

The simConstants will include the gravitational constant G used to propagate objects, the maximum acceleration (vector magnitude) your ship can endure without breaking up, the maximum and minimum time increments to be used for propagation, and a scaling factor used for scoring.

Each time AdvanceTime is called, you should determine the shipAcceleration you want to apply to your ship, compute the gravitational forces of each object on every other object, compute the new position and velocity of each object, and return the shipAcceleration and the updated Body values in parameters provided.

In the event of a collision, where the object spheres intersect, the smaller object is absorbed by the larger object, increasing its mass, and the velocity of the larger object is changed to conserve the momentum vector (mass * velocity). You only need to worry about collisions at the end of a timeStep. If this means that one of your objects passes through another object undetected, we will attribute that to pseudo quantum mechanical uncertainty in our nonrelativistic universe.

To allow longer simulations to complete, it may be necessary to vary the timeStep value used. Each timeStep will be between minTimeStep and maxTimeStep in duration. The timeStep values will be calculated so that they may increase when the largest gravitational force is smaller and your ship is far from the target, and may decrease when one or more of the gravitational forces becomes large, or when your ship comes close to the target.

Our simulated solar system has a few simplifying characteristics compared with the real world. Fortunately, all of the bodies in the system are perfect spheres of uniform density, so the center of mass is exactly at the center of the sphere, allowing gravity to be modeled as if they were point masses. Our ship has the ability to instantly accelerate in any direction, at any magnitude from zero to maxAcceleration. And for our purposes, a rendezvous is considered accomplished when the ship and the target are within 10 ship radii of intersecting, and their relative velocities differ in magnitude by less than 1 meter/sec or .0001 times the velocity of the ship.

The winner will be the solution that successfully completes the rendezvous at the lowest cost. Cost for this Challenge is primarily determined by the amount of fuel your ship uses, calculated as the sum of the magnitudes of the acceleration vectors you apply during each timeStep. In order to keep execution time reasonable, and in the spirit of the Challenge, the score will be incremented by the total amount of execution time spent in your InitSim and AdvanceTime routines, multiplied by a timePenalty scaling factor. I will not know how large to set the timePenalty scaling factor until I see how long the solutions take to execute, but the same timePenalty factor will be used for everyone. My intent is to structure the problems and the timePenalty value so that most solutions complete in minutes or tens of minutes.

All distance, mass, and time values will be in the mks (meters, kilograms, seconds) system.

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) on his return to the Challenge winner's circle, and for submitting the fastest of three entries to the Blockbuster Challenge. Based on the original Soma cube puzzle, the objective was to reassemble a collection of pieces formed from individual cubies into a designated target shape.

Ernst's solution creates a StateMap data structure that represents the goal state, or more accurately, the complement of the goal state. The space representing the goal structure starts out as empty, and is surrounded by a shell of "dummy" cubies that represent the outside boundary of the goal. Each cell contains a set of Flags that indicate the type of surface that exists at a given set of coordinates. Ernst uses the number of corners on a piece as a measure of the complexity of the piece, and I think one of the keys to his success was the fact that he uses this measure to try to place the more complex pieces first.

The three entries to the Blockbuster Challenge were evaluated using a set of seven test cases, including the original Soma cube, some alternative shapes that can be formed using the pieces of the original Soma cube, and some larger puzzles. Unfortunately, the solution time increased very quickly with puzzle size, so I was unable to wait for the entries to solve some of the puzzles I had originally intended to include in the evaluation. I do not think this affected the evaluation results, as the performance advantage of Ernst's winning entry increased as the problem size got larger.

The table below lists, for each of the solutions submitted, the total execution time for the seven test cases, the execution time for the classic Soma cube puzzle, and the execution time for one of the Soma variants. You can see that while the winning entry was not the fastest for the classic puzzle, it was fastest for the variant and fastest overall. The table also includes code size, data size, and programming language used. 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. The entry listed with an asterisk was unable to solve one of the test cases and was therefore ineligible to earn points.

Name Total Time (msec) Soma Time (msec) Soma Time2 (msec) Code Data Lang
Ernst Munter (388) 269.1 11.4 164.9 7752 8424 C++
Sebastian Maurer (30) 3244.6 1.1 256.3 5200 176 C
W.R. (*) 349046.6 1.5 234.1 12204 192 C++

Top Contestants

Both of the contestants earning points this month were already members of our points leader list. Ernst adds to his already dominating points lead, and Sebastian moves up from 10th to 7th place. Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 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 194
2. Boring, Randy 56
3. Mallett, Jeff 50
4. Saxton, Tom 49
5. Rieken, Willeke 47
6. Cooper, Greg 44
7. Maurer, Sebastian 40
8. Heithcock, JG 37
9. Nicolle, Ludovic 34
10. Lewis, Peter 31
11. Murphy, ACC 24
12. Gregg, Xan 22
13. Hart, Alan 21
14. Antoniewicz, Andy 20
15. Day, Mark 20
16. Higgins, Charles 20
17. Hostetter, Mat 20
18. Studer, Thomas 20

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

BlockBuster.cp

Copyright © 1998 Ernst Munter

/*

The Problem

Assemble puzzle pieces made from unit-size cubies into the goal shape.

The Solution

The pieces are systematically tried in assembling the goal.

Data Representation

The goal and the cubies are represented in a 3D array space with a 7 bit flag set describing the surfaces of a cubie. The left-down-front bits are stored at the 3D coordinates of the cubie, the right-up-back bits are stored at the next coordinate points in the x, y, and z direction. The seventh bit denotes the presence of a "real" cubie at a 3D location. Simple arithmetic is used to merge a piece into an open goal spot, and to remove it again.

Note: Please reserve enough stack space to handle the recursive solver. The extra stack size required is about 112 bytes per piece, e.g for a 1000 piece puzzle, one should increase the stack size from the 64K compiler default to perhaps 170K. (although this may be a moot point, considering that the algorithm is too slow for any such large number of pieces, unless they are very similar, for example just like bricks.

*/

#include <string.h>
#include <stdlib.h>
#include "BlockBuster.h"

typedef enum {
   kL=1,          // Left
   kR=2,          // Right
   kD=4,          // Down   
   kU=8,          // Up
   kF=16,         // Front
   kB=32,         // Back
   kReal=64,      // Actual Cubie
   kBlocked=kReal,
   kHidden=128,
   kCorner=kL+kD+kF,
   kPack=1} Flags;

typedef UInt16 State;   // could use UInt8 if numPieces < 256

LookupTable
// Lookup for merging/unmerging pieces into the goal
static struct LookupTable {
   UInt8 MergeTable[64][64];
   UInt8 UnmergeTable[64][64];
   LookupTable(){
      for (int goal=0;goal<64;goal++) {
         for (int piece=0;piece<64;piece++) {
            MergeTable[goal][piece] =
               (((goal & (kL+kR)) + 2*(piece & (kL+kR))) % 3) +
               (((goal & (kD+kU)) + 2*(piece & (kD+kU))) % 12) +
               (((goal & (kF+kB)) + 2*(piece & (kF+kB))) % 48);
            UnmergeTable[goal][piece] =
               (((goal & (kL+kR)) + (piece & (kL+kR))) % 3) +
               (((goal & (kD+kU)) + (piece & (kD+kU))) % 12) +
               (((goal & (kF+kB)) + (piece & (kF+kB))) % 48);
         }
      }
   }
} LUT;

Merge/Unmerge
inline int Merge(const int goal,const int piece) {
   return LUT.MergeTable[goal&0x3F][piece&0x3F]
      + ((goal ^ piece) & kReal);
}

inline int Unmerge(const int goal,const int piece) {
   return LUT.UnmergeTable[goal&0x3F][piece&0x3F]
      + ((goal ^ piece) & kReal);
}
// sequence to drive a piece through all 24 rotated positions
static char rotPattern[24] =
   {0,1,1,0, 2,1,0,1, 2,1,0,0, 1,1,1,0, 2,1,0,1, 1,1,2,1};

Spot 
// Spot is a wrapper class for cubies, and is also used for 3D algebra
struct Spot {   
   Cubie   cubie;
#define X cubie.xCoord
#define Y cubie.yCoord
#define Z cubie.zCoord
#define FLAGS cubie.value    
   Spot(){}
   Spot(const int x,const int y,const int z) {X=x;Y=y;Z=z;}
   Spot(const Cubie & C){cubie=C;}
   int CompSpot(const Spot & f) const {
      if (X == f.X) {
         if (Y == f.Y) return Z - f.Z;
         return Y - f.Y;
      }
      return X - f.X;
   }
   int CompSpotFlags(const Spot & f) const {
      if (FLAGS == f.FLAGS) return CompSpot(f);
      return FLAGS - f.FLAGS;
   }
   void LowerBound(const Spot & S) {
      if (S.X < X) X = S.X;
      if (S.Y < Y) Y = S.Y;
      if (S.Z < Z) Z = S.Z;
   }
   void UpperBound(const Spot & S) {
      if (S.X > X) X = S.X;
      if (S.Y > Y) Y = S.Y;
      if (S.Z > Z) Z = S.Z;
   }
   int MaxCoordValue() const {
      if ((X>Y) && (X>Z)) return X;
      if (Y>Z) return Y;
      return Z;
   }
   Spot operator + (const Spot b) const {
      return Spot(X+b.X,Y+b.Y,Z+b.Z);
   }
   Spot operator - (const Spot b) const {
      return Spot(X-b.X,Y-b.Y,Z-b.Z);
   }
   void operator += (const Spot b) {
      X += b.X; Y += b.Y; Z += b.Z;
   }
   void operator -= (const Spot b) {
      X -= b.X; Y -= b.Y; Z -= b.Z;
   }
   void operator |= (const Spot b) {FLAGS |= b.FLAGS;}
   bool IsNegative() const {return ((X|Y|Z) < 0);}
   int Offset(const Spot range) const {
      return (Z*range.Y+Y)*range.X+X;
   }
   void ClearFlags(const int flags){FLAGS&=~flags;}
   void CancelFlags() {
      if ((FLAGS & kL)&&(FLAGS & kR)) ClearFlags(kL+kR);
      if ((FLAGS & kD)&&(FLAGS & kU)) ClearFlags(kD+kU);
      if ((FLAGS & kF)&&(FLAGS & kB)) ClearFlags(kF+kB);
   }
   bool IsHidden() const {return FLAGS & kHidden;}
   bool IsReal() const {return FLAGS & kReal;}
   void SetFlags(const int flags) {FLAGS=flags;}
   void ShiftRight() {X++;}
   void ShiftUp() {Y++;}
   void ShiftBack() {Z++;}
   UInt32 Hash() {return (((X*511)+Y)*2503)+Z;}
};

// Two compare functions for use with quick sort

CompSpot/CompSpotFlags
// Compare coordinates only, (detect duplicates)
static int CompSpot(const void* a,const void* b) {
   return ((const Spot*)b)->CompSpot(*((const Spot*)a));
}

// Compare coordinates and flags (sort real cubies to front)
static int CompSpotFlags(const void* a,const void* b) {
   return ((const Spot*)b)->CompSpotFlags(*((const Spot*)a));
}

StateMap 
// StateMap is a 3D representation of the goal which can be indexed
// as an array.  Each state value represents a number of flags,
// which indicate if a real cubie exists, and which kind of surface
// (left, right, etc) occurs at these coordinates.
//
// Initially, the goal is empty, but surrounded by a shell of cubies
// which define the shape of the goal, and block the placement of
// pieces outside the goal.
//
// As pieces are placed, they effectively shrink the shell, by removing
// some, and adding other, surfaces, and by blocking the space they
// occupy.
//
// After the puzzle is solved, the state array is used to transfer the
// piece identifiers to the Goal of the calling program.
static struct StateMap {
   int      width;
   int      height;
   int       lengthOfState;
   State*   state;
   int      firstGoalIndex;
   int      cacheCorner;
   StateMap(const Spot goalRange,Spot cubies[],const int numCubies) {
// copies spots defining the goal surface into the state map
      width=goalRange.X;
      height=goalRange.Y;
      lengthOfState=width*height*goalRange.Z;
      state=new State[lengthOfState];   
// Initially, all spaces are blocked
      for (int i=0;i<lengthOfState;i++)
         state[i]=kBlocked;    
      Spot* C=cubies;
// Then, the cubies of the goal shape are excavated
      firstGoalIndex=lengthOfState;
      for (int i=0;i<numCubies;i++,C++) {
         int index=C->Offset(goalRange);
         state[index]=Flags(C->FLAGS) ^ kReal;
         if (index<firstGoalIndex) firstGoalIndex=index;
      }
      cacheCorner=firstGoalIndex;
   }
   ~StateMap(){delete[] state;}

   int Corner() {
// Finds a left-lower-front corner in the goal
// should never fail, and should really be better optimized
      if (state[cacheCorner]==(kL+kD+kF)) // probably still good
         return cacheCorner;
      State* C=state+firstGoalIndex-1;
      for (int i=firstGoalIndex;i<lengthOfState;i++) {
         if (*++C == (kL+kD+kF)) {
            cacheCorner=i;
            return i;
         }
      }
      return -1;   // just in case
   }

   bool Collides(const int target,const int sourceFlags) const {
// Checks if piece is compatible
      return (state[target] & sourceFlags & kBlocked);
   }
   void Place(const int target,const int sourceFlags) {
      state[target]=Merge(state[target],sourceFlags);
   }
   void Unplace(const int target,const int sourceFlags) {
      state[target]=Unmerge(state[target],sourceFlags);
   }
   void Copy(const int target,const int id) {
      state[target]=id;
   }
} * goalMap;

CommonPiece
// CommonPiece is the ancestor class for MyPieces and MyGoal
// Creates a temporary set of cubies for computing states and
// surfaces, and tracks the piece-id (value)
struct CommonPiece {
   int      numCubies;
   Spot*      cubies;      // only used during initialization
   int       id;
   void Init(Piece & thePiece,const Spot offset,bool pack) {
// record piece id value just once
      id=thePiece.theCubies[0].value;
      numCubies=thePiece.numCubies;

// Each cubie has potentially 3 virtual neighbors: R,U,B
      int tempNum=4*numCubies;
      Spot* temp=new Spot[tempNum];
      memcpy(temp,thePiece.theCubies,
               sizeof(Spot)*numCubies);
      memcpy(temp+numCubies,thePiece.theCubies,
               sizeof(Spot)*numCubies);
      memcpy(temp+2*numCubies,thePiece.theCubies,
               sizeof(Spot)*numCubies);
      memcpy(temp+3*numCubies,thePiece.theCubies,
               sizeof(Spot)*numCubies);

// setup real cubies and 3 border cubies for each
// each cubie serves to define one or more surfaces, using the flags
      for (int i=0,r=numCubies,u=r+numCubies,b=u+numCubies;
         i<numCubies;i++,r++,u++,b++) {
         temp[i].SetFlags(kL+kD+kF+kReal);
         temp[r].SetFlags(kR);temp[r].ShiftRight();
         temp[u].SetFlags(kU);temp[u].ShiftUp();
         temp[b].SetFlags(kB);temp[b].ShiftBack();
      }

// combine cubies at equal coordinates, and hide unneeded cubies
      qsort(temp,tempNum,sizeof(Spot),CompSpot) ;
      for (int i=1;i<tempNum;i++) {
         if (0==temp[i].CompSpot(temp[i-1])) {
            temp[i] |= (temp[i-1]);
            temp[i-1].SetFlags(kHidden);
         }
      }

// cancel flags, remove hidden cubies, and shift by offset
      for (int i=0;i<tempNum;) {
         if (temp[i].IsHidden()) {
            temp[i]=temp[-tempNum];
         } else {
            temp[i].CancelFlags();
            temp[i] -= offset;
            i++;
         }
      }

// Resort, to bring real cubies to front of array
      qsort(temp,tempNum,sizeof(Spot),CompSpotFlags) ;
// For the goal, we will need placeholders for all spots in 3D space,
// but for the pieces, we can shorten the list by removing all cubies
// which represent hidden internal surfaces.
      if (pack) {
         numCubies=tempNum;
         cubies=new Spot[numCubies];
         memcpy(cubies,temp,sizeof(Spot)*numCubies);
         delete[] temp;         
      } else {
         cubies=temp;
         numCubies=tempNum;
      }
   }
};

Rotate and Utility Functions
// Non-class based utility functions, for rotating the pieces while preparing
// the rotated versions of each piece, and to determine their extreme coords.
typedef void (*RotateFunction)(Piece &);
static void RotateX(Piece & thePiece) {
   Cubie* C=thePiece.theCubies;
   for (int k=0;k<thePiece.numCubies;k++,C++) {
      int save=C->zCoord;C->zCoord=C->yCoord;C->yCoord=-save;
   }
}

static void RotateY(Piece & thePiece) {
   Cubie* C=thePiece.theCubies;
   for (int k=0;k<thePiece.numCubies;k++,C++) {
      int save=C->xCoord;C->xCoord=C->zCoord;C->zCoord=-save;
   }
}

static void RotateZ(Piece & thePiece) {
   Cubie* C=thePiece.theCubies;
   for (int k=0;k<thePiece.numCubies;k++,C++) {
      int save=C->yCoord;C->yCoord=C->xCoord;C->xCoord=-save;
   }
}

static RotateFunction RotatePiece[3] = {RotateX,RotateY,RotateZ};
static Spot Lowest(const Piece & piece) {
   Cubie* C=piece.theCubies;
   Spot low=Spot(C[0]);
   for (int i=1;i<piece.numCubies;i++) {
      low.LowerBound(*++C);
   }
   return low;
}

static Spot Highest(const Piece & piece) {
   Cubie* C=piece.theCubies;
   Spot high=Spot(C[0]);
   for (int i=1;i<piece.numCubies;i++) {
      high.UpperBound(*++C);
   }
   return high;
}

static int Diameter(const Piece & piece) {
   Cubie* C=piece.theCubies;
   Spot low=Spot(C[0]);
   Spot high=Spot(C[0]);
   for (int i=1;i<piece.numCubies;i++) {
      low.LowerBound(*++C);
      high.UpperBound(*C);
   }
   return (high-low).MaxCoordValue();
}

RotPiece 
// RotPiece is one distinct rotational instance of a piece.
// Only the "state plus Index" is stored in 2 fields in a 32-bit variable,
// representing the surface state of the piece (8 bits),
// and the index in global goal map coordinates (24 bits).
struct RotPiece {
   int      lengthOfState;
   int      lengthOfReal;
   int      corner;      // current corner during search
   UInt32*   stateIndex;   // 8+24 bits
   void Init(Spot cubies[],const int numCubies,
                                    const Spot goalRange) {
      lengthOfState=numCubies;
      stateIndex=new UInt32[lengthOfState];
      corner=0;
      lengthOfReal=1;
      Spot* C=cubies;
      for (int i=0;i<numCubies;i++,C++) {
         stateIndex[i] = (C->Offset(goalRange) << 8) | 
                                          Flags(C->FLAGS);
         if (C->FLAGS & kReal) lengthOfReal++;
      }
   }
   void Destroy(){delete[] stateIndex;}

   int NumCorners() {
// a measure of complexity, we try to place more complex pieces first
      int numCorners=0;
      for (int i=0;i<lengthOfReal;i++) {
         if ((stateIndex[i] & kCorner) == kCorner) numCorners++;
         else break;
      }
      return numCorners;
   }
   int GetSpot() {
// Returns the index to the left-lower-front corner spot
// Increments the corner and returns -1 if all corners have been exhausted
      UInt32* SI=stateIndex+corner;
      if ((*SI & kCorner) == kCorner) {
         corner++;
         return (*SI >> 8);
      }
      corner=0;
      return -1;
   }

   bool Fits(int xlate) {
// Returns true if the piece would fit, when translated into the goal map.
      UInt32* SI=stateIndex-1;
// spot[0] always fits, because it was used to define xlate
      for (int i=1;i<lengthOfReal;i++) {
         int target= xlate + (*++SI >> 8);
         int sourceFlags=*SI & 0xFF;
         if (goalMap->Collides(target,sourceFlags)) return false;
      }
      return true;
   }
   void Place(int xlate) {
// Places all cubies and surfaces into the goal map.
      UInt32* SI=stateIndex-1;
      for (int i=0;i<lengthOfState;i++) {
         int target= xlate + (*++SI >> 8);
         int sourceFlags=*SI & 0xFF;
         goalMap->Place(target,sourceFlags);
      }
   }
   void Unplace(int xlate) {
// Removes this piece from the goal map.
      UInt32* SI=stateIndex-1;
      for (int i=0;i<lengthOfState;i++) {
         int target= xlate + (*++SI >> 8);
         int sourceFlags=*SI & 0xFF;
         goalMap->Unplace(target,sourceFlags);
      }
   }
   void Copy(int id,int xlate) {
// Copies the piece id into the goal map, overriding cubie states
      UInt32* SI=stateIndex-1;
      for (int i=0;i<lengthOfReal;i++) {
         int target= xlate + (*++SI >> 8);
         goalMap->Copy(target,id);
      }
   }
};

CommonPiece
// Private representation of the piece.
struct MyPiece:CommonPiece {
   RotPiece   rotPiece[24];   // there can be up to 24 unique versions
   short      numRotations;
   short      curRotation;   
   int      source;         // on the piece
   int      target;         // on the goal
   int      numCorners;
   ~MyPiece() {
      for (int i=0;i<numRotations;i++) {
         rotPiece[i].Destroy();
      }
   }
   void Init(const Spot goalRange,Piece & thePiece) {
      numRotations=0;
      curRotation=0;
      numCorners=0;
      source=0;target=-1;
      CreateRotatedPieces(goalRange,thePiece);
      for (int i=0;i<numRotations;i++) {
         numCorners+=rotPiece[i].NumCorners();
      }   
   }
   void CreateRotatedPieces(const Spot goalRange,Piece & thePiece) {
// Generates all distinct versions by rotation through a cyclic pattern
// Normalizes all pieces by aligning to 0 and sorting, so that equal versions
// can be recognized easily using hash values.
      UInt32 H[24];
      Align(thePiece);
      H[0]=Hash(thePiece);
      CommonPiece::Init(thePiece,Spot(0,0,0),kPack);// make cubies
      rotPiece[numRotations++].Init(cubies,numCubies,goalRange);
      // cubies have done their job
      delete[] cubies;                  
      for (int i=1;i<24;i++) {
         RotatePiece[rotPattern[i]](thePiece);
         Align(thePiece);
         H[i]=Hash(thePiece);               
         for (int k=0;k<i;k++) {
            if (H[k]==H[i]) goto notNew;
         }
         CommonPiece::Init(thePiece,Spot(0,0,0),kPack);
         rotPiece[numRotations++].Init(cubies,numCubies,goalRange);
         delete[] cubies;
notNew:;               
      }                              
   }
   void Align(Piece & thePiece) {
      Spot offset=Lowest(thePiece);
      Cubie* C=thePiece.theCubies;
      for (int i=0;i<thePiece.numCubies;i++,C++) {
         C->xCoord-=offset.X;
         C->yCoord-=offset.Y;
         C->zCoord-=offset.Z;
      }
      qsort(thePiece.theCubies,thePiece.numCubies,
         sizeof(Cubie),CompSpot);
   }
   UInt32 Hash(Piece & thePiece) {
      UInt32 h=1;
      for (int i=0;i<thePiece.numCubies;i++) {
         UInt32 hf=Spot(thePiece.theCubies[i]).Hash();
         h=(h<<9) + ((h>>23)^hf);
      }
      return h;
   }
   int Available(){
// A piece is available for placing if it does not have a target assigned
      return (target < 0);
   }
   bool NextRotation() {
// Cycles through the distinct rotations
      curRotation++;
      if (curRotation>=numRotations) {
         curRotation=0;
         return false;
      }
      return true;
   }
   int GetSpot(int t) {
// Cycles through the left-lower-front corners of a piece
// If a rotation is found, sets target for the piece to t
//    and returns the corresponding source corner in the piece.
      source=rotPiece[curRotation].GetSpot();
      if (source<0) target=-1;
      else target=t;
      return source;
   }
// The next 4 functions are passed on to the current rotational version
   bool Fits() {
      return rotPiece[curRotation].Fits(target-source);
   }
   void Place() {
      rotPiece[curRotation].Place(target-source);
   }
   void Unplace() {
      rotPiece[curRotation].Unplace(target-source);
   }
   void Copy() {
      rotPiece[curRotation].Copy(id,target-source);
   }
   int NumCorners(){return numCorners;}
};

CompPiece
// Comparator function for sorting pieces by complexity (in reverse order)
static int CompPiece(const void* a,const void* b) {
   MyPiece* pa=(MyPiece*)a;
   MyPiece* pb=(MyPiece*)b;
   return pb->NumCorners()-pa->NumCorners();
}

MyGoal
// Private version of the goal which directly and indirectly owns
// all other non-global private data.
struct MyGoal:CommonPiece {
   MyPiece*   pieces;
   int      numPieces;
   int      piecesLeft;
   Spot      goalOffset;   // goal aligned to 0
   Spot      goalRange;
   MyGoal(const long num,Piece thePieces[],Piece theGoal) {
// computes overall dimensions and an offset which define a safe private
// three-dimensional goal space
      goalOffset=Lowest(theGoal);
      int largest=Diameter(thePieces[0]);
      for (int i=1;i<num;i++) {
         int pieceSize=Diameter(thePieces[i]);
         if (pieceSize>largest)
            largest=pieceSize;
      }
      Spot maxPiece=Spot(largest,largest,largest);
      goalOffset-=maxPiece;
// goal cubies are translated into the (0,0,0) based goal range
// of sufficient size to handle the largest misplaced piece.
      CommonPiece::Init(theGoal,goalOffset, ! kPack);
      goalRange=Highest(theGoal)
         - goalOffset + maxPiece + Spot(1,1,1);

// Check for overflow:
      if (goalRange.IsNegative()) {
// Should not happen if diameter of puzzle is < 32K, but if it does,
// we signal this to the Solve() function with a NULL goal map.
         goalMap=0;
         pieces=0;
         return;
      }      
      goalMap = new StateMap(goalRange,cubies,numCubies);   
// these cubies have served their purpose here:
      delete[] cubies;      
// Prepare the pieces
      piecesLeft=numPieces=num;
      pieces=new MyPiece[numPieces];
      for (int i=0;i<numPieces;i++) {
         pieces[i].Init(goalRange,thePieces[i]);
      }
   }
   ~MyGoal() {
      if (pieces) delete[] pieces;
      if (goalMap) delete goalMap;
   }
   bool Solve(Piece theGoal) {   
      if (goalMap==0) // in case of overflow
         return false;   
      qsort(pieces,numPieces,sizeof(MyPiece),CompPiece);
      if (RecursiveSolve()) {
         CopyTheSolution(theGoal);            
         return true;
      } else return false;      
   }
   bool RecursiveSolve() {   
      piecesLeft-;   
                                 
      int target=goalMap->Corner();
      if (target<0) return false;
      MyPiece* P=pieces;
      for (int i=0;i<numPieces;i++,P++) {   // for all pieces   
         if (!P->Available()) continue;   // skip if used already
                               
         do {                        // for all versions
            while (P->GetSpot(target) >= 0)
            {                        // for all LDF corners
               if (P->Fits()) {            
                  P->Place();   
                  if (piecesLeft) {         // recurse until no pieces left
                     if (RecursiveSolve()) return true;
                  } else return true;
                  P->Unplace();                        
               }      
            }
         } while (P->NextRotation());
      }
      piecesLeft++;               
      return false;
   }   
   void CopyTheSolution(Piece theGoal) {
// The solution exists in the translations of the current rotated versions
// of the pieces.  These must be remapped back to the cubies list of theGoal.
// I fill the 3D indexed goal map array to temporarily hold the piece ids,
// and then scan through the cubies list to load these values by indexing
// through the goal map array.
      MyPiece* P=pieces;      
      for (int i=0;i<numPieces;i++,P++) { P->Copy();}
      Cubie* C=theGoal.theCubies;
      for (int i=0;i<theGoal.numCubies;i++,C++) {
         Spot goalSpot=Spot(*C);
         Spot mySpot=goalSpot-goalOffset;
         C->value=goalMap->state[mySpot.Offset(goalRange)];
      }
   }
};

BlockBuster
Boolean   BlockBuster(long numPieces, Piece thePieces[], Piece theGoal) {
      MyGoal* goal=new MyGoal(numPieces,thePieces,theGoal);
      bool rc=goal->Solve(theGoal);
      delete goal;
      return rc;
/*
// The following equivalent style of expression crashes on the second
// call to BlockBuster(...) (CodeWarrior Pro-3, with all updates),
// when it runs the destructor of goal before running Solve().
// However, it works fine for the first call (!?).
      MyGoal goal=MyGoal(numPieces,thePieces,theGoal);
      return goal.Solve(theGoal);
*/
}
 
AAPL
$99.18
Apple Inc.
+0.00
MSFT
$45.90
Microsoft Corpora
+0.00
GOOG
$568.27
Google Inc.
+0.00

MacTech Search:
Community Search:

Software Updates via MacUpdate

Cocktail Family License (5 Macs) 7.6.1 -...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Cocktail 8.0 Beta 2 - General maintenanc...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
QuickBooks 2015 16.0.0.1352 R1 - Financi...
QuickBooks 2015 helps you manage your business easily and efficiently. Organize your finances all in one place, track money going in and out of your business, and spot areas where you can save.... Read more
Mac DVDRipper Pro 5.0.1 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
Apple OS X bash Update 1.0 - Fix for sec...
The OS X bash Update fixes a security flaw in the bash UNIX shell on OS X 10.9.5 (also on OS X 10.8 and 10.7 [see Related Links below]). OS X 10.9.5 or later Downloads for OS X 10.8 and OS X 10.7 in... Read more
SyncTwoFolders 2.0.5 - Syncs two user-sp...
SyncTwoFolders simply synchronizes two folders. It supports synchronization across mounted network drives and it is a possibility to run a simulation showing in a log what will be done. Please visit... Read more
FinderPop 2.5.7 - Classic Mac utility, n...
FinderPop is a Universal preference pane that extends OS X's contextual menus using a FinderPop Items folder much as the Apple Menu Items folder used to do for the Apple menu. It has other features... Read more
VueScan 9.4.45 - 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
LibreOffice 4.3.2.2 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
calibre 2.4 - Complete e-library managem...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more

Latest Forum Discussions

See All

The Maze Runner Review
The Maze Runner Review By Lee Hamlet on October 2nd, 2014 Our Rating: :: A NICE CHANGE OF PACEUniversal App - Designed for iPhone and iPad The Maze Runner is a surprisingly enjoyable movie tie-in that will succeed in keeping... | Read more »
RPG Soul of Deva (Games)
RPG Soul of Deva 1.0.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.0 (iTunes) Description: SPECIAL PRICE56% OFF(USD 8.99 -> USD 3.99)!!! Demons attack humans, and humans live in fear of them...Set off on a... | Read more »
Banner Saga (Games)
Banner Saga 1.0.17 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0.17 (iTunes) Description: NOTE: The Banner Saga does NOT run on iPhone 4. iPhone 4S and more modern devices recommended. | Read more »
Beatbuddy HD (Games)
Beatbuddy HD 1.0.2 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.2 (iTunes) Description: **IMPORTANT** Beatbuddy runs only on iPhone 6, 6 Plus, 5, 5c, 5s, iPad 4, iPad Mini Retina and iPad Air. | Read more »
Spirits of Spring (Games)
Spirits of Spring 1.0.1 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.1 (iTunes) Description: From the creators of the award-winning empathy game, Papo & Yo, comes a tale about finding strength. | Read more »
I am a brave knight (Games)
I am a brave knight 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Do you have ten minutes to live a life? | Read more »
iKeywi - Customizable 5-Row Keyboard (U...
iKeywi - Customizable 5-Row Keyboard 1.0 Device: iOS Universal Category: Utilities Price: $.99, Version: 1.0 (iTunes) Description: Want to add an extra row to your iPhone/iPad? One of the most popular keyboard extension in iOS... | Read more »
Manage Your Cloud – Wunderlist Now Suppo...
Manage Your Cloud – Wunderlist Now Supports Dropbox Posted by Jessica Fisher on October 1st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Nexticy Review
Nexticy Review By Jennifer Allen on October 1st, 2014 Our Rating: :: IDEAL FORM CREATIONiPad Only App - Designed for the iPad Nexticy allows you to make your own forms for research purposes or to organize your business better. It’s... | Read more »
Tiny Troopers: Alliance Marches onto the...
Tiny Troopers: Alliance Marches onto the App Store Tomorrow Posted by Jessica Fisher on October 1st, 2014 [ permalink ] Tiny Troopers: Alliance, by Kukouri, is a | Read more »

Price Scanner via MacPrices.net

Apple drops prices on refurbished 27-inch iMa...
The Apple Store has dropped prices on Apple Certified Refurbished 27″ iMacs, now available for up to $340 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27... Read more
Logitech Type+ iPad Air Keyboard Case: Laptop...
If you want to make your iPad Air look and feel more like a laptop for productivity use, as well as protect it from impacts, spills, and scratches while on the move, the new Logitech Type+, a... Read more
ASUS, Lenovo, and Amazon Slug It Out For Tabl...
According to market intelligence firm ABI Research, Apple and Samsung have led the touchscreen tablet market by a substantial margin since Apple energized the category back in 2010. However, ABI says... Read more
Branded Tablet Growth Expected to Disappoint...
ABI Research says the 200 million annual shipments milestone for branded tablets continues to elude OEM vendors, and overall growth for 2014 is set to come in at a disappointing 2.5 percent. Apple... Read more
Amazon offers 13-inch MacBook Air for $899, $...
Amazon.com has the 13″ 1.4GHz 128GB MacBook Air on sale for $100 off MSRP including free shipping: - 13″ 1.4GHz 128GB MacBook Air: $899.99 Read more
Apple resting On Its iPhone Laurels? – The ‘B...
Apple calls its new iPhone 6 and 6 Plus “The Biggest Advancements in iPhone History,” but does reality live up to the hype? “Seldom have so many waited so breathlessly for so little,” tweeted veteran... Read more
Roundup of Apple Mac and iPad Education disco...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Apple Boycotts German Magazine Computer Bild...
Apple has revoked its PR accreditation of Germany’s Computer Bild, Europe’s best-selling PC magazine, in reaction to Bild’s posting of a “#Bentgate” YouTube video. Axel Telzerow, editor in chief of... Read more
iPhone 6 & iPhone 6 Plus Available in Chi...
Apple has announced that iPhone 6 and iPhone 6 Plus will be available in China beginning Friday, October 17 from the Apple Online Store (http://www.apple.com), Apple’s retail stores, and an expansive... Read more
MacBook Airs on sale for $100 off MSRP, start...
Best Buy has the new 2014 MacBook Airs on sale for $100 off MSRP on their online store. Choose free home shipping or free local store pickup (if available). Prices valid for online orders only, in-... Read more

Jobs Board

*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* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, 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* 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
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.