// A program to solve Jim Propp's Self-Referential Quiz using a genetic // algorithm. // // The quiz has 20 multiple-choice questions, answered A through E. A // proposed 'solution' to the quiz, then, will be an array of these characters. // // The initial generation of 'n_members' solutions will be generated at random. // Then each quiz will be score. Whichever solution generates the highest // score will be used as a 'parent' for the next generation. If multiple // scores tie for the top spot, the first one found with that score is used. // // 'Children' are simple copies of the parent, with each answer risking a // PMUTAION chance of 'mutating' to different value. // // Each time the top score is improved upon, we'll print out the generation // number, the score, and the answer string. // // The program stops (other than by a user break) when the top score of 20 // is achieved. // // Note that this sort of strategy only works, in this case, because of the // novel nature of Jim Propp's puzzle. Since it is self-referential, the // answers can be checked against themselves, rather than a key provided by // the instructor. // // mark van dine, 9/19/02 // #include #include #include #include #include #define MAX_MEMBERS 1000 #define DEFAULT_MEMBERS 100 #define MAX_GENERATIONS 10000 #define LOWER_LIMIT 10 /* PMUTATION is the default probability of a mutation when copying a */ /* character from parent to child. Defined as the number of times per */ /* 1000 (one thousand) that a typo occurs. (i.e., 30 = 3% mutation rate. */ #define PMUTATION 100 #define NQUESTIONS 20 #define TRUE 1 #define FALSE 0 typedef struct member_node { char *answers; int score; } member; member *population[MAX_MEMBERS]; char *kids[MAX_MEMBERS]; int score; int n_members; char *answers = "ABCDE"; char *errors[] = { /* 0 */ "No error. Condition 0 indicates success." /* 1 */,"Incorrect arguments" /* 2 */,"Argument out of range" }; void crossover(int); void main(int,char **); void mutate(char *,char *,int); void print_results(int,int,char *,int,int,int); void print_status(int,int,char *); void quicksort_population(int,int); char random_answer(void); int random_number(int); int score_quiz(char *); void show_error(int,char *); char *stblank(int); /* ----------------------------------------------------------- */ void quicksort_population(int left,int right) { int v, i, j, temp; char str[NQUESTIONS + 1]; /* Sorts the population array from highest score to lowest */ if (right > left) { v = population[right] -> score; strcpy(str,population[right] -> answers); i = left - 1; j = right; while (TRUE) { while (population[++i] -> score > v); while ((j > 0) && (population[--j] -> score < v)); /* I got this algorithm from Sedgewick, but hadd to add that "j > 0' */ /* condition since it was sometimes allowing j to fall to -1 */ if (i >= j) break; temp = population[i] -> score; strcpy(str,population[i] -> answers); population[i] -> score = population[j] -> score; strcpy(population[i] -> answers,population[j] -> answers); population[j] -> score = temp; strcpy(population[j] -> answers,str); } temp = population[i] -> score; strcpy(str,population[i] -> answers); population[i] -> score = population[right] -> score; strcpy(population[i] -> answers,population[right] -> answers); population[right] -> score = temp; strcpy(population[right] -> answers,str); quicksort_population(left, i - 1); quicksort_population(i + 1,right); } } // ------------------------------------------------------------------------ int random_number(int x) { int j; /* Generates a random number on the range of 0 to (x - 1) */ j = rand() % x; return(j); } // ------------------------------------------------------------------------ void print_status(int generation,int score,char *answers) { printf("status:\t%d\t%d\t%s\n",generation,score,answers); } // ------------------------------------------------------------------------ void print_results(int generation,int score,char *answers,int success,int pop_size,int m_rate) { printf(">>%sSUCCESSFUL",(success == TRUE ? "" : "UN")); printf("\t%d\t%d\t%s\t%d\t%d\n", generation,score,answers,pop_size,m_rate); } // ------------------------------------------------------------------------ void show_error(int errnum,char *extra) { fprintf(stderr,"\n\n"); fprintf(stderr,"FATAL ERROR: %s\n\n",errors[errnum]); if (extra != NULL) fprintf(stderr,"\t%s\n\n",extra); exit(errnum); } // ------------------------------------------------------------------------ char *stblank(int n) { char *t; if ((t = (char *)calloc(n + 1, sizeof(char))) == NULL) show_error(2,"stblank()"); return(t); } // ------------------------------------------------------------------------ char random_answer(void) { return(answers[random_number(5)]); } // ------------------------------------------------------------------------ void mutate(char *str1,char *str2,int rate) { int i; int j; int len; len = strlen(str1); strcpy(str1,str2); if ((rate > 0) && (rate <= 1000)) for (i = 0;i < len;i++) for (j = 0;j < rate;j++) if (random_number(1000) == 1) str1[i] = random_answer(); } // ------------------------------------------------------------------------ void main(int argc,char **argv) { int i; int j; int best_score; /* int best_candidate; */ char *winner; int last_best; int generation; int m_rate; if (argc == 1) n_members = DEFAULT_MEMBERS; else n_members = atoi(argv[1]); if ((n_members < LOWER_LIMIT) || (n_members > MAX_MEMBERS)) { fprintf(stderr,"\n"); fprintf(stderr, "%s uses an argument for number of members per population.\n", argv[0]); fprintf(stderr,"This is a number between %d and %d.\n\n", LOWER_LIMIT,MAX_MEMBERS); fprintf(stderr,"(%d is used if no argument given.)\n\n", DEFAULT_MEMBERS); show_error(1,""); } if (argc < 3) m_rate = PMUTATION; else m_rate = atoi(argv[2]); if ((m_rate < 0) || (m_rate > 1000)) show_error(3,argv[1]); randomize(); for (i = 0;i < n_members;i++) { population[i] = (member *)calloc(1,sizeof(member)); population[i] -> answers = stblank(NQUESTIONS); for (j = 0;j < NQUESTIONS;j++) population[i] -> answers[j] = answers[rand() % 5]; kids[i] = stblank(NQUESTIONS); } winner = stblank(NQUESTIONS); best_score = 0; last_best = 0; generation = 0; while ((best_score < NQUESTIONS) && (generation < MAX_GENERATIONS)) { generation++; /* best_score = 0; */ /* best_candidate = 0; */ for (i = 0;i < n_members;i++) population[i] -> score = score_quiz(population[i] -> answers); quicksort_population(0,n_members - 1); best_score = population[0] -> score; strcpy(winner,population[0] -> answers); if (best_score > last_best) { print_status(generation,best_score,winner); last_best = best_score; } if ((generation % 100) == 0) print_status(generation,best_score,winner); if (best_score == NQUESTIONS) continue; /* The following for loop represents the original algorithm, where we only used mutation to vary the population. The code that follows, between the two '----------' markers is the revised method that employs crossover and mutation. for (i = 0;i < n_members;i++) mutate(population[i] -> answers,winner,m_rate); */ crossover(10); for (i = 0;i < n_members;i++) mutate(population[i] -> answers,kids[i],m_rate); } if (best_score == NQUESTIONS) print_results(generation,best_score,winner,TRUE ,n_members,m_rate); else print_results(generation,best_score,winner,FALSE,n_members,m_rate); getch(); exit(0); } // ------------------------------------------------------------------------ void crossover(int n_winners) { int i, j, k; int point; int n; char *temp; /* For crossover, we randomly choose from our top n_winners of the */ /* current generation to breed with a random member of the population */ /* at large (other than itself). We use single-point crossover to */ /* create two children. We repeat this process until the new popula- */ /* tion is done, and then we apply mutation. */ k = 0; while (k < n_members) { i = random_number(n_winners); while ((j = random_number(n_members)) == i); point = random_number(NQUESTIONS); /* Crossover point */ temp = kids[k]; strcpy(temp,population[i] -> answers); for (n = point;n < NQUESTIONS;n++) *(temp + n) = population[j] -> answers[n]; k++; if (k == n_members) continue; temp = kids[k]; strcpy(temp,population[j] -> answers); for (n = point;n < NQUESTIONS;n++) *(temp + n) = population[i] -> answers[n]; k++; } } // ------------------------------------------------------------------------ int score_quiz(char *answer_str) { int score; int i; int counters[5]; char ch; int pairs; int count; int gap; score = 0; /* Question 1: 1. The first question whose answer is B is question (A) 1 (B) 2 (C) 3 (D) 4 (E) 5 MCV: Okay, we have to find out if there is an answer 'B' among the first five questions. If so, is it where this particular answer says it is? */ i = 0; while ((answer_str[i] != 'B') && (i < 5)) i++; if (i < 5) { ch = answer_str[0]; switch (ch) { case 'A' : if (i == 0) score++; break; case 'B' : if (i == 1) score++; break; case 'C' : if (i == 2) score++; break; case 'D' : if (i == 3) score++; break; case 'E' : if (i == 4) score++; break; } } /* Question 2: 2. The only two consecutive questions with identical answers are questions (A) 6 and 7 (B) 7 and 8 (C) 8 and 9 (D) 9 and 10 (E) 10 and 11 MCV: Two parts to scoring this ... first sorting out that 'only' business ... if there are more than one consecutive pair of matching answers, I guess any answer is wrong. If there aren't any such pairs it is wrong. If we clear those two hurdles, then we just have to check the answer. */ pairs = 0; for (i = 1;i < NQUESTIONS;i++) if (answer_str[i] == answer_str[i - 1]) pairs++; if (pairs == 1) { ch = answer_str[1]; switch (ch) { case 'A' : if (answer_str[5] == answer_str[6]) score++; break; case 'B' : if (answer_str[6] == answer_str[7]) score++; break; case 'C' : if (answer_str[7] == answer_str[8]) score++; break; case 'D' : if (answer_str[8] == answer_str[9]) score++; break; case 'E' : if (answer_str[9] == answer_str[10]) score++; break; } } /* Question 3: 3. The number of questions with the answer E is (A) 0 (B) 1 (C) 2 (D) 3 (E) 4 MCV: Just count 'em up and check the answer. */ count = 0; for (i = 0;i < NQUESTIONS;i++) if (answer_str[i] == 'E') count++; ch = answer_str[2]; switch (ch) { case 'A' : if (count == 0) score++; break; case 'B' : if (count == 1) score++; break; case 'C' : if (count == 2) score++; break; case 'D' : if (count == 3) score++; break; case 'E' : if (count == 4) score++; break; } /* Question 4: 4. The number of questions with the answer A is (A) 4 (B) 5 (C) 6 (D) 7 (E) 8 MCV: Just like the last one. Just count 'em up and check the answer. */ count = 0; for (i = 0;i < NQUESTIONS;i++) if (answer_str[i] == 'A') count++; ch = answer_str[3]; switch (ch) { case 'A' : if (count == 4) score++; break; case 'B' : if (count == 5) score++; break; case 'C' : if (count == 6) score++; break; case 'D' : if (count == 7) score++; break; case 'E' : if (count == 8) score++; break; } /* Question 5: 5. The answer to this question is the same as the answer to question (A) 1 (B) 2 (C) 3 (D) 4 (E) 5 */ ch = answer_str[4]; switch (ch) { case 'A' : if (ch == answer_str[0]) score++; break; case 'B' : if (ch == answer_str[1]) score++; break; case 'C' : if (ch == answer_str[2]) score++; break; case 'D' : if (ch == answer_str[3]) score++; break; case 'E' : if (ch == answer_str[4]) score++; break; } /* Question 6: 6. The answer to question 17 is (A) C (B) D (C) E (D) none of the above (E) all of the above MCV: Okay, answer 'E' is never right (can only have a one-letter answer!) unless 'all' means 'any', and I say it don't. */ ch = answer_str[5]; switch (ch) { case 'A' : if (answer_str[16] == 'C') score++; break; case 'B' : if (answer_str[16] == 'D') score++; break; case 'C' : if (answer_str[16] == 'E') score++; break; case 'D' : if ((answer_str[16] == 'A') || (answer_str[16] == 'B')) score++; break; } /* Question 7: 7. Alphabetically, the answer to this question and the answer to the following question are (A) 4 apart (B) 3 apart (C) 2 apart (D) 1 apart (E) the same */ ch = answer_str[6]; gap = abs(answer_str[6] - answer_str[7]); switch (ch) { case 'A' : if (gap == 4) score++; break; case 'B' : if (gap == 3) score++; break; case 'C' : if (gap == 2) score++; break; case 'D' : if (gap == 1) score++; break; case 'E' : if (gap == 0) score++; break; } /* Question 8: 8. The number of questions whose answers are vowels is (A) 4 (B) 5 (C) 6 (D) 7 (E) 8 */ count = 0; for (i = 0;i < NQUESTIONS;i++) if ((answer_str[i] == 'A') || (answer_str[i] == 'E')) count++; ch = answer_str[7]; switch (ch) { case 'A' : if (count == 4) score++; break; case 'B' : if (count == 5) score++; break; case 'C' : if (count == 6) score++; break; case 'D' : if (count == 7) score++; break; case 'E' : if (count == 8) score++; break; } /* Question 9: 9. The next question with the same answer as this one is question (A) 10 (B) 11 (C) 12 (D) 13 (E) 14 */ ch = answer_str[8]; switch (ch) { case 'A' : if (ch == answer_str[9]) score++; break; case 'B' : if (ch == answer_str[10]) score++; break; case 'C' : if (ch == answer_str[11]) score++; break; case 'D' : if (ch == answer_str[12]) score++; break; case 'E' : if (ch == answer_str[13]) score++; break; } /* Question 10: 10. The answer to question 16 is (A) D (B) A (C) E (D) B (E) C */ ch = answer_str[9]; switch (ch) { case 'A' : if (answer_str[15] == 'D') score++; break; case 'B' : if (answer_str[15] == 'A') score++; break; case 'C' : if (answer_str[15] == 'E') score++; break; case 'D' : if (answer_str[15] == 'B') score++; break; case 'E' : if (answer_str[15] == 'C') score++; break; } /* Question 11: 11. The number of questions preceding this one with the answer B is (A) 0 (B) 1 (C) 2 (D) 3 (E) 4 */ count = 0; for (i = 0;i < 10;i++) if (answer_str[i] == 'B') count++; ch = answer_str[10]; switch (ch) { case 'A' : if (count == 0) score++; break; case 'B' : if (count == 1) score++; break; case 'C' : if (count == 2) score++; break; case 'D' : if (count == 3) score++; break; case 'E' : if (count == 4) score++; break; } /* Question 12: 12. The number of questions whose answer is a consonant is (A) an even number (B) an odd number (C) a perfect square (D) a prime (E) divisible by 5 MCV: Just about everybody agrees about 'even' and 'odd'. For the purposes of the exercise, I also assume the following: 0 (zero) is neither Even nor Odd 1, 4, 9, and 16 are perfect squares we may find. 1, 2, 3, 5, 7, 11, 13, 17 and 19 are Prime numbers we need to be concerned about. Any number is divisible by 5, so we'll assume the author of the quiz means 'divisible with no remainder'. O (zero) counts! */ count = 0; for (i = 0;i < NQUESTIONS;i++) if ((answer_str[i] > 'A') && (answer_str[i] < 'E')) count++; ch = answer_str[11]; switch (ch) { case 'A' : if (count != 0) if ((count % 2) == 0) score++; break; case 'B' : if ((count % 2) == 1) score++; break; case 'C' : if ((count == 1) || (count == 4) || (count == 9) || (count == 16)) score++; break; case 'D' : if ((count == 1) || (count == 2) || (count == 3) || (count == 5) || (count == 7) || (count == 11) || (count == 13) || (count == 17) || (count == 19)) score++; break; case 'E' : if ((count % 5) == 0) score++; break; } /* Question 13: 13 The only odd-numbered problem with answer A is (A) 9 (B) 11 (C) 13 (D) 15 (E) 17 MCV: Two parts to scoring this ... again, the use of 'only' means that if we find more than one, then any answer is wrong (I assume ... you could easily make the alternate decision!) Otherwise, we just have to check the answer. */ count = 0; for (i = 0;i < NQUESTIONS;i++) if (((i + 1) % 2) != 0) if (answer_str[i] == 'A') count++; if (count == 1) { ch = answer_str[12]; switch (ch) { case 'A' : if (answer_str[8] == 'A') score++; break; case 'B' : if (answer_str[10] == 'A') score++; break; case 'C' : if (answer_str[12] == 'A') score++; break; case 'D' : if (answer_str[14] == 'A') score++; break; case 'E' : if (answer_str[16] == 'A') score++; break; } } /* Question 14: 14. The number of questions with answer D is (A) 6 (B) 7 (C) 8 (D) 9 (E) 10 */ count = 0; for (i = 0;i < NQUESTIONS;i++) if (answer_str[i] == 'D') count++; ch = answer_str[13]; switch (ch) { case 'A' : if (count == 6) score++; break; case 'B' : if (count == 7) score++; break; case 'C' : if (count == 8) score++; break; case 'D' : if (count == 9) score++; break; case 'E' : if (count == 10) score++; break; } /* Question 15: 15. The answer to question 12 is (A) A (B) B (C) C (D) D (E) E */ ch = answer_str[14]; switch (ch) { case 'A' : if (answer_str[11] == 'A') score++; break; case 'B' : if (answer_str[11] == 'B') score++; break; case 'C' : if (answer_str[11] == 'C') score++; break; case 'D' : if (answer_str[11] == 'D') score++; break; case 'E' : if (answer_str[11] == 'E') score++; break; } /* Question 16: 16. The answer to question 10 is (A) D (B) C (C) B (D) A (E) E */ ch = answer_str[15]; switch (ch) { case 'A' : if (answer_str[9] == 'D') score++; break; case 'B' : if (answer_str[9] == 'C') score++; break; case 'C' : if (answer_str[9] == 'B') score++; break; case 'D' : if (answer_str[9] == 'A') score++; break; case 'E' : if (answer_str[9] == 'E') score++; break; } /* Question 17: 17. The answer to question 6 is (A) C (B) D (C) E (D) none of the above (E) all of the above MCV: Okay, answer 'E' is never right (can only have a one-letter answer!) unless 'all' means 'any', and I say it don't. */ ch = answer_str[16]; switch (ch) { case 'A' : if (answer_str[5] == 'C') score++; break; case 'B' : if (answer_str[5] == 'D') score++; break; case 'C' : if (answer_str[5] == 'E') score++; break; case 'D' : if ((answer_str[5] == 'A') || (answer_str[16] == 'B')) score++; break; } /* Question 18: 18. The number of questions with answer A equals the number of questions with answer (A) B (B) C (C) D (D) E (E) none of the above */ for (i = 0;i < 5;i++) counters[i] = 0; for (i = 0;i < NQUESTIONS;i++) counters[answer_str[i] - 'A'] += 1; ch = answer_str[17]; switch (ch) { case 'A' : if (counters[0] == counters[1]) score++; break; case 'B' : if (counters[0] == counters[2]) score++; break; case 'C' : if (counters[0] == counters[3]) score++; break; case 'D' : if (counters[0] == counters[4]) score++; break; case 'E' : if ((counters[0] != counters[1]) && (counters[0] != counters[2]) && (counters[0] != counters[3]) && (counters[0] != counters[4])) score++; break; } /* Question 19: 19. The answer to this question is: (A) A (B) B (C) C (D) D (E) E MCV: Constructed such that any answer is correct. */ ch = answer_str[18]; if (ch == answer_str[18]) score++; /* Question 20: 20. Standardized test : intelligence :: barometer : (A) temperature (only) (B) wind-velocity (only) (C) latitude (only) (D) longitude (only) (E) temperature, wind-velocity, latitude, and longitude MCV: A non self-referential question! Since, as we know, the score of a standardized test only rates the ability to take standardized tests, then any of the answers will work. (This by the mathematical principle of "A woman needs a man like a fish needs a bicycle."). BUT, E is effectively "all of the above", so that is what we'll call the "right" answer. */ ch = answer_str[19]; if (ch == 'E') score++; return(score); } // ------------------------------------------------------------------------