Mois : janvier 2016

Une collègue m’a lancé un petit défis suite au travail de sa fille (future développeuse) : le jeu de Nim, dans sa version une grille, un puit et 4 pions. La partie défi résidait dans la question qui vise à calculer la valeur d’une cellule de la grille, le nimber, en donnant juste la colonne et la ligne en entrée.

$array = [];
define('N', 7); //Lignes
define('M', 10); //Colones

function getNim($x, $y) {
    return (((M - $x) % 3) ^ ((N - $y) % 3)) % 4;
}

//Remplir la grille
for ($y = 1; $y <= N; $y++) {
    $array[$y] = [];
    for ($x = 1; $x <= M; $x++) {
        $array[$y][$x] = getNim($x, $y);
    }
}

Le but étant d’obtenir une valeur sur base de coordonnées, la fonction passera par l’usage de $x et $y.

Ce jeu de Nim part de la dernière case inférieure droite (le puit) avec une valeur 0, on devra remonter d’où l’usage de la valeur max – index.

Comme la valeur de case ne peut avoir que comme valeurs possibles le nombre de cases où l’on peut se déplacer, dans le cas de l’énoncé, chaque pion peut se déplacer potentiellement dans maximum 4 cases. Nous aurons les valeurs [0, 3], le modulo (%) 4 nous y aidera (jouez avec le modulo).

Dernière astuce, le modèle (pattern) trouvé à la main, réside en un tableau de 3×3 se répétant indéfiniment. Ainsi, le modulo (%) 3 permettra cette répétition.

La partie complexe de ce calcul se trouve dans le rapport en x et y. Si on additionne x et y et qu’on applique le modulo 4 une partie des cellules seulement sont bonnes (une sur 2). Si on fait une soustraction, c’est l’inverse. Faire un + et un – en même temps c’est là que le xor est survenu (jouez donc avec le XOR).

Ainsi après une belle prise de tête empirique la solution est là 🙂 !