Home
Syllabus
Assignments
Tests
 Mastermind, the commercial version |
Due: 2:00pm, Thursday, October 8. Value: 30 pts. Submit to Sauron.
Bulls and Cows is an old game similar to the commercial
game Mastermind.
Two players, called the master and the guesser,
play the game. The master decides on a secret number, which we
name target.
The guesser then announces a succession of guesses
to the master; after each guess, the master
announces the number of bulls
and cows
(to be
described later). The guesser's goal is
determine target in as few guesses
as possible. (You can experience this with a
JavaScript version. There's also two-player
Bulls and Cows.) Below is a sample execution of the program.
Number of digits? 4 The user specifies the length of the target. Guess? 1234 You may assume all guesses have the same length as target. Bulls: 0; Cows: 2 Guess? 5678 Bulls: 0; Cows: 0 Guess? 3434 Bulls: 0; Cows: 1 Guess? 1313 Bulls: 2; Cows: 1 Guess? 9311 Bulls: 2; Cows: 2 Guess? 9113 That's correct!
So what's a bull and a cow? We define a bull to be a digit that occurs in both guess and target in exactly the same spot, and we define a cow as a digit that occurs in both guess and target but in different spots. For example, if target were 1215, then a guess of 1951 would have one bull (the first 1) and two cows (the 5 and 1), and a guess of 2161 would have no bulls and three cows.
Your job is to complete an implementation of this game. I'm
providing you with starting code
from which you should start.
(Right-click BullsAndCows.java,
select Save Link As…
or Save Target As…
from the pop-up menu, and save the file on your computer. Then select
Open… from Jigsaw's File menu and open the file you just saved.)
This code already defines run;
you should complete four methods as
described below.
It's tempting to attempt this program using ints
to represent target and guess.
However, it's better to use String variables, to avoid
problems with 0.
Counting the cows and bulls for each guess is somewhat tricky, and your first thought about to do it correctly is likely to be flawed. Here is a way that works correctly: We compute the following values for each possible digit d (0 through 9).
k: the number of times target and guess both have d in the same place. m: the number of times d occurs in target. n: the number of times d occurs in guess.
Knowing these values, the number of bulls that are d is of course k. Less obviously, the number of cows that are d is the smaller of m − k and n − k. Adding over all digits 0 through 9 yields the total number of bulls and cows.
Example. Suppose the target is 7080 and the guess is 0800.
For the 0 digit, we would compute that k is 1 (since both strings have 0 in the final place), that m is 2, and that n is 3. Thus, there is one bull that is 0, since k is 1; and there is one cow that is 0, since 1 is the lesser of 3 − 1 = 2 and 2 − 1 = 1.
For the 8 digit, we would compute that k is 0, that m is 1, and that n is 1. Since k is 0, there are no bulls that are 8; and there is one cow that is 8, since 1 is the lesser of 1 − 0 = 1 and 1 − 0 = 1.
For all other digits, we would compute that there are no bulls and no cows of that digit.
Summing over all digits, we conclude that the guess 0800 contains one bull and two cows.
If you think you may have a simpler technique than what I have described, please check it with me before trying to implement it: Most likely, there will be something wrong with it, as perhaps when the target happens to contain multiple copies of the same digit.
int countMatches(String a, String b, String digit)Returns the number of times that the single-character
string digit occurs at the same location
in both a and b. For example,
countMatches("7080", "0800", "0") should return 1,
since both have "0" in the final spot.
(This method is very similar to part of your solution from the
assignment DNA forensics
(Assn 5).)
int countOccurrences(String haystack, String digit)Returns the number of times the single-character string
digit occurs in haystack.
For example, countOccurrences("0800", "0")
should return 3, since "0" occurs three times in
"0800".
int countBulls(String target, String guess)Returns the total number of bulls in guess,
assuming a target string of target.
int countCows(String target, String guess)Returns the total number of cows in guess,
assuming a target string of target.
Your implementation of this method should use countMatches
and countOccurrences to compute k, m, and
n for each possible digit.