İçeriğe atla
2027 - 2028 Sınavları için son kontenjanlarBaşvuru
ITMagicITMagicAcademy
AP kaynakları
APBilgisayar BilimiCSA

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.

SecretGuessAnswer
427112341 bull, 2 cows
427156890 bulls, 0 cows
427117420 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:

  1. Put all 4536 valid numbers in a list of candidates.
  2. Guess the first candidate.
  3. Remove every candidate that would not have given the same answer.
  4. 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 isValid and score first and test them on the table above. Then write the solver and print how many guesses it needs for 4271 (the answer is 5).

İnteraktif Simülasyon

Burada oyna, her şey tarayıcında çalışır.

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.

Kısa Ders Videosu

Bu konunun ders videosu yakında eklenecek.

Deneme Sınavı

Bu konunun deneme sınavı yakında eklenecek.

Alıştırma Testi

Kendini dene: anında sonuç ve açıklama.

  1. 1. The secret is 4271 and the guess is 1234. What is the answer?

  2. 2. In score, common counts the guess digits that appear anywhere in the secret. How are the cows computed?

  3. 3. Why does the filter loop run from the last index down to 0?

  4. 4. What does "1123".indexOf("1") return?

  5. 5. The candidate list becomes empty while the computer is solving. What does that mean?

Bu konuda desteğe mi ihtiyacın var?

30 dakikalık ücretsiz tanışma görüşmesinde seviye belirlenir, kişiye özel bir çalışma planı kurulur.

Ücretsiz tanışma görüşmesi