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
$97.67
Apple Inc.
+0.64
MSFT
$44.50
Microsoft Corpora
+0.10
GOOG
$589.02
Google Inc.
-4.33

MacTech Search:
Community Search:

Software Updates via MacUpdate

TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more
Autopano Giga 3.6 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more
Airfoil 4.8.7 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
Microsoft Remote Desktop 8.0.8 - Connect...
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
xACT 2.30 - Audio compression toolkit. (...
xACT stands for X Aaudio Compression Toolkit, an application that encodes and decodes FLAC, SHN, Monkey’s Audio, TTA, Wavpack, and Apple Lossless files. It also can encode these formats to MP3, AAC... Read more
Firefox 31.0 - Fast, safe Web browser. (...
Firefox for Mac offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals... Read more
Little Snitch 3.3.3 - Alerts you to outg...
Little Snitch gives you control over your private outgoing data. Track background activityAs soon as your computer connects to the Internet, applications often have permission to send any... Read more
Thunderbird 31.0 - Email client from Moz...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more

Latest Forum Discussions

See All

Reddme for iPhone - The Reddit Client (...
Reddme for iPhone - The Reddit Client 1.0 Device: iOS iPhone Category: News Price: $.99, Version: 1.0 (iTunes) Description: Reddme for iPhone is an iOS 7-optimized Reddit client that offers a refreshing new way to experience Reddit... | Read more »
Jacob Jones and the Bigfoot Mystery : Ep...
Jacob Jones and the Bigfoot Mystery : Episode 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Jacob Jones is back in Episode 2 of one of Apples 'Best of 2013' games and an App Store... | Read more »
New Trailer For Outcast Odyssey, A New K...
New Trailer For Outcast Odyssey, A New Kind of Card Battler Posted by Jennifer Allen on July 25th, 2014 [ permalink ] Out this Fall is a new kind of card battle game: Outcast Odyssey. | Read more »
Garfield: Survival of the Fattest Coming...
Garfield: Survival of the Fattest Coming to iOS this Fall Posted by Jennifer Allen on July 25th, 2014 [ permalink ] Who loves lasagna? Me. Also everyone’s favorite grumpy fat cat, Garfield. | Read more »
Happy Flock Review
Happy Flock Review By Andrew Fisher on July 25th, 2014 Our Rating: :: HERD IT ALL BEFOREUniversal App - Designed for iPhone and iPad Underneath the gloss of Happy Flock’s visuals is a game of very little substance. It’s cute, but... | Read more »
Square Register Updates Adds Offline Pay...
Square Register Updates Adds Offline Payments Posted by Ellis Spice on July 25th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Looking For Group – Hearthstone’s Curse...
For the first time since its release (which has thankfully been a much shorter window for iPad players than their PC counterparts), Blizzard’s wildly successful Hearthstone: Heroes of Warcraft CCG is sporting some brand new content: the single... | Read more »
Poptile Review
Poptile Review By Jennifer Allen on July 25th, 2014 Our Rating: :: SIMPLY FUNUniversal App - Designed for iPhone and iPad Simple yet a little bit glorious, Poptile is a satisfying entertaining puzzle game with oodles of the ‘one... | Read more »
Modern Combat 5: Blackout Review
Modern Combat 5: Blackout Review By Brittany Vincent on July 25th, 2014 Our Rating: :: LESS QQ, MORE PEW PEWUniversal App - Designed for iPhone and iPad The fifth entry into the blockbuster Modern Combat series is what mobile... | Read more »
Watch and Share Mobile Gameplay Videos W...
Watch and Share Mobile Gameplay Videos With Kamcord Posted by Jennifer Allen on July 25th, 2014 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »

Price Scanner via MacPrices.net

Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more
iMacs on sale for $150 off MSRP, $250 off for...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more
Save on 5th generation refurbished iPod touch...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Many, but not all... Read more
What Should Apple’s Next MacBook Priority Be;...
Stabley Times’ Phil Moore says that after expanding its iMac lineup with a new low end model, Apple’s next Mac hardware decision will be how it wants to approach expanding its MacBook lineup as well... Read more
ArtRage For iPhone Painting App Free During C...
ArtRage for iPhone is currently being offered for free (regularly $1.99) during Comic-Con San Diego #SDCC, July 24-27, in celebration of the upcoming ArtRage 4.5 and other 64-bit versions of the... Read more
With The Apple/IBM Alliance, Is The iPad Now...
Almost since the iPad was rolled out in 2010, and especially after Apple made a 128 GB storage configuration available in 2012, there’s been debate over whether the iPad is a serious tool for... Read more

Jobs Board

WW Sales Program Manager, *Apple* Online St...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring 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
*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.