TweetFollow Us on Twitter

May 95 Challenge
Volume Number:11
Issue Number:5
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Mike Scanlin, Mountain View, CA

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

Hy-phen-a-tion

Hyphenation algorithms come in two flavors: rule-based and dictionary-based. Of the two, dictionary-based is more reliable but has the downside of requiring a lot of storage space. Rule-based methods require considerably less space and have the option of using an “exceptions” dictionary to improve accuracy. This month’s Challenge is to implement a rule-based hyphenation algorithm.

The algorithm is this: Each part of the word on either side of the hyphen must include a vowel, not counting a final e, es or ed. The part of the word after the hyphen cannot begin with a vowel or a double consonant. No break is made between any two of the following letter combinations: sh, gh, ph, ch, th, wh, gr, pr, cr, tr, wr, br, fr, dr, vowel-r, vowel-n, or om. That means that if any two of those pairs occur next to each other, you can’t break them apart (i.e. ‘from’ contains ‘fr’ and ‘om’, which are both on the list; therefore you would not split it between the ‘r’ and the ‘o’). The letter ‘y’ is not a vowel.

The two routines you’ll write are:

void *
InitHyphenation(maxRAM)
ulong   maxRAM;

void
Hyphenate(privateDataPtr, inPtr, outPtr)
void  *privateDataPtr;
Str255  *inPtr;
Str255  *outPtr;

The InitHyphenation routine is an untimed routine called once that can set up whatever tables you might want to use. It must not allocate more than maxRAM bytes, which will be between 16K and 64K.

Hyphenate is the routine that does the work. PrivateDataPtr is the return value from the InitHyphenation routine. InPtr is a pointer to a read-only unhyphenated Pascal word (containing only letters ‘a’..‘z’ and ‘A’..‘Z’). OutPtr is a pointer to 256 bytes of space where you store the hyphenated word. You need to preserve the case of the input and you should insert a kHyphen byte (0x2D) everywhere the above algorithm tells you to (yes, the complete output is guaranteed to fit within a Str255).

Note that this algorithm is valid for English only. It will find about 70% of all valid hyphens and will make mistakes about 45% of the time. It is assumed that if this was part of a real application that a hyphenation exception word list would be kept. That list would be checked before calling this function. You, however, don’t need to be concerned with that.

Write to me if you have any questions.

Two Months Ago Winner

Congrats to Gustav Larsson (Mountain View, CA) for winning the Method Dispatcher Challenge. Gustav was a virtual unknown to this column a few months ago but he is rising fast in the Top 20 rankings. The 20 points he wins this month move him from 10th place to 4th place.

Here are the times and code sizes for each entry. Numbers in parens after a person’s name indicate that person’s cumulative point total for all previous Programmer Challenges, not including this one:

Name time code

Gustav Larsson (40) 261 1040

Kevin Cutts (36) 304 266

Jeff Mallett (27) 338 1192

Xan Gregg 349 158

Ernst Munter (51) 385 1466

Thomas Studer 437 572

David Howarth 632 130

Scanlin’s brute force method 420 122

Everyone who entered implemented some kind of cache. Gustav chose a 10-way set-associative cache. He splits the 16K of usable cache space into 256 cache sets, each of which holds 10 entries. He uses a hash based on the class and method numbers to map to one of the 256 caches. Once he’s got that he checks the 10 entries for a match. If he doesn’t find a match he uses an efficient binary search to look for the method within the class.

In designing any cache, the choice of hash function and amount of set-associativity (if any) is highly dependent on your data and access pattern. Gustav’s code could be tuned for a variety of efficient cache uses. Nice job, Gustav.

Poker Winner Disqualified

Turns out that I failed to do adequate testing on the winning entry for the Poker Hand Evaluator Challenge, in which Kevin Cutts was the published winner. Unfortunately, I’m going to have to retro-actively disqualify Kevin and award the 1st place prize to Gustav Larsson. My apologies to Kevin and the other MacTech readers. Rather than publish Gustav’s well-commented winning solution (it’s quite long) I’ll make it available via e-mail. If you’re interested, send me a note at scanlin@genmagic.com or at any of the Programmer Challenge electronic addresses (see p. 2).

This latent win for Gustav means that he’s 3 for 3 in the last 3 challenges, which is an unmatched winning streak. Congrats, Gustav! Also, Dave Darrah was the first person to point out the flaws in Kevin’s code and so he receives 5 extra points in the cumulative point totals for doing so. Thanks, Dave!

Top 20 Contestants of All Time

Here are the Top 20 Contestants for the 33 Programmer’s Challenges to date. The numbers below include points awarded for this months’ top 5 entrants. (Note: ties are listed alphabetically by last name -- there are 23 people listed this month because 7 people have 20 points each.)

1. Boonstra, Bob 176

2. Karsh, Bill 71

3. Stenger, Allen 65

4. Larsson, Gustav 60

5. Munter, Ernst 53

6. Riha, Stepan 51

7. Goebel, James 49

8. Cutts, Kevin 46

9. Nepsund, Ronald 40

10. Vineyard, Jeremy 40

11. Darrah, Dave 34

12. Mallet, Jeff 34

13. Landry, Larry 29

14. Elwertowski, Tom 24

15. Kasparian, Raffi 24

16. Lee, Johnny 22

17. Anderson, Troy 20

18. Burgoyne, Nick 20

19. Galway, Will 20

20. Israelson, Steve 20

21. Landweber, Greg 20

22. Noll, Bob 20

23. Pinkerton, Tom 20

There are three ways to earn points: (1) by scoring in the top 5 of any challenge, (2) by 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 5 points

suggesting challenge 2 points

Here is Gustav’s winning solution:

Dispatch.c

Copyright ©1995 Gustav K. Larsson

#define kMethodNotFound ((void *) 0)
#define kClassNotFound  ((void *) -1)

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

typedef ushort  ClassID;
typedef ushort  MethodNumber;
typedef void *  MethodAddress;

typedef struct {
  MethodNumber  methodNumber;
  MethodAddress methodAddress;
} MethodEntry;

typedef struct {
  ushort        inheritedCount;
  ushort        inheritedClasses[15];
  MethodNumber  largestMethodNumber;
  ushort        methodCount;
  MethodEntry   methods[];
} Class, *ClassPtr;

/* Each block in the cache is 64 bytes and holds 10 entries. The id field distinguishes class/method pairs 
that map to the same cache block. The hits field has a bit for each entry, which is set whenever there is a 
hit on the entry.  The "next" field is 0..9 and indicates where to check first when deciding which entry to replace. 
*/

#define BLOCK_SIZE 10

typedef struct {
  ushort          id [ BLOCK_SIZE ];
  ushort          hits;
  ushort          next;
  MethodAddress   methodAddress [ BLOCK_SIZE ];
} CacheBlock;

static CacheBlock Cache[256]; /* exactly 16K */
GetClassPtr
extern ClassPtr GetClassPtr( ClassID );
MethodAddress FindMethod( ClassID, MethodNumber );
static MethodAddress HandleMiss( ClassID, MethodNumber,
                                 CacheBlock *, ushort );
FindMethod
MethodAddress
FindMethod( ClassID classID, MethodNumber methodNumber )
{
  register ulong hash;
  register ushort *idPtr;
  register CacheBlock *block;
Check cache for this class & method.

/* First, generate a hash key that is unique for each class/method pair. The formula classID + 437 * method 
works since 437 is greater than the highest class ID, 400. The ideal multiplier depends heavily on the distribution 
of class/method pairs, but 437 seems to give a reasonable spread under a variety of conditions.
    The low byte of the hash key becomes the block number, and the higher bytes become the "id" (to distinguish 
class/method pairs that map to the same block). Add one to the id so it is never zero (zero indicates an unused 
cache entry). */

  hash = classID + 437L * methodNumber;
  block = &Cache[ (uchar)hash ];
  hash = (hash >> 8) + 1;   /* now hash holds just the id */

  idPtr = block->id;
  if ( *idPtr++ == (ushort)hash ) goto hit0;
  if ( *idPtr++ == (ushort)hash ) goto hit1;
  if ( *idPtr++ == (ushort)hash ) goto hit2;
  if ( *idPtr++ == (ushort)hash ) goto hit3;
  if ( *idPtr++ == (ushort)hash ) goto hit4;
  if ( *idPtr++ == (ushort)hash ) goto hit5;
  if ( *idPtr++ == (ushort)hash ) goto hit6;
  if ( *idPtr++ == (ushort)hash ) goto hit7;
  if ( *idPtr++ == (ushort)hash ) goto hit8;
  if ( *idPtr++ == (ushort)hash ) goto hit9;

  return HandleMiss( classID, methodNumber,
                     block, (ushort)hash );

/* Handle cache hit */
hit0: block->hits |= 0x001;  return block->methodAddress[0];
hit1: block->hits |= 0x002;  return block->methodAddress[1];
hit2: block->hits |= 0x004;  return block->methodAddress[2];
hit3: block->hits |= 0x008;  return block->methodAddress[3];
hit4: block->hits |= 0x010;  return block->methodAddress[4];
hit5: block->hits |= 0x020;  return block->methodAddress[5];
hit6: block->hits |= 0x040;  return block->methodAddress[6];
hit7: block->hits |= 0x080;  return block->methodAddress[7];
hit8: block->hits |= 0x100;  return block->methodAddress[8];
hit9: block->hits |= 0x200;  return block->methodAddress[9];
}
HandleMiss
static MethodAddress
HandleMiss( ClassID classID, MethodNumber methodNumber,
            CacheBlock *blockPtr, ushort id )
{
  register ClassPtr classPtr;
  MethodAddress methodAddress;
  register ushort *temp;  /* shared address register */

  /* Not in cache, so look it up the hard way */
  classPtr = GetClassPtr( classID );
  if ( classPtr != kClassNotFound ) {

    /* Look in this class. Use a binary search. */
    {
      register MethodEntry *methods = classPtr->methods;
      ushort searchSize = classPtr->methodCount;
      register MethodNumber methodReg = methodNumber;
                                /* method # in a register */

/* Unroll the binary search for the most common cases. The BINARY macro reduces the search to progressively 
more elementary cases. If classPtr->methodCount is greater than 32, we run a general binary search until 
the search is reduced to an unrolled case.  */

continueBinarySearch:
      switch ( searchSize )
      {
        bin2: case 2:
          if ( methods[1].methodNumber == methodReg ) {
            methodAddress = methods[1].methodAddress;
            goto addCache;
          }
          /* else fall through... */
        bin1: case 1:
          if ( methods[0].methodNumber == methodReg ) {
            methodAddress = methods[0].methodAddress;
            goto addCache;
          }
          else goto checkSuperclasses;

      #define BINARY(mid,mid1)                        \
        if ( methodReg < methods[mid].methodNumber )  \
          goto bin##mid;  /* like "hi = mid" */       \
        else {                                        \
          methods += mid; /* like "lo = mid" */       \
          goto bin##mid1;                             \
        }

        /* binN: case N: BINARY(N/2,(N+1)/2) */
        bin3:  case  3: BINARY(1,2)
        bin4:  case  4: BINARY(2,2)
        bin5:  case  5: BINARY(2,3)
        bin6:  case  6: BINARY(3,3)
        bin7:  case  7: BINARY(3,4)
        bin8:  case  8: BINARY(4,4)
        bin9:  case  9: BINARY(4,5)
        bin10: case 10: BINARY(5,5)
        bin11: case 11: BINARY(5,6)
        bin12: case 12: BINARY(6,6)
        bin13: case 13: BINARY(6,7)
        bin14: case 14: BINARY(7,7)
        bin15: case 15: BINARY(7,8)
        bin16: case 16: BINARY(8,8)
        bin17: case 17: BINARY(8,9)
        bin18: case 18: BINARY(9,9)
        bin19: case 19: BINARY(9,10)
        bin20: case 20: BINARY(10,10)
        bin21: case 21: BINARY(10,11)
        bin22: case 22: BINARY(11,11)
        bin23: case 23: BINARY(11,12)
        bin24: case 24: BINARY(12,12)
        bin25: case 25: BINARY(12,13)
        bin26: case 26: BINARY(13,13)
        bin27: case 27: BINARY(13,14)
        bin28: case 28: BINARY(14,14)
        bin29: case 29: BINARY(14,15)
        bin30: case 30: BINARY(15,15)
        bin31: case 31: BINARY(15,16)
        bin32: case 32: BINARY(16,16)

        #define NUM_UNROLLED 32 /* # of unrolled cases */

        default:
          if (methodReg <= classPtr->largestMethodNumber) {
            register ushort lo, mid, hi, mn;
            lo = 0;
            hi = classPtr->methodCount - 1;
            while ( lo + NUM_UNROLLED - 1 < hi ) {
              mid = (lo + hi) >> 1;
              mn = methods[mid].methodNumber;
              if ( methodReg < mn )
                hi = mid;
              else if ( methodReg > mn )
                lo = mid;
              else {
                methodAddress = methods[mid].methodAddress;
                goto addCache;
              }
            }
            /* reduced to an unrolled case */
            searchSize = hi-lo+1;
            methods += lo;
            goto continueBinarySearch;
          }
      }
    }

/* Look in superclasses. Eliminating the recursion by keeping a custom stack of critical variables doesn't 
buy us much. Recursion also makes the code clearer. */

checkSuperclasses:
    {
      register ulong i, max = classPtr->inheritedCount;
           /* shared address register points into class list */
      temp = classPtr->inheritedClasses;

      for ( i = 0; i < max; i++ ) {
        methodAddress = FindMethod(*temp++, methodNumber);
        if ( methodAddress != kMethodNotFound )
          goto addCache;
      }
    }
  }

/* There are two ways to get here: classPtr is kClassNotFound (hopefully rare), or the method was not found 
in any of the superclasses. Either way, put a "not found" entry into the cache. This helps when searching 
complicated inheritance hierarchies or repeatedly looking up the same method in several related subclasses. 
*/

  methodAddress = kMethodNotFound;

Add an entry to the cache.
addCache:

// shared address register holds block pointer
  temp = (ushort*) blockPtr;
  #define block ((CacheBlock*) temp)
  {
    register ulong hits = block->hits;
    register ulong next = block->next;
    register ulong mask = 1L << next;

/* Choose the entry to replace. Look for a cleared bit in "hits" starting at "next". If all the bits are 1 initially, 
go all the way around; we are guaranteed to stop since we clear bits as we go. */

    while ( hits & mask ) {
      hits &= ~mask;              /* no, clear the bit */
      mask <<= 1;                 /* and try next bit */
      if ( mask == (1 << BLOCK_SIZE) )
        mask = 1;
      next++;
    }
    if ( next >= BLOCK_SIZE )
      next -= BLOCK_SIZE;

    block->methodAddress[ next ] = methodAddress;
    block->id[ next ] = id;
    block->hits = hits;
    block->next = ( next < BLOCK_SIZE-1 ? next+1 : 0 );
  }

  return methodAddress;
}

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Amazon Chime 4.3.5721 - Amazon-based com...
Amazon Chime is a communications service that transforms online meetings with a secure, easy-to-use application that you can trust. Amazon Chime works seamlessly across your devices so that you can... Read more
Posterino 3.3.7 - Create posters, collag...
Posterino offers enhanced customization and flexibility including a variety of new, stylish templates featuring grids of identical or odd-sized image boxes. You can customize the size and shape of... Read more
Airmail 3.2.9 - Powerful, minimal email...
Airmail is an mail client with fast performance and intuitive interaction. Support for iCloud, MS Exchange, Gmail, Google Apps, IMAP, POP3, Yahoo!, AOL, Outlook.com, Live.com. Airmail was designed... Read more
Arq 5.8.4 - Online backup to Google Driv...
Arq is super-easy online backup for Mac and Windows computers. Back up to your own cloud account (Amazon Cloud Drive, Google Drive, Dropbox, OneDrive, Google Cloud Storage, any S3-compatible server... Read more
Microsoft Remote Desktop 8.0.39 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Arq 5.8.4 - Online backup to Google Driv...
Arq is super-easy online backup for Mac and Windows computers. Back up to your own cloud account (Amazon Cloud Drive, Google Drive, Dropbox, OneDrive, Google Cloud Storage, any S3-compatible server... Read more
Airmail 3.2.9 - Powerful, minimal email...
Airmail is an mail client with fast performance and intuitive interaction. Support for iCloud, MS Exchange, Gmail, Google Apps, IMAP, POP3, Yahoo!, AOL, Outlook.com, Live.com. Airmail was designed... Read more
Microsoft Remote Desktop 8.0.39 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Posterino 3.3.7 - Create posters, collag...
Posterino offers enhanced customization and flexibility including a variety of new, stylish templates featuring grids of identical or odd-sized image boxes. You can customize the size and shape of... Read more
Airmail 3.2.8 - Powerful, minimal email...
Airmail is an mail client with fast performance and intuitive interaction. Support for iCloud, MS Exchange, Gmail, Google Apps, IMAP, POP3, Yahoo!, AOL, Outlook.com, Live.com. Airmail was designed... Read more

Latest Forum Discussions

See All

Pokémon GO might be getting legendaries...
The long-awaited legendary Pokémon may soon be coming to Pokémon GO at long last. Data miners have already discovered that the legendary birds, Articuno, Moltres, and Zapdos are already in the game, it’s just a matter of time. [Read more] | Read more »
The best deals on the App Store this wee...
If you’ve got the Monday blues we have just the thing to cheer you up. The week is shaping up to be a spectacular one for sales. We’ve got a bunch of well-loved indie games at discounted prices this week along with a few that are a little more... | Read more »
Honor 8 Pro, a great choice for gamers
Honor is making strides to bring its brand to the forefront of mobile gaming with its latest phone, the Honor 8 Pro. The Pro sets itself apart from its predecessor, the Honor 8, with a host of premium updates that boost the device’s graphical and... | Read more »
The 4 best outdoor adventure apps
Now that we're well into the pleasant, warmer months, it's time to start making the most of the great outdoors. Spring and summer are ideal times for a bit of trekking or exploration. You don't have to go it alone, though. There are plenty of... | Read more »
Things 3 (Productivity)
Things 3 3.0.1 Device: iOS iPhone Category: Productivity Price: $7.99, Version: 3.0.1 (iTunes) Description: Meet the all-new Things! A complete rethinking of the original, award-winning task manager – with a perfect balance between... | Read more »
Oddball mash-up Arkanoid vs Space Invade...
In a move no one was really expecting, Square Enix has put forth an Arkanoid/Space Invaders mash-up aptly titled Arkanoid vs Space Invaders. The game launched today on both iOS and Android and the reviews are actually quite good. [Read more] | Read more »
Arkanoid vs Space Invaders (Games)
Arkanoid vs Space Invaders 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: LAUNCH SALE: GET THE GAME AT 20% OFF! Two of the most iconic classic games ever made meet in Arkanoid vs Space... | Read more »
The best new games we played this week
Things got off to a bit of a slow start this week, but as we steadily creep towards Friday a bunch of great games have started cropping up. If you're looking for a quality new release to play this weekend, we've got you covered. Here's a handy... | Read more »
No Stick Shooter (Games)
No Stick Shooter 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Happy Robot presents a fresh take on the classic retro-arcade shooters we all know and love. Featuring 30 levels of non-stop... | Read more »
Chroma Squad (Games)
Chroma Squad 1.0.85 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.85 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

Five To Six Million 10.5-inch iPad Pro Tablet...
Digitimes’ Siu Han and Joseph Tsai report that upstream supply chain shipments for Apple’s new 10.5-inch iPad Pro have been increasing, with monthly shipment volume expected to hit 600,000 units by... Read more
Georgia Tech Students Win Toyota and Net Impa...
Earlier this year, a team of students at Georgia Tech realized that there was a critical gap in transportation services for people who use wheelchairs, and wondered if the solution could be in the... Read more
13-inch 2.0GHz Space Gray MacBook Pro on sale...
Amazon has the 13″ 2.0GHz Space Gray non-Touch Bar MacBook Pro (MLL42LL/A) on sale for $1299.99 including free shipping. Their price is $200 off MSRP, and it’s currently the lowest price available... Read more
Roundup of 15-inch MacBook Pro sale prices, m...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $200 off MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 15″ 2.7GHz... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for...
B&H Photo has the 2015 15″ 2.2GHz Retina MacBook Pro (MJLQ2LL/A) on sale for $1849 including free shipping plus NY & NJ sales tax only. Their price is $150 off MSRP. Read more
21-inch iMacs on sale for $100 off MSRP, save...
B&H Photo has 21″ iMacs on sale for $100 off MSRP, each including free shipping plus NY & NJ sales tax only: - 21″ 3.1GHz iMac 4K: $1399.99 $100 off MSRP - 21″ 2.8GHz iMac: $1199.99 $100 off... Read more
Groupon Survey Finds Families Will Spend One-...
With warmer weather finally arriving in most parts of the country and the school year winding down to a close, Groupon (http://www.groupon.com) asked 1,000 U.S. parents how much time their families... Read more
Panasonic Anounces Toughbook 33 2-in-1 Rugged...
Panasonic has announced the U.S. availability of the Panasonic Toughbook 33, claimed to be the first fully-rugged 2-in-1 detachable laptop that features a 3:2 display. Inspired by the hard-working... Read more
9-inch 32GB iPad Pros available for up to $10...
Amazon resellers are offering new 9″ 32GB iPad Pros for up to $101 off MSRP, starting at $498, including free shipping. Colors may be Space Gray, Silver, Gold, or Rose Gold, depending on the reseller... Read more
Back in stock: Apple refurbished Mac minis st...
Apple has Certified Refurbished Mac minis available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $80 off MSRP - 2.6GHz Mac... Read more

Jobs Board

Director, *Apple* Program - ERP & Cloud...
…make a real difference. Come, shine with us! Astellas is announcing a Director, Apple Program - ERP & Cloud Platform Architecture Lead opportunity in Northbrook, IL. Read more
*Apple* Mobile Master - Best Buy (United Sta...
**508102BR** **Job Title:** Apple Mobile Master **Location Number:** 000511-Athens-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** At Read more
*Apple* Media Products - Commerce Engineerin...
Apple Media Products - Commerce Engineering Manager Job Number: 57037480 Santa Clara Valley, California, United States Posted: Apr. 18, 2017 Weekly Hours: 40.00 Job Read more
Geek Squad *Apple* Master Consultation Agen...
**500444BR** **Job Title:** Geek Squad Apple Master Consultation Agent **Location Number:** 000103-City Of Industry-Store **Job Description:** **What does a Geek Read more
Security Engineer, *Apple* Retail - Apple I...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.