TweetFollow Us on Twitter

July 02 Challenge

Volume Number: 18 (2002)
Issue Number: 07
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

One Time Pad

A one-time pad, used properly, provides a simple and unbreakable method of encryption. The “pad” is a random block of data equal in length to the message to be encoded. Two copies of the pad are needed, one for the message sender and one for the message receiver. The message to be encrypted is combined with the data in the pad by, for example, an exclusive OR; transmitted to the recipient, and decoded by the inverse operation. To be unbreakable, the pad must consist of truly random data, and it must be used only once.

Of course, you still need to securely exchange a one-time pad for each message to be encrypted. Let’s imagine that this is too much trouble, so what we are going to do instead is to use some common text as the basis for our one-time pad. We’ll select the “random” block as an offset from the first character in that text. And we’ll reuse our “one time” over and over again for different messages, with different offsets. Since the text isn’t random, and the one-time pad is used multiple times, we may have compromised security somewhat. This is a Good Thing, because your Challenge is to crack a sequence of messages encrypted with this scheme.

The prototype for the code you should write is:

void InitOneTimePad(
   const char *oneTimePad,
   /* NULL terminated text to be used for the one-time pad */
   /* You should ignore (skip) any characters not in the range 0x20-0x7E, inclusive */
   const char *dictionary[],
   /* list of NULL-terminated words in the vocabulary, sorted in ASCII order */
   long numDictionaryWords

char *DecryptMessage(
   /* return decrypted message */
   const char *encryptedMessage,
   /* NULL terminated text to decode */
   /* Guaranteed to contain only characters in the range 0x20-0x7E, inclusive */
   long *offset
   /* offset into the oneTimePad that you determine to be the basis for encryption */

void TermOneTimePad(void);

Your InitOneTimePad routine will be called each time our Intelligence Service captures a new one-time pad being used by our adversary. You will also be given a sorted dictionary of words in the vocabulary of our adversary. You can allocate memory and do whatever analysis might be appropriate.

For each intercepted message, your DecryptMessage routine will be called with the encrypted text. Fortunately, we know that our encrypting adversary uses the oneTimePad in a consistent manner. S/he uses a section of the pad starting at an offset known to the sender and receiver, but unknown to us. The section of the pad used is as long as the encrypted message, ignoring any characters in the pad (beyond the offset) outside the range of printable ASCII characters (0x20-0x7E). The nth character x of the clear text is encrypted as x+y-0x20, modulo the legal range of the character set, where y is the nth legal character of the oneTimePad beyond the offset value. So, if the oneTimePad [offset] starts with “When in the Course of human events”, and your clear text is “The British are coming.”, the encrypted text would be “,QKnB\Xt^\N%b[rWUmYUgv”, where denotes a nonprintable (and ignored) carriage return and denotes a space character that you might not otherwise notice. Note that nonprintable characters are counted in determining the starting position (offset) within the pad.

You should determine the section of the one-time pad that was used for encryption, decrypt the message, store the oneTimePad offset used for this message, and return a NULL-terminated string containing the clear text.

Your TermOneTimePad routine should return any dynamically allocated memory.

The winner of this Challenge will be the entry that correctly solves all test cases while incuring the lowest cost. Solutions will incur a cost of 10 points per millisecond of execution time, including the time incurred for initialization, decryption, and termination. You can earn a bonus of up to 25% reduction of incurred cost based on a subjective evaluation of the clarity of your code and commentary.

This will be a native PowerPC Carbon Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X.

Winner of the February, 2002 Challenge

In February, we asked contestants to defragment a simulated disk drive. Scoring was based on making the fewest number of block moves, regardless of block size. We also awarded a bonus of 25% for incorporating optional features, like an untimed display of defragmentation progress, and another 25% bonus based on elegance of the solution. Congratulations to Jonny Taylor for taking first place in the Disk Defragmentation Challenge.

Six people entered solutions for this Challenge and five of those solved the problem correctly. (The sixth violated the constraint against overlapping the source and destination blocks.) The best scoring solution, by Jan Schotsman, was submitted after the deadline and was therefore not eligible to win. Three entries, including both Jonny’s and the second-place entry from Ernst Munter, provided options to display the evolving solution or to replay the solution. Jonny also provided menu options to control the speed of the display. Jonny’s entry required approximately 25% fewer moves to defragment the disks, although it required nearly three times as much computation time to do so.

Several of the entries chose to defragment the simulated files in ways that also consolidated all free space into one block. This behavior was not required, and Jonny chose not to do that. Instead, he chose to leave large fragments in place where possible, reasoning that these are less likely to be relocated on densely occupied disks without being split up into multiple pieces. Jonny first employs an “intelligent move” algorithm, described in the ConsiderMovingFragment routine, that selects and moves file fragments which, when moved, would allow other fragments to be moved to their final destination. For fragments that remain after applying the intelligent algorithm, the GuaranteedMoveFragment routine moves all remaining file fragments to their final destination.

I evaluated solutions using five test cases, one small and relatively simple, and the others simulating densely populated disks with varying levels of fragmentation. The subjective evaluation of features was based on whether a display option was present, and on other menu options provided to control the solution and the display. The “elegance” criterion was based on code commentary, coding style, cleverness of the algorithm, and on the conciseness of the code. Johnny’s winning entry was downrated a little because of the complexity of the code, but earned points for being well commented. As it turns out, entries were ranked in the same order both with and without considering the subjective criteria.

The table below lists, for each of the solutions submitted, the total number of disk block moves used to defragment the desks, the total execution time in microseconds, the raw score based on moves and execution time, the subjective bonuses based on elegance and features, and the total score after taking the bonuses into consideration. It also lists the programming language used for each entry and the operating system used for the 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 Moves Time Defrag Elegance Features Total Lang OS
(usecs) Score (0-1.0) (0-1.0) Score
Jonny Taylor (37) 5951 108958 786190 0.65 1.00 461886 C++ Classic/9
Ernst Munter (275) 7641 38604 836448 1.00 0.75 470502 C++ Carbon/X
Ludovic Nicolle 8586 279473 1559817 0.75 0.00 1267352 C/ObjC Cocoa/X
Allen Stenger (49) 7733 570203 2290366 1.00 0.00 1717775 C++ Carbon/X
Jan Schotsman (16) (late) 5224 166567 738581 0.75 0.90 433916 C Classic/9
T.S. 4939 426949 1093346 0.65 0.00 915677 C++ Terminal/X

Top Contestants . . .

Listed here are the Top Contestants for the Programmer’s Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points Wins Total
(24 mo) (24 mo) Points
1. Munter, Ernst 265 9 872
2. Taylor, Jonathan 57 2 83
3. Stenger, Allen 53 1 118
4. Saxton, Tom 52 1 210
5. Rieken, Willeke 46 2 134
6. Wihlborg, Claes 40 2 49
8. Gregg, Xan 20 1 140
9. Mallett, Jeff 20 1 114
10. Cooper, Tony 20 1 20
11. Truskier, Peter 20 1 20

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

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

Rank Name Points Total
(24 mo) Points
7. Sadetsky, Gregory 22 24
12. Schotsman, Jan 16 16
13. Shearer, Rob 15 62
14. Hart, Alan 14 39
15. Boring, Randy 11 144
16. Nepsund, Ronald 10 57
17. Day, Mark 10 30
18. Desch, Noah 10 10
19. Flowers, Sue 10 10
20. Nicolle, Ludovic 7 62
21. Leshner, Will 7 7
22. Miller, Mike 7 7

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 Jonny’s winning Disk Defragmentation solution:

PROGRAMMER’s Defrag.cp
Copyright © 2002
Jonny Taylor

// #include files omitted because of length; see online archive

/*   The algorithm works as follows:
Load the information from the input file about where on the disk the fragments
            of each file are to begin with
      2.   Choose where on disk we want each file to end up
      3.   “Intelligent” algorithm: where possible, move fragments to their final positions
            with minimal unnecessary moves
      4.   “Guaranteed” algorithm: move any remaining fragments to their final positions 
            whatever additional moves this takes
   Three data structures are used by these algorithms.
      FreeRange represents a single contiguous range of disk blocks that are not
      currently occupied by any file fragment. Every FreeRange is as large as possible          
      –  i.e. it is not possible to have
         one FreeRange for blocks 4-9 and another for 10-14 in existance at the same 
      Fragment represents a single contiguous range of disk blocks belonging to the 
         same file
      FileLayout represents a single file, and has a linked list of all the fragments that 
         make it up
   In addition, there are four search trees that are maintained. These allow Fragments 
   to be searched by current position and by the final position that they will end up in, 
   and allow  FreeRanges to be searched by position and by length. The tree code is 
   explained and implemented in Trees.cp, but all that really matters is that insertion, 
   deletion and searching can be done in log(N) time.
   There are quite a few nasty cases to the algorithms I have used, which need special 
   treatment. This is particularly true for the “guaranteed” algorithm because it must be 
   able to handle anything at all.
   However for the most part the special cases are handled within a single function. 
   Functions that perform tasks such as “move a block out of the way” will do what 
   they are defined to do (though they may be allowed to fail), and will handle any 
   special cases themselves.
   The solution is fairly quick on reasonably complex test cases (such as test case 2 in 
   the sample code). It slows down roughly linearly as the number of files and 
   fragments on the disk increases. This results in unacceptably long running times for 
   very nasty test cases with big disks full of tiny files. However I suspect that any 
   solution would do the same.
struct FileLayout;
struct Fragment;
struct FreeRange;

typedef struct FreeRange
   long   firstBlock;
   long   lastBlock;
   Node   *positionTreeNode;
   Node   *lengthTreeNode;
// method declarations omitted, see online archive
} FreeRange;

typedef struct FileLayout
   Fragment   *firstFragment;
   Boolean      placed;
   long      fileLength;
// method declarations omitted, see online archive
} FileLayout;

typedef struct Fragment
   long      startBlock;
   long      finalStartBlock;
   long      numBlocks;
   FileLayout   *owningFile;
   Boolean      inFinalPosition;
   Node      *currentStartTreeNode;
   Node      *finalStartTreeNode;
   long      firstFileBlock;
   Boolean      blockedBySelf;
   long      fragmentsBlockingThis;
   long      processedInThisLoop;
   long      score;
   Fragment   *next;
   Fragment   *nextInMoveList, *prevInMoveList;
   Fragment   *nextInFinalStartList, *prevInFinalStartList;
// method declarations omitted, see online archive
} Fragment;

#define kNotProcessed         -1
#define kMaxArraySize         32768
#define ABS(VAL)            ( (VAL) < 0 ? -(VAL) : (VAL) )
#define MIN(A, B)            ( (A) < (B) ? (A) : (B) )

FileLayout   **theFiles, **unplacedFilesSortedByLength;
Fragment   **sortedFragmentList;   
   /* Sorted array of fragment pointers. 
      Sort key varies depending on which bit of code we are in   */
Fragment   *firstFinalStart;      
   /* Linked list of fragments, ordered by final start   */
Fragment   *prevInList;
   /* Only used when setting up firstFinalStart   */

extern DisplayType      displayProgress;
extern AnimationType   animationType;

/*   Roots for the search trees   */
Node   *fragmentCurrentStartRoot,*fragmentFinalStartRoot;
Node   *freeRangeLengthRoot,*freeRangePositionRoot;
/*   General global variables   */
long      totalFragments, totalBlocks, totalFiles, 
long      uniqueSearchIndex, firstFreeBlock;
/*   Heads of linked lists of fragments that are free to move to their final positions   */
Fragment   *firstFragmentToMove, *firstOverlappingFragmentToMove;

// function prototypes omitted, see online archive

Main Defragmentation Code
// DoTests deleted for length, see online archive

void Defragment(void)
// test case loop omitted for length, see online archive
      totalFragments = 0;
      totalBlocks = 0;
      totalFiles = 0;
      fragmentsPositioned = 0;
      fragmentCurrentStartRoot = NULL_NODE;
      fragmentFinalStartRoot = NULL_NODE;
      freeRangeLengthRoot = NULL_NODE;
      freeRangePositionRoot = NULL_NODE;

// input logic omitted for length, see online archive


      /*   Rebuild the free range list to represent the current file positions
         (instead of their final positions)   */
      firstFreeBlock = 0;
      InorderTreeWalk(fragmentCurrentStartRoot, BuildFreeRangeTree);

      if (totalBlocks - 1 >= firstFreeBlock)
         new FreeRange(firstFreeBlock, totalBlocks - 1);

      /*   Move the fragments to their final positions      */

      /* Release memory   */
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
         delete theFiles[fileNum];
// test case completion logic omitted for length, see online archive

void RearrangeFragments(void)
   Fragment   *fragPtr;

   SetDescriptionString(“Moving fragments (intelligent algorithm)”);

   for (fragPtr = firstFinalStart; fragPtr != NULL; 
            fragPtr = fragPtr->nextInFinalStartList)
      if (!fragPtr->inFinalPosition)
         /*   Check which fragments’ FINAL POSITION is blocked solely by the
            CURRENT position of this one      */
   firstFragmentToMove = NULL;
   firstOverlappingFragmentToMove = NULL;
   /* First do a check for fragments that can move immediately to their destination 
      square */
   for (fragPtr = firstFinalStart; fragPtr != NULL; fragPtr = 
      if ((!fragPtr->inFinalPosition) &&
         (fragPtr->fragmentsBlockingThis == 0))
   uniqueSearchIndex = 0;
   for (fragPtr = firstFinalStart; fragPtr != NULL; 
         fragPtr = fragPtr->nextInFinalStartList)
   /*   There will probably be fragments left to rearrange (at least if the disk is densely 
      populated). Switch to a simple, but failsafe, algorithm to place these remaining 
      fragments      */
         “Moving fragments (guaranteed algorithm)”);

void BuildFreeRangeTree(void *keyPtr)
void KillAllFreeRanges(Node *x)
// these routines omitted for length, see online archive

Choosing File Positions
/*   Before I actually move any fragments, I decide what final position I want each file 
   to end up in. We could just aim to position the first file at the start of the disk, the 
   next one immediately after that, and so on. However in this problem this is not a 
   requirement. Instead we can choose to place the files anywhere we want, as long as 
   each individual file is contiguous. It is advantageous to choose a final position for 
   as many files as possible, such that one of its fragments is already in its final 
   position, and doesn’t have to be moved at all.
   I can’t see an easy way of determining the optimum file layout. Instead I employ a 
   greedy algorithm, picking the fragment that looks best as the first “anchor” 
   fragment, and so on. I experimented with several methods of scoring each fragment 
   as a potential anchor, taking into account factors such as:
      - Whether any fragments of the file overlap their final destination (a bad thing as 
         they then can’t be moved in a single step)
      - Whether any other fragments from the same file are also in their final positions 
         (a good thing)
      - Some attempt to determine how much selecting this file would prevent us from 
         selecting several other files
   In the end, I didn’t bother with this. Densely-populated disks are the ones that take 
   longest to solve, and the most moves to rearrange. In those cases the limiting factor 
   is the size of the fragments; a large fragment is likely to be impossible to move 
   around intact, and will have to be split up to move it. I therefore decided to 
   prioritise large fragments when selecting anchors.
   Incidentally, a final factor, that I have not tried to take into account at all, is the size 
   of the free spaces that are left in the final layout. I suspect it would be better to 
   select a final layout with fewer, larger spaces since this makes it easier to rearrang 
   the disk.
   Once I have selected as many anchor fragments as I can, there will probably be files 
   left unplaced. I don’t try and do anything clever with these. I just put them at the 
   start of the largest empty space that is available. Unfortunately, there is a problem. 
   Choosing the anchor fragments means the remaining free space may be split into a 
   number of ranges. It may be impossible to fit the remaining files into the spaces 
   (remembering the files must be contiguous). Even if it is possible, it may not be 
   possible to quickly find a valid layout. There is no obvious way of seeing when we 
   have chosen too many anchor fragments. Instead, I use a binary search method. I try 
   placing as many anchor fragments as I can, and see if I can position the remaining 
   files. If I can’t, I try with half as many anchor fragments, and continue refining the 
   value until I have a reasonable one.   */

void ChooseFilePositions(void)
   long      fileNum;
   Fragment   *theFragment;
   SetDescriptionString(“Choosing file positions”);

   /*   Sort the fragments by their length   */
   qsort(sortedFragmentList, totalFragments, sizeof(Fragment*), 

   /*   Try .........*/
   if (ArrangeFilesWithAnchorLimit(totalFiles) == false)
      long   minimumAnchorCount = 0, maximumAnchorCount = 
         totalFiles + 1;
      long   middle;

      for (long iter = 0; iter < 5; iter++)
         middle = (minimumAnchorCount + maximumAnchorCount) / 2;
         if (ArrangeFilesWithAnchorLimit(middle) == true)
            minimumAnchorCount = middle;
            maximumAnchorCount = middle;
         if (maximumAnchorCount - minimumAnchorCount == 1)
      if (middle != minimumAnchorCount)
   /*   Now we have settled on an arrangement, build the final start tree and linked list.
      Because this tree remains static, we don’t actually need to do all the red-black 
      insertions. We could just determine the sort order and then build a balanced 
      binary search tree by hand. However, doing RBInsert for every fragment is faster 
      than a quicksort of every fragment. However all we really need to do is a 
      quicksort of every file. If the number of files is less than half the number of 
      fragments, it turns out it is worth building the tree by hand. This will also lead to 
      a slightly better-balanced tree, which will speed up tree searches a little.
      We also take the opportunity to see which fragments are already in their final 
      position. If they are we mark them as such; if they aren’t then we add them to the 
      list of fragments (sortedFragmentList), which is ordered by final start. This linked 
      list will remain static until we come to the “guaranteed algorithm”, at which point 
      it may grow as fragments are split   */

   firstFinalStart = NULL;
   prevInList = NULL;
   if (totalFragments / totalFiles >= 2)
      /*   Sort the files by final position and thereby sort the fragments   */
      qsort(theFiles, totalFiles, sizeof(FileLayout*), 
      long fragNum = 0;
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
         for (theFragment = theFiles[fileNum]->firstFragment;
             theFragment != NULL;
             theFragment = theFragment->next)
            sortedFragmentList[fragNum++] = theFragment;

      /*   Build the tree, given the sorted fragment list   */
      fragmentFinalStartRoot = BuildBalancedTree(sortedFragmentList,
             0, totalFragments - 1, NULL_NODE);
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
         for (theFragment = theFiles[fileNum]->firstFragment;
             theFragment != NULL;
             theFragment = theFragment->next)
            ASSERT(theFragment->finalStartTreeNode == NULL);


            theFragment->finalStartTreeNode = new Node;
            theFragment->finalStartTreeNode->data = theFragment;
            theFragment->finalStartTreeNode->keyLong = 
            theFragment->finalStartTreeNode->keysNodePtr = 

Node *BuildBalancedTree(Fragment ** fragList, long first, 
            long last, Node *parent)
// this routine omitted for length, see online archive

Boolean ArrangeFilesWithAnchorLimit(long maxAnchors)
   long   fileNum, frag;
   long   numUnplacedFiles = 0;
   /*   Attempt to come up with a file arrangement that uses up to maxAnchors anchor 
      fragments   */

   /*   We start with no file positions chosen, and the whole disk available   */
   new FreeRange(0, totalBlocks - 1);
   /*   We should be able to leave some fragments where they are, and build up around 
      them the file that they are part of. I choose the largest fragments as a priority, 
      since they will be hardest to move around when we are rearranging the disk.
      This is not always ideal. For example, picking the largest fragment might prevent 
      us from picking a large number of slightly smaller ones. However it is the only 
      quick and simple way that I could find   */
   long numPlaced = 0;
   for (frag = totalFragments - 1; 
      (frag >= 0) && (numPlaced < maxAnchors); frag—)
      Fragment   *fragPtr = sortedFragmentList[frag];
                        /* sortedFragmentList is currently sorted by length   */
      FileLayout   *owningFile = fragPtr->owningFile;
      if (!owningFile->placed)
         /* This file has not been assigned a position yet Check if any other files we 
            have already positioned are blocking this position   */
         FreeRange *rangeAtStart = 
         if (rangeAtStart->lastBlock >= 
            fragPtr->firstFileBlock + owningFile->fileLength - 1)
            /*   There is no file blocking this position   */
            owningFile->placed = true;
   /*   We now probably have some files left over, to try and fit into the gaps that are 
      left. My heuristic here is to start with the largest file, and place it in the largest 
      gap available. This is far from ideal, but I suspect that finding the optimum 
      solution is an NP-complete problem (similar to sack-filling problems), so I’m not 
      too bothered!   */

   /*   Sort the unplaced files in order of total length   */
   for (fileNum = 0; fileNum < totalFiles; fileNum++)
      if (!theFiles[fileNum]->placed)
         unplacedFilesSortedByLength[numUnplacedFiles] = 
   qsort(unplacedFilesSortedByLength, numUnplacedFiles, 
         sizeof(FileLayout*), FileLayout::QSCompareByLength);
   for (fileNum = numUnplacedFiles - 1; fileNum >= 0; fileNum—)
      FreeRange *chosenPosition = 
      if (chosenPosition->lastBlock - chosenPosition->firstBlock + 1 
                  < unplacedFilesSortedByLength[fileNum]->fileLength)
         chosenPosition = NULL;
      if (chosenPosition != NULL)
         /*   Position the file at the start of the free range we have selected   */
         /*   Failed to position the file. Break out immediately   */

   /*   Delete all the free ranges and their search trees. Either we are going to restart the 
      algorithm, or we are going to move on to the next phase, for which we need the 
      INITIAL free ranges, rather than the FINAL ones   */
   freeRangeLengthRoot = NULL_NODE;
   freeRangePositionRoot = NULL_NODE;      

   if (fileNum >= 0)
      /*   We didn’t manage to position all the files   */

void FileLayout::SetFinalPosition(FreeRange *rangeToPlaceIn, 
            long finalStartBlock)
   for (Fragment *theFragment = firstFragment;
       theFragment != NULL;
       theFragment = theFragment->next)
      theFragment->finalStartBlock = finalStartBlock;
      finalStartBlock += theFragment->numBlocks;


void Fragment::CheckIfInFinalPosition(void)
void UnplaceAll(void)
// these routines omitted for length, see online archive

“Guaranteed” Algorithm
/*   We work through the fragments that have not yet been moved to their final 
   positions. For each one,clear any blocking fragments out of the way and move it to 
   where they were.
   This algorithm must be able to cope with all situations. This means that special 
   handling is necessary when temporary storage elsewhere on the disk is limited, and 
   when the fragment partially overlaps its final position   */

// this section deleted for length, see online archive

“Intelligent” Algorithm
/*   The idea is to identify fragments that, if moved, allow another fragment to be 
   moved to its destination.Hopefully, moving that fragment to its destination frees up 
   the space that another fragment needs to move into, and so on. For a disk with a 
   reasonable amount of free space (around half), this will move nearly all of the 
   fragments. For a disk with a very small amount of free space, it will not generally 
   work very well.

   Each fragment keeps track of how many other fragments are blocking it from being 
   moved to its final position
   1.   Find a fragment that is blocked by only one other fragment
   2.   See if it is possible to move that blocking fragment somewhere else
   3.   If THAT fragment could be moved to its destination were it not for one single 
      fragment blocking it, then repeat as many times as possible until we end up with a 
      blocking fragment we can’t move to its final destination
   4.   Move that fragment somewhere out of the way
   5.   Update the blockage information as a result of the move
   6.   While there are unblocked fragments, move them to their destinations, updating 
      the blockage information again
   There are two problems with this strategy. We might end up covering the same 
   ground several times. If we consider a long chain of dependencies before giving up, 
   we might follow that chain each time we encountered one of its members. Also, it is 
   possible to have a circular dependency chain where every fragment is waiting for 
   the next one in the loop. Under those circumstances we might end up following the 
   chain round and round for ever. To avoid both these cases I fill in the ‘unique search 
   index’ when I first process a fragment. If I come across a search index smaller than 
   the current one, I abort the search. This is not very elegant, but it works!*/

void ConsiderMovingFragment(Fragment *fragPtr)
   if ((!fragPtr->inFinalPosition) &&
      (fragPtr->fragmentsBlockingThis <= 1) &&
      (fragPtr->processedInThisLoop == kNotProcessed))
      /*   This fragment is one that we want to be able to move   */
      Fragment   *fragToMove = fragPtr;
      FreeRange   *longestRangePtr = (FreeRange*)(TreeMaximum(
      long      longestFreeRange = longestRangePtr->lastBlock – 
         longestRangePtr->firstBlock + 1;
      /*   Given the fragment that we want to move, find the one that is blocking it. 
         Check if that fragment can be moved   ...... continue description......*/
      fragPtr->processedInThisLoop = uniqueSearchIndex;
         /*   Find the fragment blocking this one   */
         Fragment *result = (Fragment*)DATA(TreeSearch(
            fragmentCurrentStartRoot, fragToMove,
         ASSERT(result != NULL);

         /*   If there isn’t anywhere we can move that fragment to, stop now   */
         if (result->numBlocks > longestFreeRange)
         /*   Processed in a previous loop, or already in this loop (in which case we have 
            found a ring where every fragment is preventing the next one from being 
            moved - moving any of these will allow all to be moved one after the other). 
            Stop the search   */
         if ((result->processedInThisLoop <= uniqueSearchIndex) &&
            (result->processedInThisLoop != kNotProcessed))
         /*   If we move ‘result’ we will be able to move ‘fragToMove’ into the space it has 
            left   */
         fragToMove = result;
         fragToMove->processedInThisLoop = uniqueSearchIndex;
         /*   If we get to a fragment that is blocked by more than one, we have reached 
            the end of the chain. Stop the loop.   */
      } while (fragToMove->fragmentsBlockingThis == 1);

      if ((fragToMove == fragPtr) &&
         (fragToMove->fragmentsBlockingThis != 0))
         return;         /*   Failed to find a place to move the one blocking it   */

      if ((fragToMove->processedInThisLoop < uniqueSearchIndex) &&
         (fragToMove->processedInThisLoop != kNotProcessed))
         return;         /*   Already processed earlier   */
      /*   Now we have decided on a fragment to move, make the move. We should have 
         checked earlier on that there a suitable space to move the fragment into. If we 
         are very unlucky, though,the new space we select will still be blocking the 
         range we are trying to free, so the call isn’t 100% guaranteed to allow any other 
         fragments to move.   */

void MarkFragmentAsBlockedBy(Fragment *theBlockedFragment, 
      Fragment *theBlocker)
// this routine omitted for length, see online archive

void MoveFragmentsToDestinationSquares(void)
   /*   While there are fragments queued as ready to move, move them to their final 
      destinations. Moving one fragment may add extra fragments to the lists. Moving 
      it may occasionally block one of the other fragments that are queued. In that case, 
      the fragment is removed from the queue automatically   */
   Fragment *fragToMove;
      while (firstOverlappingFragmentToMove != NULL)
         fragToMove = firstOverlappingFragmentToMove;
      while (firstFragmentToMove != NULL)
         fragToMove = firstFragmentToMove;
   } while (firstOverlappingFragmentToMove != NULL);

void Fragment::ForEveryFragmentBlockedByThisOne(
      void (*theCallback)(Fragment *theBlockedFragment, 
      Fragment *theBlocker))
void Fragment::FragmentAboutToUnblock(
      Fragment *theBlockedFragment, Fragment *theBlocker)
void Fragment::FragmentAboutToBlock(Fragment *theBlockedFragment, 
         Fragment *theBlocker)
// these routines omitted for length, see online archive

void Fragment::FreeToMoveToFinalPosition(void)
   /*   This function is called when there is nothing preventing the fragment from 
      moving to its final position. We do not immediately move the fragment, though – 
      we just add it to the relevant queue so it will be moved in the next call to 
      MoveFragmentsToDestinationSquares. This function was probably called 
      because another fragment is about to move, unblocking this fragment’s final 
      position. That fragment might move to a new position that is STILL blocking this 
      fragment, though, so we will
      have to wait before we actually move this fragment   */
   ASSERT(nextInMoveList == NULL);
   ASSERT(prevInMoveList == NULL);
   if (blockedBySelf)
      /*   Fragment is only blocked by itself. Add it to the list of ones to move.
         There is a separate list for these as we might want to wait for a bigger gap to be
         available as temporary storage   */
      nextInMoveList = firstOverlappingFragmentToMove;
      nextInMoveList->prevInMoveList = this;
      prevInMoveList = NULL;
      firstOverlappingFragmentToMove = this;
      /* Can be moved directly to final position   */
      nextInMoveList = firstFragmentToMove;
      nextInMoveList->prevInMoveList = this;
      prevInMoveList = NULL;
      firstFragmentToMove = this;

void Fragment::RemoveFromLists(void)
// this routine omitted for length, see online archive

Moving Fragments
void Fragment::MoveToPosition(long destBlock, Boolean 
   /*   Move the fragment as instructed, and inform any interested parties   */
   /*   We may want to keep track of which fragments are being blocked at the moment. 
      If so,maintainBlockageCount is ‘true’   */
   if (maintainBlockageCount)
      /*   Inform other fragments that this fragment’s current position is about to become 
         free   */
   /*   Mark the place it was as free   */
   OutputMoveInstruction(startBlock, destBlock, numBlocks, 
   startBlock = destBlock;
   /*   We might have moved it to its final destination by chance   */
   if (startBlock == finalStartBlock)
      inFinalPosition = true;

   /*   Do the standard processing for when a fragment has moved   */

void Fragment::MoveToPositionNoOutput(long destBlock)
// this routine omitted for length, see online archive

void Fragment::MoveOutOfTheWay(void)
// this routine omitted for length, see online archive

void Fragment::MoveToFinalPosition(Boolean maintainBlockageCount)
// this routine omitted for length, see online archive

void Fragment::MoveToFinalOverlappingPosition(Boolean maintainBlockageCount)
   /*   We want to find the most efficient way of making the move. Because the source 
      and destination ranges are not allowed to overlap for a move instruction, it cannot 
      be done with a single instruction. We could either move it somewhere completely 
      different and then back to its destination, or we could move it in several chunks, 
      but without using any extra temporary storage. This is treated as a special case 
      because there are several ways of doing it, and a number of nasty catches we need 
      to check for      */
   ASSERT(fragmentsBlockingThis == 0);
   long   movement = ABS(startBlock - finalStartBlock);
   long   blocksAvailable, firstBlockAvailable;

   /*   Start by working out how many steps it would take to move the fragment without 
      using any extra temporary storage.Calculate numBlocks/movement, rounded UP 
   FreeRange   *bestRange = NULL;
   long      bestSteps = (numBlocks + movement - 1) / movement;
   long      blocksAvailableInBestRange, 
   long      steps;
   if (bestSteps > 2)
      /*   We would take at least two steps to move the fragment via any extra space we 
         might choose, so only consider other options if we can’t do it in two moves */

      /*   Find the biggest space available, and see how many steps it would take to move 
         the fragment via it. Note that this largest range may be the one that includes the 
         destination area, in which case not all
         of it is available as temporary storage   */
      FreeRange   *largestFreeRange = 
      if ((startBlock > finalStartBlock) &&
         (largestFreeRange->lastBlock == startBlock - 1))
         /*   Overlap between source and dest fragment positions is at the end of the 
            destination,and overlap with this free range is at the start of the destination */
         blocksAvailable = finalStartBlock – 
         firstBlockAvailable = largestFreeRange->firstBlock;
      else if ((startBlock < finalStartBlock) &&
             (largestFreeRange->firstBlock == startBlock + numBlocks))
         /*   Overlap with existing fragment position is at the start of the destination, and 
            overlap with the free range is at the end of the destination */
         blocksAvailable = largestFreeRange->lastBlock – 
               (finalStartBlock + numBlocks) + 1;
         firstBlockAvailable = finalStartBlock + numBlocks;
         /*   The free range we have found is somewhere completely different (the ideal 
            case!)   */
         blocksAvailable = largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1;
         firstBlockAvailable = largestFreeRange->firstBlock;

      if (blocksAvailable > 0)
         /*   Work out how many steps it would take to transfer the whole fragment.
            Calculate 2 * (numBlocks / blocksAvailable, rounded UP)   */
         steps = 2 * ((numBlocks + blocksAvailable - 1) / 

         if (steps < bestSteps)
            /*   This is the best option so far   */
            bestSteps = steps;
            bestRange = largestFreeRange;
            blocksAvailableInBestRange = blocksAvailable;
            firstBlockAvailableInBestRange = firstBlockAvailable;
         if (blocksAvailable != largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1)
            /*   The range we just looked at is the one that includes the destination 
               position. This has been taken into account in the calculations we just made 
               to rate it. However, this means that the second-largest free range may 
               actually be a better choice. Note that since the last range we considered 
               overlapped the destination, we know this
               one doesn’t      */
            largestFreeRange = (FreeRange*) DATA(TreePredecessor(
            blocksAvailable = largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1;
            /* Calculate 2 * (numBlocks / blocksAvailable, rounded UP)   */
            steps = (2 * ((numBlocks + blocksAvailable - 1) / 

            if (steps < bestSteps)
               /*   This is the best option so far   */
               bestSteps = steps;
               bestRange = largestFreeRange;
               blocksAvailableInBestRange = blocksAvailable;
               firstBlockAvailableInBestRange = 
   long   offset, blocksToMoveThisTime,
         blocksAlreadyMoved = 0,
         blocksLeftToMove = numBlocks;

   if (bestRange == NULL)
      /*   The best way of moving it doesn’t use any additional storage. We move as 
         much as we can in one go, and this frees up another section that can be moved, 
         until the whole fragment has been moved   */

      /*   Starting from the end of the fragment, move it in chunks of size “movement”
         to its final position   */
      while (blocksLeftToMove > 0)
         blocksToMoveThisTime = MIN(movement, blocksLeftToMove);
         if (finalStartBlock > startBlock)
            offset = numBlocks - blocksAlreadyMoved – 
            offset = blocksAlreadyMoved;

         OutputMoveInstruction(startBlock + offset,
               finalStartBlock + offset, blocksToMoveThisTime, true);

         blocksAlreadyMoved += blocksToMoveThisTime;
         blocksLeftToMove -= blocksToMoveThisTime;
      /*   The best way of moving it is to move as much as possible into bestRange, and 
         from there to its final position, repeating until the whole fragment has been 
         moved   */

      /*   Starting from the end of the fragment, move it in chunks of size 
         “blocksAvailableInBestRange” to its final position via 
         firstBlockAvailableInBestRange   */
      while (blocksLeftToMove > 0)
         blocksToMoveThisTime = MIN(blocksAvailableInBestRange, 
         if (finalStartBlock > startBlock)
            offset = numBlocks - blocksAlreadyMoved – 
            offset = blocksAlreadyMoved;

         OutputMoveInstruction(startBlock + offset, 
                           blocksToMoveThisTime, false);
               finalStartBlock + offset,
                           blocksToMoveThisTime, true);

         blocksAlreadyMoved += blocksToMoveThisTime;
         blocksLeftToMove -= blocksToMoveThisTime;
   /*   Update the internal information to take account of this move (it doesn’t matter 
      exactly how we achieved the move). Also notify any other fragments affected by 
      the move, so they can update
      their blockage counts   */
   inFinalPosition = true;
   if (maintainBlockageCount)

   startBlock = finalStartBlock;
   if (maintainBlockageCount)
      blockedBySelf = false;
   if ((displayProgress == kDisplayBlocks) &&
      (animationType != kFastestAnimation))
UpdateProgress(((float)(testCase - 1) + 
   ((float)fragmentsPositioned / (float)totalFragments)) / 
         (float)numTestCases, testCase);

   /*   No need to resort the current-position tree as the fragment order hasn’t changed. 
      We do need to update its sort key, though   */
   currentStartTreeNode->keyLong = startBlock;

   if (maintainBlockageCount)


void Fragment::FragmentHasMoved(Boolean maintainBlockageCount)
// this routine omitted for length, see online archive

Fragment *Fragment::SplitToFitLength(long lengthOfFirstPart)
// this routine omitted for length, see online archive

void OutputMoveInstruction(long from, long to, long blocksToMove, Boolean finalPosition)
   if (displayProgress == kDisplayBlocks)
      ClearDisplayedBlockRange(from, from + blocksToMove - 1);
   fprintf(outputFile, “%ld,%ld,%ld\n”, from, to, blocksToMove);
   if (displayProgress == kDisplayBlocks)
      SetDisplayedBlockRange(to, to + blocksToMove - 1, true, finalPosition);

// Search function section omitted for length, see online archive

// Main.cp, ReadExisting.cp, Trees.cp, Trees.h, Windows.cp omitted because of 
//  length; see online archive


Community Search:
MacTech Search:

Software Updates via MacUpdate

Quicken 4.6.3 - 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
Smultron 10.0 - Easy-to-use, powerful te...
Smultron 10 is an elegant and powerful text editor that is easy to use. You can use Smultron 10 to create or edit any text document. Everything from a web page, a note or a script to any single piece... Read more
Apple Numbers 4.3 - Apple's spreads...
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 Pages 6.3 - Apple's word proc...
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
Opera 47.0.2631.83 - High-performance We...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
BetterTouchTool 2.304 - Customize multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Drive Genius 5.0.5 - $49.50 (50% off)
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
Apple Configurator 2.5 - Configure and d...
Apple Configurator makes it easy to deploy iPad, iPhone, iPod touch, and Apple TV devices in your school or business. Use Apple Configurator to quickly configure large numbers of devices connected to... Read more
Apple Keynote 7.3 - Apple's present...
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
Vivaldi 1.12.955.36 - An advanced browse...
Vivaldi is a browser for our friends. In 1994, two programmers started working on a web browser. Our idea was to make a really fast browser, capable of running on limited hardware, keeping in mind... 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 »
The best deals on the App Store this wee...
Good news, everyone! Your favorite day of the week has arrived at last -- it's discount roundup day! This fine Wednesday evening we're gathering up the hottest deals on the App Store. We've got action platformers, we've got puzzle games, we've got... | Read more »
Morphite (Games)
Morphite 1.08 Device: iOS Universal Category: Games Price: $7.99, Version: 1.08 (iTunes) Description: | Read more »
Fitness AR (Healthcare & Fitness)
Fitness AR 0.1.1 Device: iOS Universal Category: Healthcare & Fitness Price: $2.99, Version: 0.1.1 (iTunes) Description: Explore your Strava bike rides and runs in augmented reality. A beautiful 3D terrain map, powered by Mapbox... | Read more »
ARise (Games)
ARise 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: **ARKit only Puzzle game****Chapter 1 available now - More worlds coming soon!** ARise is an experience about perspective. Using the AR... | Read more »
The best games to play while you wait fo...
SteamWorld Dig 2 is out this week on PC and Switch, and people are understandably excited. This clever series by Image and Form combines our favorite metroidvania mechanics with an esquisite universe, excellent storytelling, and true wit. While... | Read more »
Drag'n'Boom beginner's gu...
Have you ever wanted to burn and pillage a village as a bloodthirsty dragon? If you answered yes to that question, Drag'n'Boom offers you the perfect chance to do so, casting you as an adorable little dragon that wants to set humankind aflame. It... | Read more »
Thimbleweed Park (Games)
Thimbleweed Park 1.0.0 Device: iOS Universal Category: Games Price: $9.99, Version: 1.0.0 (iTunes) Description: A brand new adventure game from Ron Gilbert and Gary Winnick, creators of the classics Monkey Island and Maniac Mansion!... | Read more »

Price Scanner via

Apple restocks Certified Refurbished 13-inch...
Apple has Certified Refurbished 2015 13″ MacBook Airs available starting at $719 and 2016 models available starting at $809. An Apple one-year warranty is included with each MacBook, and shipping is... Read more
Is iPhone X Really The Future Of The Smartpho...
Should iPhone X even be called a telephone? It does of course support telephony and texting, but its main feature set is oriented to other things. It is also debatable whether it makes any rational... Read more
OtterBox Announces Full Case Lineup for iPhon...
Apple revolutionized the smartphone industry 10 years ago with the original iPhone, and OtterBox has set the standard of protection from the very beginning by protecting every generation of iPhone.... Read more
LifeProof Introduces What’s NEXT Cases for iP...
LifeProof built its reputation on sleek, ultra-protective iPhone cases. From 360-degree coverage to the first screenless waterproof case, the protection pioneer has always pushed the limits.... Read more
Apple Refurbished 2016 15-inch MacBook Pros a...
Apple has Certified Refurbished 2016 15″ Touch Bar MacBook Pros available starting at $1949. An Apple one-year warranty is included with each model, and shipping is free: – 15″ 2.7GHz Touch Bar Space... Read more
Wednesday deal: 15-inch MacBook Pros for up t...
B&H Photo has 2017 15″ MacBook Pros on sale for $150-$200 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only: – 15″ 2.8GHz MacBook Pro Space Gray: $2199, $200 off MSRP... Read more
2.6GHz Mac mini on sale for $599, $100 off MS...
B&H Photo has the 2.6GHz Mac mini (MGEN2LL/A) on sale for $599 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
Snag a 15-inch 2.2GHz Retina MacBook Pro, App...
Apple has Certified Refurbished 2015 15″ 2.2GHz Retina MacBook Pros available for $1699. That’s $300 off original MSRP, and it’s the lowest price available for a 15″ MacBook Pro currently offered by... Read more
Apple Refurbished 3TB Time Capsule for $279,...
Apple has Certified Refurbished 3TB Time Capsules available for $279 including free shipping plus Apple’s standard one-year warranty. Their price is $120 off MSRP. Read more
19% off Smart Battery Cases for iPhone 7
Amazon has both Black and White Smart Battery Cases for iPhone 7s available for $80.41 including free shipping. Their price is $18.59, or 19%, off MSRP. Read more

Jobs Board

Full time *Apple* Hardware Tech needed - ma...
…high level of attention to detail Ethics, integrity and trust Be a geek & Previous Apple experience a must. Previous Apple Retail or other Apple Specialist 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* Store - Technical Specialist - Apple...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of 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* News Product Marketing Mgr., Publish...
Job Summary The Apple News Product Marketing Manager will work closely with a cross-functional group to assist in defining and marketing new features and services. Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.