Skip to content
Snippets Groups Projects

Home

Last edited by sbalev

Introduction

TODO: Introduce game rules and related work.

Notations

Let

NN
be the number of pegs in the code and
CC
be the number of possible peg colors. A code is a vector in
{0,…,C−1}N\{0, \ldots, C - 1\}^N
. The number of possible codes is
M=CNM = C^N
. The game is played as follows:

  1. The codemaker chooses a secret code
    cc
    .
  2. The codebreaker tries to guess
    cc
    in as few iterations as possible. At each iteration
    tt
    :
  • The codebreaker produces a guess code
    gtg_t
    .
  • The codemaker provides a feedback
    f(c,gt)=⟨b(c,gt),w(c,gt)⟩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.
  1. 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;
}

Note for developers

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 number
51 = 0 \times 6^3 + 1 \times 6^2 + 2 \times 6^1 + 3 \times 6^0
represents the code
0123
.

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 situation, 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.

Exhaustive strategies

Evolution

References