TweetFollow Us on Twitter

Feb 97 Challenge

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

Programmer's Challenge

By Bob Boonstra, Westford, MA

Othello™

This month's Challenge is going to be another round-robin competition for a well-known board game - this time the game of Othello. The classic game of Othello is played on an 8x8 board using discs that are black on one side and white on the other side. The game starts with four discs in the center squares of the board, two black discs on diagonally adjacent squares, and two white discs on the other diagonally adjacent squares. Players alternate placing an additional disc, with black moving first. A move consists of "outflanking" one or more of your opponent's discs. Outflanking means placing a disc so that at least one row of your opponent's discs is bordered by a disc of your color, including the disc just placed on the board. A row is defined as one or more discs of a single color in a continuous straight horizontal, vertical, or diagonal line. When a player moves, the row or rows of outflanked discs are flipped over showing his or her color. If a player cannot outflank a disc, the turn is forfeited and the opponent takes another turn. The game is over when the board is filled or neither player can move. The player with the most discs showing is the winner.

In this Challenge, the game will be generalized to boards larger than 8x8. The prototype for the code you should write is:

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


For your first move, Othello will be called with newGame set to TRUE. The size of the board, an even number between 8 and 64, will be provided in boardSize. On your first move you should initialize the board with white tiles at (row,col) = (boardSize/2-1,boardSize/2-1) and (boardSize/2,boardSize/2), and black tiles at (boardSize/2-1,boardSize/2) and (boardSize/2,boardSize/2-1). Rows and columns are numbered from 0 to boardSize-1. If playBlack is TRUE, you are to play the black pieces, and therefore play first. Otherwise, you play the white pieces. Your code and the code of an opponent will alternate play. Your opponent's move will be provided in (oppRow, oppCol), which will be set to (-1,-1) if your opponent is unable to move or if you are moving first. When your code is called you should flip your tiles that were outflanked by your opponent's move, calculate your own move, and store it in (*moveRow, *moveCol). If you are unable to move, store the values (-1,-1). If for any reason you believe your opponent has made an illegal move, Othello should return a value of FALSE, otherwise it should return TRUE.

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

The Challenge will be scored by a tournament where each entry plays against each other entry twice for each of a number of board sizes, once playing the black pieces and once playing the white pieces. In the event that a large number of entries are received, another fair tournament schedule may be used. The score will be based on the margin of victory (or loss) and the execution time used to compute the moves. For each game, the score will be computed by

[(# of player's pieces showing - # of opponent's pieces showing) - (execution time in seconds)/30] /

(boardSize*boardSize)

The player with the highest score for all games in the tournament will be the winner.

Those of you needing more information about the rules of the game can check out your local toy store, or look at http://www.daimi.aau.dk/~tusk/pbmserv/othello/othello.rules.html. Other information can be found at http://www.armory.com/~iioa/othguide.html, the International Internet Othello Association page.

Othello is a registered trademark of Tsukuda Original, licensed by Anjar Co., copyright 1973, 1990 by Pressman Toy Corporation.

Three Months Ago Winner

Congratulations to Thomas Studer (Syracuse, N.Y.) for submitting the winning entry to the Router Rules Challenge. The problem was to generate a set of (mask, value, allow/deny) triplets that could be used by a router to allow net access to a specified set of subnet addresses. Given a subnet address, the rules would be scanned in sequence by the router, and the first rule to fire would determine whether access was allowed or denied. A rule fires when the subnet address, logically ANDed with the rule mask, is equal to the rule value. Solutions were to minimize a score that was the sum of two quantities, the number of rules generated, and the time taken to generate those rules (in half-seconds).

Of the six solutions I received, only two of them worked correctly for my test cases. The other four either generated rules that produced incorrect results for some input subnet values or had not completed execution after running overnight. Thomas' winning solution assigns each input value to a group determined by the number of bits set in each "chunk" of 1, 2, 4, or 8 bits. The code then uses this mapping to search for "buddy" input values that differ in only one bit position. When such a "buddy" value is found, the values are combined, and a mask is updated to indicate which bits should be masked out in a router rule. The code makes use of three large pre-built BitGrpMapper tables that allow Thomas to calculate the number of bits set in each chunk of 2, 4, or 8 bits. For each chunk of size n, these tables represent the number of bits set in each input value as a base n+1 number, an interesting and compact representation.

The second-place solution by Alan Hart used a recursive technique to generate the Karnough map representing the allowed values. While this approach generated more rules (and therefore a poorer score) than the winning solution, it ordered the rules more optimally, in that rules governing a larger number of allowed subnets occurred earlier. This was not a criterion for scoring this Challenge, but it would be an important real-world consideration.

More compact rule sets than those generated by the two correct solutions might be possible. The very long-running solution mentioned above appeared to generate a small number of rules, half as many in some cases, at significant execution time expense.

The table below provides the language, code size, and data size for each of the six entries received. For the two correct entries, it also provides the score (based on rules generated and execution time), the average number of rules scanned before an allowed subnet value is granted access (summed over all test cases), and the total number of rules generated for all test cases.

Name Language Score Avg Rules Rules Gen Code Data

Thomas Studer C++ 3365 1414 3365 3844 12824

Alan Hart C 4716 1193 4715 1472 148

E. M. C++ * 6308 6672

L. N. C * 4024 220

K. S. C * 2472 8

M. Y. C++ * 3312 299

TOP 20 CONTESTANTS

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

Rank Name Points

1. Munter, Ernst 195

2. Gregg, Xan 114

3. Larsson, Gustav 87

4. Lengyel, Eric 40

5. Lewis, Peter 32

6. Boring, Randy 27

7. Cooper, Greg 27

8. Antoniewicz, Andy 24

9. Beith, Gary 24

10. Kasparian, Raffi 22

11. Cutts, Kevin 21

12. Nicolle, Ludovic 21

13. Picao, Miguel Cruz 21

14. Brown, Jorg 20

15. Gundrum, Eric 20

16. Studer, Thomas 20

17. [Name deleted] 20

18. Karsh, Bill 19

19. Mallett, Jeff 17

20. Nevard, John 17

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points 5th place 2 points

2nd place 10 points finding bug 2 points

3rd place 7 points suggesting Challenge 2 points

4th place 4 points

Here is Thomas' winning solution:

RouterRules.cp

    Copyright © 1996 Thomas Studer

// Memory requirements
// ----------
// About 12K of static tables. A variable amount of heap memory. The program will run // faster and/or yield 
compacter results given more memory (in most cases). The 
// maximum amount of dynamic memory is approximately (chunkSize+1)^chunkCount // times the size of 
a pointer + the number of input values times 12 bytes (the size of
// BitGrpEntry). ‘chunkSize' is 1, 2, 4 or 8. ‘chunkCount' is the width (in bits) of the 
// input values / chunkSize, rounded up. ‘chunkCount' is between 4 and 32, inclusive.
// 
// How it works
// ------
// - The values to be reduced are arranged in memory in a number of linked lists. The 
// program then loops through these lists trying to find values (with matching masks) 
// that differ in exactly one bit (‘buddy' values).  The value in a pair of such compatible // values that has 
a ‘1' in the only differing bit position is thrown away and the mask of // the the remaining value is updated 
by clearing that bit. If, for a given value no 
// ‘buddy' can be found, it is output and the program continues until all the internal 
// lists are empty.
//
// - The values are arranged in ‘bit groups' to quickly locate a given value's buddy. A bit
// group is identified by a number whose individual digits denote the number of bits set
// to 1 within a range of consecutive bits in the input value. A range of consecutive bits // is called a ‘chunk'. 
Chunk sizes can be 1, 2, 4 or 8. For example, an input value of 16 // bits that looks like this (chunkSize 4): 
1101 1001 0001 0111, will have group value 
// 3213 (base 5, since every digit denotes the number of 1's (0..4) per bit sequence 
// (chunk). During initialization, all the input values are categorized using that scheme // by storing them 
in lists (one list for every bit group). Pointers to the first elements 
// (BitGrpEntry's) of these lists are kept in the gBitGrpLists array. A particular bit group // can now be accessed 
using the bit group value as an index into that array. For any 
// given value, to locate a buddy, only those bit group lists have to be searched that 
// differ by 1 in exactly one digit.
//
// - The class BitGrpMapper is responsible for the initial categorization of the input
// values (through one of three lookup tables, depending on chunkSize). The class also
// calculates and stores some other values pertaining to the current run's chunk size.
// The bulk of the base 3, 5 or 9 arithmetic (namely, when for a given value the buddy
// groups have to be located) is done in RemoveLoop(). For the chunkSize == 1 case,
// no lookup table is required because the bit group number is a binary number. Some
// of the functions have been optimized for the 1 bit case.
// 
// I think the algorithm is quite nice. However, there is some room for improvement in
// the implementation. Moreover, the style of the code could be improved - it is not
// particularly readable and it doesn't make enough use of types to make the code more
// expresive (basically another one of those C turned C++ programs - I'm working on it).
// -----------------------------

#define ALTER_INPUT_VALUES  1

#include "ProvidedCode.h"
#include "BitGrpMapper.h"

// Data structs and types

enum ErrCode {   kNoErr = 0,
                 kErr = 1
};

struct BitGrpEntry {
  BitGrpEntry    *next;
  ulng           value;
  ulng           mask;
};

typedef BitGrpEntry *BitGrpEntryPtr;


Prototypes

ErrCode  Init( void );

ErrCode Process( void );

long    CleanUp( void );

void    MakeComplement(    void );

void    InitBitGrpLists(   long    startValue,
                           long    pastValue );

void    ClearMemory(       long  *p,
                           long  blockCount );

void    ProcessLists(      void );

long     RemoveValues(     void );

void    RemoveLoop(        long            curIdx,
                           BitGrpEntryPtr  beforeEntry,
                           BitGrpEntryPtr  curEntry );

void    RemoveLoop1Bit(    ulng            curIdx, 
                           BitGrpEntryPtr  beforeEntry, 
                           BitGrpEntryPtr  curEntry );

                    
long    ScanAndKeep(       BitGrpEntryPtr  compareEntry,
                           BitGrpEntryPtr  beforeEntry,
                           ulng            mask,
                           ulng            matchBit );
                         
long    ScanAndRemove(     BitGrpEntryPtr  compareEntry,
                           BitGrpEntryPtr  beforeEntry,
                           ulng            mask,
                           ulng            matchBit );
                         
inline  long  Match(       BitGrpEntryPtr  compareEntry,
                           BitGrpEntryPtr  thisEntry,
                           ulng            matchBit );
                 
void     AddToOutput(      BitGrpEntryPtr  curEntry );
                  

Global data

long              *gAllowedValues;
long              gNumAllowedValues;
long              gNumBits;
Rule              *gCurRule;
long              gMaxRules;
long              gRulesLeft;
long              gBlockNumAllowedValues;
long              gStartMask;
long              gAllow;

BitGrpMapper      gBitGrpMapper; // the BitGrpMapper class
BitGrpEntryPtr    *gBitGrpLists; // Array of BitGrpEntry
                                 // list headers
BitGrpEntryPtr    gFirstFreeEntry;  
long              gNumBitGrpBlocks; 
long              gNumValuesInLists;
                        

// Implementation


Init
// For any run, depending on the number of input values  and the amount of available
// memory, various combinations of chunkSize and gBlockNumAllowedValues are
// possible, yielding different results and different execution times. There wasn't
// enough time to sufficiently analyze the program's algorithm. That's why this function
// contains a lot of guessing. The while loop in Init() starts with a small chunkSize (1 or
// 2) and tries to allocate the required amount of memory. If that fails, the number of
// input values processed at a time is split in half, requiring less memory for the actual
// values. If that still takes too much memory, the chunkSize is increased, the number
// of values to be processed is reset and the attempt to allocate memory is repeated.
//
ErrCode  Init( void )
{
  const long  kBitLimit = 27;
  const long  kMemLimit = 1L << kBitLimit;
  long        valueMem;
  long        splitCount = 0;
  long        chunkSize = 1;
    
  gBitGrpLists = NULL;
  gBlockNumAllowedValues = gNumAllowedValues;
  if (gNumBits > kBitLimit) chunkSize = 2;  
    
  while (gBlockNumAllowedValues > 0) {
  
    // Init gBitGrpMapper fur current chunk size
    gBitGrpMapper.Init( chunkSize, gNumBits );
    
    if (splitCount == 0 && chunkSize != 8 &&
        gBitGrpMapper.numGrpLists / gBlockNumAllowedValues
        > 60) {
    // Very scarce -> Force shift to next chunk size
      splitCount = 100;  
      
    } else {
    
      if ( 4 * gBitGrpMapper.numGrpLists < kMemLimit) {
      
    // How many blocks of 8 BitGrpEntryPtr's?
        gNumBitGrpBlocks = gBitGrpMapper.numGrpLists/8 + 1;
        
    // How much memory for the values
        valueMem =
          gBlockNumAllowedValues * sizeof( BitGrpEntry );
      
        if (valueMem < kMemLimit) {
                  
    // Allocate memory for the BitGrpEntry's
          gBitGrpLists = (BitGrpEntryPtr*)
            NewPtr(valueMem + 32 * gNumBitGrpBlocks);
                    
    // Successful allocation?
          if (gBitGrpLists) {
            gFirstFreeEntry = (BitGrpEntryPtr) 
              &gBitGrpLists[ 8 * gNumBitGrpBlocks ];
            return kNoErr;
          }
        }
      }
    }
    
    switch (chunkSize) {
      case 1:
        if (splitCount>=1 || gBlockNumAllowedValues < 4) {
          gBlockNumAllowedValues = gNumAllowedValues;
          splitCount = 0;
          chunkSize = 2;
          continue;
        }
      case 2:
        if (splitCount>=2 || gBlockNumAllowedValues < 4) {
          gBlockNumAllowedValues = gNumAllowedValues;
          splitCount = 0;
          chunkSize = 4;
          continue;
        }
      case 4:
        if (splitCount>=3 || gBlockNumAllowedValues < 4) {
          gBlockNumAllowedValues = gNumAllowedValues;
          splitCount = 0;
          chunkSize = 8;
          continue;
        }
    }

    gBlockNumAllowedValues /= 2;
    splitCount++;
  }

  return kErr;
}


MakeComplement
// If the number of allowed values in the input exceeds half the maximum number of 
// allowed values (plus some slack), the number of values that are not in the
// gAllowedValues array are calculated and replace the values in gAllowedValues. These
// values are then to be denied.
//


void  MakeComplement( void )
{
  ulng  *bitMap;
  ulng  numLongs = (1L << gNumBits) / 32;
  
  bitMap = (ulng*) NewPtr( 4 * (numLongs + 8));
  
  if (bitMap) {  
        
    // Clear bitMap
    ClearMemory( (long*)bitMap, (numLongs + 8) / 8 );
  
    // For every allowed value set its bit in bitMap
    ulng *pastVal=(ulng*)&gAllowedValues[gNumAllowedValues];
    ulng *curVal = (ulng*)gAllowedValues;
    
    do {
      bitMap[*curVal>>5] |= (1L << (*curVal & 0x0000001f));
      curVal++;
    } while (curVal != pastVal);

    // Determine the values to be denied by looking for
    // 0 bits in bitMap. Write them out to gAllowedValues
    ulng *curEntry = bitMap;
    ulng curIndex; // into bitMap
    ulng curBit;
    curVal = (ulng*)gAllowedValues;
    
    for (curIndex = 0; curIndex<numLongs; curIndex++) {
      if (*curEntry != 0xffffffff) {
        for (curBit = 0; curBit<32; curBit++) {
          if ((*curEntry & (1L << curBit)) == 0) {
            *curVal = (curIndex << 5) | curBit;
            curVal++;
          }
        }
      }
      curEntry++;
    }
    
    // Set the new number of values in gAllowedValues 
    // and flip the gAllow variable from kAllow to kDeny
    gNumAllowedValues = curVal - (ulng*)gAllowedValues;
    gAllow = kDeny;
    
    DisposPtr( (char*) bitMap );
  }
}


InitBitGrpLists
// Initialization of the internal lists by reading values from gAllowedValues and storing
// them as BitGrpEntry items.
//
void  InitBitGrpLists( long    startValue,
                       long    pastValue )
{  
  long            *curVal = &gAllowedValues[startValue];
  long            *pastVal = &gAllowedValues[pastValue];
  BitGrpEntryPtr  curEntry = gFirstFreeEntry;
  BitGrpEntryPtr  *curHead;
  
  ClearMemory( (long*)gBitGrpLists, gNumBitGrpBlocks );
  
// Two times the same while loop. Once for the special case of chunkSize == 1 and
// then for the general case of chunkSize == 2, 4 or 8. Only the chunkSize == 2, 4
// and 8 cases need gBitGrpMapper's LookUp method since these cases deal with
// base 3, 5 and 9 integers, respectively.
  
  if (gBitGrpMapper.chunkSize == 1) {
    while (curVal < pastVal) {
      gBitGrpLists[ *curVal ] = curEntry;
      curEntry->next = NULL;
      curEntry->value = *curVal;
      curEntry->mask = gStartMask; 
      curEntry++;
      curVal++;
    }
  } else {
    while (curVal < pastVal) {
      curHead = 
        &gBitGrpLists[ gBitGrpMapper.LookUp( *curVal ) ];
      curEntry->next = *curHead;
      curEntry->value = *curVal;
      curEntry->mask = gStartMask; 
      *curHead = curEntry;
      curEntry++;
      curVal++;
    }
  }
  
  gNumValuesInLists = pastValue - startValue;
} 


ClearMemory
// Unfortunately I don't know the PPC processors well enough to know whether the
// way this loop is unrolled really helps much.
//
void  ClearMemory(   long  *p,
                     long  blockCount )
{
  while (blockCount-) {
    *p = NULL;
    p++;
    *p = NULL;
    p++;
    *p = NULL;
    p++;
    *p = NULL;
    p++;
    *p = NULL;
    p++;
    *p = NULL;
    p++;
    *p = NULL;
    p++;
    *p = NULL;
    p++;
  }
}


AddToOutput
// Add a value for which no ‘buddy' can be found to the output array.
//
inline void AddToOutput(  BitGrpEntryPtr  curEntry )
{
  if (gRulesLeft) {
    // Add to output rules
    gCurRule->value = curEntry->value;
    gCurRule->mask = curEntry->mask;
    gCurRule->allow = gAllow;
    gCurRule++;
    gRulesLeft-;
  }
}

Process
// Entry point for the main processing loop. If there is enough memory, all the available
// values are considered at the same time. If memory is low, the input values are
// processed in blocks of size gBlockNumAllowedValues (likely to produce a higer
// number of output rules).
//
ErrCode Process( void)
{    
  long  numValuesLeft = gNumAllowedValues;
  long  startValue = 0;
  long  pastValue = 0;
  while (numValuesLeft) {
        pastValue += gBlockNumAllowedValues;
    if (pastValue > gNumAllowedValues) {
      pastValue = gNumAllowedValues;
    }
    InitBitGrpLists( startValue, pastValue );
    ProcessLists();
    if (gRulesLeft <= 0) return kErr; // Output array full
    numValuesLeft -= pastValue - startValue;
    startValue = pastValue;
  }
  
  return kNoErr;
}

ProcessLists
// Loop over gBitGrpLists while there are values to combine.
//
void ProcessLists( void )
{
  while (gNumValuesInLists) {
    gNumValuesInLists -= RemoveValues();
  }
}


RemoveValues
// One loop over gBitGrpLists, combining pairs of values that differ in exactly one bit. If
// for a given value such a compatible value is found (referred to as ‘buddy' in many
// places in the code), they are combined. This is done by ‘throwing away' the value
// that has a ‘1' in  the bit position that differs and then clearing the same bit in the
// remaining value's mask. 
//
long RemoveValues( void )
{
  long            valuesRemoved = 0;
  long            curIdx = 0;
  BitGrpEntryPtr  beforeEntry;
  BitGrpEntryPtr  curEntry;
  BitGrpEntryPtr  *curList   = gBitGrpLists;
  BitGrpEntryPtr  *pastList = 
    &gBitGrpLists[ gBitGrpMapper.numGrpLists ];

  if (gBitGrpMapper.chunkSize == 1) {

    while (curList < pastList) {
      if (*curList) {  
        beforeEntry = (BitGrpEntryPtr)curList;
        curEntry = *curList;
        RemoveLoop1Bit( curIdx, beforeEntry, curEntry );
        valuesRemoved++;
      }
      curList++;
      curIdx++;
    }
    
  } else {
    
    while (curList < pastList) {
      if (*curList) {
        beforeEntry = (BitGrpEntryPtr)curList;
        curEntry = *curList;  
        do {
          RemoveLoop( curIdx, beforeEntry, curEntry );
          valuesRemoved++;
          if (beforeEntry->next == curEntry) {
            beforeEntry = curEntry;
          }
          curEntry = curEntry->next;
        } while (curEntry);
      }
      curList++;
      curIdx++;
    }
  }
  
  return valuesRemoved;
}


RemoveLoop
// RemoveLoop deals with chunkSize == 2, 4 and 8. This Function loops over
// curEntry's buddy lists (lists that may contain values that, compared with the value in
// curEntry, differ in exactly one bit).
//
void  RemoveLoop( long            curIdx,
                  BitGrpEntryPtr  beforeEntry,
                  BitGrpEntryPtr  curEntry )
{  
  short            curChunk = gBitGrpMapper.chunkCount;
  ulng            mask = gBitGrpMapper.firstMask;
  ulng            matchBit = gBitGrpMapper.firstMatchBit;
  long            magIdx = curIdx;
  long            magStep;
  ulng            scanVal;
  BitGrpEntryPtr  *buddyList;
    
  while (curChunk) {
    
    scanVal = curEntry->value & ~mask;   
    magStep = gBitGrpMapper.lbTable[curChunk];
    if (magIdx < gBitGrpMapper.ubTable[curChunk]) {
      
      buddyList = &gBitGrpLists[ curIdx + magStep ];
      if (*buddyList) {
        if (ScanAndRemove( curEntry, 
            (BitGrpEntryPtr)buddyList, ~mask, matchBit )) {
          
          return; // Found a ‘buddy'
        }
      }
    }
    
    if (magIdx >= magStep) {
      buddyList = &gBitGrpLists[ curIdx - magStep ];
      if (*buddyList) {
        if (ScanAndKeep( curEntry, 
          (BitGrpEntryPtr)buddyList, ~mask, matchBit )) {
          
    // remove curEntry from list
 beforeEntry->next = curEntry->next; 
 return;  // Found a ‘buddy'
        }
      }
      
      do {
        magIdx -= magStep;
      } while (magIdx >= magStep);
    }
    
    mask >>= gBitGrpMapper.chunkSize;
    matchBit >>= gBitGrpMapper.chunkSize;
    curChunk-;
  }
  
    // No match found -> add to output and remove from list
  AddToOutput( curEntry );
  beforeEntry->next = curEntry->next;

}


RemoveLoop1Bit 
// The 1 bit only version of RemoveLoop()
//
void  RemoveLoop1Bit ( ulng              curIdx,
                       BitGrpEntryPtr    beforeEntry,
                       BitGrpEntryPtr    curEntry )
{
  ulng            matchBit = gBitGrpMapper.firstMatchBit;
  BitGrpEntryPtr  *buddyHead;
  
  while (matchBit) {
    
    if (curIdx & matchBit) {
      
      if (buddyHead = &gBitGrpLists[ curIdx & ~matchBit ]) {
        if ((*buddyHead)->mask == curEntry->mask) {
          (*buddyHead)->mask &= ~matchBit;
          beforeEntry->next = NULL;
          return;
        }
      }
      
    } else {

      if (buddyHead = &gBitGrpLists[ curIdx | matchBit ]) {
        if ((*buddyHead)->mask == curEntry->mask) {
          curEntry->mask &= ~matchBit;
          *buddyHead = NULL;
          return;
        }
      }
    }
    

    matchBit >>= 1;
  }
      
  AddToOutput( curEntry );
  
  beforeEntry->next = NULL;
}


ScanAndKeep
// For a given value, scans through a group list and searches for a buddy for that value.
// If a buddy is found, compareEntry will be removed by RemoveValues().
//
long  ScanAndKeep(    BitGrpEntryPtr  compareEntry,
                      BitGrpEntryPtr  beforeEntry,
                      ulng            mask,
                      ulng            matchBit )
{
  BitGrpEntryPtr  thisEntry = beforeEntry->next;
  ulng            scanValue = compareEntry->value & mask;
  while (thisEntry) {
    if ((thisEntry->value & mask) == scanValue) {
      if (compareEntry->mask == thisEntry->mask) {
        if (Match( compareEntry, thisEntry, matchBit)) {
        
          thisEntry->mask &= ~(compareEntry->value ^
            thisEntry->value);
          return 1;
        }
      }
    }
    beforeEntry = thisEntry;
    thisEntry = thisEntry->next;
  }
  
  return 0;
}


ScanAndRemove
// Same as ScanAndKeep() except that if a buddy is found, it is removed after the
// compareEntry's mask has been updated (see RemoveValues()).
// 
long  ScanAndRemove(   BitGrpEntryPtr  compareEntry,
                       BitGrpEntryPtr  beforeEntry,
                       ulng            mask,
                       ulng            matchBit )
{
  BitGrpEntryPtr  thisEntry = beforeEntry->next;
  ulng            scanValue = compareEntry->value & mask;
  
  while (thisEntry) {
    if ((thisEntry->value & mask) == scanValue) {
      if (compareEntry->mask == thisEntry->mask) {
        if (Match( compareEntry, thisEntry, matchBit)) {
          
          compareEntry->mask &= ~(compareEntry->value ^
            thisEntry->value);
          beforeEntry->next = thisEntry->next;
          return 1;
        }
      }
    }
    beforeEntry = thisEntry;
    thisEntry = thisEntry->next;
  }
  
  return 0;
}


Match
// The two values compareEntry->value and thisEntry->value can be combined if they
// differ in exactly one bit. In those cases, refVal, below, will have exactly one bit set.
// The rest of the code tests to see if that is so. I have the feeling that this function's
// efficiency could be improved.
//
inline long  Match(   BitGrpEntryPtr  compareEntry,
                      BitGrpEntryPtr  thisEntry,
                      ulng            matchBit )
{
  ulng  refVal = compareEntry->value ^ thisEntry->value;
  ulng  matchCount = 0;
    
  switch (gBitGrpMapper.chunkSize) {
    case 2:
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      return 0;
    case 4:
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      return 0;
    case 8:
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      matchBit >>= 1;
      if (! (refVal ^ matchBit)) return 1;
      return 0;
  }
  return 0;
}


CleanUp
// I first developped this solution using the Symantec environment where I used the
// C++ new and delete functions for memory management. After moving to
// CodeWarrior, however, I had to use the Mac Toolbox function NewPtr to allocate
// memory in Init() (and DisposPtr to dispose of it here) because Codewarrior's
// implementation of new didn't seem to reliably return NULL in cases a memory
// request could not be satisfied.
// 
long    CleanUp( void )
{
  if (gBitGrpLists) DisposPtr( (char*)gBitGrpLists );
  
  if (gRulesLeft > 0) {
    gCurRule->value = 0;
    gCurRule->mask = 0;
    if (gAllow == kAllow) {
      gCurRule->allow = kDeny;
    } else {
      gCurRule->allow = kAllow;
    }
    gRulesLeft-;
    
    return gMaxRules - gRulesLeft;
  } else {
    return -1;
  }
  
}


RouterRules
// Main entry point
//
long RouterRules( long  allowedValues[],
                  long  numAllowedValues,
                  long  numBits,
                  Rule  rulesArray[],
                  long  maxRules )
{
  gAllowedValues = allowedValues;
  gNumAllowedValues = numAllowedValues;
  gNumBits = numBits;
  gCurRule = rulesArray;
  gMaxRules = maxRules;
  gRulesLeft = maxRules;
  gStartMask = 0xffffffff >> (32-gNumBits);
  gAllow = kAllow;
  
  if (maxRules <= 0) return -1;
  
  if (numAllowedValues <= 0) {
    gCurRule->mask = 0;
    gCurRule->value = 0;
    gCurRule->allow = kDeny;
    return 1;
  }
  if (numAllowedValues == (1L << numBits)) {
    gCurRule->mask = 0;
    gCurRule->value = 0;
    gCurRule->allow = kAllow;
    return 1;
  }  
  
  #if ALTER_INPUT_VALUES == 1
  if (numBits > 5 && numBits < 32 && numAllowedValues > 
    ( (1<<L(numBits-1)) + (1<<L(numBits-5)) )) {
    MakeComplement();
  }
  #endif
  
  if (Init() == kErr) return -1;
  Process();
  return CleanUp();
}

BitGrpMapper.cp

// -----------------------------
// Implementation of class BitGrpMapper - a class that does most of the base 2, 3, 5 and
// 9 arithmetic
// -----------------------------

#define WRITE_LOOKUP_TABLES     0

#if WRITE_LOOKUP_TABLES == 1
# include <stdlib.h>
# include <fstream.h>
#endif

#include "BitGrpMapper.h"

long BitGrpMapper::ubTable[33] = { 0 };
long BitGrpMapper::lbTable[33] = { 0 };

void BitGrpMapper::Init(  long        chunkSz,
                          long        numBits )
{
  switch (chunkSz) {
    case 1:
      lookupTable = NULL;
      firstMask = 0x01;
      firstMatchBit = 0x01;
      break;
    case 2:
      lookupTable = lookupTable2;
      firstMask = 0x03;
      firstMatchBit = 0x02;
      break;
    case 4:
      lookupTable = lookupTable4;
      firstMask = 0x0f;
      firstMatchBit = 0x08;
      break;
    case 8:
      lookupTable = lookupTable8;
      firstMask = 0xff;
      firstMatchBit = 0x80;
      break;
  }
    
// Calculate the upper bound and lower bound lookup tables used in RemoveLoop()
// of RouterRules.cp
  chunkSize = chunkSz;
  chunkCount = numBits / chunkSz;
  long excessBits = numBits % chunkSz;
  if (excessBits) chunkCount++;
  firstMask <<= ((chunkCount - 1) * chunkSz);
  firstMatchBit <<= ((chunkCount - 1) * chunkSz);
  
  ulng base = chunkSz + 1;
  ulng curBase = 1;
  long i;
  
  for (i=1; i<chunkCount; i++) {
    lbTable[i] = curBase;
    ubTable[i] = chunkSz * curBase;
    curBase *= base;
  }
  lbTable[i] = curBase;
  if (excessBits) ubTable[i] = excessBits * curBase;
  else            ubTable[i] = chunkSz * curBase;
  numGrpLists = ubTable[i] + curBase;
  
#if WRITE_LOOKUP_TABLES == 1
  {
    IndexEntry  tmpTable[256];
    ofstream    file;
    
    file.open( "BitGrpMapperTables.cp" );
    file << "#include \"BitGrpMapper.h\"" << endl << endl;
    CalcLookupTable( tmpTable, 2 );
    WriteLookupTable( file, tmpTable, "lookupTable2" );
    CalcLookupTable( tmpTable, 4 );
    WriteLookupTable( file, tmpTable, "lookupTable4" );
    CalcLookupTable( tmpTable, 8 );
    WriteLookupTable( file, tmpTable, "lookupTable8" );
    file.close();
  }
#endif
}

#if WRITE_LOOKUP_TABLES == 1

void BitGrpMapper::CalcLookupTable( IndexEntry  lookupTbl[],
                                    long        chunkSz )
{
  long  lookupByte;// 0 .. 255
  long  byteInLong;// 3 .. 0, 0 for the most sig. byte
  long  chunkCount = 8 / chunkSz;  // 8, 4, 2 or 1
  long  curChunk;         // 0 .. chunkCount-1
  long  bitCounts[8];     // bitCounts[0]: right most chunk
  long  curBit;           //  bit 0 .. bit 7 (right to left)
  long  bitIndex;         // 0 .. chunkSz-1
  long  base = chunkSz + 1; // base 2, 3, 5, or 9
  long  curBase;          // a power of base
  
  for (lookupByte=0; lookupByte<256; lookupByte++) {
    
    curBit = 1;
    for (curChunk=0; curChunk<chunkCount; curChunk++) {
      bitCounts[curChunk] = 0;
      for (bitIndex=0; bitIndex<chunkSz; bitIndex++) {
        if (lookupByte & curBit) bitCounts[curChunk]++;
        curBit <<= 1;
      }
    }
    
    curBase = 1;
    for (byteInLong=3; byteInLong>=0; byteInLong-) {
      lookupTbl[lookupByte].index[byteInLong] = 0;
      for (curChunk=0; curChunk<chunkCount; curChunk++) {
        lookupTbl[lookupByte].index[byteInLong] +=
          curBase * bitCounts[curChunk];
        curBase *= base;
      }
    }
  }          
}

void BitGrpMapper::WriteLookupTable( ofstream    &file,
                                     IndexEntry table[],
                                     char*      tableName )
{
  long  entryCount;
  long  indexCount;
  
  file << "IndexEntry BitGrpMapper::" 
    << tableName << "[256] = {" << endl;
  
  for (entryCount=0; entryCount<256; entryCount++) {
    file << "  { ";
    for (indexCount=0; indexCount<4; indexCount++) {
    // Printing as pointer to long writes value as a four byte hex number in the
    // Symantec environ. Not so with my brand new CodeWarrior (at least using the
    // default project settings). Would need to be fixed if the lookup tables had to be
    // rebuilt.
      file << (long*) table[entryCount].index[indexCount];
      file << ((indexCount == 3) ? " }" : ", ");
    }
    file << ((entryCount == 255) ? ‘ ‘ : ‘,' ) << endl;
  }
      
  file << "};" << endl << endl;
}
#endif  

BitGrpMapper.h

// -----------------------------
// class BitGrpMapper 
// -----------------------------

#ifndef NULL
const void * const NULL = 0;
#endif

typedef unsigned long ulng;

struct IndexEntry {
..long..index[4];
};

class BitGrpMapper {..
public:
 static long  ..ubTable[33];
 static long  ..lbTable[33];
 long   chunkSize; // 1, 2, 4 or 8 bits per chunk
 long   chunkCount;// # of chunks/digits in group index
 ulng   firstMask; // used to reset curMask
 ulng   firstMatchBit;
 long   numGrpLists;

 void.. ..Init( long..chunkSize,
 long..numBits );

 inline longLookUp( ulng  value );
private:
 static IndexEntry lookupTable2[];
 static IndexEntry lookupTable4[];
 static IndexEntry lookupTable8[];

 IndexEntry *lookupTable; // lookup group index

#if WRITE_LOOKUP_TABLES == 1
 void   CalcLookupTable( IndexEntry  lookupTbl[],
 long chunkSz );
 void WriteLookupTable( ofstream &file,
 IndexEntry table[],
 char   tableName );
#endif..
};

inline long BitGrpMapper::LookUp( ulng..value )
{
 long..index = lookupTable[value >> 24].index[0];
 
 index += lookupTable[(value >> 16) & 0xff].index[1];
 index += lookupTable[(value >> 8) & 0xff].index[2];
 index += lookupTable[value & 0xff].index[3];

 return index;
}

ProvidedCode.h

// -----------------------------
// Code copied from problem statement
// -----------------------------

enum {  kDeny = 0, 
 kAllow = 1 
};

#ifdef __cplusplus
extern "C" {
#endif
typedef struct Rule {
 long   mask;
 long   value;
 long   allow;
} Rule;
long RouterRules( long    allowedValues[],
 long   numAllowedValues,
 long   numBits,
 Rule   rulesArray[],
 long   maxRules );
#ifdef __cplusplus
}
#endif

BitGrpMapperTables.cp

#include "BitGrpMapper.h"

IndexEntry BitGrpMapper::lookupTable2[256] = {
  { 0x00000000, 0x00000000, 0x00000000, 0x00000000 },
  { 0x00081BF1, 0x000019A1, 0x00000051, 0x00000001 },
  { 0x00081BF1, 0x000019A1, 0x00000051, 0x00000001 },
  { 0x001037E2, 0x00003342, 0x000000A2, 0x00000002 },
  { 0x001853D3, 0x00004CE3, 0x000000F3, 0x00000003 },
  { 0x00206FC4, 0x00006684, 0x00000144, 0x00000004 },
  { 0x00206FC4, 0x00006684, 0x00000144, 0x00000004 },
  { 0x00288BB5, 0x00008025, 0x00000195, 0x00000005 },
  { 0x001853D3, 0x00004CE3, 0x000000F3, 0x00000003 },
  { 0x00206FC4, 0x00006684, 0x00000144, 0x00000004 },
  { 0x00206FC4, 0x00006684, 0x00000144, 0x00000004 },
  { 0x00288BB5, 0x00008025, 0x00000195, 0x00000005 },
  { 0x0030A7A6, 0x000099C6, 0x000001E6, 0x00000006 },
  { 0x0038C397, 0x0000B367, 0x00000237, 0x00000007 },
  { 0x0038C397, 0x0000B367, 0x00000237, 0x00000007 },
  { 0x0040DF88, 0x0000CD08, 0x00000288, 0x00000008 },
  { 0x0048FB79, 0x0000E6A9, 0x000002D9, 0x00000009 },
  { 0x0051176A, 0x0001004A, 0x0000032A, 0x0000000A },
[   and more - see online archive for complete file]
  { 0x02809F5F, 0x0007E8AF, 0x000018FF, 0x0000004F },
  { 0x0288BB50, 0x00080250, 0x00001950, 0x00000050 } 
};

IndexEntry BitGrpMapper::lookupTable4[256] = {
  { 0x00000000, 0x00000000, 0x00000000, 0x00000000 },
  { 0x00003D09, 0x00000271, 0x00000019, 0x00000001 },
  { 0x00003D09, 0x00000271, 0x00000019, 0x00000001 },
  { 0x00007A12, 0x000004E2, 0x00000032, 0x00000002 },
  { 0x00003D09, 0x00000271, 0x00000019, 0x00000001 },
  { 0x00007A12, 0x000004E2, 0x00000032, 0x00000002 },
  { 0x00007A12, 0x000004E2, 0x00000032, 0x00000002 },
  { 0x0000B71B, 0x00000753, 0x0000004B, 0x00000003 },
  { 0x00003D09, 0x00000271, 0x00000019, 0x00000001 },
  { 0x00007A12, 0x000004E2, 0x00000032, 0x00000002 },
  { 0x00007A12, 0x000004E2, 0x00000032, 0x00000002 },
  { 0x0000B71B, 0x00000753, 0x0000004B, 0x00000003 },
  { 0x00007A12, 0x000004E2, 0x00000032, 0x00000002 },
  { 0x0000B71B, 0x00000753, 0x0000004B, 0x00000003 },
  { 0x0000B71B, 0x00000753, 0x0000004B, 0x00000003 },
  { 0x0000F424, 0x000009C4, 0x00000064, 0x00000004 },
  { 0x0001312D, 0x00000C35, 0x0000007D, 0x00000005 },
[   and more - see online archive for complete file]
  { 0x00057BCF, 0x00003827, 0x0000023F, 0x00000017 },
  { 0x00057BCF, 0x00003827, 0x0000023F, 0x00000017 },
  { 0x0005B8D8, 0x00003A98, 0x00000258, 0x00000018 } 
};
IndexEntry BitGrpMapper::lookupTable8[256] = {
  { 0x00000000, 0x00000000, 0x00000000, 0x00000000 },
  { 0x000002D9, 0x00000051, 0x00000009, 0x00000001 },
  { 0x000002D9, 0x00000051, 0x00000009, 0x00000001 },
  { 0x000005B2, 0x000000A2, 0x00000012, 0x00000002 },
  { 0x000002D9, 0x00000051, 0x00000009, 0x00000001 },
  { 0x000005B2, 0x000000A2, 0x00000012, 0x00000002 },
  { 0x000005B2, 0x000000A2, 0x00000012, 0x00000002 },
  { 0x0000088B, 0x000000F3, 0x0000001B, 0x00000003 },
  { 0x000002D9, 0x00000051, 0x00000009, 0x00000001 },
  { 0x000005B2, 0x000000A2, 0x00000012, 0x00000002 },
  { 0x000005B2, 0x000000A2, 0x00000012, 0x00000002 },
  { 0x0000088B, 0x000000F3, 0x0000001B, 0x00000003 },
  { 0x000005B2, 0x000000A2, 0x00000012, 0x00000002 },
  { 0x0000088B, 0x000000F3, 0x0000001B, 0x00000003 },
  { 0x0000088B, 0x000000F3, 0x0000001B, 0x00000003 },
  { 0x00000B64, 0x00000144, 0x00000024, 0x00000004 },
  { 0x000002D9, 0x00000051, 0x00000009, 0x00000001 },
  { 0x000005B2, 0x000000A2, 0x00000012, 0x00000002 },
[   and more - see online archive for complete file]
  { 0x000013EF, 0x00000237, 0x0000003F, 0x00000007 },
  { 0x000013EF, 0x00000237, 0x0000003F, 0x00000007 },
  { 0x000016C8, 0x00000288, 0x00000048, 0x00000008 } 
};

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

ExpanDrive 5.4.6 - $49.99
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Apple Pages 6.1.1 - Apple's word pr...
Apple Pages is a powerful word processor that gives you everything you need to create documents that look beautiful. And read beautifully. It lets you work seamlessly between Mac and iOS devices, and... Read more
Apple Numbers 4.1.1 - Apple's sprea...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
Apple Keynote 7.1.1 - Apple's prese...
Easily create gorgeous presentations with the all-new Keynote, featuring powerful yet easy-to-use tools and dazzling effects that will make you a very hard act to follow. The Theme Chooser lets you... Read more
Espresso 5 - Powerful HTML, XML, CSS, an...
Espresso is back. For people who make delightful, innovative, and fast websites -- in an app to match. Espresso helps you write, code, design, build, and publish with flair and efficiency.... Read more
Vitamin-R 2.47 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
Dash 4.0.3 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Posterino 3.3.6 - Create posters, collag...
Posterino offers enhanced customization and flexibility including a variety of new, stylish templates featuring grids of identical or odd-sized image boxes. You can customize the size and shape of... Read more
Together 3.8.3 - Store and organize all...
Together helps you organize your Mac, giving you the ability to store, edit and preview your files in a single clean, uncluttered interface. Features Smart storage. With simple drag-and-drop... Read more
iClock Pro 3.4.9 - Customize your menuba...
iClock Pro is a menu bar replacement clock for Apple's default clock. iClock Pro is an update, total rewrite and improvement to the popular iClock. Have the day, date and time in different fonts and... Read more

Latest Forum Discussions

See All

Minimalist puzzle game, Cuts, free on iO...
If you're looking for a gorgeous puzzle experience on iOS devices, developer Gamebra.in's aesthetically interesting puzzler, Cuts, is discounted to free on the iOS App Store right now. [Read more] | Read more »
Anime tactical RPG, War of Crown, comes...
If you're looking for another tactical RPG fix to go alongside your Fire Emblem Heroes campaigns check out Gamevil's newest, anime-inspired tactics RPG, War of Crown, which comes out tomorrow. [Read more] | Read more »
Fantasy MMORPG MU Origin adds new modes,...
MU Origin, Webzen’s highly popular fantasy MMORPG is getting ready to shake things up for the second time this year, as a new update makes its way to the Google Play and App Store from today. Introducing new systems, modes, and events, the land of... | Read more »
Blizzard is looking to hire a mobile dev...
A new thread on the popular video game rumor forum, NeoGAF, uncovered an interesting job listing over at Blizzard Entertainment. It appears the studio behindStarCraft, World of WarCraft, Hearthstone,andOverwatch is looking to bring on a new hire... | Read more »
Legend of Zelda meets Cooking Mama in ne...
Dungeon Chef is what happens when you mix the RPG elements (and style) of a Legend of Zelda game, with cooking elements. Although, now that The Legend of Zelda: Breath of the Wild also has cookingelements, so maybe the gameplay is not so novel.... | Read more »
ChordFlow (Music)
ChordFlow 1.0.0 Device: iOS Universal Category: Music Price: $6.99, Version: 1.0.0 (iTunes) Description: ChordFlow is a chord sequencer with a unique 4-track polyphonic arpeggiator, extensive chord library, MIDI out and Ableton Link... | Read more »
The Walking Dead: A New Frontier is out...
The newest season of Telltale Games'The Walking Dead is well underway. After the release of the third episode, "Above the Law" about a month ago, episode four, "Thicker Than Water" is hot and ready for more zombies and gut-wrenching emotional... | Read more »
Best games we played this week
Another week, another new wave of mobile games do dive into. We've dug through the list of apps that came out this week to tell you which apps are worth your sweet time. And while there weren't too many games this week, there were some big ones.... | Read more »
Vignettes (Games)
Vignettes 1.0.1 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.1 (iTunes) Description: Vignettes is a casual but unique exploration game without text or characters, where objects shapeshift as you spin them around... | Read more »
Get Me Outta Here is an 80s retro shoote...
Are you ready to fight some aliens? Because Crescent Moon Games has released the retro shooter Get Me Outta Here on iOS devices today. [Read more] | Read more »

Price Scanner via MacPrices.net

HyperX Ships Pulsefire FPS Gaming Mouse, Winn...
Your reporter is a longtime fan of gaming mice for general purpose coomnputing use, finding them typically superior in comfort and performance. HyperX, a division of Kingston Technology Company, Inc... Read more
Penske Truck Leasing Unveils “Penske Fleet” M...
Penske Truck Leasing has introduced a free mobile app called “Penske Fleet” to benefit its full-service truck leasing and contract maintenance customers. The mobile app enables Penske’s customers to... Read more
DEVONthink To Go 2.1.3 For iOS Adds New Declu...
DEVONtechnologies has updated DEVONthink To Go, its iOS companion to DEVONthink for Mac. Enhancements and bug fixes in Version 2.1.3 include DEVONtechnologies’ new decluttering service for clipping... Read more
Use Apple’s Education discount to save up to...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free: -... Read more
Apple refurbished Apple Watches available sta...
Apple is now offering Certified Refurbished Series 1 and Series 2 Apple Watches for 14-16% off MSRP, starting at $229. An Apple one-year warranty is included with each watch. Shipping is free: Series... Read more
15-inch Touch Bar MacBook Pros, Apple refurbi...
Apple is offering Certified Refurbished 2016 15″ Touch Bar MacBook Pros for $360 to $420 off original MSRP. An Apple one-year warranty is included with each model, and shipping is free: - 15″ 2.6GHz... Read more
13-inch MacBook Airs on sale for up to $150 o...
Overstock.com has 13″ MacBook Airs on sale for up to $150 off MSRP including free shipping: - 13″ 1.6GHz/128GB MacBook Air (sku MMGF2LL/A): $869.99 $130 off MSRP - 13″ 1.6GHz/256GB MacBook Air (sku... Read more
15-inch Touch Bar MacBook Pros on sale for $1...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $200 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
15-inch 2.7GHz Touch Bar MacBook Pros on sale...
Amazon has 2016 15″ 2.7GHz Apple Touch Bar MacBook Pros in stock today and on sale for $150-$200 off MSRP. Shipping is free: - 15″ 2.7GHz Touch Bar MacBook Pro Space Gray (sku MLH42LL/A): $2599 $200... Read more
Apple now offering Certified Refurbished 13-i...
Apple is now offering Certified Refurbished 2016 13″ Touch Bar MacBook Pros for $270-$300 off original MSRP. An Apple one-year warranty is included with each model, and shipping is free: - 13″ 2.9GHz... Read more

Jobs Board

*Apple* Mac Computer Technician - GeekHampto...
…complex computer issues over the phone and in person? GeekHampton, Long Island's Apple Premium Service Provider, is looking for you! Come work with our crew 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
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 56881986 Middletown, NY, New York, United States Posted: Apr. 17, 2017 Weekly Hours: 40.00 **Job Summary** As an Apple Read more
*Apple* Mobile Master - Best Buy (United Sta...
**489879BR** **Job Title:** Apple Mobile Master **Location Number:** 000402-Utica-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** At Read more
Music Marketing Lead, iTunes & *Apple*...
# Music Marketing Lead, iTunes & Apple Music Job Number: 56868140 Culver City, California, United States Posted: Apr. 17, 2017 Weekly Hours: 40.00 **Job Summary** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.