Algorithms in Action: Bulls and Cows
AP Computer Science A: build the Bulls and Cows code-breaking game in Java with String methods, loops and an ArrayList, then let the computer solve any secret in at most 9 guesses.
Bulls and Cows is a code-breaking game. One player picks a secret 4-digit number, the other tries to find it. After every guess the answer is two numbers:
- a bull is a right digit in the right place
- a cow is a right digit in the wrong place
In our version all four digits are different and the number does not start with 0, so there are 9 × 9 × 8 × 7 = 4536 possible secrets.
| Secret | Guess | Answer |
|---|---|---|
| 4271 | 1234 | 1 bull, 2 cows |
| 4271 | 5689 | 0 bulls, 0 cows |
| 4271 | 1742 | 0 bulls, 4 cows |
The whole game uses only AP CSA tools: String methods, loops, if statements and an ArrayList.
Step 1: checking a guess
A guess is valid if it has 4 characters, every character is a digit, no digit repeats and the first digit is not 0.
public static boolean isValid(String code) {
if (code.length() != 4 || code.substring(0, 1).equals("0")) {
return false;
}
for (int i = 0; i < 4; i++) {
String d = code.substring(i, i + 1);
if ("0123456789".indexOf(d) == -1) {
return false; // not a digit
}
if (code.indexOf(d) != i) {
return false; // the same digit appears earlier
}
}
return true;
}
code.indexOf(d) != i is a neat trick: indexOf returns the first position of d, so if that position is not i, the digit already appeared before.
Step 2: scoring
Count the bulls position by position. Then count every guess digit that appears anywhere in the secret: those are bulls plus cows, so cows = common minus bulls.
public static int[] score(String secret, String guess) {
int bulls = 0;
int common = 0;
for (int i = 0; i < 4; i++) {
String d = guess.substring(i, i + 1);
if (secret.substring(i, i + 1).equals(d)) {
bulls++;
}
if (secret.indexOf(d) != -1) {
common++;
}
}
return new int[] {bulls, common - bulls};
}
This works only because the digits are all different. With repeated digits a digit could be counted twice.
Step 3: the computer as the player
The strategy is short and surprisingly strong:
- Put all 4536 valid numbers in a list of candidates.
- Guess the first candidate.
- Remove every candidate that would not have given the same answer.
- Repeat until the answer is 4 bulls.
ArrayList<String> candidates = new ArrayList<String>();
for (int n = 1000; n <= 9999; n++) {
String s = "" + n;
if (isValid(s)) {
candidates.add(s);
}
}
// after guess g received the answer {b, c}:
for (int i = candidates.size() - 1; i >= 0; i--) {
int[] r = score(candidates.get(i), g);
if (r[0] != b || r[1] != c) {
candidates.remove(i);
}
}
The loop runs backwards. Removing from an ArrayList shifts the later elements left; going from the end means no element is skipped. This is a classic AP CSA free response trap.
Why is it safe to remove those numbers? If the secret were one of them, the answer would have been different. So the secret is always still in the list, and if the list ever becomes empty, one of the answers was miscounted.
How good is the strategy?
Try every one of the 4536 secrets: the computer needs 5.47 guesses on average and never more than 9. You can run that experiment in the Statistics tab of the simulation below.
Connections to the exam
- Unit 1 and 2:
substring,indexOf,equals, nested conditions and loops - Unit 4: traversing and removing from an
ArrayList, arrays as return values - Algorithms: this is a filter algorithm, the same idea as a linear search that keeps every match
Try it yourself: write
isValidandscorefirst and test them on the table above. Then write the solver and print how many guesses it needs for 4271 (the answer is 5).
Interactive Simulation
Play it right here. Everything runs in your browser.
The computer picked a 4-digit number. All digits are different and it does not start with 0. A bull is a right digit in the right place, a cow is a right digit in the wrong place.
Short Lesson Video
Mock Exam
Practice Quiz
Test yourself: instant results and explanations.
1. The secret is 4271 and the guess is 1234. What is the answer?
2. In score, common counts the guess digits that appear anywhere in the secret. How are the cows computed?
3. Why does the filter loop run from the last index down to 0?
4. What does "1123".indexOf("1") return?
5. The candidate list becomes empty while the computer is solving. What does that mean?
Need support with this topic?
In a free 30-minute intro call we assess your level and build a study plan tailored to you.
Free intro call