TweetFollow Us on Twitter

Mar 01 Challenge Volume Number: 17 (2001)
Issue Number: 3
Column Tag: Programmer's Challenge

Programmer's Challenge

By Bob Boonstra, Westford, MA

DragSort

I'll confess. I've done it. More than once, actually. It's probably not legal, strictly speaking. But how bad can it be. I mean, lots of people must do it. It's not something truly evil like, well, like Napster.

What am I talking about? Downloading music. From the internet. Music that other people posted, music that I haven't purchased. Yet, that is. Music posted to the UseNet alt.binaries.sounds.* newsgroups.

What does this have to do with the Programmer's Challenge? Downloading Usenet binaries is a (perhaps contrived) motivation for this month's problem, that of sorting a list of items in a particular way. Large binaries are posted in a sequence of parts, and newsreaders thread the parts based on sequence information included by convention in the subject line. But sometimes the subject line contains information that confuses the sequencing, meaning that the parts need to be sorted manually before the binary information can be extracted. With the newsreader I use, the parts are sorted by dragging items from one position in the list to another position, until the parts appear in the correct order.

Your Challenge is to find an efficient way to perform this sort. Efficient in this case means minimizing the amount of tiresome clicking and dragging needed to put the parts in the correct order. Specifically, you want to minimize the cumulative number of positions that you need to move to select the part to be dragged, and the number of positions you need to drag the parts. An example in a later paragraph will make this a little clearer.

Oh, and before you turn me in to the authorities, downloading music from the internet allows one to sample the music before deciding whether to buy it. We all, of course, buy what we keep.

The prototype for the code you should write is:

typedef struct Move {      /* describes moves used to sort itemsToSort */
   long selectPosition;   /*   select this item in the array, origin 0 */
   long dragToPosition;   /*   drag selected item to this position in the array, origin 0 */
} Move;

long /* numMoves */ DragSort(
   long itemsToSort[],         /* array of items to be sorted */
   long numItemsToSort,      /* number of itemsToSort */
   long startPosition,         /* item initially selected */
   Move sortMoves[]            /* store Moves that sort the array here */
);

Your DragSort routine will be called with a list of itemsToSort, a count of the number of items in the list (numItemsToSort), and the element of the list initially selected (selectPosition). DragSort should calculate a sequence of Moves that reorder the list into ascending order by moving the item located at one position in the list (selectPosition) to another position in the list (dragToPosition). Moves are returned in the sortMoves array, and the number of Moves needed to sort the array should be returned by DragSort.

Sounds simple and boring, right? The catch is in how your sort solution is scored. You are penalized one point for each position move your solution makes while performing the sort - one point for each position between your current location and the selectPosition of the next Move, and one point for each position between that selectPosition and the dragToPosition. When a Move is completed, your current position is the dragToPosition. The penalty for the next Move is the number of positions between the previous dragToPosition and the current selectPosition, plus the distance from the current selectPosition and the current dragToPosition, etc.

Imagine, for example, that you are asked to sort the following list, with a startPosition of 0:

            6 1 2 3 5 4

You might employ a bubble sort. Your first Move is to select the 2nd item in the list and move it to the 1st position, at a cost of two penalty points (moving from [0] to [1], and dragging from [1] to [0]). The list now looks like this:

            1 6 2 3 5 4

Next you might move the 3rd item to the 2nd position, at a cost of 3 penalty points (moving from [0] to [2], and dragging from [2] to [1]), leaving the list like this:

            1 2 6 3 5 4

Then you might move the 4th item to the 3rd position, at a cost of 3 more penalty points. Then the 6th item to the 4th position (cost 5 points), and the 6th item to the 5th position (cost 3 points). The list would then be correctly sorted, at a cost, if I have counted correctly, of 16 points.

And you would lose the Challenge.

A more successful contestant would sort the list at a cost of 7 points as follows:

            6 1 2 3 5 4
            1 2 3 5 4 6 (cost 5 points)
            1 2 3 4 5 6 (cost 2 points)

In addition to the points incurred for dragging list items around, a penalty of 1 point will be assessed for each millisecond of execution time. The winner will be the entry that correctly sorts a sequence of lists while accumulating the fewest penalty points. The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal. You may provide a solution in Java instead, provided you also provide a test driver equivalent to the C code provided on the web for this problem.

Three Months Ago Winner

Congratulations to Tom Saxton for winning the December Crutches Challenge. Motivated by a broken foot injury to a member of the family, this variation on the traveling salesperson problem required contestants to find optimal way of moving a set of objects from one location to another, operating with connectivity constraints among the locations, and limited by a maximum carrying capacity. The object was to minimize a score that was a combination of the length of the path traversed and the amount of execution time required to complete the solution. Tom's entry was not the fastest, but it did compute a more optimal path than the second-place entry by Ernst Munter.

Tom first calculates the distance from each node to each other node in the _MapConnections function. He then calculates a baseline solution in the _CatCrutchesCore routine, a solution that picks up the closest object when nothing is being carried, delivers the closest object when something is being carried, and tries to move objects closer to their eventual destination when there is spare carrying capacity. Tom then successively refines the baseline solution until a time allocation is exceeded. Refinement uses a variant of the "Algorithm of the Gods", published in Scientific American in March, 1997 (see http://www.scientificamerican.com/0397issue/0397amsci.html). Basically, the algorithm makes small perturbations in the baseline solution to see if the perturbed solution results in a lower cost.

Ernst's entry was approximately three times faster than Tom's, but it resulted in less optimal solutions. Actually, Ernst's solutions were slightly shorter in approximately half of the test cases, but Tom's were shorter by 1/3 to 1/2 in the larger test cases, giving him the win.

I used 12 test cases for evaluation, where the number of nodes ranged from 10 to 200, the number of connections was as high as 2200, and the number of tasks to be accomplished ranged from 20 for the small graphs to 500 for the larger graphs.

The table below lists, for each of the solutions submitted, the total execution time, the cumulative distance traveled to accomplish all of the delivery tasks, and the number of points earned. As points were incurred based on distance traveled and elapsed time, a smaller number of points was better. 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 solution marked with an asterisk did not complete the larger problems in a reasonable amount of time.

NameTotal Time (msec)Distance MovedTotal PointsCode SizeData SizeLang
Tom Saxton (165)12773.54568155120188004586C++
Ernst Munter (701)4408.65574775965114852324C++
J. S.***5948344C++

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 281
2. Saxton, Tom 96
3. Maurer, Sebastian 68
4. Rieken, Willeke 65
5. Boring, Randy 52
6. Shearer, Rob 48
7. Taylor, Jonathan 36
8. Wihlborg, Charles 29

... and the Top Contestants Looking For a Recent Win

Starting this month, in order to give some recognition to other participants in the Challenge, we are also going to list the high scores for contestants who have accumulated points without taking first place in a Challenge. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

9. Downs, Andrew 12
10. Jones, Dennis 12
11. Day, Mark 10
12. Duga, Brady 10
13. Fazekas, Miklos 10
14. Flowers, Sue 10
15. Sadetsky, Gregory 10
16. Selengut, Jared 10
17. Strout, Joe 10
18. Hala, Ladislav 7
19. Miller, Mike 7
20. Nicolle, Ludovic 7
21. Schotsman, Jan 7
22. Widyyatama, Yudhi 7
23. Heithcock, JG 6

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

Crutches.cpp
Copyright © 2000
Tom Saxton
//
// Crutches Challenge Solution, December 2000.
// (c) 2000, Tom Saxton
//
#include "Crutches.h"

#include <Events.h>

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

// the basics
enum { fFalse = 0, fTrue = 1 };

// disable asserts
#define Assert(f)

// how long should we spend trying to find a better answer?
#define dtickSecond 60
#define dtickMax (1*dtickSecond)

// random
static unsigned short URand(unsigned short uMac);

// heapsort
typedef unsigned long INDEX;
typedef int (*PFNCMP)(INDEX i1, INDEX i2, void *pv);
extern void HeapSort(void *prgfoo, INDEX iMac, int cbFoo, PFNCMP pfncmp);

// maximum distance value
#define distMax 0x7FFFFFFF

// structures for mapping problem to node indices
typedef struct TSK TSK;
struct TSK
{
   long itaskObject;
   long inodeStart;
   long inodeCur;
   long inodeDst;
   long wgt;
   int  fWanted;
   long rankDrop;
   TSK  *ptskNext;
};

typedef struct ENODE ENDOE;
struct ENODE
{
   long inode;
   Node node;
   long cobj;
   long rankGrab;
};

// connection map stuff
typedef struct CONN CONN;
struct CONN
{
   // base information for this connection
   long inode1;
   long inode2;
   long dist;
};

typedef struct CMAP CMAP;
struct CMAP
{
   long distDirect;
   long distPath;
};

typedef struct NODC NODC;
struct NODC // node connection, used when looking for paths between nodes
{
   long distFromStart;
   int fCheckNeighbors;
};

static CONN *s_paconn;
static long s_cconn;
static CMAP *s_pacmap;
static NODC *s_panodc;

// translation globals
static const Node *s_panode;
static ENODE *s_pdnnode;
static long s_cnode;
static TSK *s_patsk;
static TSK *s_ptskFirst;
static long s_ctsk;
static long s_wgtCarryMost;

// core algorithm stuff
static long _CactCrutchesCore(long inodeStart, Action paact[], 
      long cactMax, long distStop, long *painodePath, 
      long *paitskOrder, long *paitskOrderUsed, long *pdist);
static long _InodeGetTarget(long inodeCur, long cobjCarry, 
      int fUseWantedFlag, long *paitskOrder, long *pcnodeOrderGrab, 
      long *pctskOrderDrop);
static void _RandomizeOrder(long iTry, long cTry, long ctsk, 
      long cnode, const long paitskOrderOld[], 
      long paitskOrderNew[]);

// translation helpers
static long _InodeFromNode(Node node);
static int _CmpEnodeNode(INDEX i1, INDEX i2, void *pv);
static int _CmpEnodeInode(INDEX i1, INDEX i2, void *pv);

// action functions
static int _FTakeStep(long inodeDst, long cactMax, 
   Action paact[], long *pcact, long *pinodeCur, long *pdist);
static int _FFollowPath(long cactMax, Action paact[], 
      long *pcact, long *pinodeCur, long *pwgtCarry, 
long *pcobjCarry, long cnodePath, const long painodePath[]);
static int _FGrabObject(long cactMax, Action paact[], 
   long *pcact, long *pwgtCarry, long *pcobjCarry, long inode, 
      long itsk);
static int _FDropObject(long cactMax, Action paact[], 
   long *pcact, long *pwgtCarry, long *pcobjCarry, long inode, 
      long itsk);

// connection map functions
static void _MapConnections(long cconn, 
      const Connection paconnection[]);
static void _FreeConnectionMap(void);
static int _FConnectedNodes(long inode1, long inode2, 
      long *pdist);
static long _CnodeFindMinPath(long inodeStart, 
      long inodeEnd, long painodePath[]);
static void _ComputeNodeDistances(long inode);
static long _InodeNearestTask(long inodeCur);
static inline long _DistNodeToNode(long inode1, long inode2)
{
   return s_pacmap[inode2*s_cnode + inode1].distPath;
}

static void _ResetState();
static TSK *_PtskRemoveTsk(TSK *ptsk);

Crutches
long /* actions in solution */ Crutches (
  const Node panode[],                  /* Nodes defining the problem */
  long cnode,                                 /* number of Nodes */
  const Connection paconnection[],   /* Connections between nodes */
  long cconn,                               /* number of Connections */
  const Task patask[],                  /* objects to be moved */
  long ctask,   /* objects to be moved, numbered as index into objectsToMove */
  Node nodeStart,                           /* start from this node */
  Weight wgtCarryMost,            /* maximum weight that you can carry */
  Action paact[],                           /* return your solution here */
  long cactMax                              /* size of solutionPath array */
)
{
   long cactBest = 0;
   long *paitskOrderTry = NULL;
   long *paitskOrderBest = NULL;
   long *paitskOrderUsed = NULL;
   long *painodePathBuffer = NULL;
   
   // start the clock running...
   long tickStart = TickCount();
   
   // allocate the memory buffers we need (_MapConnections also allocates memory)
   try
   {
      s_pdnnode =         new ENODE[cnode];
      s_patsk =           new TSK[s_ctsk = ctask];
      paitskOrderTry =    new long[ctask+cnode];
      paitskOrderBest =   new long[ctask+cnode];
      paitskOrderUsed =   new long[ctask+cnode];
      painodePathBuffer = new long[s_cnode];
   } catch (...) {
         printf("Bob, can I have some more memory?
            I need %ld bytes, plus some more for the 
                  connections map.\n",
          sizeof(ENODE)*cnode
         +sizeof(TSK)*ctask
         +sizeof(long)*(ctask+cnode)*3
         +sizeof(long)*s_cnode
         );
      throw;
   }
   if (s_pdnnode == NULL || s_patsk == NULL || 
            paitskOrderUsed == NULL || paitskOrderTry == NULL || 
         paitskOrderBest == NULL || painodePathBuffer == NULL)
      goto LCleanup;

   // initialize the node entry array
   s_cnode = cnode;
   s_panode = panode;
   for (long inode = 0; inode < cnode; ++inode)
   {
      ENODE *penode = &s_pdnnode[inode];
      penode->inode = inode;
      penode->node = panode[inode];
      penode->cobj = 0;
   }

   // sort node entries by node value
   HeapSort(s_pdnnode, cnode, sizeof(s_pdnnode[0]), 
               _CmpEnodeNode);
   
   // fill in TSK records, with inode values
   for (long itask = 0; itask < ctask; ++itask)
   {
      TSK *ptsk = &s_patsk[itask];
      const Task *ptask = &patask[itask];
      
      ptsk->itaskObject = itask;
      ptsk->inodeStart = _InodeFromNode(ptask->fromNode);
      ptsk->inodeDst = _InodeFromNode(ptask->toNode);
      ptsk->wgt = ptask->weight;
   }
   
   _MapConnections(cconn, paconnection);
   
   long inodeStart = _InodeFromNode(nodeStart);
   
   // sort node entries by node index
   HeapSort(s_pdnnode, cnode, sizeof(s_pdnnode[0]), 
               _CmpEnodeInode);
   
   // get the baseline solution
   _ResetState();
   s_wgtCarryMost = wgtCarryMost;
   long distBest;
   cactBest = _CactCrutchesCore(inodeStart, paact, cactMax, 
         distMax, painodePathBuffer, NULL, paitskOrderUsed, 
         &distBest);

   // if we have a non-trivial number of tasks, try to improve our solution using partial 
   // ordering info from the baseline
   // based loosely on "Algorithm of the Gods", Scientific American, March 1997
   if (ctask > 2)
   {
      long distToAccept = distMax;
      long cIter = 0;
      long cIterMax = 10 * cconn * ctask;
      long dtickNext = 0;

      BlockMove(paitskOrderUsed, paitskOrderBest, 
               sizeof(paitskOrderBest[0])*(ctask+cnode));

      for (long dtick = TickCount(); 
            (dtick -= tickStart) < dtickMax && cIter < cIterMax; 
            ++cIter, dtick = TickCount())
      {
         _ResetState();
         
         _RandomizeOrder(dtick, dtickMax, ctask, cnode, 
               paitskOrderBest, paitskOrderTry);
         
         long distTry;
      long cact = _CactCrutchesCore(inodeStart, paact+cactBest, 
               cactMax-cactBest, distToAccept, painodePathBuffer, 
               paitskOrderTry, NULL, &distTry);
         if (distTry < distToAccept)
         {
            distToAccept = distTry;
            BlockMove(paitskOrderTry, paitskOrderBest, 
               sizeof(paitskOrderBest[0])*(ctask+cnode));
            
            if (distTry < distBest)
            {
               distBest = distTry;
      BlockMove(paact+cactBest, paact, cact*sizeof(paact[0]));
               cactBest = cact;
            }
         }
      }
   }

LCleanup:
   _FreeConnectionMap();
   if (s_patsk != NULL)
   {
      delete s_patsk;
      s_patsk = NULL;
   }
   if (s_pdnnode != NULL)
   {
      delete s_pdnnode;
      s_pdnnode = NULL;
   }
   if (paitskOrderTry != NULL)
      delete paitskOrderTry;
   if (paitskOrderBest != NULL)
      delete paitskOrderBest;
   if (paitskOrderUsed != NULL)
      delete paitskOrderUsed;
   if (painodePathBuffer != NULL)
      delete painodePathBuffer;
   
   return cactBest;
}

_CactCrutchesCore
// core function to computer a solution, possibly using a partial node/task ordering array
static long _CactCrutchesCore(
   long inodeStart,
   Action paact[],
   long cactMax,
   long distStop,
   long *painodePath,
   long *paitskOrder,
   long *paitskOrderUsed,
   long *pdist
)
{
   int fSuccess = fFalse;
   long inodeCur = inodeStart;
   long cnodePath = 0;
   long iinodePath = 0;
   long cact = 0;
   long wgtCarry = 0;
   long cobjCarry = 0;
   long inodePath = -1;
   long inodeTarget = -1;
   long cnodeOrderGrab = 0, ctskOrderDrop = 0;

   {
      long iitskRank, iinodeRank;
      
      // reset the priority ranks
      for (iitskRank = 0; iitskRank < s_ctsk; ++iitskRank)
         s_patsk[iitskRank].rankDrop = -1;
      for (iinodeRank = 0; iinodeRank < s_cnode; ++iinodeRank)
         s_pdnnode[iinodeRank].rankGrab = -1;
         
      // if we have a priority order, set task ranks
      if (paitskOrder != NULL)
      {
         for (iitskRank = 0; iitskRank < s_ctsk; ++iitskRank)
         s_patsk[paitskOrder[iitskRank]].rankDrop = iitskRank;
         
      for (iinodeRank = 0; iinodeRank < s_cnode; ++iinodeRank)
            s_pdnnode[paitskOrder[s_ctsk+iinodeRank]].rankGrab = 
                     iinodeRank;
      }
   }
      
   for (long itskCur = *pdist = 0; itskCur < s_ctsk; )
   {
      TSK *ptskT;
      long inodeNext = -1;
      
      // drop any objects whose distination is the current node
      if (cobjCarry > 0)
      {
         for (ptskT = s_ptskFirst; ptskT != NULL; )
         {
   if (ptskT->inodeCur == -1 && ptskT->inodeDst == inodeCur)
            {
            if (!_FDropObject(cactMax, paact, &cact, &wgtCarry,
                      &cobjCarry, inodeCur, ptskT - s_patsk))
                  goto LCleanup;
               inodeTarget = -1;
               ptskT = _PtskRemoveTsk(ptskT);
               ++itskCur;
               continue;
            }
            ptskT = ptskT->ptskNext;
         }
         
         if (itskCur == s_ctsk)
            break;
      }
      
      // see if we want to grab or drop items at this node
      if (s_pdnnode[inodeCur].cobj > 0)
      {
         _ComputeNodeDistances(inodeCur);
         
         // clear the wanted flags for all objects
         for (ptskT = s_ptskFirst; ptskT != NULL; 
                  ptskT = ptskT->ptskNext)
            ptskT->fWanted = fFalse;
            
         long wgtWanted = 0;
         long cobjCarryWanted = 0;
         for(;;)
         {
            // find the object with the nearest desination
            TSK *ptskWant = NULL;
            long distBest = distMax;
            for (ptskT = s_ptskFirst; ptskT != NULL; 
                     ptskT = ptskT->ptskNext)
            {
               if (ptskT->fWanted || 
         (ptskT->inodeCur != inodeCur && ptskT->inodeCur != -1) 
                  || wgtWanted + ptskT->wgt > s_wgtCarryMost)
                  continue;
               
               long distLook;
               if (paitskOrder != NULL)
                  distLook = ptskT->rankDrop;
               else
         distLook = _DistNodeToNode(inodeCur, ptskT->inodeDst);
               if (distLook < distBest)
               {
                  distBest = distLook;
                  ptskWant = ptskT;
               }
            }
         
            // bail if we didn't find anything more to pick up
            if (ptskWant == NULL)
               break;
               
            // mark the new item as wanted
            ptskWant->fWanted = fTrue;
            wgtWanted += ptskWant->wgt;
            cobjCarryWanted += 1;
         }
         
         // did anything change?
         for (ptskT = s_ptskFirst; ptskT != NULL; 
                     ptskT = ptskT->ptskNext)
   if ((ptskT->inodeCur == -1) != (ptskT->fWanted != fFalse))
               break;
         if (ptskT != NULL)
         {
      inodeTarget = _InodeGetTarget(inodeCur, cobjCarryWanted, 
               fTrue/*fUseWantedFlag*/, paitskOrder, &cnodeOrderGrab, 
               &ctskOrderDrop);
            if (inodePath != inodeTarget)
            {
               // make sure we have a path to the current target
               inodePath = inodeTarget;
      if ((cnodePath = _CnodeFindMinPath(inodeCur, inodePath, 
                  painodePath)) == 0)
                  goto LGiveUp;
               iinodePath = 0;
            }
            inodeNext = painodePath[iinodePath];
            
            // clear items that aren't going to be helped by the path to the new target
            for (ptskT = s_ptskFirst; ptskT != NULL; 
                     ptskT = ptskT->ptskNext)
            {
               if (!ptskT->fWanted)
                  continue;
               
               _ComputeNodeDistances(ptskT->inodeDst);
               if (_DistNodeToNode(ptskT->inodeDst, inodeNext) > 
                        _DistNodeToNode(ptskT->inodeDst, inodeCur))
               {
                  ptskT->fWanted = fFalse;
                  wgtWanted -= ptskT->wgt;
                  cobjCarryWanted -= 1;
               }
            }
            
            // drop items we're carrying that we no longer want
            for (ptskT = s_ptskFirst; ptskT != NULL; 
               ptskT = ptskT->ptskNext)
               if (ptskT->inodeCur == -1 && !ptskT->fWanted)
            if (!_FDropObject(cactMax, paact, &cact, &wgtCarry, 
                        &cobjCarry, inodeCur, ptskT - s_patsk))
                     goto LCleanup;
            
            // grab wanted items we're not carrying
            for (ptskT = s_ptskFirst; ptskT != NULL; 
                        ptskT = ptskT->ptskNext)
               if (ptskT->inodeCur == inodeCur && ptskT->fWanted)
            if (!_FGrabObject(cactMax, paact, &cact, &wgtCarry, 
                              &cobjCarry, inodeCur, ptskT - s_patsk))
                     goto LCleanup;
         }
      }
      
      // pick the current target node
      if (inodeTarget == -1)
         inodeTarget = _InodeGetTarget(inodeCur, cobjCarry, 
         fFalse/*fUseWantedFlag*/, paitskOrder, &cnodeOrderGrab, 
               &ctskOrderDrop);
      
      // make sure we have a path to the current target
      if (inodePath != inodeTarget)
      {
         inodePath = inodeTarget;
      if ((cnodePath = _CnodeFindMinPath(inodeCur, inodePath, 
                        painodePath)) == 0)
            goto LGiveUp;
         iinodePath = 0;
      }
      inodeNext = painodePath[iinodePath];
      if (++iinodePath >= cnodePath)
         inodeTarget = inodePath = -1;
      
      // drop any objects not helped by our pending move
      if (cobjCarry > 0)
      {
         for (ptskT = s_ptskFirst; ptskT != NULL; 
                        ptskT = ptskT->ptskNext)
         {
            if (ptskT->inodeCur != -1)
               continue;
            
            _ComputeNodeDistances(ptskT->inodeDst);
            if (_DistNodeToNode(ptskT->inodeDst, inodeNext) > 
                     _DistNodeToNode(ptskT->inodeDst, inodeCur))
            if (!_FDropObject(cactMax, paact, &cact, &wgtCarry, 
                           &cobjCarry, inodeCur, ptskT - s_patsk))
                  goto LCleanup;
         }
      }
      
      // move
if (!_FTakeStep(inodeNext, cactMax, paact, &cact, &inodeCur, 
                     pdist))
         goto LCleanup;
      
      if (*pdist > distStop)
      {
         // fix the object counts
         for (long inodeClean = 0; inodeClean < s_cnode; 
                        ++inodeClean)
            s_pdnnode[inodeClean].cobj = 0;
         goto LGiveUp;
      }
   }
   // set the actual ordering used
   long itskOrder, inodeOrder;
   if (paitskOrderUsed != NULL)
   {
      for (itskOrder = 0; itskOrder < s_ctsk; ++itskOrder)
      {
         TSK *ptskSetOrder = &s_patsk[itskOrder];
         
         if (ptskSetOrder->rankDrop == -1)
            ptskSetOrder->rankDrop = ctskOrderDrop++;
         paitskOrderUsed[ptskSetOrder->rankDrop] = itskOrder;
      }
      for (inodeOrder = 0; inodeOrder < s_cnode; ++inodeOrder)
      {
         ENODE *penode = &s_pdnnode[inodeOrder];
         if (penode->rankGrab == -1)
            penode->rankGrab = cnodeOrderGrab++;
         paitskOrderUsed[s_ctsk+penode->rankGrab] = inodeOrder;
      }
   }
LGiveUp:
   fSuccess = fTrue;
      
LCleanup:
   if (!fSuccess)
      *pdist = distMax;
   return cact;
}

_InodeGetTarget
static long _InodeGetTarget(long inodeCur, long cobjCarry, 
            int fUseWantedFlag, long *paitskOrder, 
            long *pcnodeOrderGrab, long *pctskOrderDrop)
{
   TSK *ptsk;
   // if we have a chosen order, use that
   if (paitskOrder != NULL)
   {
      if (cobjCarry == 0)
      {
         long inodeGrab = -1;
         long rankGrab = s_cnode;
         for (long inode = 0; inode < s_cnode; ++inode)
         {
            ENODE *penode = &s_pdnnode[inode];
            if (penode->cobj == 0)
               continue;
            
            if (penode->rankGrab < rankGrab)
            {
               rankGrab = penode->rankGrab;
               inodeGrab = inode;
            }
         }
         return inodeGrab;
      }
      else
      {
         TSK *ptskChoose = NULL;
         long rankChoose = s_ctsk;
for(ptsk = s_ptskFirst; ptsk != NULL; ptsk = ptsk->ptskNext)
         {
            int fCarried = fUseWantedFlag ? ptsk->fWanted : 
                                                      ptsk->inodeCur == -1;
            
            // only consider carried objects
            if (!fCarried)
               continue;
            
            // pick the one with the lowest rank
            if (ptsk->rankDrop < rankChoose)
            {
               rankChoose = ptsk->rankDrop;
               ptskChoose = ptsk;
            }
         }
         return ptskChoose->inodeDst;
      }
   }
   
   // otherwise if we're not carrying anything, go to the nearest node with an object
   _ComputeNodeDistances(inodeCur);
   if (cobjCarry == 0)
   {
      // pick the nearest node with a task
      long inodeTarget = _InodeNearestTask(inodeCur);
      
      // try to assign a priority to this node
      if (s_pdnnode[inodeTarget].rankGrab == -1)
         s_pdnnode[inodeTarget].rankGrab = (*pcnodeOrderGrab)++;
      return inodeTarget;
   }
   // otherwise deliver the object with the nearest destination
   TSK *ptskDeliver = NULL;
   long distBest = distMax;
for (ptsk = s_ptskFirst; ptsk != NULL; ptsk = ptsk->ptskNext)
   {
   if (fUseWantedFlag ? !ptsk->fWanted : ptsk->inodeCur != -1)
         continue;
   long distLook = _DistNodeToNode(inodeCur, ptsk->inodeDst);
      if (distLook < distBest)
      {
         distBest = distLook;
         ptskDeliver = ptsk;
      }
   }
   if (ptskDeliver->rankDrop == -1)
      ptskDeliver->rankDrop = (*pctskOrderDrop)++;
   return ptskDeliver->inodeDst;
}

#pragma mark -
// annealing functions

_RandomizeOrder
static void _RandomizeOrder(long iTry, long cTry, long ctsk, 
         long cnode, const long paitskOrderOld[], 
         long paitskOrderNew[])
{
   // copy the old to the new
   BlockMove(paitskOrderOld, paitskOrderNew, 
            sizeof(paitskOrderNew[0])*(ctsk+cnode));
   // swap some pairs of elements
long cpairSwap = 1 + (ctsk + cnode) * (cTry-iTry)/(4*cTry);
   while (cpairSwap- >= 0)
   {
      long itsk1, itsk2;
      // swap tasks or nodes?
      if (URand(ctsk + cnode) < ctsk)
      {
         // swap tasks
         itsk1 = URand(ctsk);
         itsk2 = URand(ctsk-1);
      }
      else
      {
         // swap nodes
         itsk1 = ctsk + URand(cnode);
         itsk2 = ctsk + URand(cnode-1);
      }
      if (itsk2 >= itsk1)
         ++itsk2;
      
      long itskT = paitskOrderNew[itsk1];
      paitskOrderNew[itsk1] = paitskOrderNew[itsk2];
      paitskOrderNew[itsk2] = itskT;
   }
}
 // utilities for translation to inode problem
#pragma mark -

_InodeFromNode
// find the index to the specified Node
static long _InodeFromNode(Node node)
{
   long iinodeMin, iinodeLast;
   
   iinodeMin = 0;
   iinodeLast = s_cnode - 1;
   
   while (iinodeMin < iinodeLast)
   {
      long iinodeMid = (iinodeMin + iinodeLast + 1)/2;
      
      if (s_pdnnode[iinodeMid].node > node)
         iinodeLast = iinodeMid - 1;
      else
         iinodeMin = iinodeMid;
   }
   
   return s_pdnnode[iinodeMin].inode;
}

_CmpEnodeNode
// compare two ENODE entries by their node values for HeapSort
static int _CmpEnodeNode(INDEX i1, INDEX i2, void *pv)
{
   ENODE *pdnnode = (ENODE *)pv;
   
   return pdnnode[i1].node - pdnnode[i2].node;
}
// compare two ENODE entries by their inode values for HeapSort
static int _CmpEnodeInode(INDEX i1, INDEX i2, void *pv)
{
   ENODE *pdnnode = (ENODE *)pv;
   
   return pdnnode[i1].inode - pdnnode[i2].inode;
}

#pragma mark -

_FTakeStep
static int _FTakeStep(long inodeDst, long cactMax, 
         Action paact[], long *pcact, long *pinodeCur, long *pdist)
{
   if (*pcact >= cactMax)
   {
      printf("OOM in _FTakeStep\n");
      return fFalse;
   }
   
   long dist;
   if (!_FConnectedNodes(*pinodeCur, inodeDst, &dist))
      return fFalse;

   *pdist += dist;
   *pinodeCur = inodeDst;
   Action *pact = &paact[(*pcact)++];
   pact->action = kMoveTo;
   pact->node = s_panode[inodeDst];
   return fTrue;
}

_FGrabObject
static int _FGrabObject(long cactMax, Action paact[], 
         long *pcact, long *pwgtCarry, long *pcobjCarry, 
         long inode, long itsk)
{
   if (*pcact >= cactMax)
   {
      printf("OOM in _FGrabObject\n");
      return fFalse;
   }
   
   Action *pact = &paact[(*pcact)++];
   TSK *ptsk = &s_patsk[itsk];
   
   pact->action = kPickUpObject;
   pact->object = ptsk->itaskObject;
   
   ptsk->inodeCur = -1;
   s_pdnnode[inode].cobj -= 1;
   
   ++(*pcobjCarry);
   *pwgtCarry += ptsk->wgt;
   return fTrue;
}

_FDropObject
static int _FDropObject(long cactMax, Action paact[], 
            long *pcact, long *pwgtCarry, long *pcobjCarry, 
            long inode, long itsk)
{

   if (*pcact >= cactMax)
   {
      printf("OOM in _FDropObject\n");
      return fFalse;
   }
   
   Action *pact = &paact[(*pcact)++];
   TSK *ptsk = &s_patsk[itsk];
   
   pact->action = kDropOffObject;
   pact->object = ptsk->itaskObject;
   
   ptsk->inodeCur = inode;
   if (ptsk->inodeDst != inode)
      s_pdnnode[inode].cobj += 1;
   
   -(*pcobjCarry);
   *pwgtCarry -= ptsk->wgt;

   return fTrue;
}

#pragma mark -

_MapConnections
static void _MapConnections(long cconn, const Connection paconnection[])
{
   s_cconn = cconn;
   
   try
   {
      s_paconn = new CONN[cconn];
      
      Assert(s_pacmap == NULL);
      s_pacmap = new CMAP[s_cnode*s_cnode];
      for (long iT = s_cnode*s_cnode; -iT >= 0; )
      {
         s_pacmap[iT].distDirect = -1;
         s_pacmap[iT].distPath = -1;
      }
      
      s_panodc = new NODC[s_cnode];
   }
   catch(...)
   {
         printf("Bob, I need more memory, somewhere 
                                                      around %ld bytes\n",
          sizeof(CONN)*cconn
         +sizeof(CMAP)*s_cnode*s_cnode
         +sizeof(NODC)*s_cnode
         );
   }
   
   for (long iconn = 0; iconn < cconn; ++iconn)
   {
      CONN *pconn = &s_paconn[iconn];
      const Connection *pconnection = &paconnection[iconn];
      
      pconn->dist = pconnection->distance;
      pconn->inode1 = _InodeFromNode(pconnection->node1);
      pconn->inode2 = _InodeFromNode(pconnection->node2);
      
      s_pacmap[pconn->inode1*s_cnode + pconn-
                                                   >inode2].distDirect = 
               pconn->dist;
      s_pacmap[pconn->inode2*s_cnode + pconn-
                                                   >inode1].distDirect = 
               pconn->dist;
   }
}

_FreeConnectionMap
static void _FreeConnectionMap()
{
   if (s_paconn != NULL)
   {
      delete s_paconn;
      s_paconn = NULL;
   }
   if (s_pacmap != NULL)
   {
      delete s_pacmap;
      s_pacmap = NULL;
   }
   if (s_panodc != NULL)
   {
      delete s_panodc;
      s_panodc = NULL;
   }
}

_FConnectedNodes
static int _FConnectedNodes(long inode1, long inode2, 
            long *pdist)
{
   long distT;
   if (pdist == NULL)
      pdist = &distT;
   *pdist = s_pacmap[inode1*s_cnode + inode2].distDirect;
   return *pdist != -1;
}

_ComputeNodeDistances
static void _ComputeNodeDistances(long inode)
{
   if (s_pacmap[inode*s_cnode + inode].distPath == -1)
      _CnodeFindMinPath(inode == 0 ? 1 : 0, inode, NULL);
}

_CnodeFindMinPath
static long _CnodeFindMinPath(long inodeStart, long inodeEnd, 
               long painodePath[])
{
   if (inodeStart == inodeEnd)
      return 0;
   // clear the NODC array
   for (long inode = 0; inode < s_cnode; ++inode)
   {
      s_panodc[inode].distFromStart = distMax;
      s_panodc[inode].fCheckNeighbors = fFalse;
   }
   
   // seed the fill with the end node
   s_panodc[inodeEnd].distFromStart = 0;
   s_panodc[inodeEnd].fCheckNeighbors = fTrue;
   
   long distPathKnown = s_pacmap[inodeStart*s_cnode + 
               inodeEnd].distPath;

   // expand out from base node until we've exhaused all possibilities
   for (int fExpanded = fTrue; fExpanded; )
   {
      fExpanded = fFalse;
      
      for (long inodeSrc = 0; inodeSrc < s_cnode; ++inodeSrc)
      {
         if (!s_panodc[inodeSrc].fCheckNeighbors)
            continue;
      for (long inodeDst = 0; inodeDst < s_cnode; ++inodeDst)
         {
            long dist;
            if (inodeSrc == inodeDst || 
                  !_FConnectedNodes(inodeSrc, inodeDst, &dist))
               continue;
            if (s_panodc[inodeSrc].distFromStart + dist < 
                        s_panodc[inodeDst].distFromStart)
            {
               s_panodc[inodeDst].distFromStart = 
                     s_panodc[inodeSrc].distFromStart + dist;
               s_panodc[inodeDst].fCheckNeighbors = fTrue;
               
               if (inodeDst == inodeStart && distPathKnown != -1)
                  if (s_panodc[inodeDst].distFromStart == 
                                                            distPathKnown)
                     goto LHavePath;
               fExpanded = fTrue;
            }
         }
         s_panodc[inodeSrc].fCheckNeighbors = fFalse;
      }
   }

   // if we need to, record the results for this node
   if (s_pacmap[inodeEnd*s_cnode + inodeEnd].distPath == -1)
   {
      for (long inodeConnect = 0; inodeConnect < s_cnode; 
                     ++inodeConnect)
      {
         long dist = s_panodc[inodeConnect].distFromStart;
         s_pacmap[inodeConnect*s_cnode + inodeEnd].distPath = dist;
      }
      s_pacmap[inodeEnd*s_cnode + inodeEnd].distPath = 0;
   }
   // walk from the start node to the end node
LHavePath:
   if (s_panodc[inodeStart].distFromStart == distMax)
   {
      printf("Hey! There's no way to get from node %ld to node %ld!\n", 
      s_panode[inodeStart], s_panode[inodeEnd]);
      return 0;
   }
   
   long cnodePath;
   long inodeCur;
   for (cnodePath = 0, inodeCur = inodeStart; 
                     inodeCur != inodeEnd; ++cnodePath)
   {
      long inodeNext;
      long distConnect;
      long distCur = s_panodc[inodeCur].distFromStart;
      for (inodeNext = 0; inodeNext < s_cnode; ++inodeNext)
         if (_FConnectedNodes(inodeNext, inodeCur,                                                                   
         &distConnect) && 
               s_panodc[inodeNext].distFromStart + distConnect == 
                           s_panodc[inodeCur].distFromStart)
            break;
      
      if (painodePath != NULL)
         painodePath[cnodePath] = inodeNext;
      inodeCur = inodeNext;
   }
   
   return cnodePath;
}

_InodeNearestTask
static long _InodeNearestTask(long inodeCur)
{
   // find the nearest object
   long distBest = distMax;
   long inodeBest = -1;
   for (long inodeLook = 0; inodeLook < s_cnode; ++inodeLook)
   {
      if (s_pdnnode[inodeLook].cobj == 0)
         continue;
      
      long dist = _DistNodeToNode(inodeCur, inodeLook);
      if (dist < distBest)
      {
         inodeBest = inodeLook;
         distBest = dist;
      }
   }
   
   return inodeBest;
}

#pragma mark -

_ResetState
static void _ResetState()
{
   
   // fill in object counts in dnnode
   for (long itsk = 0; itsk < s_ctsk; ++itsk)
   {
      TSK *ptsk = &s_patsk[itsk];

      ptsk->inodeCur = ptsk->inodeStart;
      if (ptsk->inodeCur != ptsk->inodeDst)
         s_pdnnode[ptsk->inodeCur].cobj += 1;
      
      // chain the records together
      ptsk->ptskNext = ptsk+1;
   }
   
   // set up the pointers at the start and end of the list
   s_ptskFirst = s_patsk;
   s_patsk[s_ctsk-1].ptskNext = NULL;
}

_PtskRemoveTs
static TSK *_PtskRemoveTsk(TSK *ptsk)
{
   TSK **pptsk = &s_ptskFirst;
   while ((*pptsk) != ptsk)
      pptsk = &(*pptsk)->ptskNext;
   
   TSK *ptskNext = ptsk->ptskNext;
   ptsk->ptskNext = NULL;
   *pptsk = ptskNext;
   return ptskNext;
}

#pragma mark -

URand
// return a random number in the range [0, uMax)
// NOTE: this only works for values that fit into a short
static unsigned short URand(unsigned short uMac)
{
   unsigned short u, uLim;
   
   // remove bias toward small numbers
#define wRandMax 0xFFFF
   Assert(sizeof(int) > sizeof(short));
   Assert(uMax < wRandMax);
   Assert(wRandMax > 0 && (wRandMax+1) > wRandMax);
   uLim = wRandMax - ((wRandMax+1) % uMac);
   do
   {
      u = (unsigned short)Random();
   } while (u > uLim);
      
   return u % uMac;
}

// heap sort code

static void _Swap(INDEX i1, INDEX i2, void *pv, int cbFoo);

HeapSort
void HeapSort(void *prgfoo, INDEX iMac, int cbFoo, PFNCMP pfncmp)
{
   INDEX iTop, iLast, iUnder, iCur;
   
   if (iMac == 0)
      return;
   
   iTop = iMac/2;       /* first initial line worker */
   iLast = iMac - 1;   /* the last element */
   
   for(;;)
   {
      if (iTop > 0)
      {
         /* hire a new supervisor, put him in his place */
         -iTop;
      }
      else
      {
         /* retire the chairman of the board,
         /* trickle the last line worker into his correct spot
         /**/
         _Swap(iLast, 0, prgfoo, cbFoo);
         
         if (iLast- <= 1)
            return;
      }
         
      iCur = iTop;            /* new supervisor */
      iUnder = iCur + iCur + 1;      /* first underling */
      
      while (iUnder <= iLast)
      {
         /* compare to the better underling */
         if (iUnder < iLast)
            if ((*pfncmp)(iUnder, iUnder+1, prgfoo) < 0)
               ++iUnder;
         if ((*pfncmp)(iCur, iUnder, prgfoo) < 0)            
         {
            /* promote the underling */
            _Swap(iCur, iUnder, prgfoo, cbFoo);
            
            /* check the demoted "supervisor" against his new underlings */
            iCur = iUnder;
            iUnder += iUnder + 1; /* first underling of demoted supervisor */
         }
         else
         {
            /* we're done sifting, terminate loop */
            break;
         }
      }
   }
}

_Swap
static void _Swap(INDEX i1, INDEX i2, void *pv, int cbFoo)
{
   char *pb1, *pb2, bT;
   int cb;
   pb1 = (char*)pv + (long)i1*cbFoo;
   pb2 = (char*)pv + (long)i2*cbFoo;

   for (cb = cbFoo; cb-; )
   {
      bT = *pb1;
      *pb1++ = *pb2;
      *pb2++ = bT;
   }
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

BBEdit 11.6.4 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
beaTunes 4.6.12 - Organize your music co...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music Library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
Tinderbox 7.0.1 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
FotoMagico 5.4 - 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
Direct Mail 4.3.9 - Create and send grea...
Direct Mail is an easy-to-use, fully-featured email marketing app purpose-built for OS X. It lets you create and send great looking email campaigns. Start your newsletter by selecting from a gallery... Read more
Tinderbox 7.0.1 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
Direct Mail 4.3.9 - Create and send grea...
Direct Mail is an easy-to-use, fully-featured email marketing app purpose-built for OS X. It lets you create and send great looking email campaigns. Start your newsletter by selecting from a gallery... Read more
FotoMagico 5.4 - 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
beaTunes 4.6.12 - Organize your music co...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music Library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
Spotify 1.0.49.125. - Stream music, crea...
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

The best sales on the App Store this wee...
The App Store has quite an exciting lineup of discount games this week that range across a variety of genres. It's a great opportunity to catch up on some of the premium games you may have been holding off on -- and some you can even grab for free... | Read more »
The best new games we played this week
Ah, here we are again at the close of another busy week. Don't rest too easy, though. We had a lot of great new releases in mobile games this week, and now you're going to have to spend all weekend playing them. That shouldn't be too much of a... | Read more »
Rollercoaster Tycoon Touch Guide: How to...
| Read more »
Rabbids Crazy Rush Guide: How to unlock...
The Rabbids are back in a new endless running adventure, Rabbids Crazy Rush. It's more ridiculous cartoon craziness as you help the little furballs gather enough fuel (soda) to get to the moon. Sure, it's a silly idea, but everyone has dreams --... | Read more »
Tavern Guardians (Games)
Tavern Guardians 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Tavern Guardians is a Hack-and-Slash action game played in the style of a match-three. You can experience high pace action... | Read more »
Slay your way to glory in idle RPG Endle...
It’s a golden age for idle games on the mobile market, and those addictive little clickers have a new best friend. South Korean developer Ekkorr released Endless Frontier last year, and players have been idling away the hours in the company of its... | Read more »
Tiny Striker: World Football Guide - How...
| Read more »
Good news everyone! Futurama: Worlds of...
Futurama is finding a new home on mobile in TinyCo and Fox Interactive's new game, Futurama: Worlds of Tomorrow. They're really doing it up, bringing on board Futurama creator Matt Groening along with the original cast and writers. TinyCo wants... | Read more »
MUL.MASH.TAB.BA.GAL.GAL (Games)
MUL.MASH.TAB.BA.GAL.GAL 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: ENDLESS UPGRADES. CONSTANT DANGER. ANCIENT WISDOM. BOUNCY BALLS. Launch Sale, 40% OFF for a very limited time!!! MUL.... | Read more »
Dungeon Rushers (Games)
Dungeon Rushers 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dungeon Rushers is a 2D tactical RPG combining dungeon crawler’s gameplay and turn based fights. Manage your team, loot dusty... | Read more »

Price Scanner via MacPrices.net

13-inch 2.0GHz Apple MacBook Pros on sale for...
B&H has the non-Touch Bar 13″ 2.0GHz MacBook Pros in stock today and on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz MacBook Pro Space Gray (... Read more
15-inch Touch Bar MacBook Pros on sale for up...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
12-inch Retina MacBooks on sale for $1150, $1...
B&H has 12″ 1.1GHz Retina MacBooks on sale for $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 12″ 1.1GHz Space Gray Retina MacBook: $1149 $150 off MSRP - 12″ 1.1GHz... Read more
Apple restocks refurbished 11-inch MacBook Ai...
Apple has Certified Refurbished 11″ MacBook Airs (the latest models recently discontinued by Apple), available for up to $170 off original MSRP. An Apple one-year warranty is included with each... Read more
Apple Park Opens to Employees in April With T...
Apple has announced that Apple Park, the company’s new 175-acre campus, will be ready for employees to begin occupying in April. The process of moving more than 12,000 people will take over six... Read more
Manhattan Neighbors for Safer Telecommunicati...
A new education and advocacy group focused on cell phone and wireless risks, Manhattan Neighbors for Safer Telecommunications, launched today at http://www.ManhattanNeighbors.org. Manhattan... Read more
Portable Dual DisplayPort Monitor Dock Enable...
IOGEAR has announced the launch of its USB-C Dual DisplayPort Monitor Portable Dock (GUC3CMST). The dock enables users to easily connect two DisplayPort monitors to a USB-C or Thunderbolt 3 laptop to... Read more
13-inch 2.7GHz Retina MacBook Pro on sale for...
Amazon.com has restocked the 13″ 2.7GHz/128GB Retina MacBook Pro (MF839LL/A) for $200 off MSRP including free shipping: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1099 $200 off MSRP This model tends to... Read more
Apple’s New iPad Ads Don’t Address Pro Users’...
Apple launched a new tranche of iPad Pro TV ads last week addressing actual queries and challenges from the Twitterverse, albeit using actors for the visuals. That’s great. As an iPad fan and heavy... Read more
Free Verbum Catholic Bible Study App For iOS
The Verbum mobile app runs on Logos’ powerful Bible software and is an advanced resource for mobile Catholic study. The Verbum app surrounds the Bible with the Tradition. Verbum comes with 15 free... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions- Chicago...
SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Manager *Apple* Systems Administration - Pu...
Req ID 3315BR Position Title Manager, Apple Systems Administration Job Description The Manager of Apple Systems Administration oversees the administration and Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Manager *Apple* Systems Administration - Pu...
Req ID 3315BR Position Title Manager, Apple Systems Administration Job Description The Manager of Apple Systems Administration oversees the administration and Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.