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

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

Latest Forum Discussions

See All

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

Price Scanner via MacPrices.net

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

Jobs Board

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