Oct 95 Challenge
- Jan 95 Challenge
- Feb 95 Challenge
- Mar 95 Challenge
- Apr 95 Challenge
- May 95 Challenge
- Jun 95 Challenge
- Jul 95 Challenge
- Aug 95 Challenge
- Sep 95 Challenge
- Nov 95 Challenge
- Dec 95 Challenge
Volume Number: 11
Issue Number: 10
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 orsource code disks.
Master MindReader
This month’s Challenge, MindReader, was suggested by Carl Constantine (Victoria,
British Columbia), who earns points for the suggestion. The problem is to write code
that will guess a sequence of colors (represented by integers) known only to the caller.
You will be provided with a callback routine that can be used to examine a guess and
return two values: the number of elements of your guess where the correct color is
located in the correct place in the sequence, and the number of elements where the
correct color is in an incorrect place in the sequence. You may revise your guess and
use the callback routine as many times as you wish.
The prototype of the code you must write is:
typedef void (*CheckGuessProcPtr)( /* callback routine */
unsigned char *theGuess, /* your guess to be checked */
unsigned short *numInCorrectPos, /* return value - number in
correct position */
unsigned short *numInWrongPos); /* return value - number in wrong
position */
);
void MindReader(
unsigned char theAnswer[], /* preallocated storage to return the
sequence you guess */
CheckGuessProcPtr checkGuess, /* callback */
unsigned short answerLength, /* length of theAnswer */
unsigned short numColors /* colors are numbered 1..numColors */
);
You would invoke the callback using code something like this:
unsigned short correctPos,wrongPos;
unsigned char guess[kMaxLength];
(*checkGuess)(guess,&correctPos,&wrongPos);
Given inputs of:
correctAnswer[] = {1,3,4,3};
theGuess[] = {3,4,4,3};
the call back would produce the following:
numInCorrectPos = 2;
numInWrongPos = 1;
You may assume that answerLength and numColors will each be no larger than
16. The winning entry will be the one which correctly guesses the sequence in the
minimum amount of time. The number of times you call the callback routine is not an
explicit factor in determining the winner. However, to encourage you to guess
efficiently, all execution time used by MindReader, including the time spent in the
callback, is included in your time. The code for the callback will be very close to the
following:
#define kMaxLength 16
static unsigned short answerLength;
static unsigned char correctAnswer[kMaxLength];
void CheckGuess(
unsigned char *theGuess,
unsigned short *numCorrectPosition,
unsigned short *numWrongPosition
) {
unsigned short correctPosition=0, wrongPosition=0;
unsigned char answerUsed[kMaxLength], guessUsed[kMaxLength];
register unsigned char *guessP = theGuess;
register unsigned char *correctP = correctAnswer;
register int i,j;
/* find correct position matches first */
for (i=0; i
if (*guessP++ == *correctP++) {
*(answerUsed+i) = *(guessUsed+i) = 1;
++correctPosition; /* increment number in correct position*/
} else {
*(answerUsed+i) = *(guessUsed+i) = 0;
}
};
/* find wrong position matches */
guessP = theGuess;
for (i=0; i
if (!*(guessUsed+i)) {
register unsigned char *answerUsedP = answerUsed;
correctP = correctAnswer;
j = answerLength; do {
if ((!*answerUsedP) && (*guessP == *correctP)) {
*answerUsedP = 1;
++wrongPosition; /* increment number in wrong position*/
goto nextGuess;
}
++correctP; ++answerUsedP;
} while (--j);
}
nextGuess:
++guessP;
};
*numCorrectPosition = correctPosition;
*numWrongPosition = wrongPosition;
}
The target instruction set for this Challenge will be the PowerPC - I’ll be testing
your native code on a 6100/80. This problem will be scored using Symantec C++
version 8.0.3, which Symantec generously provided for use in the Challenge. If you
have any questions, please send them to me at one of the Programmer’s Challenge
e-mail addresses, or directly to boonstra@ultranet.com.
Two Months Ago Winner
Three people were brave enough to attempt the Diff-Warrior Challenge.
Unfortunately, probably due in large part to the complexity of the problem statement,
none of them passed my first set of test cases, so it was necessary to relax the test. The
winner is Ernst Munter (Kanata, ON), who submitted one of two entries that
successfully completed the relaxed test suite. I’ll try to make future Challenges a little
less difficult to understand and solve (MindReader should be a little easier). Then
again, we don’t want them to become too easy - MacTech has increased the amount of
the prize (see the Rules box), and we want you to earn it!
The problem was to generate a procedure for converting oldText into newText.
Ernst uses a hash table to find words in oldText that might have been moved to new
locations in newText. Blocks of contiguous words that do not have corresponding
entries are marked for insertion or deletion, while blocks that do match are marked as
text that has been moved, subject to a heuristic that tries to minimize the distance
moved. See Ernst’s well-commented code for further insight into his approach.
Here are the time and code sizes for the two most correct entries. Numbers in
parens after a person’s name indicate that person’s cumulative point total for all
previous Challenges, not including this one.
Name time code
Ernst Munter (70) 55 6318
Ken Slezak 250 3114
Top 20 Contestants of All Time
Here are the Top 20 Contestants for the Programmer’s Challenges to date. The numbers
below include points awarded for this month’s entrants. (Note: ties are listed
alphabetically by last name; there are more than 20 people listed this month because
of ties.)
1. [Name deleted] 176
2. Munter, Ernst 90
3. Karsh, Bill 78
4. Stenger, Allen 65
5. Larsson, Gustav 60
6. Gregg, Xan 51
7. Riha, Stepan 51
8. Goebel, James 49
9. Nepsund, Ronald 47
10. Cutts, Kevin 46
11. Mallett, Jeff 44
12. Kasparian, Raffi 42
13. Vineyard, Jeremy 42
14. Darrah, Dave 31
15. Landry, Larry 29
16. Elwertowski, Tom 24
17. Lee, Johnny 22
18. Noll, Robert 22
19. Anderson, Troy 20
20. Beith, Gary 20
21. Burgoyne, Nick 20
22. Galway, Will 20
23. Israelson, Steve 20