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
}

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

The beginner's guide to Warbits
Warbits is a turn-based strategy that's clearly inspired by Nintendo's Advance Wars series. Since turn-based strategy games can be kind of tricky to dive into, see below for a few tips to help you in the beginning. Positioning is crucial [Read... | Read more »
How to upgrade your character in Spellsp...
So you’ve mastered the basics of Spellspire. By which I mean you’ve realised it’s all about spelling things in a spire. What next? Well you’re going to need to figure out how to toughen up your character. It’s all well and good being able to spell... | Read more »
5 slither.io mash-ups we'd love to...
If there's one thing that slither.io has proved, it's that the addictive gameplay of Agar.io can be transplanted onto basically anything and it will still be good fun. It wouldn't be surprising if we saw other developers jumping on the bandwagon,... | Read more »
How to navigate the terrain in Sky Charm...
Sky Charms is a whimsical match-'em up adventure that uses creative level design to really ramp up the difficulty. [Read more] | Read more »
Victorious Knight (Games)
Victorious Knight 1.3 Device: iOS Universal Category: Games Price: $1.99, Version: 1.3 (iTunes) Description: New challenges awaits you! Experience fresh RPG experience with a unique combat mechanic, packed with high quality 3D... | Read more »
Agent Gumball - Roguelike Spy Game (Gam...
Agent Gumball - Roguelike Spy Game 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Someone’s been spying on Gumball. What the what?! Two can play at that game! GO UNDERCOVERSneak past enemy... | Read more »
Runaway Toad (Games)
Runaway Toad 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: It ain’t easy bein’ green! Tap, hold, and swipe to help Toad hop to safety in this gorgeous new action game from the creators of... | Read more »
PsyCard (Games)
PsyCard 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: From the makers och Card City Nights, Progress To 100 and Ittle Dew PSYCARD is a minesweeper-like game set in a cozy cyberpunk... | Read more »
Sago Mini Robot Party (Education)
Sago Mini Robot Party 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: -- Children's Technology Review Editor's Choice -- | Read more »
Egz – The Origin of the Universe (Games...
Egz – The Origin of the Universe 1.0.2 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.2 (iTunes) Description: ►►► Special offer until 2nd may : get the game at 2.99€ instead of 3.99€ ! ◄◄◄ Egz is a mesmerizing mix... | Read more »

Price Scanner via MacPrices.net

Mac minis on sale for up to $100 off MSRP
B&H Photo has Mac minis on sale for up to $100 off MSRP including free shipping plus NY sales tax only: - 1.4GHz Mac mini: $449 $50 off MSRP - 2.6GHz Mac mini: $649 $50 off MSRP - 2.8GHz Mac mini... Read more
13-inch Retina MacBook Pros on sale for up to...
B&H Photo has 13″ Retina MacBook Pros on sale for $130-$200 off MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1169 $130 off MSRP - 13″ 2.7GHz/... Read more
Apple price trackers, updated continuously
Scan our Apple Price Trackers for the latest information on sales, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. We update the trackers continuously: - 15″... Read more
SanDisk Half-Terabyte SSD Optimized for Every...
SanDisk Corporation has announced the SanDisk Z410 SSD, a cost-competitive, half-terabyte solid state drive (SSD) that enables manufacturers to design for a broad range of desktop PCs and laptops.... Read more
Churchill Downs Racetrack Selects VenueNext t...
Churchill Downs Racetrack has announced an agreement with VenueNext to implement its technology platform for the start of Churchill Downs 2016 Spring Meet, which includes the 142nd running of the... Read more
Record 700 Million Pounds of CE Recycled in 2...
The Consumer Technology Association (CTA) reports that a record-setting 700 million pounds of consumer electronics (CE) have been recycled under the eCycling Leadership Initiative (ELI). According to... Read more
Price drops on clearance 12-inch Retina MacBo...
B&H Photo has dropped prices on leftover 2015 12″ Retina MacBooks with models now available starting at $999. Shipping is free, and B&H charges NY tax only: - 12″ 1.1GHz Gray Retina MacBook... Read more
15-inch Retina MacBook Pros available for $20...
B&H Photo has 15″ Retina MacBook Pros on sale for up to $210 off MSRP. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799 $200 off MSRP - 15″ 2.5GHz Retina... Read more
Target offers Apple Watch Sport for $50 off M...
Target has Apple Watch Sports on sale for $50 off MSRP for a limited time. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary... Read more
Apple restocks Certified Refurbished Mac mini...
Apple has restocked Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Restaurant Manager (Neighborhood Captain) - A...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
Restaurant Manager (Neighborhood Captain) - A...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
Simply Mac *Apple* Specialist- Service Repa...
Simply Mac is the largest premier retailer of Apple products in the nation. In order to support our growing customer base, we are currently looking for a driven Read more
*Apple* Retail - Multiple Positions - Apple,...
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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.