Programming assignment A4M33PAL

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.

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

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.