TweetFollow Us on Twitter

May 96 Challenge
Volume Number:12
Issue Number:5
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Bob Boonstra, Westford, Massachusetts

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

Edge Detector

This month’s Challenge is to write a small image-processing application that scans a color image and identifies the boundaries of possible objects in that image. Applications for such a program might include image enhancement, special effects, or pattern recognition, although those applications would use a more sophisticated approach for detecting edges than we will be implementing for this Challenge.

The prototype for the code you should write is:

typedef enum {
 redOnly=1, greenOnly, redAndGreen, blueOnly,
 redAndBlue, greenAndBlue, redGreenAndBlue
} EdgeType;

void EdgeDetect(
 PixMapHandle pMapH, /* find edges in this PixMap */
 BitMap *bMap,   /* store edges in this BitMap */
 unsigned short threshold,/* color separations >= dist create an edge */
 EdgeType eType  /* which color components to look at */
);

Each pixel in the PixMap should be compared to the eight (or fewer) adjacent pixels differing in position by up to one row or column. If the pixel color is sufficiently different (as defined below) from any of the adjacent pixels, then the bit in the BitMap corresponding to that pixel should be set to 1. Otherwise, the BitMap bit should be set to 0. Obviously, pixels located in the first and last row and column will have fewer than eight adjacent pixels.

Whether two pixels differ by enough to constitute an edge is determined by comparing their rgb values. The distance between two pixels is the root-mean-square difference between the color components of their rgb values, considering only those components specified in the input EdgeType. For example, if the EdgeType is greenOnly, then the distance between two pixels is the absolute value of the difference in the green components of their colors. If the EdgeType is redGreenAndBlue, then the distance is the square root of the sum of the squares of the differences of the red components, the green components, and the blue components.

As a specific example, suppose we have two pixels with (red, green, blue) values of (0x1000, 0x2000, 0x4000) and (0x2000, 0x5000, 0xB000). The distance between these two pixels is:

 redOnly: 0x1000
 redAndGreen:    0x3298=sqrt(0x01000000+0x09000000)
 redGreenAndBlue:0x7AE5=sqrt(0x01000000+0x09000000+0x31000000)

Two pixels define an edge if their distance is greater than or equal to the threshold parameter. The threshold parameter is deliberately declared to be an unsigned short, even though pixels can differ by a greater amount. Since the definition of distance is symmetric, the bits corresponding to both edge pixels would be set in the BitMap.

The BitMap will be allocated and initialized for you by the calling routine. The storage pointed to by the BitMap baseAddr will also be allocated and initialized to zero. The bounds rectangles will be the same for the BitMap and the PixMap. Your code needs to deal with pixelSize values of 8, 16, or 32, with each case being equally weighted in the scoring. For PixMaps with indexed pixels, you will obviously need to look at the color table to find the rgb value corresponding to a given index. In the 16-bit case, you should follow the rules for converting a 5-bit color component into an 8-bit RGBColor component value (i.e., replicating the 3 most significant bits and appending them to constitute the least significant bits of the 8-bit component).

This will be a native PowerPC Challenge, scored using the latest Metrowerks C compiler. (No C++ or Pascal this month.)

Entries Due Ten Days Earlier

Although two issues may seem like a long time to wait for the results of the Challenge, it has always been a challenge (no pun intended) to complete the scoring of results in time for publication two issues later. We have been searching for a way to allow a little more time for evaluating the entries and writing the column without introducing any additional delay between publication of the problem and publication of the solution. The Challenge mailing list has allowed us to deliver the Challenge to readers on a predictable schedule wherever they live, regardless of variations in mailing dates. We are going to use the mailing list to advance the due date for Challenge solutions, without reducing the amount of time available for solving the Challenge. Starting with this month’s contest, Challenge entries will be due earlier, on the 1st of the month printed on the front cover. We will mail the problem to the mailing list on the 12th of the preceding month, also about ten days earlier than before.

If you are not already a member of the Challenge mailing list, you can join the ~300 subscribers from 25 countries already on the list by sending email to macjordomo@listmail.xplain.com with the line “sub challenge-A YourName” in the body.

Two Months Ago Winner

The response to the Words the Reverse Challenge was overwhelming. I don’t know if it was due to allowing C++ and Pascal entries, or to the relative simplicity of the problem, but I received a record 45 entries to this Challenge. The Challenge was to write code that would reverse the order of words in a block of input text while preserving intervening white space and special characters, and adjusting capitalization of the reversed words to match that of corresponding input words. It is appropriate that the first Challenge admitting Pascal solutions was won by a well-known proponent of Pascal (see MacTech Magazine 12.4 [April 1996] 70, and p.20 of this issue). Congratulations to Peter Lewis (Perth, Australia), author of Anarchie, NetPresenz, ObiWan, and other shareware products, for submitting the fastest entry to the Words The Reverse Challenge.

The test cases included a number of short, untimed strings designed to verify correctness. To my surprise, more than one-third of the entries failed these tests (or crashed outright). People had problems with strings that contained a single word, with strings that began with punctuation, with words of a single letter, and with the middle word in strings that contained an odd number of words. Remember, correctness is the first requirement for your solution.

For the timing tests, I ran a set of cases averaging around 40,000 words per case, totaling upwards of 500,000 words and 3 million characters for all cases. I eliminated from the input any “words” that started with a digit, because the problem statement was silent on how to deal with capitalization in that case. A number of people, including the winner, chose to treat words starting with digits as capitalization-neutral, so that the word being exchanged with the digit-word retained its original capitalization. This was a very reasonable approach (and I wish I had included it in the problem statement), but since the problem was silent, the fairest thing to do was to eliminate this condition from the test data.

The experiment allowing multiple languages and compilers went reasonably well. Most people, as requested, either provided a project/make file to link their solution with C code, or specifically indicated which compiler they wanted me to use. For those C entries that did not indicate a preference, I used the Metrowerks C compiler. A few people submitted solutions for environments that either did not generate native PowerPC code (e.g., non-SPM THINK C) or did not link with C code (e.g., THINK Pascal). For those entries, I mapped them to the closest possible environment (SPM C and Metrowerks Pascal, in these two cases).

Here are the times, compiler selection, code size, and data size for the correct solutions. Numbers in parentheses are the cumulative point total for all previous Challenges, not including this one.

Nametimecompilercodedata
Peter N Lewis (10)525MW Pascal89642
Ludovic Nicolle (4)602MW C12408
Kevin M. Cutts (50)607MW C65620
Gary Beith (20)626MW C20888
Ernst Munter (132)630MW C680560
Robert Marsa650MW C55259
Eric Lengyel (40)669MW C368140
John Nevard (17)670MW C56420
Wolfgang Thaller (4)681MW C61620
Randy Boring687MW C10432024
Bill Karsh (80)695MW C11288
Kirill Medvinsky703MW C++54012
Mark Bassam Salem705MW C++59232
Tom Saxton (10)710MW C360422
Karl Anderson716MW C604536
Lars Farm762MW C++90470
David McLeod842MW C5001315
Erik Sea884MW C760532
Robert Leslie/Geoff Hulten938MW C436268
Björn Davidsson (4)1122MW C++102020
Tom Stone1180SPM C75216
Gustav Larsson (87)1270MW C784536
Ryan Gronlie1294MW C44420
Michael White1397MW C1924130
Rishi Khan1447MW C9608
Richard Fattic1576MW C9088
Stefan C. Sinclair1668SPM MrC124840
David Newport2420SPM C78416
Ken Slezak (10)2468SPM C80816

To help understand why the single correct Pascal entry was faster than all of the C entries, I hand-translated the winning Pascal code into C, compiled it with several C compilers, and compared the results. I turned on all speed optimizations in each case, and optimized for the 604 processor when the compiler supported that option. Since conventional wisdom is that C is more efficient than Pascal, I expected to find that the winning algorithm would be faster in C than it was in Pascal. In fact, the results for two of the C compilers were essentially the same as the Pascal results, and one was measurably worse (for reasons that I did not have time to investigate). Here are the results of my test:

Environment / Languageexecution timecode size
Metrowerks / Pascal525896
Metrowerks / C533868
SPM / Symantec C536712
SPM / MrC6111992

Top 20 Contestants of All Time

Here are the Top Contestants for the Programmer’s Challenges to date, including everyone who has accumulated more than 20 points. The numbers below include points awarded for this month’s entrants.

RankNamePoints
1.[Name deleted]176
2.Munter, Ernst134
3.Gregg, Xan92
4.Larsson, Gustav87
5.Karsh, Bill80
6.Stenger, Allen65
7.Cutts, Kevin57
8.Riha, Stepan51
9.Goebel, James49
10.Nepsund, Ronald47
11.Mallett, Jeff44
12.Kasparian, Raffi42
13.Vineyard, Jeremy42
14.Lengyel, Eric40
15.Darrah, Dave31
16.Brown, Jorg30
17.Lewis, Peter30
18.Landry, Larry29
19.Beith, Gary24
20.Elwertowski, Tom24
21.Lee, Johnny22
22.Noll, Robert22

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) 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:

points to win table:

1st place20 points5th place2 points
2nd place10 pointsfinding bug2 points
3rd place7 pointssuggesting Challenge2 points
4th place4 points

Peter’s solution is relatively straightforward, and he hints in the preamble that he might have done better if he had spent more time on it. One tip that you might glean from Peter’s code is the way he allocates dynamic memory. First, he deals with small problems with memory allocated on the stack. Second, he uses NewHandle rather than NewPtr to allocate dynamic memory. NewHandle is faster than NewPtr, because NewPtr may move relocatable blocks around before doing the allocation to avoid fragmenting the heap. Peter also locks the handle before using it, which is always safe, but is not necessary unless your code does something that moves memory. Whether locking is necessary in this case depends on whether you believe the documentation that says BlockMove doesn’t move memory. Here is Peter’s winning solution:

Challenge.p

Peter N Lewis, peter@stairways.com.au

unit Challenge;

interface

 uses
 Types;
 
 type
 CharsArray = packed array[0..0] of byte;
 CharsArrayPtr = ^CharsArray;
 
 procedure ReverseTheWords( 
    text: CharsArrayPtr; 
    numCharsIn: longint );

implementation

 uses
 Memory;

{
    This is not really optimal, I felt compelled to send in a Pascal solution since I was
    one of the people who complained about the language bias.  I didn’t have time to 
    do this challenge justice.
    
    Method:
    *     Allocate a block of memory equal in size to numCharsIn (if numCharsIn < 2048, 
    we short circuit this to use a block of memory on the stack).
    *     Initialize a 0..255 array to determine whether a character is  an alphanum (I 
    could just use the ANSI ctype.p file, but without a macro call, there is a pretty 
    big hit).
    *     reverse the words from the source to our new buffer.  We move in from both
    ends,  copying non-alphanums, and then swapping words and fixing the case.
    *     BlockMoveData the buffer back to the source buffer.
    *     Release the memory if we allocated any.
}

 procedure ReverseTheWords( 
      text: CharsArrayPtr; 
      numCharsIn: longint );
 const
 stack_space_size = 2048;
 var
 space: packed array[0..stack_space_size] of byte;
 buffer: CharsArrayPtr;
 memory: Handle;
 leftin, leftout, rightin, rightout, leftedge, 
 rightedge: longint;
 i: longint;
 leftchar, rightchar: integer;
 alphanum_set:array[0..255] of Boolean;
 begin
    { allocate memory if needed }
 if numCharsIn < stack_space_size then begin
 memory := nil;
 buffer := @space;
 end else begin
 memory := NewHandle( numCharsIn );
 if memory = nil then begin
 DebugStr( 'Memory allocation failed!' );
 exit( ReverseTheWords );
 end;
 HLock(memory);
 buffer := CharsArrayPtr( memory^ );
 end;
 
    { init - I wish I could do this at compile time - Turbo Pascal can }
 for i := 0 to 255 do alphanum_set[i] := false;
 for i := 48 to 57 do alphanum_set[i] := true; { 0..9 }
 for i := 65 to 90 do alphanum_set[i] := true; { A..Z }
 for i := 97 to 122 do alphanum_set[i] := true; { a..z }

    { reverse }
 leftin := 0;
 leftout := leftin;
 rightin := numCharsIn - 1;
 rightout := rightin;
 while leftin <= rightin do begin
 while not alphanum_set[text^[leftin]] & (leftin <= rightin) 
                                                do begin
 buffer^[leftout] := text^[leftin];
 Inc(leftout);
 Inc(leftin);
 end;
 while not alphanum_set[text^[rightin]] & (leftin < rightin) 
                                                do begin
 buffer^[rightout] := text^[rightin];
 Dec(rightout);
 Dec(rightin);
 end;
 leftedge := leftin;
 rightedge := rightin;
 while alphanum_set[text^[leftin]] & (leftin <= rightin) 
                                                do begin
 Inc(leftin);
 end;
 if leftin > rightin then begin { central word, just copy, ignore case }
 for i := leftedge to leftin - 1 do begin
 buffer^[leftout] := text^[i];
 Inc(leftout);
 end;
 end else begin
 while alphanum_set[text^[rightin]] do begin 
    { there is a sentinel now, we dont need to check leftin < rightin }
 Dec(rightin);
 end;
 leftchar := text^[leftedge];
 rightchar := text^[rightin+1];
 if ( leftchar > 57 ) & ( rightchar > 57 ) then begin 
    { both letters }
 if leftchar > 90 then begin
 if rightchar <= 90 then begin
 rightchar := rightchar + $20;
 leftchar := leftchar - $20;
 end;
 end else begin
 if rightchar > 90 then begin
 rightchar := rightchar - $20;
 leftchar := leftchar + $20;
 end;
 end;
 end;
 buffer^[leftout] := rightchar;
 Inc(leftout);
 for i := rightin+2 to rightedge do begin
 buffer^[leftout] := text^[i];
 Inc(leftout);
 end;
 for i := leftin-1 downto leftedge+1 do begin
 buffer^[rightout] := text^[i];
 Dec(rightout);
 end;
 buffer^[rightout] := leftchar;
 Dec(rightout);
 end;
 end;
 
    { copy buffer }
 BlockMoveData( buffer, text, numCharsIn );
 
    { free memory if required }
 if memory <> nil then begin
 DisposeHandle( memory );
 end;
 end;
 
end.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

SpamSieve 2.9.38 - Robust spam filter fo...
SpamSieve is a robust spam filter for major email clients that uses powerful Bayesian spam filtering. SpamSieve understands what your spam looks like in order to block it all, but also learns what... Read more
TeamViewer 15.0.8397 - Establish remote...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for non... Read more
SteerMouse 5.4.3 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Toast Titanium 18.2.1 - The ultimate med...
Roxio Toast Titanium, the leading DVD burner for Mac, makes burning even better, adding Roxio Secure Burn to protect your files on disc and USB in Mac- or Windows-compatible formats. Get more style... Read more
HoudahSpot 5.0.11 - Advanced file-search...
HoudahSpot is a versatile desktop search tool. Use HoudahSpot to locate hard-to-find files and keep frequently used files within reach. HoudahSpot will immediately feel familiar. It works just the... Read more
ClipGrab 3.8.6 - Download videos from Yo...
ClipGrab is a free downloader and converter for YouTube, Vimeo, Facebook and many other online video sites. It converts downloaded videos to MPEG4, MP3 or other formats in just one easy step Version... Read more
ExpanDrive 7.4.0 - 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
Adobe Dreamweaver CC 2020 20.0 - Build w...
Dreamweaver CC 2020 is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2020 allows you to... Read more
Eye Candy 7.2.3.85 - 30 professional Pho...
Eye Candy renders realistic effects that are difficult or impossible to achieve in Photoshop alone, such as Fire, Chrome, and the new Lightning. Effects like Animal Fur, Smoke, and Reptile Skin are... Read more
Sparkle Pro 2.8.5 - Visual website creat...
Sparkle Pro will change your mind if you thought building websites wasn't for you. Sparkle is the intuitive site builder that lets you create sites for your online portfolio, team or band pages, or... Read more

Latest Forum Discussions

See All

Pre-register for Hello Kitty AR: Kawaii...
Hello Kitty — the cute cat that launched a multi-billion-pound franchise — has been brought to life… sort of. Sanrio has teamed up with the Bublar Group to create a new mobile game that uses AR tech to turn the real world into Hello Kitty’s... | Read more »
Gorgeous and tranquil puzzler Spring Fal...
One-man indie studio SPARSE//GameDev has now launched its tranquil puzzler, Spring Falls. It's described as "a peaceful puzzle game about water, erosion, and watching things grow". [Read more] | Read more »
Black Desert Mobile gets an official rel...
Pearl Abyss has just announced that its highly-anticipated MMO, Black Desert Mobile, will launch globally for iOS and Android on December 11th. [Read more] | Read more »
Another Eden receives new a episode, cha...
Another Eden, WFS' popular RPG, has received another update that brings new story content to the game alongside a few new heroes to discover. [Read more] | Read more »
Overdox guide - Tips and tricks for begi...
Overdox is a clever battle royale that changes things up by adding MOBA mechanics and melee combat to the mix. This new hybrid game can be quite a bit to take in at first, so we’ve put together a list of tips to help you get a leg up on the... | Read more »
Roterra Extreme - Great Escape is a pers...
Roterra Extreme – Great Escape has been described by developers Dig-It Games as a mini-sequel to their acclaimed title Roterra: Flip the Fairytale. It continues that game's tradition of messing with which way is up, tasking you with solving... | Read more »
Hearthstone: Battlegrounds open beta lau...
Remember earlier this year when auto battlers were the latest hotness? We had Auto Chess, DOTA Underlords, Chess Rush, and more all gunning for our attention. They all had their own reasons to play, but, at least from where I'm standing, most... | Read more »
The House of Da Vinci 2 gets a new gamep...
The House of Da Vinci launched all the way back in 2017. Now, developer Blue Brain Games is gearing up to deliver a second dose of The Room-inspired puzzling. Some fresh details have now emerged, alongside the game's first official trailer. [Read... | Read more »
Shoot 'em up action awaits in Battl...
BattleBrew Productions has just introduced another entry into its award winning, barrelpunk inspired, BattleSky Brigade series. Whilst its previous title BattleSky Brigade TapTap provided fans with idle town building gameplay, this time the... | Read more »
Arcade classic R-Type Dimensions EX blas...
If you're a long time fan of shmups and have been looking for something to play lately, Tozai Games may have just released an ideal game for you on iOS. R-Type Dimensions EX brings the first R-Type and its sequel to iOS devices. [Read more] | Read more »

Price Scanner via MacPrices.net

13″ 2.4GHz MacBook Pros available for up to $...
Apple has a full line of Certified Refurbished 2019 13″ 2.4GHz 4-Core Touch Bar MacBook Pros available starting at $1529 and up to $300 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
New at T-Mobile: Switch to T-Mobile, and get...
T-Mobile is offering a free 64GB iPhone 8 for new customers who switch to T-Mobile and open a new line of service. Eligible trade-in required, and discount applied over a 24 month period. The fine... Read more
Xfinity Mobile’s Black Friday Apple savings:...
Take $250 off the purchase of any iPhone at Xfinity Mobile with a new line activation, and transfer of phone number to Xfinity Mobile, through December 8, 2019. This includes Apple’s new iPhone 11... Read more
2019 13″ 1.4GHz MacBook Pros available starti...
Apple has a full line of Certified Refurbished 2019 13″ 1.4GHz 4-Core Touch Bar MacBook Pros available starting at $1099 and up to $230 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
Save up to $350 on a 21″ or 27″ iMac with the...
Apple has Certified Refurbished 2019 21″ & 27″ iMacs available starting at $929 and up to $350 off the cost of new models. Apple’s one-year warranty is standard, shipping is free, and each iMac... Read more
Early Holiday 2019 Sale: B&H again offers...
B&H Photo has 10.2″ iPads on sale again for $30 off Apple’s MSRP, starting at $299, as part of their early Holiday 2019 sale. Overnight shipping is free to many addresses in the US: – 10.2″ 32GB... Read more
Apple iMacs on sale today at B&H Photo fo...
B&H Photo has new 2019 21″ and 27″ 5K iMacs on stock today and on sale for up to $150 off Apple’s MSRP. Overnight shipping is free to many locations in the US. These are the same iMacs sold by... Read more
2018 4 and 6-Core Mac minis on sale today for...
Apple resellers are offering new 2018 4-Core and 6-Core Mac minis for $80-$100 off MSRP for a limited time. B&H Photo has the new 2018 4-Core and 6-Core Mac minis on sale for up to $100 off Apple... Read more
Early Holiday 2019 sale at B&H Photo: 12....
B&H Photo has new 12.9″ iPad Pros on sale for up to $120 off Apple’s MSRP as part of their early Holiday 2019 sale. Overnight shipping is free to many addresses in the US: – 12.9″ 64GB WiFi iPad... Read more
8-Core iMac Pro on sale today for $4499 at B...
B&H Photo has the base 8-Core 3.2GHz 32GB/1TB iMac Pro on sale today for $4499 — $500 off Apple’s MSRP. Shipping is free. Their price is the lowest available for a new iMac Pro from any Apple... Read more

Jobs Board

*Apple* Health Benefit Specialist - Call Cen...
Description ** Apple Health Benefit Specialist - Call Center (MAS 3/MACSC)** **Olympia, WA Multiple Positions** *The ideal candidate for this position will have Read more
Hair Stylist - *Apple* Blossom Mall - JCPen...
Hair Stylist - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1065040Salon Professionals Job Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**747088BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000297-Reston-Store **Job Description:** At Best Read more
Nurse Practitioner - Field Based (San Bernard...
Nurse Practitioner - Field Based (San Bernardino, CA, Apple Valley, Hesperia) **Location:** **United States** **Requisition #:** PS30312 **Post Date:** Nov 11, 2019 Read more
Best Buy *Apple* Computing Master - Best Bu...
**747061BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Store NUmber or Department:** 000647-Kildeer-Store **Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.