Быки и Коровы (Bulls and Cows)
XESXOR9/2/20264 min read
#misc#custom#easy#api_interaction#candidate_filtering#minimax_strategy#permutation_generation#linux
Быки и Коровы (Bulls and Cows)
Platform: duckerz | Category: Misc | Type: Challenge | Difficulty: Easy | OS: Linux | Author: XESXOR | Date: 2026-01-08 | Status: Solved Techniques: api_interaction, candidate_filtering, minimax_strategy, permutation_generation
Summary
Task: Guess a 9-digit number in Bulls and Cows game within 10 attempts, win 10 games in a row. Solution: Minimax algorithm with candidate filtering to guarantee optimal guessing strategy.
Быки и Коровы (Bulls and Cows) — duckerz
Description
Extended version of the "Bulls and Cows" game. You need to guess a 9-digit number within one minute and 10 attempts.
URL: http://tasks.duckerz.ru:30026
Analysis
Game Rules
The "Bulls and Cows" game (also known as Mastermind):
- The server picks a 9-digit number with unique digits (from 10 possible: 0-9)
- The player makes attempts to guess the number
- After each attempt, feedback is provided:
- Bulls — digits in the correct positions
- Cows — correct digits in wrong positions
- Constraints: 10 attempts, 60 seconds per game
- To get the flag, you need to win 10 games in a row
API Endpoints
Web interface analysis revealed the following API:
POST /api/new-game - start a new game
POST /api/check - check a guess {"guess": "123456789"}
GET /api/game-status - get game status
Problem Mathematics
- Total possible combinations: P(10,9) = 10!/1! = 3,628,800
- Need to guess within 10 attempts
- Optimal strategy — minimax algorithm
Solution
Algorithm
- Candidate generation — all permutations of 9 digits from 10
- First guess — fixed (e.g., "012345678")
- Filtering — after each response, eliminate incompatible candidates
- Next guess selection — minimize the maximum remaining group size
Bulls and Cows Scoring Function
python read-only • copy alloweddef score(candidate, guess): """Calculates (bulls, cows) for a pair of numbers""" bulls = sum(c == g for c, g in zip(candidate, guess)) common = sum(min(candidate.count(d), guess.count(d)) for d in set(guess)) cows = common - bulls return (bulls, cows)
Candidate Filtering
python read-only • copy alloweddef filter_candidates(candidates, guess, bulls, cows): """Keep only candidates that produce the same result""" return [c for c in candidates if score(c, guess) == (bulls, cows)]
Complete Solver
python read-only • copy allowed#!/usr/bin/env python3 """ Bulls and Cows Solver - Minimax Strategy Solves the "Bulls and Cows" game with 9-digit numbers """ import requests from itertools import permutations import time BASE_URL = "http://tasks.duckerz.ru:30026" def score(candidate, guess): """Calculates (bulls, cows)""" bulls = sum(c == g for c, g in zip(candidate, guess)) common = sum(min(candidate.count(d), guess.count(d)) for d in set(guess)) return (bulls, common - bulls) def filter_candidates(candidates, guess, bulls, cows): """Filters candidates by result""" return [c for c in candidates if score(c, guess) == (bulls, cows)] def choose_guess(candidates, all_guesses): """ Chooses optimal guess using minimax. Minimizes maximum group size after response. """ if len(candidates) <= 2: return candidates[0] best_guess = None best_max_group = float('inf') # Check subset of guesses for speed test_guesses = candidates[:500] if len(candidates) > 500 else candidates for guess in test_guesses: groups = {} for cand in candidates: result = score(cand, guess) groups[result] = groups.get(result, 0) + 1 max_group = max(groups.values()) if max_group < best_max_group: best_max_group = max_group best_guess = guess return best_guess def play_game(session): """Plays one game""" # Generate all possible candidates all_candidates = [''.join(p) for p in permutations('0123456789', 9)] candidates = all_candidates.copy() # Start game r = session.post(f"{BASE_URL}/api/new-game") # First guess - fixed guess = "012345678" for attempt in range(10): r = session.post(f"{BASE_URL}/api/check", json={"guess": guess}) data = r.json() if data.get("win"): return True, data bulls = data.get("bulls", 0) cows = data.get("cows", 0) print(f" Attempt {attempt+1}: {guess} -> {bulls}B {cows}C") # Filter candidates candidates = filter_candidates(candidates, guess, bulls, cows) if not candidates: print(" Error: no candidates!") return False, None if len(candidates) == 1: guess = candidates[0] else: guess = choose_guess(candidates, all_candidates) return False, None def main(): session = requests.Session() wins = 0 while wins < 10: print(f"\n=== Game {wins + 1}/10 ===") success, data = play_game(session) if success: wins += 1 print(f" WIN! Streak: {wins}") if "flag" in str(data): print(f"\n*** FLAG: {data} ***") return else: print(" Loss. Starting over...") wins = 0 time.sleep(0.5) if __name__ == "__main__": main()
Running
bash read-only • copy allowedpython3 solve_v3.py
Example Output
=== Game 1/10 ===
Attempt 1: 012345678 -> 2B 4C
Attempt 2: 023156749 -> 3B 3C
Attempt 3: 023416758 -> 4B 3C
Attempt 4: 023516748 -> 5B 2C
Attempt 5: 923516740 -> 7B 1C
Attempt 6: 823516740 -> 8B 0C
Attempt 7: 823516740 -> 9B 0C
WIN! Streak: 1
...
=== Game 10/10 ===
Attempt 1: 012345678 -> 1B 5C
...
WIN! Streak: 10
*** FLAG: {'win': True, 'flag': 'DUCKERZ{REDACTED}'} ***
Theory: Minimax for Bulls and Cows
Why Minimax?
Minimax strategy guarantees worst-case performance:
- For each possible guess, calculate how candidates will split by results
- Choose the guess that minimizes the maximum group
- This guarantees progress even with "unlucky" responses
Complexity
- Naive minimax: O(n² × k), where n — candidates, k — possible results
- Optimization: check only a subset of guesses
- In practice: 5-8 attempts for a 9-digit number
Alternative Approaches
- Random selection — works but unreliable
- Entropy strategy — choose guess with maximum information entropy
- Genetic algorithm — for very large search spaces
References
- Mastermind (board game) - Wikipedia
- Donald Knuth's Mastermind Algorithm