TweetFollow Us on Twitter

Apr 94 Challenge
Volume Number:10
Issue Number:4
Column Tag:Programmers’ Challenge

Related Info: Memory Manager

Programmers’ Challenge

By Mike Scanlin, MacTech Magazine Regular Contributing Author

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

The rules

Here’s how it works: Each month there will be a different programming challenge presented here. First, you must write some code that solves the challenge. Second, you must optimize your code (a lot). Then, submit your solution to MacTech Magazine (formerly MacTutor). A winner will be chosen based on code correctness, speed, size and elegance (in that order of importance) as well as the postmark of the answer. In the event of multiple equally desirable solutions, one winner will be chosen at random (with honorable mention, but no prize, given to the runners up). The prize for the best solution each month is $50 and a limited edition “The Winner! MacTech Magazine Programming Challenge” T-shirt (not to be found in stores).

In order to make fair comparisons between solutions, all solutions must be in ANSI compatible C (i.e., don’t use Think’s Object extensions). Only pure C code can be used. Any entries with any assembly in them will be disqualified (except for those challenges specifically stated to be in assembly). However, you may call any routine in the Macintosh toolbox you want (i.e., it doesn’t matter if you use NewPtr instead of malloc). All entries will be tested with the FPU and 68020 flags turned off in THINK C. When timing routines, the latest version of THINK C will be used (with ANSI Settings plus “Honor ‘register’ first” and “Use Global Optimizer” turned on) so beware if you optimize for a different C compiler. All code should be limited to 60 characters wide. This will aid us in dealing with e-mail gateways and page layout.

The solution and winners for this month’s Programmers’ Challenge will be published in the issue two months later. All submissions must be received by the 10th day of the month printed on the front of this issue.

All solutions should be marked “Attn: Programmers’ Challenge Solution” and sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or preferably, e-mail - AppleLink: MT.PROGCHAL, Internet: progchallenge@xplain.com, CompuServe: 71552,174 and America Online: MT PRGCHAL. If you send via snail mail, please include a disk with the solution and all related files (including contact information). See page 2 for information on “How to Contact Xplain Corporation.”

MacTech Magazine reserves the right to publish any solution entered in the Programming Challenge of the Month and all entries are the property of MacTech Magazine upon submission. The submission falls under all the same conventions of an article submission.

SWAP BLOCKS

This month’s challenge is to swap two adjacent blocks of memory using a finite amount of temporary swap space. This is something the Memory Manager has to do quite often as it shuffles blocks around in the heap.

The prototype of the function you write is:


/* 1 */
void SwapBlocks(p1, p2, swapPtr size1,
  size2, swapSize)
void    *p1;
void    *p2;
void    *swapPtr;
unsigned long  size1;
unsigned long  size2;
unsigned long  swapSize;

p1 and p2 point to the beginnings of the two blocks to swap. size1 and size2 are their respective sizes (in bytes). Both blocks begin on addresses divisible by 4 and have sizes that are divisible by 4. swapPtr points to the scratch area you can use (if you need to) and swapSize is the size of that area (between 256 and 4096 bytes, inclusive). swapPtr and swapSize are also each divisible by 4. If the two blocks look like this on entry:


/* 2 */
12345678ABCDEFGHIJKL
^       ^
p1      p2    size1 = 8   size2 = 12

then the same memory locations will look like this on exit:


/* 3 */
ABCDEFGHIJKL12345678

When measuring performance I will be calling your routine many times. The distribution of the sizes of the blocks is as follows:

4 to 16 bytes 20% of the time

20 to 32 bytes 20% of the time

36 to 64 bytes 20% of the time

68 to 256 bytes 20% of the time

260 to 4096 bytes 10% of the time

4100 or more bytes 10% of the time

You would normally write this kind of routine in assembly, but let’s see how well you can do in pure C (remember, everyone has the same handicap). If you want to submit a pure assembly solution along with your pure C solution then please do so (but the assembly version will NOT be counted as an entry in the challenge and it will not win anything other than a mention in this column).

TWO MONTHS AGO WINNER

Of the 11 entries I received for the We Pry Any Heap (Happy New Year) anagram challenge, only 5 worked correctly. Congrats to Larry Landry (Rochester, NY) for the dual honor of coming in 1st both in terms of speed and smallest code size.

The times for anagramming “programmer” (462 anagrams) and “mactech magazine” (3365 anagrams) with a 19,335 word English dictionary are given here (more weight was given to longer inputs (15-30 characters) when ranking contestants). Numbers in parens after a person’s name indicate how many times that person has finished in the top 5 places of all previous Programmer Challenges, not including this one:

Name code time 1 time 2

Larry Landry (1) 830 20 1048

Stepan Riha (5) 2352 45 1166

Bob Boonstra (6) 1370 52 1688

Allen Stenger (3) 1044 23 1701

Mark Nagel 1134 81 51407

Most of the entrants figured out that the key to speeding up the anagram process was to pare down the size of the dictionary first. Once you have the input characters you can eliminate any word in the dictionary that: (1) contains more characters than the input, (2) contains at least one letter not in the input set or, (3) contains more of any particular character than the input. For instance, if your input is “programmer” then you can remove any word in the dictionary that (1) is more than 10 characters long, (2) is not made up entirely of the letters [p, r, o, g, a, m, e] and, (3) contains more than any one of: 1 p, 3 r’s, 1 o, 1 g, 1 a, 2 m’s, or 1 e.

Stepan Riha (Austin, TX) took this “reduce the dictionary” idea one step further and came up with a way to store words that are permutations of each other (like ‘stop’, ‘post’ and ‘pots’) as one entry in the dictionary (and when it’s time to output an anagram he outputs all permutations for each word in the output).

Several people wrote to me and asked if reordering the words in each output anagram was necessary (i.e. ‘pale rain’ and ‘rain pale’). I admit that it wasn’t clear in the puzzle specification exactly what qualified as a ‘unique’ anagram so I allowed either interpretation. The only one of the 5 correct entries that did count word reorderings as unique anagrams is Mark Nagel (Irvine, CA) and his times above reflect that fact.

Here’s Larry’s winning solution:

Anagram Programmer's Challenge

by Larry Landry

This implementation uses a large amount of memory to optimize the CPU utilization. To guarantee that we have enough memory for all matching words, we actually allocate an array of pointers for 30,000 words. Since the rules stated that there would be about 20,000 words in the dictionary, even if every word matched, we would still have enough storage. In reality this number could probably be less than 1-200 for all but the most rare of scenarios.

The basic algorithm is: 1) Convert the input string into a table of counts for each character from a-z. So "sammy" would have a count of 2 for "m" and 1 for each of "s", "a", and "y". This makes testing for the presence of a character as simple as checking and indexed value in an array. 2) Parse through the dictionary and find the words that can be composed of some portion of characters from the input characters. Build a list of pointers to each word. The number of words in this list will be in the tens instead of thousands. 3) Recursively process the words in this list and find strings of words that use up all of the characters. For each matching sequence, output the words to the file. The processing required by this algorithm is then

D * C1 + M * log2(M) * C2

where

D = size of input dictionary

M = number of matching words

C1 & C2 are constants

This algorithm works very well for cases where there are few words that match the input letters. The worst case scenario where all words can be made from the input letters will still take a very long time. I expect that matching words will typically be less than 100.


/* 4 */
#include   <stdio.h>

typedef unsigned char   uchar;
typedef unsigned short ushort;
typedef unsigned long  ulong;

#define MAX_WORDS   30000L
#define OUTPUT_BUFFER_SIZE  10000L
#define RETURN  '\n'

typedef struct {
   char*fWordStart;
   short   fWordLength;
} WordLoc;

/* Usage counts for each character (only indexes 'a' to 'z' are actually 
used) */
typedef uchar   CharData[256];

unsigned long Anagram(Str255 inputText, FILE *wordList,
   FILE *outputFile);

ulong findInputWords(register char *wordBuffer,
   WordLoc *validWords);
ulong findAnagrams(short numValidChars, ulong wordCount,
   WordLoc *validWords, short prevWordCount);

/* I use some global variables here to avoid passing them down into the 
recursive routine findAnagrams().  These values are constant once findAnagrams() 
is called. */

char     gOutputBuffer[OUTPUT_BUFFER_SIZE];
char    *gOutputBufferEnd = gOutputBuffer + 
 OUTPUT_BUFFER_SIZE - 512;
char    *gOutputPtr;
CharData  gValidChars;
WordLoc  *gWordsInUse[255];
FILE    *gOutputFile;

unsigned long Anagram(Str255 inputText, FILE *wordList,
   FILE *outputFile)
{
   fpos_t  wordBufferLength;
   char*  wordBuffer;
   short   index;
   short   numValidChars;
   WordLoc validWords[MAX_WORDS];
   char   ch;
   ulong   wordCount;

   gOutputFile = outputFile;
   gOutputPtr = gOutputBuffer;

/* To save on file I/O time, read the whole file all at once.  First, 
find the length of the file by seeking the end and finding the file pos. 
 Then allocate a buffer of that size, plus 2 bytes  (for a return and 
NULL char) and read the data into it.  Finally put the return and NULL 
char at the end. */

   fseek(wordList, 0L, SEEK_END);
   fgetpos(wordList, &wordBufferLength);
   wordBuffer = (char*) NewPtr((Size) wordBufferLength + 2);
   if (wordBuffer == NULL)
   return 0L;  /* real error handling here */
   rewind(wordList);
   fread(wordBuffer, (size_t) 1,
   (size_t) wordBufferLength, wordList);
   if (wordBuffer[wordBufferLength-1] != RETURN)
   wordBuffer[wordBufferLength++] = RETURN;
   wordBuffer[wordBufferLength] = '\0';

/* To save time ruling out words, we build a list of the valid characters 
in the words.  We start with no valid characters. */
   for (index='a'; index<'z'; index++)
   gValidChars[index] = 0;

/* Now build the list of valid characters.  Each array entry will be 
a count of how many times that character is present. */
   numValidChars = *inputText++;
   for (index=numValidChars; index>0; index--)
   if ((ch = *inputText++) != ' ')
   gValidChars[ch]++;
   else
   numValidChars--;
/* Find the list of words that can be made up from the letters in the 
input word */
   wordCount = findInputWords(wordBuffer,
 &validWords[MAX_WORDS-1]);
/* Now find the list of full anagrams that can be created from these 
words */
   wordCount = findAnagrams(numValidChars, wordCount,
   &validWords[MAX_WORDS-wordCount], 0);
/* Write the results to the output */
   *gOutputPtr = 0;/* Terminate the string */
   fprintf(outputFile, gOutputBuffer);
   DisposPtr(wordBuffer);
   return wordCount;
} /* Anagram */


ulong findInputWords(register char *wordBuffer,
   WordLoc *validWords)
{
   char*saveStart = wordBuffer;
   ulong   numberWords = 0;
   char ch;

   while (*wordBuffer)
   {
   ch = *wordBuffer++;
   if (ch == RETURN)
   {
/* Record this entry as a valid word */
   numberWords++;
   validWords->fWordStart = saveStart;
   validWords->fWordLength = (short)(wordBuffer -
   saveStart - 1);
   validWords--;

   wordBuffer--;
   while (saveStart < wordBuffer)
 gValidChars[*saveStart++]++;

/* Save the new start of word pointer */
   saveStart = ++wordBuffer;
   } else if (gValidChars[ch])
   gValidChars[ch]--;
   else
   {
/* This word didn't match so reset and go to the next word */
   wordBuffer--;
   while (saveStart < wordBuffer)
   gValidChars[*saveStart++]++;
   while (*wordBuffer++ != RETURN)
   ;
/* Save the new start of word pointer */
   saveStart = wordBuffer;
   } /* else */
   } /* while */
   return numberWords;
} /* findInputWords */


ulong findAnagrams(short numValidChars, ulong wordCount,
   WordLoc *validWords, short prevWordCount)
{
   ulong   wordIndex;
   ulong   usedIndex;
   short   chIndex;
   ulong   matchCount = 0;
   Boolean wordFits;
   char ch;
   char*tempPtr;
   WordLoc *theWord;



/* Try each word we have against the list of characters. */
   for (wordIndex=0; wordIndex<wordCount; wordIndex++)
   {
/* If there aren't enough characters left,  it can't be a match */
   if (validWords->fWordLength <= numValidChars)
   {
/* Go through the chars in this word testing to make sure that there 
is at least one of each char  available */
   wordFits = TRUE;
   for (chIndex=0; chIndex<validWords->fWordLength; chIndex++)
   {
   ch = validWords->fWordStart[chIndex];
   if (gValidChars[ch])
   gValidChars[ch]--;
   else
   {
/* Found an unavailable character, so this can't be part of the anagram. 
 Reset the character usage array and go to the next word. */
   wordFits = FALSE;
   while (--chIndex >= 0)
   gValidChars[validWords->fWordStart[chIndex]]++;
   break;  /* get out of the for loop */
   } /* else */
   } /* for */

   if (wordFits)
   {
/* This word fit, so see if it uses all the characters.   If so, then 
we have found an anagram.  Output the  anagram and increment the anagram 
count. */
   if (validWords->fWordLength == numValidChars)
   {
   matchCount++;
/* Copy the previous words for this anagram separated by spaces. */
   for (usedIndex=0; usedIndex<prevWordCount; usedIndex++)
   {
   theWord = gWordsInUse[usedIndex];
   memcpy(gOutputPtr, theWord->fWordStart,
   (size_t) theWord->fWordLength);
   gOutputPtr += theWord->fWordLength;
   *gOutputPtr++ = ' ';
   } /* for */
/* Now copy this new word and a return character */
   memcpy(gOutputPtr, validWords->fWordStart,
   (size_t) validWords->fWordLength);
   gOutputPtr += validWords->fWordLength;
   *gOutputPtr++ = RETURN;

/* To ensure that we don't overrun the output buffer check against the 
end of the buffer.  If the end pointer has been passed, write the data 
to the file  and reset the output pointer to the beginning of the buffer. 
*/
   if (gOutputPtr > gOutputBufferEnd)
   {
 *gOutputPtr = 0;/* Terminate the string */
   fprintf(gOutputFile, gOutputBuffer);
   gOutputPtr = gOutputBuffer;
   } /* if */
   }  /* if */
   else
   {
/* This word did fit, but didn't use all of the characters so add it 
to the list of previous words  in the anagram and then call this procedure 
recursively to find if there are more words that can be added to make 
an anagram with this base. */
   gWordsInUse[prevWordCount] = validWords;
   matchCount += findAnagrams(
   numValidChars - validWords->fWordLength,
   wordCount - wordIndex, validWords,
   prevWordCount + 1);
   } /* else */

/* Now undo the characters we took out of the validChar array */
   for (chIndex=0;chIndex<validWords->fWordLength;chIndex++)
   gValidChars[validWords->fWordStart[chIndex]]++;
   } /* if */
   } /* if */

  validWords++;
 } /* for */

   return matchCount;
} /* findAnagrams */







  
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Chromium 75.0.3770.142 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. Version 75.0.3770.142: Release notes were... Read more
Viber 11.1.0 - Send messages and make fr...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more
Wireshark 3.0.3 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
DEVONthink Pro 3.0beta4 - Knowledge base...
DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research papers, your life often fills your hard drive in the... Read more
Adobe Creative Cloud 4.9.0.512 - Access...
Adobe Creative Cloud costs $20.99/month for a single app, or $52.99/month for the entire suite. Introducing Adobe Creative Cloud desktop applications, including Adobe Photoshop CC and Illustrator CC... Read more
SketchUp 19.1.174 - Create 3D design con...
SketchUp is an easy-to-learn 3D modeling program that enables you to explore the world in 3D. With just a few simple tools, you can create 3D models of houses, sheds, decks, home additions,... Read more
ClamXav 3.0.12 - Virus checker based on...
ClamXav is a popular virus checker for OS X. Time to take control ClamXAV keeps threats at bay and puts you firmly in charge of your Mac’s security. Scan a specific file or your entire hard drive.... Read more
BetterTouchTool 3.151 - 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
FontExplorer X Pro 6.0.9 - Font manageme...
FontExplorer X Pro is optimized for professional use; it's the solution that gives you the power you need to manage all your fonts. Now you can more easily manage, activate and organize your... Read more
Dropbox 77.4.131 - Cloud backup and sync...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keeps them up-to-date between systems... Read more

Latest Forum Discussions

See All

Upcoming visual novel Arranged shines a...
If you’re in the market for a new type of visual novel designed to inform and make you think deeply about its subject matter, then Arranged by Kabuk Games could be exactly what you’re looking for. It’s a wholly unique take on marital traditions in... | Read more »
TEPPEN guide - The three best decks in T...
TEPPEN’s unique take on the collectible card game genre is exciting. It’s just over a week old, but that isn’t stopping lots of folks from speculating about the long-term viability of the game, as well as changes and additions that will happen over... | Read more »
Intergalactic puzzler Silly Memory serve...
Recently released matching puzzler Silly Memory is helping its fans with their intergalactic journeys this month with some very special offers on in-app purchases. In case you missed it, Silly Memory is the debut title of French based indie... | Read more »
TEPPEN guide - Tips and tricks for new p...
TEPPEN is a wild game that nobody asked for, but I’m sure glad it exists. Who would’ve thought that a CCG featuring Capcom characters could be so cool and weird? In case you’re not completely sure what TEPPEN is, make sure to check out our review... | Read more »
Dr. Mario World guide - Other games that...
We now live in a post-Dr. Mario World world, and I gotta say, things don’t feel too different. Nintendo continues to squirt out bad games on phones, causing all but the most stalwart fans of mobile games to question why they even bother... | Read more »
Strategy RPG Brown Dust introduces its b...
Epic turn-based RPG Brown Dust is set to turn 500 days old next week, and to celebrate, Neowiz has just unveiled its biggest and most exciting update yet, offering a host of new rewards, increased gacha rates, and a brand new feature that will... | Read more »
Dr. Mario World is yet another disappoin...
As soon as I booted up Dr. Mario World, I knew I wasn’t going to have fun with it. Nintendo’s record on phones thus far has been pretty spotty, with things trending downward as of late. [Read more] | Read more »
Retro Space Shooter P.3 is now available...
Shoot-em-ups tend to be a dime a dozen on the App Store, but every so often you come across one gem that aims to shake up the genre in a unique way. Developer Devjgame’s P.3 is the latest game seeking to do so this, working as a love letter to the... | Read more »
Void Tyrant guide - Guildins guide
I’ve still been putting a lot of time into Void Tyrant since it officially released last week, and it’s surprising how much stuff there is to uncover in such a simple-looking game. Just toray, I finished spending my Guildins on all available... | Read more »
Tactical RPG Brown Dust celebrates the s...
Neowiz is set to celebrate the summer by launching a 2-month long festival in its smash-hit RPG Brown Dust. The event kicks off today, and it’s divided into 4 parts, each of which will last two weeks. Brown Dust is all about collecting, upgrading,... | Read more »

Price Scanner via MacPrices.net

Verizon is offering a 50% discount on iPhone...
Verizon is offering 50% discounts on Apple iPhone 8 and iPhone 8 Plus models though July 24th, plus save 50% on activation fees. New line required. The fine print: “New device payment & new... Read more
Get a new 21″ iMac for under $1000 today at t...
B&H Photo has new 21″ Apple iMacs on sale for up to $100 off MSRP with models available starting at $999. These are the same iMacs offered by Apple in their retail and online stores. Shipping is... Read more
Clearance 2017 15″ 2.8GHz Touch Bar MacBook P...
Apple has Certified Refurbished 2017 15″ 2.8GHz Space Gray Touch Bar MacBook Pros available for $1809. Apple’s refurbished price is currently the lowest available for a 15″ MacBook Pro. An standard... Read more
Clearance 12″ 1.2GHz MacBook on sale for $899...
Focus Camera has clearance 12″ 1.2GHz Space Gray MacBooks available for $899.99 shipped. That’s $400 off Apple’s original MSRP. Focus charges sales tax for NY & NJ residents only. Read more
Get a new 2019 13″ 2.4GHz 4-Core MacBook Pro...
B&H Photo has new 2019 13″ 2.4GHz MacBook Pros on sale for up to $150 off Apple’s MSRP. Overnight shipping is free to many addresses in the US: – 2019 13″ 2.4GHz/256GB 6-Core MacBook Pro Silver... Read more
AirPods with Wireless Charging Case now on sa...
Amazon has extended their Prime Day savings on Apple AirPods by offering AirPods with the Wireless Charging case for $169.99. That’s $30 off Apple’s MSRP, and it’s the cheapest price available for... Read more
New 2019 15″ MacBook Pros on sale for $200 of...
B&H Photo has the new 2019 15″ 6-Core and 8-Core MacBook Pros on sale for $200 off Apple’s MSRP. Overnight shipping is free to many addresses in the US: – 2019 15″ 2.6GHz 6-Core MacBook Pro Space... Read more
Amazon drops prices, now offers clearance 13″...
Amazon has new dropped prices on clearance 13″ 2.3GHz Dual-Core non-Touch Bar MacBook Pros by $200 off Apple’s original MSRP, with prices now available starting at $1099. Shipping is free. Be sure to... Read more
2018 15″ MacBook Pros now on sale for $500 of...
Amazon has dropped prices on select clearance 2018 15″ 6-Core MacBook Pros to $500 off Apple’s original MSRP. Prices now start at $1899 shipped: – 2018 15″ 2.2GHz Touch Bar MacBook Pro Silver: $1899.... Read more
Price drop! Clearance 12″ 1.2GHz Silver MacBo...
Amazon has dropped their price on the recently-discontinued 12″ 1.2GHz Silver MacBook to $849.99 shipped. That’s $450 off Apple’s original MSRP for this model, and it’s the cheapest price available... Read more

Jobs Board

Best Buy *Apple* Computing Master - Best Bu...
**696259BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Location Number:** 001076-Temecula-Store **Job Description:** The Read more
Business Development Manager, *Apple* Globa...
Business Development Manager, Apple Global Tampa, FL, US Requisition Number:73805 As a Global Apple Business Development Manager at Insight, you proactively Read more
*Apple* Systems Architect/Engineer, Vice Pre...
…its vision to be the world's most trusted financial group. **Summary:** Apple Systems Architect/Engineer with strong knowledge of products and services related to Read more
*Apple* IOS Systems Engineer - Randstad (Uni...
Apple IOS Systems Engineer **job details:** + location:Irvine, CA + salary:$45 - $55 per hour + date posted:Tuesday, July 16, 2019 + job type:Temp to Perm + Read more
Business Development Manager, *Apple* Globa...
Business Development Manager, Apple Global Tampa, FL, US Requisition Number:73805 As a Global Apple Business Development Manager at Insight, you proactively Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.