Task: The Mastermind-- Assistant Program
The game Mastermind-- is a modification of the well-known game Mastermind (in Czech also known as "hra logik").
Gameplay and Rules
Mastermind-- is a code-breaking game for two players. One player becomes the codemaker, the other the codebreaker. The codemaker chooses a secret pattern of k pegs. All the pegs used in the secret pattern must be taken from a bag. The content of this bag is known to both players only before the game starts. So the codebreaker is not able to detect which pegs were chosen from the bag by the codemaker. The secret pattern is invisible for the codebreaker until the game is over. Pegs are distinguishable only by the number. These numbers are written on each peg and are not unique.
The codebreaker tries to guess the secret pattern, in both order and number of pegs, within some defined number of turns. Each guess is made by placing a row of code pegs on the decoding board. Once placed, the codemaker provides feedback by placing a number in range from zero to k of the row with the guess. This number represents Hamming distance between the secret pattern and the guessed pattern.
Once feedback is provided, another guess is made; guesses and feedback continue to alternate until either the codebreaker guesses correctly, or enough incorrect guesses are made.
The authors of Mastermind-- invented the following algorithm for computing score points of each player.
- If the codebreaker guessed correctly the secret pattern then he gains a number of points equals to the number of remaining turns.
- If the codebreaker depleted all his guesses then the codemaker gains a number of points equals to the number of patterns that have the same evaluation of all codebreaker's guesses as the secret pattern on the decoding board.
The Task
Your task is to create a program that will assist to Mastermind-- players identifying the score points in case that the codebreaker depletes all his guesses.
The program reads the description of the bag content before the game starts and the decoding board (without the secret pattern) as the input. Then the program returns a number that represent how many k-pegs patterns would have the same evaluation of all codebreaker's guesses as the secret pattern already has on the decoding board.
It can be assumed that both players play by the rules and the format of the input is every time correct.
The Input
- On the first line is a number n of pegs in the bag.
- On the second line is n numbers separated by space that represent the content of the bag where the numbers on the pegs are in range from 0 to 255.
- On the third line is the number k of pegs in the secret pattern.
- On the fourth line is a number of guesses for the codebreaker.
- On the other lines is the decoding board. Every line represents one guess and each such line consists k+1 numbers separated by space, where from the first to k-th number is a guessed pattern and the (k+1)-th number is its Hamming distance from the secret pattern.
The Output
The output is only one line with one integer as the result defined above.
The authors of Mastermind-- have quite a good reason to expect that there is no polynomial algorithm, proportional to k, solving the task. On the other hand, the information about the bag content and the decoding board can play a significant role in finding fast solution of the task.
Example 1:
Input:
14 2 2 2 2 2 1 1 1 1 1 3 3 3 3 2 1 1 2 1
Output:
4
For your convenience we add all patterns that satisfy the conditions of the task:
2 2 3 2 1 1 1 3
Example 2:
Input:
23 9 2 2 2 2 2 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 8 5 2 9 8 3 2 1 5 1 2 3 8 9 1
Output:
2
For your convenience we add all patterns that satisfy the conditions of the task:
1 2 1 8 9 1 2 2 8 9
Example 3:
Input:
13 9 0 3 4 2 7 7 5 8 1 5 5 1 5 6 9 0 3 4 2 3 7 0 7 9 4 5 3 9 4 5 8 3 3 4 1 0 9 4 5 1 5 4 5 3 1 2 5 3 1 4
Output:
1
For your convenience we add the secret pattern: 3 9 5 4 2.