home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 11.10 / 11.10ChallengeText < prev    next >
Text File  |  2010-09-21  |  4KB  |  90 lines
  1. This is the text of an article orginially printed in MacTech Magazine™.  MacTech Magazine, for Macintosh Programmers and Developers.  For subscription information, please contact us at:
  2.   •  http://www.mactech.com
  3.   •  mailto:info@mactech.com
  4.   •  805/494-9797
  5.  
  6. Programmer's Challenge
  7. by Bob Boonstra
  8.  
  9. Master MindReader
  10. 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. 
  11. The prototype of the code you must write is:
  12.  
  13. typedef void (*CheckGuessProcPtr)(    /* callback routine */
  14.     unsigned char  *theGuess,                /* your guess to be checked */
  15.     unsigned short *numInCorrectPos,    /* return value – number in                                                                          correct position */
  16.     unsigned short *numInWrongPos);        /* return value – number in wrong                                                                     position */
  17. );
  18.  
  19. void MindReader(
  20.     unsigned char  theAnswer[],    /* preallocated storage to return the                                                                 sequence you guess */
  21.     CheckGuessProcPtr checkGuess,    /* callback */
  22.     unsigned short answerLength,    /* length of theAnswer */
  23.     unsigned short numColors            /* colors are numbered 1..numColors */
  24. );
  25. You would invoke the callback using code something like this:
  26.  
  27. unsigned short correctPos,wrongPos;
  28. unsigned char guess[kMaxLength];
  29.  
  30. (*checkGuess)(guess,&correctPos,&wrongPos);
  31. Given inputs of:
  32.  
  33. correctAnswer[] = {1,3,4,3};
  34. theGuess[]      = {3,4,4,3};
  35.  
  36. the call back would produce the following:
  37.  
  38. numInCorrectPos = 2;
  39. numInWrongPos   = 1;
  40.  
  41. 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:
  42.  
  43. #define kMaxLength 16
  44. static unsigned short answerLength;
  45. static unsigned char correctAnswer[kMaxLength];
  46. void CheckGuess(
  47.     unsigned char  *theGuess, 
  48.     unsigned short *numCorrectPosition,
  49.     unsigned short *numWrongPosition
  50. ) {
  51. unsigned short correctPosition=0, wrongPosition=0;
  52. unsigned char  answerUsed[kMaxLength], guessUsed[kMaxLength];
  53. register unsigned char *guessP = theGuess;
  54. register unsigned char *correctP = correctAnswer;
  55. register int i,j;
  56.     
  57. /* find correct position matches first */
  58.     for (i=0; i<answerLength; ++i) {
  59.         if (*guessP++ == *correctP++) {
  60.             *(answerUsed+i) = *(guessUsed+i) = 1;
  61.             ++correctPosition; /* increment number in correct position*/
  62.         } else {
  63.             *(answerUsed+i) = *(guessUsed+i) = 0;
  64.         }
  65.     };
  66.     
  67. /* find wrong position matches */
  68.     guessP = theGuess;
  69.     for (i=0; i<answerLength; ++i) {
  70.         if (!*(guessUsed+i)) {
  71.             register unsigned char *answerUsedP = answerUsed;
  72.             correctP = correctAnswer;
  73.             j = answerLength; do {
  74.                 if ((!*answerUsedP) && (*guessP == *correctP)) {
  75.                     *answerUsedP = 1;  
  76.                     ++wrongPosition; /* increment number in wrong position*/
  77.                     goto nextGuess;
  78.                 }
  79.                 ++correctP; ++answerUsedP;
  80.             } while (--j);
  81.         }
  82. nextGuess:
  83.         ++guessP;
  84.     };
  85.  
  86.     *numCorrectPosition = correctPosition;
  87.     *numWrongPosition = wrongPosition;
  88. }
  89.  
  90. 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.