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

ExpanDrive 5.4.4 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Dash 3.4.3 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Civilization VI 1.0.2 - Next iteration o...
Sid Meier’s Civilization VI is the next entry in the popular Civilization franchise. Originally created by legendary game designer Sid Meier, Civilization is a strategy game in which you attempt to... Read more
TurboTax 2016 - Manage your 2016 U.S. ta...
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
Microsoft Office 2016 15.30 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
FotoMagico 5.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Acorn 5.6.1 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
iMazing 2.1.8 - Complete iOS device mana...
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
Logic Pro X 10.3 - Music creation and au...
Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get creative... Read more
Microsoft Remote Desktop 8.0.37 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more

Red's Kingdom (Games)
Red's Kingdom 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Mad King Mac has kidnapped your father and stolen your golden nut! Solve puzzles and battle goons as you explore and battle your... | Read more »
Turbo League Guide: How to tame the cont...
| Read more »
Fire Emblem: Heroes coming to Google Pla...
Nintendo gave us our first look at Fire Emblem: Heroes, the upcoming mobile Fire Emblem game the company hinted at last year. Revealed at the Fire Emblem Direct event held today, the game will condense the series' tactical RPG combat into bite-... | Read more »
ReSlice (Music)
ReSlice 1.0 Device: iOS Universal Category: Music Price: $9.99, Version: 1.0 (iTunes) Description: Audio Slice Machine Slice your audio samples with ReSlice and create flexible musical atoms which can be triggered by MIDI notes or... | Read more »
Stickman Surfer rides in with the tide t...
Stickson is back and this time he's taken up yet another extreme sport - surfing. Stickman Surfer is out this Thursday on both iOS and Android, so if you've been following the other Stickman adventures, you might be interested in picking this one... | Read more »
Z-Exemplar (Games)
Z-Exemplar 1.4 Device: iOS Universal Category: Games Price: $3.99, Version: 1.4 (iTunes) Description: | Read more »
5 dastardly difficult roguelikes like th...
Edmund McMillen's popular roguelike creation The Binding of Isaac: Rebirth has finally crawled onto mobile devices. It's a grotesque dual-stick shooter that tosses you into an endless, procedurally generated basement as you, the pitiable Isaac,... | Read more »
Last week on PocketGamer
Welcome to a weekly feature looking back on the past seven days of coverage on our sister website, PocketGamer. It’s taken a while for 2017 to really get going, at least when it comes to the world of portable gaming. Thank goodness, then, for... | Read more »
ROME: Total War - Barbarian Invasion set...
To the delight of mobile strategy fans, Feral Interactive released ROME: Total War just a few months ago. Now the game's expansion, Barbarian Invasion is marching onto iPads as a standalone release. [Read more] | Read more »
Yuri (Games)
Yuri 1.0 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: It's night. Yuri opens his eyes. He wakes up in a strange forest.The small, courageous explorer rides on his bed on casters in this... | Read more »

Price Scanner via MacPrices.net

Laptop Market – Flight To Quality? – The ‘Boo...
Preliminary quarterly PC shipments data released by Gartner Inc. last week reveal an interesting disparity between sales performance of major name PC vendors as opposed to that of less well-known... Read more
IBM and Bell Transform Canadian Enterprise Mo...
IBM and Bell Canada have announced they are joining forces to offer IBM MobileFirst for iOS market-ready enterprise applications for iPad, iPhone or Apple Watch. Bell, Canada’s largest communications... Read more
Otter Products is Closing… For a Day of Givin...
On Thursday, Feb. 9, Otter Products is closing doors to open hearts. In partnership with the OtterCares Foundation, the company is pausing operations for a day so all employees can volunteer with... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for...
Amazon has 2015 15″ 2.2GHz Retina MacBook Pros (MJLQ2LL/A) available for $1799.99 including free shipping. Apple charges $1999 for this model, so Amazon’s price is represents a $200 savings. Read more
Back in stock: Apple refurbished 13-inch Reti...
Apple has Certified Refurbished 2015 13″ Retina MacBook Pros available for up to $360 off original MSRP, starting at $1099. An Apple one-year warranty is included with each model, and shipping is... Read more
CalcTape for macOS 1.2 Adding Machine App for...
schoettler Software has announced CalcTape 1.2, an update to their desktop calculator for macOS. When it comes to adding long columns of numbers, doing complex calculations or playing around with... Read more
New MacBooks And MacBook Pros WIth Kaby Lake...
Digitimes’ Joseph Tsai cites a Chinese-language Economic Daily News (EDN) report that unnamed market watchers are predicting Apple MacBook shipments to grow 10 percent in 2017, and projecting 15... Read more
New 2016 13-inch MacBook Pros on sale for up...
B&H Photo has the new 2016 13″ MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.9GHz/512GB Touch Bar MacBook Pro... Read more
New 15-inch Touch Bar MacBook Pros in stock a...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
Opera Announces Neon Concept Browser For Mac
Opera is inviting users to get a glimpse of what Opera for computers could become with its Opera Neon browser concept. Each Opera Neon feature is described as “an alternate reality” for the Opera... Read more

Jobs Board

*Apple* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Los Angeles, CA Introduction: We have immediate job openings for several Desktop Support Technicians with one of our Read more
*Apple* Retail - Multiple Positions - Apple,...
SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (Multi-L...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*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
*Apple* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Stamford, CT We have immediate job openings for several Desktop Support Technicians with one of our most well-known Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.