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
$524.94
Apple Inc.
+5.93
MSFT
$40.01
Microsoft Corpora
-0.39
GOOG
$536.10
Google Inc.
-20.44

MacTech Search:
Community Search:

Software Updates via MacUpdate

Mac DVDRipper Pro 4.1.7 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
PDFpenPro 6.2 - Advanced PDF toolkit for...
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Create... Read more
PDFpen 6.2 - Edit and annotate PDFs with...
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more
Monolingual 1.5.9 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. It requires a 64-bit capable Intel-based Mac and at least... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Starcraft II: Wings of Liberty 1.1.1.180...
Download the patch by launching the Starcraft II game and downloading it through the Battle.net connection within the app. Starcraft II: Wings of Liberty is a strategy game played in real-time. You... Read more
Sibelius 7.5.0 - Music notation solution...
Sibelius is the world's best-selling music notation software for Mac. It is as intuitive to use as a pen, yet so powerful that it does most things in less than the blink of an eye. The demo includes... Read more
Typinator 5.9 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
MYStuff Pro 2.0.16 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
TurboTax 2013.r17.002 - Manage your 2013...
TurboTax guides you through your tax return step by step, does all the calculations, and checks your return for errors and overlooked deductions. It lets you file your return electronically to get... Read more

Latest Forum Discussions

See All

Livescribe 3 Smartpen Review
Made by: Livescribe Price: $149.99 for Livescribe 3 Hardware/iOS Integration Rating: 4.5 out of 5 stars Usability Rating: 4 out of 5 stars Reuse Value Rating: 4.75 out of 5 stars Build Quality Rating: 4.5 out of 5 stars Overall Rating: 4.44 out of... | Read more »
Unpossible Review
Unpossible Review By Carter Dotson on April 17th, 2014 Our Rating: :: RALPH WIGGUM APPROVESUniversal App - Designed for iPhone and iPad Unpossible is much better than its English!   | Read more »
Hitman GO Review
Hitman GO Review By Carter Dotson on April 17th, 2014 Our Rating: :: GO HITMAN, GO!Universal App - Designed for iPhone and iPad Hitman GO is not the obvious way to do a mobile version of the Hitman series, but it’s an incredibly... | Read more »
Monster High Ghouls and Jewels is a Frea...
Monster High Ghouls and Jewels is a Freaky Fashion-Forward Match-3 Puzzler Posted by Rob Rich on April 17th, 2014 [ permalink ] | Read more »
Dinosaur Train A to Z Review
Dinosaur Train A to Z Review By Amy Solomon on April 17th, 2014 Our Rating: :: DINO DETAILSUniversal App - Designed for iPhone and iPad Dinosaur Train A to Z is an educational app about dinosaurs that includes In-App Purchases... | Read more »
Easter Comes to Junk Jack X – Bringing N...
Easter Comes to Junk Jack X – Bringing New Crafts, Chemistry, and More Posted by Rob Rich on April 17th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Call of Cookie Review
Call of Cookie Review By Jordan Minor on April 17th, 2014 Our Rating: :: COOKIE CRUMBLESUniversal App - Designed for iPhone and iPad Call of Cookie proves that plants aren’t the only fighting foods out there.   | Read more »
Corel Launches Video Editing App Pinnacl...
Corel Launches Video Editing App Pinnacle Studio for iPhone, Updates iPad Version for iOS 7 Posted by Tre Lawrence on April 17th, 2014 [ | Read more »
Bad Vamp Review
Bad Vamp Review By Jennifer Allen on April 17th, 2014 Our Rating: :: BASIC VAMPIRIC ADVENTURESUniversal App - Designed for iPhone and iPad Run or destroy the vampires in this simple, single-screen game that lacks real bite.   | Read more »
The Shadow Sun gets a New Update, Goes o...
The Shadow Sun gets a New Update, Goes on Sale for the First Time Since its Release Posted by Tre Lawrence on April 17th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

Apple restocks refurbished Mac minis starting...
The Apple Store has restocked Apple Certified Refurbished Mac minis for up to $150 off the cost of new models. Apple’s one-year warranty is included with each mini, and shipping is free: - 2.5GHz Mac... Read more
Hyundai Brings Apple CarPlay To The 2015 Sona...
Hyundai Motor America has announced it will bring Apple CarPlay functionality to the 2015 Sonata. CarPlay is pitched as a smarter, safer and easier way to use iPhone in the car and gives iPhone users... Read more
Updated iPads Coming Sooner Than We Had Thoug...
MacRumors, cites KGI securities analyst Ming Chi Kuo, well-respected as an Apple product prognisticator, saying that Apple will introduce an upgraded iPad Air and iPad mini in 2014/Q3, meaning the... Read more
Toshiba Unveils New High And Low End Laptop M...
Toshiba has announced new laptop models covering both the high-end and low-end of the notebook computer spectrum. Toshiba 4K Ultra HD Laptop Toshiba’s new Satellite P55t features one of the world’s... Read more
Save up to $270 with Apple refurbished 13-inc...
The Apple Store has Apple Certified Refurbished October 2013 13″ Retina MacBook Pros available starting at $1099, with models up to $270 off MSRP. Apple’s one-year warranty is standard, and shipping... Read more
Apple now offering refurbished iPad mini with...
The Apple Store has Certified Refurbished 2nd generation iPad minis with Retina Displays now available starting at $339. Apple’s one-year warranty is included with each model, and shipping is free.... Read more
Microsoft Blinks – Drops Microsoft Office 365...
Microsoft has dropped the annual subscription fee for Microsoft Office 365 Personal – which is needed in order to create and edit documents in Microsoft Office for iPad. However, Apple’s iOS and OS X... Read more
New AVG Vault Apps for iOS and Android Help K...
AVG Technologies N.V. an online security company for 177 million active users, has announced the launch of its latest mobile application, AVG Vault. The free app introduces an innovative user... Read more
Free Local Carrot iPhone App Helps Find Fresh...
I love fresh vegetables. I’m not a vegan, although I was for several years in the 1980s, but fresh vegetables and other whole foods are still my dietary mainstays as a matter of taste rather than... Read more
CarSO Pro – Car Service and Finance Manager/O...
Lviv, Ukraine-based BM-Studios’ CarSO Pro is a tool to manage operations concerning your car. Never forget to change the oil or prolong the insurance for your car. Remember when you’ve done the car... 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
*Apple* Retail - Manager - Holyoke - Apple I...
Job Summary Keeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you’re a master of them all. In the store’s fast-paced, Read more
*Apple* Retail - Manager - Apple (United Sta...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic 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* Retail - Market Leader - Cincinnati...
…challenges of developing individuals, building teams, and affecting growth across Apple Stores. You demonstrate successful leadership ability - focusing on excellence Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.