# Introduction

TODO: Introduce game rules and related work.

## Notations

Let `N`

be the number of pegs in the code and `C`

be the number of possible peg colors. A *code* is a vector in `\{0, \ldots, C - 1\}^N`

. The number of possible codes is `M = C^N`

. The game is played as follows:

- The codemaker chooses a secret code
`c`

. - The codebreaker tries to guess
`c`

in as few as possible iterations. At each iteration`t`

:

- The codebreaker produces a guess code
`g_t`

. - The codemaker provides a feedback
`f(c, g_t) = \langle b(c,g_t), w(c, g_t) \rangle`

where`b`

is the number of pegs which are correct in both color and position and`w`

is the number of pegs which are correct in color but not in position.

- The game ends when the codebreaker guesses the secret code (gets feedback
`\langle N, 0 \rangle`

) or when a predefined maximum number of iterations`T`

is reached.

The notion of "correct in color but not in position" is a bit tricky because color repetitions are allowed. To avoid ambiguity, here is a possible feedback implementation:

```
int[] feedback(int[] code, int[] guess) {
int[] vCode = new int[C]; // count vector of colors in code
int[] vGuess = new int[C]; // count vector of colors in guess
int black = 0;
for (int i = 0; i < N; i++) {
if (code[i] == guess[i]) {
black++;
} else {
vCode[code[i]]++;
vGuess[guess[i]]++;
}
}
int white = 0;
for (int c = 0; c < C; c++) {
white += min(vCode[c], vGuess[c]);
}
int[] f = {black, white};
return f;
}
```

### Implementation details

For performance reasons, we represent codes as integers between `0`

and `M - 1`

. Writing the code in base `C`

we obtain the vector of peg colors. For example, in the classic settings `N = 4`

and `C = 6`

, the code `0123`

is represented by `0 \times 6^3 + 1 \times 6^2 + 2 \times 6^1 + 3 \times 6^0 = 51`

.

The feedbacks are also encoded as integers between `0`

and `F - 1`

, where `F = \frac{(N + 1)(N + 2)}{2}`

. To reduce the size of arrays indexed by the possible feedbacks, we use the fact that `b + w \le N`

. Here is an example of encoding for `N = 3`

.

b/w | O | 1 | 2 | 3 |
---|---|---|---|---|

0 | 6 | 7 | 8 | 9 |

1 | 3 | 4 | 5 | - |

2 | 1 | 2 | - | - |

3 | 0 | - | - | - |

Using this encoding, feedback `0`

always means that the codebreaker guessed the code. According to the values of `N`

and `C`

, some of the feedbacks above are impossible. For example, the codebreaker can never get a feedback `\langle N - 1, 1 \rangle`

. This encoding tries to find a good trade-off between implementation simplicity and memory economy.

The class `CodeToolkit`

makes these encodings more or less transparent. The main method is `int feedback(int code, int guess)`

For performance reasons, feedbacks are precomputed and stored in a `M \times M`

symmetrical `feedbacks`

matrix. The class also contains some methods for encoding, decoding and displaying codes and feedbacks.