TweetFollow Us on Twitter

Jul 95 Challenge
Volume Number:11
Issue Number:7
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Bob Boonstra and Mike Scanlin

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

Goodbye Mike

[Most of you are well aware of the excellence Mike Scanlin has brought to the magazine since the summer of 1992. Back then, Mike suggest to me that we start a programming puzzle to encourage programmers to write efficient code. Like many quality programmers, Mike was concerned that with the advent of faster machines, programmers were becoming lax in their ways.

The MacTech Programmer’s Challenge grew out of these conversations into the industry icon it is today. We’ve been stopped at trade shows and user group meetings by folks who are proudly wearing their MacTech Programmer’s Challenge Winner t-shirts. They should be proud - it is an accomplishment. We’re thrilled that the Challenge has had this impact on the developer community.

As publisher, working with Mike has been an absolute joy. After almost three years of running the challenge and devising puzzles, Mike is moving on. While his career has spanned such greats like WriteNow, PhotoFlash, and today General Magic, Mike cares about you all, the Challenge, and the magazine. So together, we’ve hand-picked someone we feel is the most qualified successor - Bob Boonstra.

Some of you might recognize Bob as a regular participant (and all-time winner) in past Challenges. Bob’s passion for efficiency dates back to his self-taught introduction to programming, starting in hex, then assembly language, and only later graduating to high level languages. He is a member of the Value-Added NewsWatcher team, adding a few features to John Norstad’s excellent newsreader. When he isn’t writing or reverse engineering code (or working at an unspecified day job), Bob spends time introducing his 8- and 10-year old children to the joys of hiking in the White Mountains, and to the world of Macintosh, but usually not both at the same time.

We wish Mike the best of luck and we welcome Bob with open arms. We hope you do as well. Ed./Pub. -nst]

Sprite Blitz

Most of you are probably familiar with the great shareware arcade games that are available for the Mac. This month you will be writing a key element of an arcade game - the code that moves graphic elements (“sprites”) across a background. There are a number of libraries that do much of this work for the aspiring game writer, but I want to see how fast you can do it, and hopefully we will all benefit from the techniques in the winning code.

The prototypes of the code you must write are as follows:

void StartGame(
/* pointer to CWindow */
 CWindowPtr theWind
);

short /*theSpriteID*/ AddSprite(
/* pointer to ‘cicn' */
 CIconPtr theSprite,
/* initial sprite location */
 Point startLoc 
); /* returns sprite ID to be used in MoveSprite, DeleteSprite */

void DeleteSprite(
/* ID of sprite to delete */
 short theSpriteID 
);

void MoveSprite(
/* ID of sprite to move */
 short theSpriteID,
/* amount to move sprite 
    NOTE: offset, not new location */
 Point amountToMove
);

void UpdateScreen(void);  

The problem works like this. Your routine StartGame will be called first and will be provided with a pointer to a color window. The window will be preset to a background that must be preserved, except for portions that are obscured by sprites. StartGame will not be timed, so you can do whatever initialization you need to do, like allocating an offscreen pixmap and initializing it to the contents of the window. Your routines AddSprite, DeleteSprite, and MoveSprite will then be called repeatedly to add, delete, and move sprites. Your routine UpdateScreen will also be called repeatedly, at which time you must redraw all sprites at their current locations and restore the background at their old locations.

Sprites will be provided to AddSprite as ‘cicn’ data structures, described in IM V-80 or NIM Imaging 4-105. Even though a ‘cicn’ can have an arbitrary shape, the sprites your code sees will have widths that are 1, 2, 4, 8, 16, or 32 pixels, to simplify things, but any height up to 32 pixels. A ‘cicn’ also has an associated mask, and you need to remember to show the correct part of the background through any holes in the mask. One way to draw the sprites, of course, is with the toolbox routine PlotCIcon, but you might find a better way

To simplify the problem, you can rely on (**theWind->portPixMap).bounds being longword aligned on a single monitor that is in 256 color mode, and on the pixelSize being 8 bits. The background will not change over time (i.e., you don’t have to handle a scrolling background). You can assume that there will be no more than 200 active sprites, and you can assume a sprite will not move more than 8 pixels horizontally or more than 8 pixels vertically in any given MoveSprite call. The color table of each sprite ‘cicn’ will be the same as that in the window PixMap. In a real game, you would probably do some collision detection on sprites, but our sprites will pass thru one another oblivious to the collision. In the event sprites overlap, you should draw them in the order that they were created by AddSprite (so that the sprite created last would be drawn over other sprites). You will need to do bounds checking of the sprite location against the window, because our sprites may move partially or completely out of the window.

This problem would be appropriate for an assembly language Challenge, but we’ll see how well you can do in straight C. Entries with obviously jerky visual effects will be considered less “correct” than those with smooth visual effects. I’ll select the winner from the correct entries based on how fast the code runs on a 68040 using the THINK C compiler, but - deadline permitting - I’ll also measure native execution time on a PowerPC. Now start blitting those sprites!

Two Months Ago Winner

Congratulations to Raffi Kasparian (Baltimore, MD) for having the fastest and smallest entry in the Hyphenation Challenge. Excellent job! This is Raffi’s second 1st place showing (he also won the Tile Windows Challenge in July 1993).

Here are the times and code sizes for the entries that worked. 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

Raffi Kasparian (22) 99 348

Peter McA’Nulty 111 616

Ronald Nepsund (40) 121 402

Björn Davidsson 137 788

Robert Noll (20) 139 542

Bill Wade 165 462

Ernst Munter (60) 165 1036

Brian Moffat 171 1240

Dave Darrah (31) 220 666

Robert Westlund 293 476

Rick Genter 315 4276

D.H. 16928 978

E.O. 36536 764

M.D. 39727 3562

Raffi made the observation that there was a simpler rule that satisfied the given rules for hyphenating. This was not my intention (I try hard not to give trick Challenges) but I congratulate Raffi on finding this alternative. His main rule (given in his comments) is “Working forward from the beginning of the word until the last vowel is reached (not counting final e, es or ed), hyphenate every vowel-consonant pair unless the vowel is followed by a double consonant. In this case, hyphenate between the double consonant. This method meets the hyphenation requirements without having to deal directly with all the letter combination rules.” Needless to say, this simplifies the code quite a bit.

Many people wrote to me and asked about the “pairs of unsplitable pairs” rule. In the Challenge, I said, “No break is made between any two of the following letter combinations: sh, gh, p, ch, th, wh, gr, pr, cr, tr, wr, br, fr, dr, vowel-r, vowel-n, or om.” Then I proceeded to give a confusing example that wouldn’t have been hyphenated anyway because of other rules. Sorry. Here’s a better example: This hyphen in ‘chin-chilla’ is illegal because ‘in’ and ‘ch’ are both on the list of pairs that can’t have a hyphen between them. Some people misinterpreted the rule to mean “don’t hyphenate any of these pairs”. My apologies. Once again, I urge you to send e-mail to one of the Programmer Challenge addresses if there is any doubt about the stated rules.

As I said last month, I am turning this column over to Bob Boonstra. This month’s Sprite Blitz Challenge is Bob’s second puzzle. Next month is Bob’s first month at owning both halves of this column (a new puzzle and a previous answer). Please direct any future ideas, questions, or comments regarding this column to Bob at any of the Programmer Challenge addresses given in the front of the magazine.

So long and keep on optimizing!

Mike Scanlin
scanlin@genmagic.com

Top 20 Contestants of All Time

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

1. Boonstra, Bob 176

2. Karsh, Bill 71

3. Stenger, Allen 65

4. Larsson, Gustav 60

5. Munter, Ernst 60

6. Riha, Stepan 51

7. Goebel, James 49

8. Nepsund, Ronald 47

9. Cutts, Kevin 46

10. Mallett, Jeff 44

11. Kasparian, Raffi 42

12. Vineyard, Jeremy 40

13. Darrah, Dave 31

14. Landry, Larry 29

15. Elwertowski, Tom 24

16. Gregg, Xan 24

17. Lee, Johnny 22

18. Noll, Robert 22

19. Anderson, Troy 20

20. Burgoyne, Nick 20

21. Galway, Will 20

22. Israelson, Steve 20

23. Landweber, Greg 20

24. 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 Raffi’s winning solution:

/*                     HY-PHEN-A-TION                               */
/*                                                             */
/*                   Raffi J. Kasparian                                 */
/*                                                             */
/* Please set the following three defines to appropriate    */
/* values if their default settings are not appropriate.              */

#define AllowMixedCaseDoubleConsonants                  true
/* if, for example, “Ss” or “sS” might occur in the       */
/* middle of the word (as in “paSsion”).                  */

#define AllowZeroLengthWords                           false
/* if the length byte might be a zero.                    */

#define AllowMultipleConsonants                         true
/* if multiple ( >2 ) same-consonants are po“sssss”ible.  */

#define uchar unsigned char
#define ulong unsigned long
#define kHyphen 0x2D
#define v( a ) ( a == 'A' || a == 'a' || \
                 a == 'E' || a == 'e' || \
                 a == 'I' || a == 'i' || \
                 a == 'O' || a == 'o' || \
                 a == 'U' || a == 'u' )

static Boolean vowelTable[128] = {
  v(0), v(1), v(2), v(3), v(4), v(5), v(6), v(7), v(8), 
  v(9), v(10), v(11), v(12), v(13), v(14), v(15), v(16), 
  v(17), v(18), v(19), v(20), v(21), v(22), v(23), v(24), 
  v(25), v(26), v(27), v(28), v(29), v(30), v(31), v(32), 
  v(33), v(34), v(35), v(36), v(37), v(38), v(39), v(40), 
  v(41), v(42), v(43), v(44), v(45), v(46), v(47), v(48), 
  v(49), v(50), v(51), v(52), v(53), v(54), v(55), v(56), 
  v(57), v(58), v(59), v(60), v(61), v(62), v(63), v(64), 
  v(65), v(66), v(67), v(68), v(69), v(70), v(71), v(72), 
  v(73), v(74), v(75), v(76), v(77), v(78), v(79), v(80), 
  v(81), v(82), v(83), v(84), v(85), v(86), v(87), v(88), 
  v(89), v(90), v(91), v(92), v(93), v(94), v(95), v(96), 
  v(97), v(98), v(99), v(100), v(101), v(102), v(103), 
  v(104), v(105), v(106), v(107), v(108), v(109), v(110), 
  v(111), v(112), v(113), v(114), v(115), v(116), v(117), 
  v(118), v(119), v(120), v(121), v(122), v(123), v(124), 
  v(125), v(126), v(127)
};

void *InitHyphenation( ulong maxRAM )
{
  return (void*)vowelTable;
}

void Hyphenate( privateDataPtr, inPtr, outPtr )
  void *privateDataPtr;
  Str255 *inPtr;
  Str255 *outPtr;
{
  #define mIsVowel( a ) ( ((Boolean*)privateDataPtr)[a] )
  #define mIsConsonant( a ) ( ! mIsVowel( a ) )

  #if AllowMixedCaseDoubleConsonants
    #define mIsDoubleConsonant( in )\
      ( *in == ( a = *( in + 1 ) ) || *in == a + 'a' - 'A' \
        || *in == a + 'A' - 'a' )
  #else
    #define mIsDoubleConsonant( in ) ( *in == *( in + 1 ) )
  #endif
  
  register uchar *in, *out, *out0, *inLast, *lastVowel;
  #if AllowMixedCaseDoubleConsonants
    register uchar a;
  #endif
  
  in = *inPtr;
  out = out0 = *outPtr;
  lastVowel = inLast = in + *in;

  /* working from back to front of the word, locate the   */
  /* last vowel not including final ‘e’, ‘es’, or ‘ed.    */
  if( mIsVowel( *lastVowel ) ){
    if( *lastVowel == 'e' || *lastVowel == 'E' ){
      lastVowel--;
      goto FIND_LAST_VOWEL;
    }
    else goto ALGORITHM;
  }
  switch( *lastVowel-- ){
  case 's': case 'd': case 'S': case 'D':
    if( *lastVowel == 'e' || *lastVowel == 'E' )
      lastVowel--;
    break;
  #if AllowZeroLengthWords
    case '\0': goto COPY_TO_END;
  #endif
  }  
  FIND_LAST_VOWEL: do{
    if( lastVowel == in ) goto COPY_TO_END;
    if( mIsVowel( *lastVowel ) ) break;
    lastVowel--;
  }while( true );

  ALGORITHM:  
  /* Working forwards from the beginning of the word                */
  /* until lastVowel is reached, hyphenate every           */
  /* vowel/consonant pair unless the vowel is followed by                       */
  /* a double consonant.  In this case, hyphenate between                    */
  /* the double consonant.  This method meets the             */
  /* hyphenation requirements without having to deal               */
  /* directly with all the letter combination rules.            */
  
  *out++ = *in++; /* copy length byte */
  while( true ){
    while( mIsConsonant( *in ) )
      *out++ = *in++;                    
    do{
      if( in == lastVowel ) goto COPY_TO_END;
      *out++ = *in++;        
    }while( mIsVowel( *in ) );    
    
    /* handle double or multiple consonants               */
    #if AllowMultipleConsonants
      while( mIsDoubleConsonant( in ) ) *out++ = *in++;
    #else
      if( mIsDoubleConsonant( in ) ) *out++ = *in++;
    #endif       
    *out++ = kHyphen; *out++ = *in++; (*out0)++;
  }
  COPY_TO_END: do *out++ = *in++; while( in <= inLast );
  
#undef mIsVowel
#undef mIsConsonant
#undef mIsDoubleConsonant
}

 
AAPL
$119.00
Apple Inc.
+1.40
MSFT
$47.75
Microsoft Corpora
+0.28
GOOG
$540.37
Google Inc.
-0.71

MacTech Search:
Community Search:

Software Updates via MacUpdate

Skype 7.2.0.412 - Voice-over-internet ph...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
HoudahSpot 3.9.6 - Advanced file search...
HoudahSpot is a powerful file search tool built upon MacOS X Spotlight. Spotlight unleashed Create detailed queries to locate the exact file you need Narrow down searches. Zero in on files Save... Read more
RapidWeaver 6.0.3 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
iPhoto Library Manager 4.1.10 - Manage m...
iPhoto Library Manager lets you organize your photos into multiple iPhoto libraries. Separate your high school and college photos from your latest summer vacation pictures. Or keep some photo... Read more
iExplorer 3.5.1.9 - View and transfer al...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
MacUpdate Desktop 6.0.3 - Discover and i...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
SteerMouse 4.2.2 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. It also supports Apple Mighty Mouse very well. SteerMouse can assign various functions to buttons that Apple's software does not allow,... Read more
iMazing 1.1 - Complete iOS device manage...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
PopChar X 7.0 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more
OneNote 15.4 - Free digital notebook fro...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more

Latest Forum Discussions

See All

Raby (Games)
Raby 1.0.3 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.3 (iTunes) Description: ***WARNING - Raby runs on: iPhone 5, iPhone 5C, iPhone 5S, iPhone 6, iPhone 6 Plus, iPad Mini Retina, iPad Mini 3, iPad 4, iPad Air,... | Read more »
Oddworld: Stranger's Wrath (Games)
Oddworld: Stranger's Wrath 1.0 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0 (iTunes) Description: ** PLEASE NOTE: Oddworld Stranger's Wrath requires at least an iPhone 4S, iPad 2, iPad Mini or iPod Touch 5th gen... | Read more »
Bounce On Back (Games)
Bounce On Back 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Dwelp (Games)
Dwelp 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: === 50% off for a limited time, to celebrate release === Dwelp is an elegant little puzzler with a brand new game mechanic. To complete a... | Read more »
Make Way for Fat Chicken, from the Maker...
Make Way for Fat Chicken, from the Makers of Scrap Squad Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Relevant Games has announced they will be releasing their reverse tower defense game, | Read more »
Tripnary Review
Tripnary Review By Jennifer Allen on November 26th, 2014 Our Rating: :: TRAVEL BUCKET LISTiPhone App - Designed for the iPhone, compatible with the iPad Want to create a travel bucket list? Tripnary is a fun way to do exactly that... | Read more »
Ossian Studios’ RPG, The Shadow Sun, is...
Ossian Studios’ RPG, The Shadow Sun, is Now Available for $4.99 Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Mmmm, Tasty – Having the Angry Birds for...
The very first Angry Birds debuted on iOS back in 2009. When you sit back and tally up the number of Angry Birds games out there and the impact they’ve had on pop culture as a whole, you just need to ask yourself: “How would the birds taste... | Read more »
Rescue Quest Review
Rescue Quest Review By Jennifer Allen on November 26th, 2014 Our Rating: :: PATH BASED MATCH-3Universal App - Designed for iPhone and iPad Guide a wizard to safety by matching gems. Rescue Quest might not be an entirely original... | Read more »
You Can Play the Final Chapter of Lone W...
You Can Play the Final Chapter of Lone Wolf: Dawn Over V’taag Right Now Posted by Jessica Fisher on November 26th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

BEVL Releases Dock Tailored for iPhone 6 and...
Seattle based BEVL has released their first product: an iPhone dock that is divergent in build quality, rock-solid function and visual simplicity to complement the iPhone. BEVL is now accepting... Read more
Black Friday: $150 off 13-inch Retina MacBook...
 Best Buy has 13-inch 2.6GHz Retina MacBook Pros on sale for $150 off MSRP on their online store as part of their Black Friday sale. Choose free shipping or free local store pickup (if available).... Read more
Black Friday: $300 off 15-inch Retina MacBook...
 B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for $300 off MSRP as part of their Black Friday sale. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina... Read more
Black Friday: Up to $140 off MacBook Airs, fr...
 B&H Photo has 2014 MacBook Airs on sale for up to $140 off MSRP as part of their Black Friday sale. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $799 $100... Read more
Black Friday: 13-inch 2.5GHz MacBook Pro on s...
 Best Buy has the 13″ 2.5GHz MacBook Pro on sale for $899.99 on their online store as part of their Black Friday sale. Choose free shipping or free instant local store pickup (if available). Their... Read more
2014 1.4GHz Mac mini on sale for $449, save $...
 B&H Photo has the new 1.4GHz Mac mini on sale for $449.99 including free shipping plus NY tax only. Their price is $50 off MSRP, and it’s the lowest price available for this new model. Adorama... Read more
Early Black Friday pricing on 27-inch 5K iMac...
 B&H Photo continues to offer Black Friday sale prices on the 27″ 3.5GHz 5K iMac, in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP... Read more
Early Black Friday sale prices on iPad Air 2,...
 MacMall is discounting iPad Air 2s by up to $75 off MSRP as part of their Black Friday sale. Shipping is free: - 16GB iPad Air WiFi: $459 $40 off - 64GB iPad Air WiFi: $559 $40 off - 128GB iPad Air... Read more
Early Black Friday MacBook Air sale prices, $...
 MacMall has posted early Black Friday MacBook Air sale prices. Save $101 on all models for a limited time: - 11″ 1.4GHz/128GB MacBook Air: $798 - 11″ 1.4GHz/256GB MacBook Air: $998 - 13″ 1.4GHz/... Read more
Why iPhone 6 Tablet/Laptop Cannibalization Is...
247wallst.com blogger Douglas A. McIntyre noted last week that according to research posted on the Applovin blog site the iPhone 6 is outselling the iPhone 6 Plus by a wide margin . Hardly a surprise... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.