TweetFollow Us on Twitter

Dec 00 Challenge Volume Number: 16 (2000)
Issue Number: 12
Column Tag: Programmer's Challenge

Programmer's Challenge

By Bob Boonstra, Westford, MA

Crutches

Crutches? What an odd topic for a Programmer's Challenge, you might think. Let me explain. This month's problem was actually suggested by my wife, whose connection with the Challenge has until now been limited to the patience required to put up with the amount of time I spend running the contest. She recently had the misfortune to break her foot, which has, you guessed it, put her on crutches for six or so weeks. Being on crutches gives one a new perspective on distance, particularly distance between points around the house. And while she tries to stay off the foot as much as possible, she still has to get from place to place, so the broken foot also motivates one to find ways to minimize distance. Which leads us to this month's Challenge, a practical extension of the well-known Traveling Salesperson problem.

The prototype for the code you should write is:

typedef long Node;
typedef long Weight;

typedef struct Connection {
   Node node1;         /* a connection exists between node1 ... */
   Node node2;         /* ... and node2 .... */
   long distance;      /* ... separated by this distance */
} Connection;

typedef struct Task {
   Weight weight;   /* you need to carry an object with this weight ... */
   Node fromNode;   /* ... from fromNode ... */
   Node toNode;      /* ... to toNode */
} Task;

typedef enum {kPickUpObject=1, kDropOffObject, kMoveTo} ActionType;

typedef struct Action {
   ActionType action,   /* actions comprising the solution */
   long object,            /* kPickUpObject or kDropOffObject this object */
   Node node               /* kMoveTo this node */
} Action;

long /* actions in solution */ Crutches (
   const Node nodes[],            /* Nodes defining the problem */
   long numNodes,
   const Connection connections[],   /* Connections between nodes */
   long numConnections,
   const Task objectsToMove[],   /* objects to be moved */
   long numObjects,
   Node startingNode,            /* start from this node */
   Weight maxWeightToCarry,   /* maximum weight that you can carry */
   Action solutionPath[]      /* return your solution here */
);

Your job is to write code that will perform a set of Tasks and minimize the distance traveled in doing so. Each Task consists of moving an object of a specified weight from one place (Node) to another. You can travel from one Node to another only if a Connection exists between the Nodes, and moving between a pair of Nodes requires traveling the associated distance along that Connection.

At the start of the problem, you are located at the startingNode. You are given the numNodes Nodes describing the problem space and the numConnections Connections between them. You are also given numObjects objectsToMove, each of which needs to be transported from the fromNode to the toNode. You can carry more than one object along your journey, provided the sum of the weights of the objects being carried does not exceed the maxWeightToCarry. The solution is described as a sequence of Actions. An Action consists of picking up an object (kPickUpObject) from the current Node, dropping off an Object at the current Node (kDropOffObject), or moving to an adjacent Node (kMoveTo) and carrying all objects that have been picked up to that Node. You may not pick up an object if doing so would cause the maxWeightToCarry to be exceeded. The sequence of Actions that transports all of the objectsToMove to the appropriate Nodes should be returned as the solutionPath, and Crutches should return the number of Actions in your solution.

None of the Tasks will be impossible to perform. No object will have a weight greater than maxWeightToCarry, so it will be possible to carry each object. It will be possible to reach each fromNode and each toNode by traversing Connections from the startingNode. Connections may not satisfy the triangle inequality, that is, it may be the case that a direct Connection between two Nodes is not the shortest path between them. No other a priori information about the Connections, Nodes, or Tasks is available.

Your solution will be evaluated first on correctness (as always), and then on score. Your score for this Challenge will be the total distance traveled to perform the required Tasks, plus a 10% penalty for each second of execution time expended. Lower scores are, of course, better.

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. If you have wanted to compete in the Challenge, but have been discouraged from doing so by the quality of the entries from our veteran contestants, perhaps this is your chance at some recognition and a share of the Challenge prize.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C, C++, or Pascal.

Next month, perhaps we'll solve the problem of how to motivate a couple of teenage children to perform these Tasks, allowing the broken foot more time to rest and heal. But perhaps that would be too difficult, even for Challenge readers. (Actually, the kids are being very helpful with the household chores.)

Three Months Ago Winner

Congratulations to Claes Wihlborg (Sweden) for submitting the winning entry to the September Busy Beaver Challenge. This Challenge required contestants to do two things. First, contestants were to produce a 5-state "Busy Beaver" Turing Machine that writes as large a number of 1s as possible when given a blank input tape. Second, they had to write a general Turing Machine simulator that executes this Busy Beaver as quickly as possible. The problem statement provided a reference to a Turing Machine demonstrating that BB(5), the maximum number of 1s produced by any 5-state Busy Beaver, is at least 4098. Alas, none of the nine entries in this Challenge broke new ground in Busy Beaver research by providing a Busy Beaver that produced more than 4098 1s. So this competition was based on how quickly the Busy Beaver could be executed.

Claes' solution is extraordinarily fast, five times faster than the second place solution, and more than sixty times faster than the third-place solution. Upon investigation, while somewhat difficult to understand because of sparse commentary, Claes' entry is fascinating. To fully understand it, I inserted some debugging code and watched it in operation. I'll try to compensate for the terseness of the code by providing some additional explanation here.

The first thing Claes does is to call the CreateOptimizedTMRules routine to compile the Turing Machine rules into OptimizedTMRules. Two OptimizedTMRules are created for each Turing Machine rule, encoding both the rule and the associated binary input symbol. Each OptimizedTMRule contains a OneBitActionRoutines action field that combines two elements of the original Turing Machine rule: the move direction, and whether the output symbol is unchanged, 0, or 1. These actions are encoded as follows:

abaLeft, abaRight , abaHalt - leave the input unchanged and move left, right, or halt

abaLeftSet, abaRightSet, abaHaltSet - write a 1 and move left, right, or halt

abaLeftClear, abaRightClear, abaHaltClear - write a 0 and move left, right, or halt

This optimization allows Claes to factor out some logic tests during the Turing Machine simulation, and to avoid modifying the output tape when it doesn't change.

The runNBitTuringMachine performs the Turing Machine simulation. This routine processes the input tape in chunks of either 6 bits or 8 bits in size, trying the former first, and the latter if the former fails. It creates and uses two additional data structures, the TapeSegment structure that encodes a segment of the Turing Machine tape, and the MacroNTMRule data structure that further encodes the OptimizedTMRules. The TapeSegment data structure takes advantage of the fact that repeating sequences can occur on a Turing Machine tape, and do occur on Busy Beaver Turing Machines. It contains a symbol field, which is a 6- or 8-bit section of the tmTape, an exponent that contains a repetition count for that section, and left and right pointers to adjacent tape segments.

The MacroNTMRule is a little more difficult to explain. The 256 Turing Machine states that the problem statement requires entries to support are expanded into 512 OptimizedTMRules, and further expand into 512*256 MacroNTMRules. A MacroNTMRule is indexed by 8 bits that identify the OptimizedTMRule, plus of the TapeSegment symbol value (6 or 8 bits). In effect, the MacroNTMRule expands the symbol set from 1 bit to 6 or 8 bits, and expands the set of Turing Machine states accordingly.

When runNBitTuringMachine executes the Turing Machine, it first looks to see if the MacroNTMRule corresponding to the current state has been created. If not, it calls the createNbitMacroRule routine to create it. This routine simulates the effect of the OptimizedTMRules on the current input symbol, determines what newSymbol output is produced, counts the number of OptimizedTMRules executed for this one MacroNTMRule, characterizes the nature of the rule into an NBitActionRoutines action, and stores a pointer to the new MacroNTMRule state.

The NBitActionRoutines field characterizes the MacroNTMRule by encoding the move direction, whether the output is different from the input, and whether the state is changed after processing this chunk of input. The most interesting values for this NBitActionRoutines field are as follows:

  • tbaBounceLeft, tbaBounceRight - leave the input unchanged and reverse direction left or right
  • tTbaBounceLeftChange, tbaBounceRightChange - write changed output and reverse direction left or right
  • tTbaThruLeft, tbaThruRight - leave the input unchanged, continue moving left or right, and modify the state
  • tTbaThruLeftChange, tbaThruRightChange - write changed output, continue moving left or right, and modify the state
  • tTbaThruOptimized tbaThruRightOptimized - leave the input unchanged, continue moving left or right, and stay in the same state
  • tTbaThruChangeOptimized tbaThruRightChangeOptimized - write changed output, continue moving left or right, and stay in the same state

The optimizations in the runNBitTuringMachine code allow the final output of Claes' Busy Beaver to be represented in a few TapeSegments:

SegmentSymbol (Hex)Exponent (Hex)
00180
111
2361023
3371
40395

When runNBitTuringMachine returns, it indicates whether the attempt to execute with 6-bit tape segments succeeded or failed. If it failed, it is run again using 8-bit segments. While the 6-bit optimization is clearly intended to speed up the 5-state Busy Beaver Turing machines, it also kicks in for other machines. More importantly, the program meets the requirement of correctly simulating any Turing Machine with up to 256 states, without hard-coding any particulars of the Busy Beaver problem.

Before RunTuringMachine returns, it copies the TapeSegments back to the Turing Machine tape. (Until this point, the output of the Turing Machine exists only in the TapeSegment database.) For the 6-bit tape segment case, Claes uses an unrolled loop. For the 8-bit case, he uses memset. In both cases, the exponent field in the TapeSegment controls the number of times a TapeSegment symbol is copied.

I'd encourage you to take a look at Claes solution. I found it to be very clever.

The table below lists, for each of the solutions submitted, the number of 1s generated by the entry's Busy Beaver Turing Machine, the number of rules executed by that machine, the execution time of the Busy Beaver in milliseconds, and cumulative test case execution time. It also provides the code size, data size, and programming language used for each entry. 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.

Name# of 1s# of RulesBB Time (msecs)Time (msecs)Code SizeData SizeLang
Claes Wihlborg (9)4098117988260.933.0466801080033C
Ernst Munter (651)4098117988265.1022.824764749C++
Mike Miller40981179882661.49306.932044410C
Rob Shearer (51)40981179882664.92311.591432716C++
Randy Boring (133)409811798826213.091066.58445694C++
Willeke Rieken (112)409811798826489.742456.3491216C
Tom Saxton (165)409811798826734.273678.83708180C++
Yung-Lueng Lan409811798826743.583726.49137228C
Ladislav Hala (7)4098471768702954.955922.871520750C

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

... 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.

10. Downs, Andrew 12
11. Jones, Dennis 12
12. Day, Mark 10
13. Duga, Brady 10
14. Fazekas, Miklos 10
15. Selengut, Jared 10
16. Strout, Joe 10
17. Hala, Ladislav 7
18. Miller, Mike 7
19. Nicolle, Ludovic 7
20. Schotsman, Jan 7
21. Widyyatama, Yudhi 7
22. 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 Claes' winning Busy Beaver solution:

BusyBeaver.c
Copyright © 2000
Claes Wihlborg

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

#include "BusyBeaver.h"


BusyBeaver5
ulong /* return number of rules */ BusyBeaver5(
   TMRule theTMRules[]
       /* preallocated storage, return the rules for your BB machine */
)
{
   TMRule tm01[] = {
                           {0,0, 1,1,kMoveRight}, 
                           {0,1, 0,1,kMoveRight},
                           {1,0, 2,1,kMoveLeft},
                           {1,1, 1,1,kMoveLeft},
                           {2,0, 0,1,kMoveRight},
                           {2,1, 3,1,kMoveLeft},
                           {3,0, 0,1,kMoveRight},
                           {3,1, 4,1,kMoveLeft},
                           {4,0, 1,1,kHalt},
                           {4,1, 2,0,kMoveLeft}
                        };
      
   memcpy( theTMRules, tm01, 10*sizeof(TMRule) );
   return 5*2;
}

TYPES
typedef enum {obaNotYetDefined, 
                     obaLeft, obaLeftSet, obaLeftClear,
                     obaHalt, obaHaltSet, obaHaltClear, 
                     obaRight, obaRightSet, obaRightClear } OneBitActionRoutines;

typedef struct OptimizedTMRule { 
   OneBitActionRoutines action;
   struct OptimizedTMRule *newState; 
      /* set current state to newState when this rule fires */
} OptimizedTMRule;

typedef enum {tbaNotYetDefined, tbaUndefined,
                     tbaHaltFromLeft, tbaHaltFromRight, 
                     tbaBounceLeft, tbaBounceRight, 
                     tbaBounceLeftChange, tbaBounceRightChange, 
                     tbaThruLeft, tbaThruRight, 
                     tbaThruLeftChange, tbaThruRightChange, 
                  tbaThruLeftOptimized, tbaThruRightOptimized,
                     tbaThruLeftChangeOptimized, 
            tbaThruRightChangeOptimized } NBitActionRoutines;

typedef struct MacroNTMRule { 
   NBitActionRoutines action;
   unsigned char newSymbol;
   unsigned short ruleCount;
   struct MacroNTMRule *newState;
        /* set current state to newState when this rule fires */
} MacroNTMRule;

typedef struct TapeSegment { 
   unsigned int symbol;
   unsigned int exponent;
   struct TapeSegment *left,*right;   
} TapeSegment;

GLOBAL VARIABLES
static OptimizedTMRule optimizedTMRules[512];
static unsigned int highestState;

static    MacroNTMRule rules[256*2*256];

static unsigned int nBit, maxBit;

#define tapeDim 1520
static int nxtTapeIx;
static TapeSegment myTape[tapeDim], *freeSegment, *rightmostSegment, *leftmostSegment;

static unsigned char *TheTapeCenter;
static ulong allocatedLeft, maxALeft, allocatedRight, maxARight;
static ulong numberOf1sOnInputTape;

static int aLotOfZeroes[] = {
                     0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 
                     0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 
                     0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 
                     0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 
                     0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0      };

FUNCTION PROTOTYPES
static Boolean CreateOptmizedTMRules( 
   TMRule theTMRules[],     /* contains the rules for your BB machine */
   ulong numberOfTMRules);
   
static void createNbitMacroRule( unsigned int inSymbol, MacroNTMRule *inState );

static Boolean MoreSegments( void );
static TapeSegment *GetFreeSegment( void );
static TapeSegment *expandLeft( void );
static TapeSegment *expandRight( void );

static Boolean runNBitTuringMachine(
   ulong *numberOf1sGenerated,
   ulong *numberOfRulesExecuted
);

CreateOptmizedTMRules
static Boolean CreateOptmizedTMRules( 
   TMRule theTMRules[],     /* contains the rules for your BB machine */
   ulong numberOfTMRules)
{
   unsigned int i,state,inputSymbol;
   OptimizedTMRule *destRule;

   highestState = 0;
  memset( optimizedTMRules, 0x00, 512*sizeof(OptimizedTMRule) );

   for(i=0; i<numberOfTMRules; i++)
   {
      if ((state = theTMRules[i].oldState) > highestState) 
                  highestState = state;
      destRule = optimizedTMRules + ((theTMRules[i].oldState << 1) + 
                              (inputSymbol=theTMRules[i].inputSymbol));
      if (destRule->action != obaNotYetDefined)
      {
         printf("State: %d  Input: %d multiply defined\n",
                           theTMRules[i].oldState,inputSymbol);
         return false;
      }
      destRule->newState = optimizedTMRules + 
                                                   (theTMRules[i].newState << 1);
      destRule->action = obaHalt + 3*theTMRules[i].moveDirection;
      if (inputSymbol != theTMRules[i].outputSymbol)
            if (theTMRules[i].inputSymbol) destRule->action+=2; 
            else destRule->action++;
   }
   return true;
}

createNbitMacroRule
static void createNbitMacroRule( unsigned int inSymbol, 
                              MacroNTMRule *inState )
{
   int   mySymbol = inSymbol;
   int bit;
   OptimizedTMRule *state;
   int iState;
  OneBitActionRoutines action;
  int   ruleCount = 0;
  MoveDir inDir,outDir;
   
   iState = (inState - rules) >> nBit;
   state = optimizedTMRules + (iState & 0xfffe);
   
   if (iState & 1)
   {
      bit = 1;
      inDir = kMoveLeft;
   }
   else
   {
      bit = maxBit;
      inDir = kMoveRight;
   }

loop:
      ruleCount++;
      if (mySymbol & bit)
      {
         action = state[1].action;
         state = state[1].newState;
      }
      else
      {
         action = state->action;
         state = state->newState;
      }
      switch (action)
      {
      case obaNotYetDefined:
                  inState->ruleCount = ruleCount;
                  inState->newSymbol = mySymbol;
                  inState->action = tbaUndefined;
                  return;
      case obaLeft:
                  if ((bit <<= 1) <= maxBit) goto loop;
                  break;
      case obaLeftSet:
                  mySymbol |= bit;
                  if ((bit <<= 1) <= maxBit) goto loop;
                  break;
      case obaLeftClear:
                  mySymbol &= -1 - bit;
                  if ((bit <<= 1) <= maxBit) goto loop;
                  break;
      case obaHalt:
                  inState->ruleCount = ruleCount;
                  inState->newSymbol = mySymbol;
                  inState->action = (inDir == kMoveRight)? 
                                 tbaHaltFromLeft : tbaHaltFromRight;
                  return;
      case obaHaltSet:
                  mySymbol |= bit;
                  inState->ruleCount = ruleCount;
                  inState->newSymbol = mySymbol;
                  inState->action = (inDir == kMoveRight)? 
                                 tbaHaltFromLeft : tbaHaltFromRight;
                  return;
      case obaHaltClear:
                  mySymbol &= -1 - bit;
                  inState->ruleCount = ruleCount;
                  inState->newSymbol = mySymbol;
                  inState->action = (inDir == kMoveRight)? 
                                 tbaHaltFromLeft : tbaHaltFromRight;
                  return;
      case obaRight:
                  if (bit >>= 1) goto loop;
                  break;
      case obaRightSet:
                  mySymbol |= bit;
                  if (bit >>= 1) goto loop;
                  break;
      case obaRightClear:
                  mySymbol &= -1 - bit;
                  if (bit >>= 1) goto loop;
                  break;
      }
      
   inState->ruleCount = ruleCount;
   inState->newSymbol = mySymbol;
   inState->action = tbaBounceLeft;
   if (!bit) 
   {
      outDir = kMoveRight;
      inState->action++;
   }
   else
   {
      outDir = kMoveLeft;
      state++;
   }
   if (mySymbol != inSymbol)
      inState->action += 2;
   
   inState->newState = ((state - optimizedTMRules) << nBit) + 
                                                      rules;
   if (outDir == inDir)
   {
      inState->action += 4;
      if ((state - optimizedTMRules) == iState)
         inState->action += 4;
   }      

   return;
}
   
MoreSegments
static Boolean MoreSegments( void )
{
  int end;
  if (nBit == 6) return false;
  if (nxtTapeIx < tapeDim)
  {
     end = nxtTapeIx + 149;
     freeSegment = myTape + nxtTapeIx;
      do
      {
         myTape[nxtTapeIx].right = myTape + nxtTapeIx + 1;
      }
      while (++nxtTapeIx < end);
     myTape[nxtTapeIx++].right = 0;
      return true;
   }
//  printf("Segments finito!!!!\n");
   return false;
}

GetFreeSegment
static TapeSegment *GetFreeSegment( void )
{
   TapeSegment *tmp;
   
   if (freeSegment || MoreSegments())
   {
      tmp = freeSegment;
      freeSegment = tmp->right;
      return tmp;
   }
   return 0;
}

expandLeft
static TapeSegment *expandLeft( void )
{
  ulong delta;
   TapeSegment *tmp, *newCurrent, *oldLeftmost;
   unsigned char *p,*pOld;
  ulong oneCount, oldValue;

  if (!(delta = (((maxALeft - allocatedLeft) >300) ? 
                              300 : (maxALeft - allocatedLeft))))
      return 0;

  allocatedLeft += delta;
  p = TheTapeCenter - allocatedLeft;
  
  if (!(newCurrent = GetFreeSegment()))
      return 0;
  newCurrent->left = 0;
  oldLeftmost = leftmostSegment;
  leftmostSegment = newCurrent;
  
  if (!memcmp( p, aLotOfZeroes, delta))
  {
     newCurrent->symbol = 0;
     newCurrent->exponent = 8*delta / nBit;
  }
  else
  if (nBit == 8)
  {
     newCurrent->symbol = *p;
     newCurrent->exponent = 1;
     pOld = p + delta;
     while (++p < pOld)
     {
        if (*p == newCurrent->symbol)
        {
           newCurrent->exponent++;
        }
        else
        {
           tmp = newCurrent;
           if (!(newCurrent = GetFreeSegment()))
               return 0;
            newCurrent->left = tmp;
            tmp->right = newCurrent;
           newCurrent->symbol = *p;
           newCurrent->exponent = 1;
        }
     }
      tmp = newCurrent;
      do
     {
        if ((oldValue = tmp->symbol)!=0) 
        {
            oneCount = 0;
           do {
            ++oneCount;
            } while (oldValue = oldValue & (oldValue-1));
            numberOf1sOnInputTape += oneCount*tmp->exponent;
         }
     }
     while (tmp = tmp->left);
  }
  else/*nBit==6*/
  {
      return 0;
  }
  
  newCurrent->right = oldLeftmost;
  if (oldLeftmost)
  {
     oldLeftmost->left = newCurrent;
  }
  else
  {
     rightmostSegment = newCurrent;
  }
  return newCurrent;
}

expandRight
static TapeSegment *expandRight( void )
{
  ulong delta;
   TapeSegment *tmp, *newCurrent, *oldRightmost;
   unsigned char *p,*pOld;
  ulong oneCount, oldValue;

  if (!(delta = (((maxARight - allocatedRight) >300) ? 
                              300 : (maxARight - allocatedRight))))
      return 0;

  pOld = TheTapeCenter + allocatedRight;
  allocatedRight += delta;
  
  if (!(newCurrent = GetFreeSegment()))
      return 0;
  newCurrent->right = 0;
  oldRightmost = rightmostSegment;
  rightmostSegment = newCurrent;
  
  if (!memcmp( pOld, aLotOfZeroes, delta))
  {
     newCurrent->symbol = 0;
     newCurrent->exponent = 8*delta / nBit;
  }
  else
  if (nBit == 8)
  {
     p = pOld + delta -1;
     newCurrent->symbol = *p;
     newCurrent->exponent = 1;
     while (—p >= pOld)
     {
        if (*p == newCurrent->symbol)
        {
           newCurrent->exponent++;
        }
        else
        {
           tmp = newCurrent;
           if (!(newCurrent = GetFreeSegment()))
               return 0;
            newCurrent->right = tmp;
            tmp->left = newCurrent;
           newCurrent->symbol = *p;
           newCurrent->exponent = 1;
        }
     }
      tmp = newCurrent;
      do
     {
        if ((oldValue = tmp->symbol)!=0) 
        {
            oneCount = 0;
           do {
            ++oneCount;
            } while (oldValue = oldValue & (oldValue-1));
            numberOf1sOnInputTape += oneCount*tmp->exponent;
         }
     }
     while (tmp = tmp->right);
  }
  else/*nBit==6*/
  {
      return 0;
  }
  
  newCurrent->left = oldRightmost;
  oldRightmost->right = newCurrent;
  return newCurrent;
}


runNBitTuringMachine
static Boolean runNBitTuringMachine(
   ulong *numberOf1sGenerated,
   ulong *numberOfRulesExecuted
)
{
// Local data areas
   ulong oneCount;
   ulong ruleCount = 0;
    int oldValue,i;
    MacroNTMRule *state;
    TapeSegment *currentSegment, *tmp;
    Boolean resultat = false;

// Init 

   *numberOf1sGenerated = 0;
   numberOf1sOnInputTape = 0;
   
  memset( rules, 0x00, 
                     (highestState+1)*2*(1<<nBit)*sizeof(MacroNTMRule) );
  state = rules;  

  for (i=0;i<19;i++) 
  {
     myTape[i].right = myTape + i + 1;
  }
  myTape[19].right = 0;
  freeSegment = myTape;

   rightmostSegment = 0;
   leftmostSegment = 0;
   allocatedLeft = 0;
   allocatedRight = 0;
   
  expandLeft();
  currentSegment = expandRight();
  
mainLoop:
     state += currentSegment->symbol;
loop:
     ruleCount += state->ruleCount;
     switch (state->action)
     {
     case tbaNotYetDefined:
        createNbitMacroRule( currentSegment->symbol, state );
                 goto loop;
                 
     case tbaUndefined:
                 goto avsluta;
     
     case tbaHaltFromLeft:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment)) 
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp->left;
                    currentSegment->left->right = currentSegment;
                    currentSegment->right = tmp;
                    tmp->left = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 currentSegment->symbol = state->newSymbol;
                 break;
                 
     case tbaHaltFromRight:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment)) 
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp;
                    currentSegment->right = tmp->right;
                    tmp->right->left = currentSegment;
                    tmp->right = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 currentSegment->symbol = state->newSymbol;
                 break;
                 
     case tbaBounceLeft:
                 state = state->newState;
                 currentSegment = currentSegment->left;
                 goto mainLoop;
                 
     case tbaBounceRight:
                 currentSegment = currentSegment->right;
                 state = state->newState;
                 goto mainLoop;

     case tbaBounceLeftChange:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment)) 
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp->left;
                    currentSegment->right = tmp;
                    tmp->left->right = currentSegment;
                    tmp->left = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 currentSegment->symbol = state->newSymbol;
                 state = state->newState;
                 currentSegment = currentSegment->left;
                 goto mainLoop;

     case tbaBounceRightChange:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment))
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp;
                    currentSegment->right = tmp->right;
                    tmp->right->left = currentSegment;
                    tmp->right = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 currentSegment->symbol = state->newSymbol;
                 currentSegment = currentSegment->right;
                 state = state->newState;
                 goto mainLoop;

     case tbaThruLeft:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment)) 
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp;
                    currentSegment->right = tmp->right;
                    tmp->right->left = currentSegment;
                    tmp->right = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 state = state->newState;
                 if (currentSegment = currentSegment->left) 
                              goto mainLoop;
              if (currentSegment = expandLeft()) goto mainLoop;
                 break;

     case tbaThruRight:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment)) 
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp->left;
                    currentSegment->right = tmp;
                    tmp->left->right = currentSegment;
                    tmp->left = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 state = state->newState;
                 if (currentSegment = currentSegment->right) 
                              goto mainLoop;
           if (currentSegment = expandRight()) goto mainLoop;
                 break;

     case tbaThruLeftChange:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment)) 
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp;
                    currentSegment->right = tmp->right;
                    tmp->right->left = currentSegment;
                    tmp->right = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 currentSegment->symbol = state->newSymbol;
                 state = state->newState;
                 if (currentSegment = currentSegment->left) 
                              goto mainLoop;
           if (currentSegment = expandLeft()) goto mainLoop;
                 break;

     case tbaThruRightChange:
                 if (currentSegment->exponent > 1)
                 {
                    tmp = currentSegment;
                    if (!(currentSegment = freeSegment)) 
                    {
                       if (!MoreSegments()) goto avsluta;
                       currentSegment = freeSegment;
                    }
                    freeSegment = currentSegment->right;
                    currentSegment->left = tmp->left;
                    currentSegment->right = tmp;
                    tmp->left->right = currentSegment;
                    tmp->left = currentSegment;
                    currentSegment->exponent = 1;
                    tmp->exponent—;
                 }
                 currentSegment->symbol = state->newSymbol;
                 state = state->newState;
                 if (currentSegment = currentSegment->right) 
                              goto mainLoop;
           if (currentSegment = expandRight()) goto mainLoop;
                 break;

     case tbaThruLeftOptimized:
                 while ((tmp = currentSegment->left) && 
                        (currentSegment->symbol == tmp->symbol))
                 {
                    currentSegment->exponent += tmp->exponent;
                    tmp->right = freeSegment;
                    freeSegment = tmp;
                    currentSegment->left = tmp->left;
                    if (currentSegment->left)
                 currentSegment->left->right = currentSegment;
                    else
                       leftmostSegment = currentSegment;
                 }
                 ruleCount += state->ruleCount*
                                                (currentSegment->exponent-1);
                 state = state->newState;
                 if (currentSegment = currentSegment->left) 
                              goto mainLoop;
                 if (currentSegment = expandLeft()) goto mainLoop;
                 break;

     case tbaThruRightOptimized:
                 while ((tmp = currentSegment->right) && 
                                 (currentSegment->symbol == tmp->symbol))
                 {
                    currentSegment->exponent += tmp->exponent;
                    currentSegment->right = tmp->right;
                    tmp->right = freeSegment;
                    freeSegment = tmp;
                    if (currentSegment->right)
                       currentSegment->right->left = currentSegment;
                    else
                       rightmostSegment = currentSegment;
                 }
                 ruleCount += state->ruleCount*
                                                (currentSegment->exponent-1);
                 state = state->newState;
                 if (currentSegment = currentSegment->right) 
                              goto mainLoop;
                 if (currentSegment = expandRight()) goto mainLoop;
                 break;

     case tbaThruLeftChangeOptimized:
                 while ((tmp = currentSegment->left) && 
                                 (currentSegment->symbol == tmp->symbol))
                 {
                    currentSegment->exponent += tmp->exponent;
                    tmp->right = freeSegment;
                    freeSegment = tmp;
                    currentSegment->left = tmp->left;
                    if (currentSegment->left)
                 currentSegment->left->right = currentSegment;
                    else
                       leftmostSegment = currentSegment;
                 }
                 currentSegment->symbol = state->newSymbol;
                 ruleCount += state->ruleCount*
                                          (currentSegment->exponent-1);
                 state = state->newState;
                 if (currentSegment = currentSegment->left) 
                              goto mainLoop;
           if (currentSegment = expandLeft()) goto mainLoop;
                 break;

     case tbaThruRightChangeOptimized:
                 while ((tmp = currentSegment->right) && 
                        (currentSegment->symbol == tmp->symbol))
                 {
                    currentSegment->exponent += tmp->exponent;
                    currentSegment->right = tmp->right;
                    tmp->right = freeSegment;
                    freeSegment = tmp;
                    if (currentSegment->right)
                 currentSegment->right->left = currentSegment;
                    else
                       rightmostSegment = currentSegment;
                 }
                 currentSegment->symbol = state->newSymbol;
                 ruleCount += state->ruleCount*
                                          (currentSegment->exponent-1);
                 state = state->newState;
    if (currentSegment = currentSegment->right) goto mainLoop;
           if (currentSegment = expandRight()) goto mainLoop;
     }

   if (currentSegment)
   {
      resultat = true;
   }
  
avsluta:

   *numberOfRulesExecuted = ruleCount;

   for (currentSegment = leftmostSegment; currentSegment; 
               currentSegment=currentSegment->right)
  {
     if ((oldValue = currentSegment->symbol)!=0) 
     {
         oneCount = 0;
        do {
               ++oneCount;
         } while (oldValue = oldValue & (oldValue-1));
   *numberOf1sGenerated += oneCount*currentSegment->exponent;
      }
  }
// bug in following line corrected by JRB, doesn't affect results
//   numberOf1sGenerated -= numberOf1sOnInputTape;
   *numberOf1sGenerated -= numberOf1sOnInputTape;
   
   return resultat;
}

RunTuringMachine
Boolean /* return true for success */ RunTuringMachine(
   TMRule theTMRules[],
     /* contains the rules for your BB machine */
   ulong numberOfTMRules,
     /* the number of rules in theTMRules */
   ulong numBytesInHalfTape,
     /* half-size of the "infinite" Turing Machine tape */
   unsigned char *tmTape,
         /* pointer to preallocated Turing Machine tape storage */
         /* Each byte contains 8 tape symbols, each symbol is 0 or 1. */
         /* The tape extends from tmTape[-numBytesInHalfTape] to
                           tmTape[numBytesInHalfTape -1] */
         /* Tape position 0 is (tmTape[0] & 0x80),
             tape position 1 is (tmTape[0] & 0x40)
             tape position -1 is (tmTape[-1] & 0x01), etc. */
   ulong *numberOf1sGenerated,
     /* return the number of 1s placed on the tape */
   ulong *numberOfRulesExecuted
     /* return the number of rules executed when running BB, including the halt rule */
)
{

// Local data areas
    unsigned char *p;
    ulong myDoubleSymbol;
    Boolean resultat;
    TapeSegment *currentSegment;

// Init data areas
   if (!CreateOptmizedTMRules( theTMRules, numberOfTMRules))
   {
      return false;
   }

   TheTapeCenter = tmTape;
  
   nBit = 6;
   maxBit = 0x20;

  maxALeft = numBytesInHalfTape - numBytesInHalfTape%3;
  maxARight = maxALeft;
    
   resultat = runNBitTuringMachine( numberOf1sGenerated, 
         numberOfRulesExecuted );
    
  if (resultat)
  {
     p = tmTape - allocatedLeft;
      currentSegment = leftmostSegment;

#define CHECK_SEGMENT \
   if (—(currentSegment->exponent) == 0) \ 
                  currentSegment=currentSegment->right
   
      while (currentSegment)
      {
         myDoubleSymbol  = currentSegment->symbol << 18;
         CHECK_SEGMENT;
         myDoubleSymbol |= currentSegment->symbol << 12;
         CHECK_SEGMENT;
         myDoubleSymbol |= currentSegment->symbol << 6;
         CHECK_SEGMENT;
         myDoubleSymbol |= currentSegment->symbol;
         CHECK_SEGMENT;
         *p++ = myDoubleSymbol>>16;
         *p++ = myDoubleSymbol>>8;
         *p++ = myDoubleSymbol;
      }
     
     return true;
   }
   
   nBit = 8;
   maxBit = 0x80;
   
  maxALeft = numBytesInHalfTape;
  maxARight = maxALeft;
   nxtTapeIx = 20;

   resultat = runNBitTuringMachine( numberOf1sGenerated, 
                                 numberOfRulesExecuted );

   p = tmTape - allocatedLeft;
   for (currentSegment = leftmostSegment; currentSegment; 
               currentSegment=currentSegment->right)
   {
      memset( p, currentSegment->symbol, currentSegment->exponent );
      p += currentSegment->exponent;
   }
  
   return resultat;
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Google Chrome 61.0.3163.100 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
iMazing 2.4.2 - Complete iOS device mana...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
Quicken 4.6.4 - Complete personal financ...
Quicken makes managing your money easier than ever. Whether paying bills, upgrading from Windows, enjoying more reliable downloads, or getting expert product help, Quicken's new and improved features... Read more
Yasu 4.0.5 - System maintenance app.
Yasu was created with system administrators who service large groups of workstations in mind, Yasu (Yet Another System Utility) was made to do a specific group of maintenance tasks quickly within a... Read more
Stacks 3.5.5 - New way to create pages i...
Stacks is a new way to create pages in RapidWeaver. It's a plugin designed to combine drag-and-drop simplicity with the power of fluid layout. Features Fluid Layout: Stacks lets you build pages... Read more
Things 3.2 - Elegant personal task manag...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
Tweetbot 2.5.3 - Popular Twitter client.
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
Hopper Disassembler 4.2.19- - Binary dis...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
Monosnap 3.4.0 - Versatile screenshot ut...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel perfect with our... Read more
Duet 1.6.5.5 - Use your iPad as an exter...
Duet is the first app that allows you to use your iDevice as an extra display for your Mac using the Lightning or 30-pin cable. Note: This app requires a $14.99 iOS companion app. Version 1.6.5.5:... Read more

The best visual novels on mobile
Narrative games have been around for ages, but only now have they been creeping into the mainstream spotlight. These games tell some of the industry's finest stories, and they break new ground in terms of gameplay and mechanics regularly. Here are... | Read more »
The best new games we played this week -...
It's pretty much been one big release after another. We were privy to a bunch of surprises this week, with a lot of games we'd been waiting for quite some time dropping unexpectedly. We hope you're free this weekend, because there is a lot for... | Read more »
Stormbound: Kingdom Wars guide - how to...
Stormbound: Kingdom Wars is an excellent new RTS turned card battler out now on iOS and Android. Lovers of strategy will get a lot of enjoyment out of Stormbound's chess-like mechanics, and it's cardbased units are perfect for anyone who loves the... | Read more »
The best AR apps and games on iOS right...
iOS 11 has officially launched, and with it comes Apple's ARKit, a helpful framework that makes it easier than ever for developers to create mobile AR experiences. To celebrate the occassion, we're featuring some of the best AR apps and games on... | Read more »
Phoenix Wright: Ace Attorney - Spirit of...
Phoenix Wright: Ace Attorney - Spirit of Justice 1.00.00 Device: iOS Universal Category: Games Price: $.99, Version: 1.00.00 (iTunes) Description: ************************************************※IMPORTANT※・Please read the “When... | Read more »
Kpressor (Utilities)
Kpressor 1.0.0 Device: iOS Universal Category: Utilities Price: $4.99, Version: 1.0.0 (iTunes) Description: The ultimate ZIP compression application for iPhone and iPad. - Full integration of iOS 11 with support for multitasking.-... | Read more »
Find out how you can save £35 and win a...
Nothing raises excitement like a good competition, and we’re thrilled to announce our latest contest. We’ll be sending one lucky reader and a friend to the Summoners War World Arena Championship at Le Comedia in Paris on October 7th. It’s the... | Read more »
Another Lost Phone: Laura's Story...
Another Lost Phone: Laura's Story 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Another Lost Phone is a game about exploring the social life of a young woman whose phone you have just... | Read more »
The Witness (Games)
The Witness 1.0 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0 (iTunes) Description: You wake up, alone, on a strange island full of puzzles that will challenge and surprise you. You don't remember who you are, and... | Read more »
Egg, Inc. guide - how to build your gold...
Egg, Inc.'s been around for some time now, but don't you believe for one second that this quirky clicker game has gone out of style. The game keeps popping up on Reddit and other community forums thanks to the outlandish gameplay (plus, the... | Read more »

Price Scanner via MacPrices.net

Sunday sale: 13-inch 3.1GHz MacBook Pros for...
Amazon has 2017 13″ 3.1GHz MacBook Pros on sale today for up to $150 off MSRP, each including free shipping: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (MPXV2LL/A): $1649.99 $150 off MSRP – 13″ 3.1GHz... Read more
Looking for a 2017 12″ Retina MacBook? Save $...
Apple has Certified Refurbished 2017 12″ Retina MacBooks available for $200-$240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free.... Read more
Apple Offering Up To $455 Credit Toward iPhon...
iPhone 8 and 8 Plus are now available at the Apple Store, and you can receive up to $375 credit toward a new iPhone purchase when you trade in your eligible smartphone. Photo Courtesy Apple Just... Read more
AnyTrans Offers iOS Users Three Ways For Movi...
iMobie Inc. today announceed AnyTrans v6.0.1, which now can help iOS users move all data to iPhone 8/8 Plus seamlessly. The software is available both on Mac and Windows and fully able to move all... Read more
Snag a 13-inch 2.3GHz MacBook Pro for $100 of...
B&H Photo has 2017 13″ 2.3GHz MacBook Pros in stock today and on sale for $100 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook... Read more
Verizon offers new iPhone 8 for $100-$300 off...
Verizon is offering the new iPhone 8 for up to $300 off MSRP with an eligible trade-in: • $300 off: iPhone 6S/6S Plus/7/7 Plus, Google Pixel XL, LG G6, Moto Z2 Force, Samsung Galaxy S7/S7 edge/S8/S8... Read more
Apple Refurbished 2017 13-inch MacBook Pros a...
Apple has Certified Refurbished 2017 13″ Touch Bar MacBook Pros in stock today and available for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is... Read more
OWC USB-C Travel Dock with 5 Ports Connectivi...
OWC have announced the new OWC USB-C Travel Dock, the latest addition to their line of connectivity solutions. The USB-C Travel Dock lets you connect its integrated USB-C cable to a Mac or PC laptop... Read more
Pelican Products, Inc. Unveils Cases For All...
Pelican Products, Inc. has announced the launch of its full line of cases including Voyager, Adventurer, Protector, Ambassador, Interceptor (for the Apple iPhone 8 and 8 Plus backwards compatible... Read more
$100 off new 2017 13-inch MacBook Airs
B&H Photo has 2017 13″ MacBook Airs on sale today for $100 off MSRP including free shipping. B&H charges NY & NJ sales tax only: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): $899, $100 off... Read more

Jobs Board

Development Operations and Site Reliability E...
Development Operations and Site Reliability Engineer, Apple Payment Gateway Job Number: 57572631 Santa Clara Valley, California, United States Posted: Jul. 27, 2017 Read more
Development Operations and Site Reliability E...
Development Operations and Site Reliability Engineer, Apple Payment Gateway Job Number: 57572631 Santa Clara Valley, California, United States Posted: Jul. 27, 2017 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
Instructional Designer, *Apple* Product Doc...
Job Summary The Apple Product Documentation team is looking for an instructional designer or a video editor to write user documentation for its professional video 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.