Problem Statement |
| | MasterMind is a popular two player board game. In this generalized version of the game, there are k different colors for pegs. A sequence of l pegs, the code is created by one of the players -- the code-maker. The other player, the code-breaker makes a series of guesses, also sequences of l pegs. After each guess, the code-maker gives the code-breaker two numbers as feedback. First, the number of pegs that are in the same place and of the same color in both the guess and the code. Second, the number of pegs in the guess that are of the same color but in different locations than pegs in the code. No peg from either the guess or the code may be counted twice, and if a peg could be counted towards either the first or the second number, it is counted only towards the first. For example, if there are three colors, R(ed), G(reen) and B(lue), the following guesses would be scored as follows:
code | guess | num1 | num2
-----+-------+------+------
RRGR | RRRG | 2 | 2
RRGR | RRRB | 2 | 1
RRGR | RBRB | 1 | 1
RRGR | GGRG | 0 | 2
RRGR | RBGB | 2 | 0
RRGR | RRGR | 4 | 0
Your job is to play this game as the code-breaker. First, a method init will be called, which takes the parameters k and l. This method should return your first guess as a int[] with l elements. Each element should be between 0 and k-1, representing the k colors.
Subsequently, the method nextGuess will be called with a int[], prev, representing your previous guess, and a int[] with two elements, results. This method should return your next guess.
Naturally, the goal is to find the exact code in as few guesses as possible. Once you get the exact code, no more calls to nextGuess will be made. If you haven't cracked the code after 3000 guesses, you will receive 0 points for the test case. For each test case, your score will be l * lg(k) / numGuesses (lg is logarithm base-2). Your total score is simply the sum of your scores for the individual test cases.
In generating test cases, k will be chosen uniformly between 5 and 20, inclusive. l will be chosen uniformly between 5 and 100, inclusive. Then, a probability distribution over the colors will be chosen (see notes). Finally, a sequence will be generated with the color of each peg chosen independently according to the probability distribution.
You will be given a total of 20 seconds of processing time for each test case. The memory limit is 64 megabytes. |
| |
Definition |
| | | Class: | MasterMind | | Method: | init | | Parameters: | int, int | | Returns: | int[] | | Method signature: | int[] init(int k, int l) | | | | Method: | nextGuess | | Parameters: | int[], int[] | | Returns: | int[] | | Method signature: | int[] nextGuess(int[] prev, int[] results) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | To generate the color probability distribution, each color is assigned a random real number between 0 and 1. Then, the probabilities are simply normalized by dividing each one by the original sum, such that the sum of the probabilities is 1. |
| - | To facilitate testing, k and l were not chosen randomly in the first 10 examples. In the last 10, they were. |
| - | The following pseudocode may be used to calculate the results of a guess: for(int i = 0 to l-1){
if(guess[i] == code[i]){
results[0]++;
}else{
for(int j = 0 to l-1){
if(guess[i] == code[j] && guess[j] != code[j] && !used[j]){
used[j] = true;
results[1]++;
break;
}
}
}
}
|
| |
Examples |
| 0) | |
| | | Returns: "k = 5
l = 5
code =
[4 3 3 3 0]
" | Here is one potential sequences of guesses, where each guess is consistent with the results of the previous guesses.
guess | result
----------+-------
3 2 0 2 4 | 0 3
0 0 1 3 2 | 1 1
0 3 3 4 3 | 2 3
4 3 3 3 0 | done
|
|
|
| 1) | |
| | | Returns: "k = 6
l = 6
code =
[1 2 4 4 4 1]
" | A potential sequence of guesses:
gues s | result
------------+-------
4 0 2 1 3 0 | 0 3
0 1 0 0 0 1 | 1 1
0 2 1 2 2 2 | 1 1
0 3 3 3 1 3 | 0 1
1 1 4 2 4 4 | 3 3
1 2 4 4 4 1 | done
|
|
|
| 2) | |
| | | Returns: "k = 7
l = 7
code =
[1 2 5 3 4 5 2]
" | |
|
| 3) | |
| | | Returns: "k = 8
l = 8
code =
[3 7 2 3 6 1 7 3]
" | |
|
| 4) | |
| | | Returns: "k = 9
l = 9
code =
[4 3 5 8 3 1 3 6 1]
" | |
|
| 5) | |
| | | Returns: "k = 10
l = 10
code =
[8 1 2 4 8 7 9 0 8 4]
" | |
|
| 6) | |
| | | Returns: "k = 11
l = 11
code =
[1 8 9 6 3 0 2 2 8 8 2]
" | |
|
| 7) | |
| | | Returns: "k = 12
l = 12
code =
[8 0 8 6 10 0 4 11 5 4 4 3]
" | |
|
| 8) | |
| | | Returns: "k = 13
l = 13
code =
[8 10 8 1 11 3 0 5 6 1 4 3 1]
" | |
|
| 9) | |
| | | Returns: "k = 14
l = 14
code =
[2 8 6 2 5 11 5 6 1 2 7 11 9 8]
" | |
|
| 10) | |
| | | Returns: "k = 14
l = 16
code =
[4 6 10 4 6 10 4 2 13 9 6 2 9 6 13 9]
" | |
|
| 11) | |
| | | Returns: "k = 16
l = 13
code =
[3 9 12 8 12 8 9 0 12 2 11 11 9]
" | |
|
| 12) | |
| | | Returns:
"k = 9
l = 70
code =
[5 0 6 7 0 3 5 2 7 0 2 5 5 2 4 7 2 2 1 5 1
4 3 3 0 0 4 5 7 0 7 5 7 7 8 7 0 5 5 3 7
3 1 5 0 6 7 8 5 5 2 5 7 7 3 5 2 2 2 8 5
7 1 7 5 0 5 5 3 5]
" | |
|
| 13) | |
| | | Returns:
"k = 12
l = 54
code =
[10 10 11 7 2 6 4 4 5 1 9 5 11 8 1 0 0 6 8 9 0
11 10 6 1 0 4 0 5 5 3 6 9 6 6 3 7 11 5 0 0
4 5 9 3 2 3 11 2 8 10 11 8 0]
" | |
|
| 14) | |
| | | Returns: "k = 19
l = 19
code =
[14 4 17 4 3 4 17 10 14 10 9 0 8 12 6 1 9 12 15]
" | |
|
| 15) | |
| | | Returns:
"k = 18
l = 51
code =
[10 10 4 9 2 9 2 4 9 16 14 9 16 17 12 6 5 11 13 4 2
13 13 16 13 16 4 2 6 11 14 13 12 2 17 2 12 2 14 6 15
2 9 2 16 9 16 10 4 17 15]
" | |
|
| 16) | |
| | | Returns:
"k = 9
l = 32
code =
[4 0 6 7 0 5 4 5 1 2 5 3 7 3 6 0 4 6 7 2 1
4 5 1 0 5 1 6 0 0 5 5]
" | |
|
| 17) | |
| | | Returns:
"k = 5
l = 80
code =
[0 0 0 4 4 2 3 0 3 0 2 2 2 0 2 2 4 2 0 1 2
3 2 2 1 2 0 0 0 2 2 0 4 2 1 2 1 0 0 0 2
2 2 4 0 4 3 0 2 0 2 0 2 4 0 0 4 3 2 3 3
2 2 0 3 0 3 2 4 4 2 4 2 1 0 2 1 0 3 0]
" | |
|
| 18) | |
| | | Returns:
"k = 13
l = 91
code =
[11 9 3 11 5 2 1 5 5 11 11 8 7 9 11 7 7 7 7 7 11
6 5 11 7 2 9 9 12 3 9 1 5 9 2 3 3 3 5 9 0
12 6 7 9 6 9 5 11 7 6 11 3 9 7 9 3 3 7 4 5
3 6 2 7 11 6 12 4 3 4 12 9 5 3 3 5 7 8 8 2
7 11 7 4 12 5 0 1 2 6]
" | |
|
| 19) | |
| | | Returns: "k = 13
l = 17
code =
[7 11 0 5 11 2 4 11 1 7 11 8 8 0 12 9 2]
" | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.