TweetFollow Us on Twitter

Jan 97 Challenge

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

Programmer's Challenge

By Bob Boonstra, Westford, MA

BeSort

The theme of this issue of the magazine is the Be Operating System, so it seemed appropriate to focus the Challenge on the BeOS, and give you a chance to use the BeOS for Macintosh CD-ROM bundled in this issue. Since the BeOS will be new to most of you, this Challenge will be a simple one. The problem is to write a window class that will display and sort a list of strings by one of three specified methods: a bubble sort, an exchange sort, and an algorithm of your choosing. The prototype for the class you should write is

typedef enum SortType {
 kBubbleSort = 1,
 kExchangeSort = 2,
 kMySort = 3
} SortType;

class SortWindow : public BWindow {

public:
 SortWindow(BRect frame); 
virtual void   DoSort(
 char *thingsToSort[],  /* list of strings to sort, also returns sorted list */
 int numberOfThings, /* number of thingsToSort */
 SortType sortMethod);  /* sort method to use */
};

My test code will open three instances of your window class and ask each one to sort a copy of the same list of strings: one by the kBubbleSort method, one by kExchangeSort, and one by kMySort. Your SortWindow constructor should create a BListView and attach it to your SortWindow. When the DoSort method is invoked, you should display the thingsToSort and sort them into ascending ASCII order by the sortMethod algorithm. Each time two thingsToSort are exchanged, the BListView display should be updated. When the sort is complete, DoSort should post a B_QUIT_REQUESTED message to the application. The list should be sorted in place and returned in thingsToSort.

This will be a native PowerPC Challenge, using the latest Macintosh CodeWarrior environment, targeted for the BeOS. Solutions must be coded in C++. The code will be tested on my 8500 using the BeOS. (In the event I cannot get the BeOS to run on my Mac, I will run the tests on a 2x133MHz BeBox with one processor disabled.) The winner will be the solution that completes all three sorts correctly in the minimum time.

Three Months Ago Winner

Congratulations to Andy Antoniewicz (Mountain View, CA) for narrowly beating second and third place finishers Greg Cooper and Ludovic Nicolle in the October DNA Match Challenge. Of the fifteen entries I received for this Challenge, ten worked completely correctly, two were partially correct, and the remaining three crashed my machine.

Recall that the DNA Match Challenge was essentially a string matching problem, where the strings were allowed to differ in a specified number of positions (or fewer). The object was to return the number of near matches of a fragment string found in a reference database string.

My intent had been to test the solutions submitted using very long database strings. The run times of the solutions imposed a practical limit of about 2 MB on the size of the database string in an individual test case. The fragments to be matched were all significantly shorter than the database string, as indicated in the problem statement. The tests ranged from requiring very accurate matches, with a small value for the number of differences allowed, to approximate matches that could differ in up to half of the characters in the reference string.

The problem statement allowed for a timed initialization routine that would be executed once prior to testing matches against multiple fragments for a given database string. None of the top-ranked solutions made any significant use of this option, although a number of people used it to initialize small translation tables. Several people commented that it was difficult to find a use for this initialization routine, when the scratch storage provided was smaller than the maximum size database string.

Andy's winning entry parses the fragment string to create, for each character in the DNA "alphabet", a list of offsets where that character is located in the fragment. He then walks the database string and increments a match counter for each possible alignment of the fragment that matches the database at that character position. Andy uses a circular buffer twice the size of the fragment to store the match counts, which allows him to perform bounds checking on that buffer only once per database character, rather than within the innermost character matching loop. I had to read the code several times and run through a few cases manually before the light went on and I understood the algorithm, after which I found it quite clever.

While A.C.C. Murphy's solution did not place in the top five, one of his algorithms used a refinement worthy of note. He kept a running total of the counts of characters in a fragment-sized segment of the database, only checking for a specific match if the frequency counts were close enough to those of the fragment. In test cases where the character frequencies of the fragment were significantly different than much of the database, this technique might have done very well.

The table below summarizes the results for each correct or partially correct entry, including total execution time for all of the test cases and code size. Numbers in parenthesis after a person's name indicate that person's cumulative point total for all previous Challenges, not including this one. An asterisk indicates a result that was partially correct and therefore not eligible to win.

NameLanguageTotal TimeCode Size
Andy Antoniewicz (4)C123823728
Greg Cooper (17)C126233872
Ludovic Nicolle (14)C126646528
Michael Panchenko (6)C148243800
Bjorn Davidsson (4)C149171424
A.C.C. Murphy (10)C1510861800
Ernst Munter (224)C++176521752
Peter Lewis (32)C195312240
Mark DayC197385848
Larry Landry (29)C2671181376
Alan Hart (*)C210701848
Xin Xu (*)C2230151576

TOP 20 CONTESTANTS

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

RankNamePoints
1.Munter, Ernst193
2.Gregg, Xan114
3.Larsson, Gustav87
4.Lengyel, Eric40
5.[Name deleted]40
6.Lewis, Peter32
7.Boring, Randy27
8.Cooper, Greg27
9.Antoniewicz, Andy24
10.Beith, Gary24
11.Kasparian, Raffi22
12.Cutts, Kevin21
13.Nicolle, Ludovic21
14.Picao, Miguel Cruz21
15.Brown, Jorg20
16.Gundrum, Eric20
17.Karsh, Bill19
18.Stenger, Allen19
19.Mallett, Jeff17
20.Nevard, John17

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 place20 points
2nd place10 points
3rd place7 points
4th place4 points
5th place2 points
finding bug2 points
suggesting Challenge2 points

Here is Andy's winning solution:

DNA_Match.c

© 1996 Andy Antoniewicz

/* 
Problem:
DNA string match with wildcard & constant distance

Notes:
No setup calculations on the database are performed. It seemed kind of pointless to attempt the equivalent 
of a 50 to 1 loss, less compression of the database ( it was 1000 to 1 for the first problem statement ).

This is a simple and quick single byte per pass index and count type algorithm. It uses three tables: a byte 
to code index table "aTable", a fragment index list array "alphaList",
and a hit count circular array "matchQueue". A precursor list is built and used once to build the alphaList 
array, and I do not clean up after (plenty of allocated storage).
Once built, the aTable contains an index into the alphaList for each given alphabet letter in the fragment. 
The alphaList contains a sequential list of all occurrences of that character in the fragment string.

The algorithm then increments the match count for all possible alignments of the fragment for each database 
character. Since the maximum misalignment is less than the fragment size, only the previous fragmentSize 
database characters need to be considered for matches at any particular time. Hence the circular queue 

The database search execution time is order( pN ) where N = number of database characters
p = average fragment entries per alphabet char 
( for example: A=3,C=3,G=2,T=2 -
> p = 2.5 )
The storage used is almost totally dependent on the fragment size. Storage used in bytes
    = 20     ( storage struct )
    + 256         ( 16bit aTable )
    + 2 * fragment chars( 16bit precursor )
    + 2 * fragment chars( 16bit alphaList )
    + 2 * alphabet chars (  more alphaList )
    + 4 * fragment chars( 2x16bit matchQueue )

 ********* ********* ********* ********* ********* ********/
 
#define kAlphaTableSize   128
#define kEndOfAlphaList   -1
 
typedef struct {
 long storageSize; // total storage available
 long usedStorage; // total storage used
 long fragmentSize;// size in chars of fragment
 short  *alphaList;// start of fragment index list
 short  *matchQueue; // start of match count queue
 
 short  alphaTable[ kAlphaTableSize ];
 short  precursor[]; // start of match count queue
} DNAStore;

/********* ********* ********* ********* ********* ********
 Function Prototypes
 ********* ********* ********* ********* ********* ********/

void InitMatch(
 char *alphabet, // legal characters in database
 char *database, // the reference database
 void *storage,  // pre-allocated storage
 long storageSize// size of storage in bytes
);

long FindMatch(  // return number of matches
 char *alphabet, // legal characters in database
 char *database, // the reference database
 void *storage,  // pre-allocated storage
 char *fragment, // the fragment to find
 long diffsAllowed,// num of diffs allowed between
    //  a "match" and the database
 long matchPosition[]// match return array
);

void BuildAlphaList(
 char   *alphabet, // legal characters in database
 char   *fragment, // the fragment to find; 0 term
 DNAStore *storage // my storage area
);

/********* ********* ********* ********* ********* ********
 * InitMatch
 * This routine does nothing except to store the
 *  size of memory allocated by the calling program.
 * All of the structures used are based on the fragment
 * to be searched for.
 ********* ********* ********* ********* ********* ********/

InitMatch
void InitMatch(
 char *alphabet, // legal characters in database
 char *database, // the reference database
 void *storage,  // pre-allocated storage
 long storageSize// size of storage in bytes
)
{
 ((DNAStore*)storage)->storageSize = storageSize;
 
}// end of InitMatch

/********* ********* ********* ********* ********* ********
 * BuildAlphaList
 * 
 * This routine has three parts:
 * Build the AlphaTable
 * The AlphaTable is an index table used to find
 * the start location inside the AlphaList
 * that corresponds to the given alphabet
 * character.
 * Build the AlphaList precursor
 * This is a linked list of the indexes to each
 * character in the fragment. It is used once
 * to build the AlphaList and never re-used.
 * Build the AlphaList
 * This is a sorted list of indexes for each
 * alphabet character. The head of each list is
 * stored in the AlphaTable, and each list is
 * ended by a -1.
 * 
 ********* ********* ********* ********* ********* ********/

BuildAlphaList
void BuildAlphaList(
 char   *alphabet, // legal characters in database
 char   *fragment, // the fragment to find; 0 term
 DNAStore *storage // my storage area
)
{
 short  *aTable; // ptr in the AlphaTable
 short  *precursor;// the AlphaList precursor
 short  *alphaList;// the AlphaList

 char *aString;  // ptr to a character string
 long aChar;// a character from a string
 
 long count;
 short  index;

  /*********
     * Initialize alphabet entries to kEndOfAlphaList
     *     Proper function for characters not in the alphabet
     *     requires that the other entries be preset to zero.
     *     This is automatic if the storage is cleared by
     *     the calling program and if the alphabet does not
     *     change between calls to InitMatch.
     */
 aTable = storage->alphaTable;
 aString = alphabet - 1;
 while( (aChar = (long)(*(++aString)) ) > 0x00 )
 {
 *(aTable+aChar) = kEndOfAlphaList;
 }
 
  /*********
     * Build precursor linked index list
     *     This list is only used to produce the 
     *     AlphaList below. The precursor and
     *     the AlphaList are rebuilt for each
     *     new fragment that will be searched for.
     */
 precursor= storage->precursor;
 aString= fragment - 1;
 index  = 0;
 count  = 0;
 while( (aChar = (long)(*(++aString))) > 0x00 )
 {
 index = *(aTable+aChar); // get prev head
 *(aTable+aChar) = count; // put new head
 *(precursor+count) = index;// store prev head
 count++;
 }
 storage->fragmentSize = count;
 
  /*********
     * Build AlphaList
     *     by walking each alphabet character's precursor 
     *     list and writing the index list into the 
     *     AlphaList the algorithm gets a sorted list of
     *     indexes into the fragment for each letter in the
     *     alphabet. The aTable will point to the first entry
     *     in the AlphaList and the last entry of each 
     *     character list is equal to the constant 
     *     kEndOfAlphaList ( = -1 ). Note that AlphaList
     *     location 0 is used to ignore database characters
     *     which are not in the given alphabet (it was free).
     */
 alphaList = precursor + count;
 *(alphaList) = kEndOfAlphaList;
 aString = alphabet - 1;
 count = 1;
 while( (aChar = (long)(*(++aString)) ) > 0x00 )
 {
 index = *(aTable+aChar);
 *(aTable+aChar) = count;
 while( index != kEndOfAlphaList )
 {
 *(alphaList+count) = index;
 index = *(precursor+index);
 count++;
 }
 *(alphaList+count) = kEndOfAlphaList;
 count++;
 }
 storage->alphaList= alphaList;
 storage->matchQueue = alphaList + count + 1;
 
}// end of BuildAlphaList


/********* ********* ********* ********* ********* ********
 * FindMatch
 *
 * For each character in the database increment every
 * match count that has the same character ( a hit ).
 * If after all possible alignments have been tallied,
 * the match count is greater than or equal to the value
 * of the threshold, then a match has been found.
 * Add the matching entry to the return array and continue
 * until all database characters have been tested.
 * 
 ********* ********* ********* ********* ********* ********/

FindMatch
long FindMatch(  // return number of matches
 char *alphabet, // legal characters in database
 char *database, // the reference database
 void *storage,  // pre-allocated storage
 char *fragment, // the fragment to find
 long diffsAllowed,// num of diffs allowed between
    //  a "match" and the fragment
 long matchPosition[]// match return array
)
{
 DNAStore *theStore; // typed storage
 short  *matchTop; // top of match array
 short  *matchCur; // current match array entry
 short  *aTable; // alpha to aList index table
 short  *aList;  // array of hit offsets
 short  *hitOffset;// current hit offset entry
 char   *dbString; // current database char entry
 long   dbChar;  // current database character
 long   count;   // current database location
 long   numMatch;// number of matches found
 long   fragSize;// fragment size in bytes
 long   loop;    // loop counter
 long   hitPos;  // current hit offset position
 long   threshold; // the threshold for matching
 
 theStore = (DNAStore*)storage;
 BuildAlphaList( alphabet,fragment,theStore);
 fragSize = theStore->fragmentSize;
 matchTop = theStore->matchQueue;
 matchCur = matchTop + fragSize;
 
 theStore->usedStorage
 = (long)(matchCur+fragSize)-(long)theStore;
    /*********
     * Clear the Match Count Array
     *     clear out the match counts for the entire array
     */
 for( count=0; count<fragSize; count++ )
 {
 *(matchCur+fragSize) = 0;
 *matchCur- = 0;
 }

    /*********
     * Walk the Database
     *
     *    The match count array is a double size circular
     *    queue of match counts. It is double size so I do
     *    not need to check the array bounds in the inner
     *    match count increment loop.
     */
  
 dbString = database - 1;
 aTable = theStore->alphaTable;
 aList = theStore->alphaList;
 threshold = fragSize-diffsAllowed;

 numMatch = 0;
 count = -fragSize;// count = current database loc.
 
 while( (dbChar = (long)(*(++dbString))) > 0x00 )
 {
    // circular queue reset to center
 if( matchCur == matchTop )
 {
 matchCur += fragSize;
 }
 
    // check for a match to the fragment
 if((*matchCur+*(matchCur+fragSize)) >= threshold )
 {
 matchPosition[ numMatch ] = count;
 numMatch++;
 }
 
    // clear both old counts
 *matchCur = 0;
 *(matchCur+fragSize) = 0;

    // increment match counts for all possible
    //     fragment alignments
 hitOffset = aList + *(aTable + dbChar) - 1;
 while( (hitPos = (long)(*(++hitOffset))) >= 0 )
 {
 *(matchCur + hitPos ) += 1;
 }
 
    // The match count queue is walked in reverse
    //     order through memory because the alphaList
    //     indexes are positive.
 matchCur-;
 count++;
 }
 
    /*********
     * Check the remaining match count entries for
     *    any fragments that extend beyond the end of
     *    the database.
     */
  
 for( loop=0; loop < diffsAllowed; loop++)
 {
 if( matchCur == matchTop )
 {
 matchCur += fragSize;
 }
 
 if((*matchCur+*(matchCur+fragSize)) >= threshold )
 {
 matchPosition[ numMatch ] = count;
 numMatch++;
 }
 matchCur-;
 count++; 
 }
 
 return(numMatch);
 }
 
    // end of DNA_Match.c

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Day One 2.3 - Maintain a daily journal.
Day One is the easiest and best-looking way to use a journal / diary / text-logging application for the Mac. Day One is well designed and extremely focused to encourage you to write more through... Read more
Carbon Copy Cloner 4.1.16 - Easy-to-use...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
Sketch 45 - Design app for UX/UI for iOS...
Sketch is an innovative and fresh look at vector drawing. Its intentionally minimalist design is based upon a drawing space of unlimited size and layers, free of palettes, panels, menus, windows, and... Read more
NeoFinder 7.1 - Catalog your external me...
NeoFinder (formerly CDFinder) rapidly organizes your data, either on external or internal disks, or any other volumes. It catalogs all your data, so you stay in control of your data archive or disk... Read more
TunnelBear 3.0.15 - Subscription-based p...
TunnelBear is a subscription-based virtual private network (VPN) service and companion app, enabling you to browse the internet privately and securely. Features Browse privately - Secure your data... Read more
Hopper Disassembler 4.2.5- - Binary disa...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32-bit and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about... Read more
BetterTouchTool 2.261 - 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
Sketch 44.1 - Design app for UX/UI for i...
Sketch is an innovative and fresh look at vector drawing. Its intentionally minimalist design is based upon a drawing space of unlimited size and layers, free of palettes, panels, menus, windows, and... Read more
BetterTouchTool 2.260 - 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
Chromium 59.0.3071.115 - 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 59.0.3071.115: This update has no Flash plug... Read more

Latest Forum Discussions

See All

Super Samurai Rampage (Games)
Super Samurai Rampage 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Super Samurai Rampage is a bloody, retro pixel style high score chaser. You play as a legendary Samurai warrior provoked... | Read more »
You can now travel to Skyrim in The Elde...
The Elder Scrolls: Legends' new expansion has opened up Skyrim's craggy mountains and snowy plains for exploration today. Heroes of Skyrim is out now, adding a bunch of new Skyrim content to Bethesda's recent CCG. [Read more] | Read more »
High-stakes solitaire game 'Missile...
Missile Command and Solitaire might seem like an odd couple, but indie developer Nathan Meunier has brought them together to create his first game, Missile Cards, which launched on the App Store today. [Read more] | Read more »
Eos 2 (Music)
Eos 2 2.0.2 Device: iOS Universal Category: Music Price: $5.99, Version: 2.0.2 (iTunes) Description: | Read more »
Supercell celebrates Hay Day's comm...
Before there was Clash Royale or Clash of Clans, there was Hay Day. Now, Supercell's first game is celebrating its fifth anniversary, and the developer is commemorating the event with this touching new video. Supercell picked one long-running Hay... | Read more »
Dive into epic summer adventure with Oce...
Summer may be the best time to enjoy ocean adventures, and now you don’t even have to leave the comfort of your own home, thanks to the folks at Joycity, creators of Oceans & Empires. The old-timey naval MMO is getting a sizable new June Grand... | Read more »
Missile Cards (Games)
Missile Cards 1.0.9 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.9 (iTunes) Description: "Missile Command meets Solitaire...only with more doomlasers, death, and explosions." | Read more »
Collect mini assassins in 'Assassin...
Assassin's Creed is traveling back in time to the Spanish Inquisition for its latest mobile entry, Assassin's Creed Rebellion. The game is giving the series a look that's a huge departure from its past design, recreating classic characters in a... | Read more »
Animal Crossing is still coming to mobil...
Animal Crossing is still coming to mobile in 2017, according to aWaypointinterview with Nintendo. Announced in 2016, the game was delayed without a defined release window. However, fans of Nintendo's fantasy slice of life game won't have to wait... | Read more »
Ravenscroft 275 Piano (Music)
Ravenscroft 275 Piano 1.0.0 Device: iOS Universal Category: Music Price: $35.99, Version: 1.0.0 (iTunes) Description: Experience the splendor of a Ravenscroft Grand with the most realistic sounding piano ever created for iOS. Launch... | Read more »

Price Scanner via MacPrices.net

Will iPad Running iOS 11 Be The ‘Ute’ Of The...
Steve Jobs’ analogy comparing iPads and PCs to cars and trucks respectively is seven years old but still stimulates discussion and debate. Appearing on an All Things D panel in 2010 shortly after the... Read more
Free CarePassport App gives Patients control...
Boston based CarePassport is on a mission to enable patients to take control of their medical records by allowing patients to aggregate, store, share and manage all their medical data including... Read more
Western Digital Launches New My Passport Ultr...
Western Digital Corporation has expanded its WD brand My Passport portable drive line with the redesigned My Passport Ultra drive. In addition to a new metallic look, the drive offers intuitive WD... Read more
Clearance 2016 13-inch MacBook Pros available...
B&H Photo has clearance 2016 13″ MacBook Pros in stock today for up to $210 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 13″ 2.9GHz/512GB Touch Bar... Read more
Apple Releases iOS 11 Public Beta; How To Get...
The official release of Apple’s latest mobile operating system iOS 11 is vaguely slated for the fall, but as of June 26, ordinary users can download an iOS 11 public beta. To download the iOS 11... Read more
Extend Life of MacBook Pro Retina 2.0TB With...
MacSales.com/Other World Computing has announced availability of the new OWC 2.0TB Aura Pro Solid State Drive for mid-2012 to early 2013 Apple MacBook Pro with Retina display. One of the fastest... Read more
BBEdit SummerFest 2017 Discount Ends Friday,...
You can get 20% off BBEdit for a limited time in Bare Bones Software’s http://www.eastgate.com/Tinderbox/Specials/SummerFest.html?mc_cid=f2101ca260&mc_eid=[UNIQID]SummerFest 2017 sale and... Read more
Use Apple’s Education discount to save up to...
Purchase a new Mac using Apple’s Education discount, and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free: - 15″ 2... Read more
Clearance 27-inch 3.3GHz 5K iMac available fo...
Amazon clearance 27″ 3.3GHz 5K iMacs (MK482LL/A) available for $1799.90 including free shipping. Their price is $500 off original MSRP, and it’s the lowest price available for this model from any... Read more
13-inch 1.8GHz/256GB MacBook Air on sale for...
B&H Photo has the updated 2017 13″ 1.8GHz/256GB MacBook Air (MQD42LL/A) in stock and on sale for $1129 including free shipping plus NY & NJ tax only. Their price is $70 off MSRP. Read more

Jobs Board

*Apple* Online Store WW Customer Insights -...
…with data mining tools: R, SAS, etc.Experience with common shell scripting tools: unix, python, apple script, Swift etc. Apple Online is one of the largest and Read more
Engineering Project Manager, *Apple* Online...
…the electronic commerce (eCommerce) systems and solutions that enable and support the Apple Online Store (AOS) - one of world's largest online retail businesses, Read more
*Apple* News Product Marketing Mgr., Publish...
…organizational consensus on strategy and vision for publisher tools, authoring, and Apple News Format.Carries this strategy and vision across the organization to 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
Security Data Analyst - *Apple* Information...
…data sources need to be collected to allow Information Security to better protect Apple employees and customers from a wide range of threats.Act as the subject matter Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.