 Play the Game Mastermind
This function plays the game Mastermind.
Mastermind is played with small pegs of different colors. One player creates a secret code, which consists of a sequence of colored pegs. (The standard game has four pegs in the code and six colors to choose from, but other variations exist.) The other player attempts to decipher the secret code by making guesses at the sequence. After each guess, the first player assigns a score to the guess by using a second set of pegs that are black and white. The score is one black peg for each peg in the guess that matches up exactly with a peg in the secret (same color, same location) and one white peg for each guess that matches up improperly with a peg in the secret (same color, different location).
Each peg in the guess gets only one score peg, either black or white. If it is credited with a black peg, for example, it cannot also receive a white peg for matching the same color in a different location.
In the program, the user is the keeper of the secret, and the program is the guesser. The program creates a list of all possible guesses, and simply walks through the list, guessing each one in turn. However, after each guess, it prunes its list of possible guesses down to those that would have given the same score if they were the secret. Eventually, the list of guesses that satisfy all the previous scores is narrowed down to one, and that must be the secret.
To ensure that the user doesn't make a mistake in scoring, after the program prompts the user for the secret it checks each score given by the player to ensure that it is accurate. However, the program doesn't cheat by looking at the secret.
The program uses secrets of length 3. The colors are specified in an array that currently has six elements, but could be arbitrarily expanded. Colors are specified by a single letter, and scores are specified by a combination of the letters "B" (black) and "w" (white).
The Perl splice() function takes a set of elements in an array and replaces them with new elements, or removes them if new elements are not provided, as used in this function:
splice(@colorarray, $index, 1);
This removes from @colorarray the single element indexed by $index.
The join() function converts an array back to a string using a separator specified by a string, which in the example used in this program is an empty string:
$allcolors = join "", @colors;
This string runs all the elements in @colors together with no separator.
This program uses the shortcut qw (the letter q followed by the letter w), which allows you to define a list of strings without including the quotes around each one. (The strings cannot contain white space for obvious reasons.) In this case, the list has six elements, each a string of length one:
@colors = qw/ R P V O Y B /;
Source Code
1. # score a single guess
2.
3. sub score {
4. # $_[0] is the secret value, $_[1] is the guess
5. my $result = "";
6. my $secret = $_[0];
7. my $guess = $_[1];
8. my $index;
9.
10. for ($index=0; $index < length($secret); $index++) {
11. if (substr($secret, $index, 1) eq
12. substr($guess, $index, 1)) {
13. $result .= "B";
14. # remove it once it is matched
15. substr($secret, $index, 1) = "";
16. substr($guess, $index, 1) = "";
17. $index--; # since iteration will add one back
18. }
19. }
20. for ($index=0; $index < length($secret); $index++) {
21. my $loc =
22. index($secret, substr($guess, $index, 1));
23. if ($loc != -1) {
24. $result .= "w";
25. # remove it once it is matched
26. substr($secret, $loc, 1) = "";
27. substr($guess, $index, 1) = "";
28. $index--; # since iteration will add one back
29 }
30. }
31. return $result;
32. }
33.
34. # colors are Red, Pink, Violet, Orange, Yellow, Blue
35.
36. @colors = qw/ R P V O Y B /;
37. $allcolors = join "", @colors;
38. $numcolor = @colors;
39. print("Possible color choices: @colors\n");
40.
41. # fill @colorarray with all possible choices
42.
43. for (0..((3**$numcolor)-1)) {
44. $colorarray[$_] =
45. @colors[$_ / ($numcolor**2)] .
46. @colors[($_ / $numcolor) % $numcolor] .
47. @colors[$_ % $numcolor];
48. }
49.
50. # ask user for secret code, until valid one entered
51.
52. do {
53. print("Enter your secret code:\n");
54. chomp ($code = <STDIN>);
55. } until ($code =~ /^[$allcolors]{3}$/);
56.
57. # now play the game until @colorarray has only one left
58. # or we happen to guess the secret
59.
60. while (@colorarray >= 2) {
61. $guess = $colorarray[0];
62. do {
63. print("I guess $colorarray[0]; score is?\n");
64. chomp ($score = <STDIN>);
65. } until ($score eq score($code, $guess));
66.
67. if ($score eq "BBB") {
68 print ("I guessed it!\n");
69. last; # got it!
70. }
71.
72. # guess was wrong, so take it out of @colorarray
73. shift @colorarray;
74.
75. # remove all guesses that would not score the same
76. $index = 0;
77. while ($index < @colorarray) {
78. if (score($colorarray[$index], $guess) ne
79. $score) {
80. splice(@colorarray, $index, 1); # remove
81. } else {
82. $index++;
83. }
84. }
85. }
86.
87. if (@colorarray == 1) {
88. print("Your code is $colorarray[0]\n");
89. }
Suggestions
Pick values to test the score() function that will result in the following results: "", "www", "BBB", "Bww". How many different variables called $index are used in the program, and what scope do they have? What variables in the program hold codes or guesses? What restrictions are there on such variables? Are these restrictions enforced properly? The result of the game can be printed out on either line 68 or 88. Can you be sure that only one of those two lines will be executed? The program has the number of elements in the secret hardcoded at 3, but is designed to make the number and names of the colors completely dependent on the declaration of the @colors array on line 36. Does it accomplish this goal?
Hints
Walk through the code for the following secrets:
The trivial case where the secret is "RRR", which will be the first secret guessed because it's the first entry in @colorarray. The secret is "RRP", which is the second entry in @colorarray. The secret is "PPP", which is the first entry in the @colorarray that does not contain an "R".
Explanation of the Bug
The bug is in the initialization of @colorarray. Line 43 reads as follows:
for (0..((3**$numcolor)-1)) {
It is wrong. With three pegs, each of which can have one of $numcolor colors, the number of possible choices is $numcolor * $numcolor *numcolor. In other words, line 43 should read as follows:
for (0..(($numcolor**3)-1)) {
With three pegs and six colors, the bug causes the initialization loop on lines 43-48 to execute 729 times instead of 216. The array index on line 45 ($_ / ($numcolor**2)) winds up being larger than the size of @colors, which leads to entries in @colorarray that only have two characters. (The second and third characters in the @colorarray entries, calculated on lines 46 and 47, continue to cycle through all possible values in an orderly fashion because of their use of the modulo operator.) The program won't crash, but it winds up with many extra, malformed entries in @colorarray, which causes it to take longer than necessary to find the secret. (It eventually does prune out the two-character elements because they won't ever score the same as a three-character guess that scores at least "www".)
This error could be classified as either A.logic or B.expression. As with many errors that are in that situation, it depends on what the programmer was thinking when he or she wrote the code.
|
