Cette semaine, c'est M@xime qui vous propose un #KataOfTheWeek : Sand piles
Briefing du Kata : Une pile de sable est une matrice carrée (de dimension impaire obligatoirement) de nombres entiers compris entre 0 et 3 représentant le nombre d'unité de sable présentes sur chaque portion de la pile.
Lorsque l'on ajoute une unité de sable celle-ci est lachée au milieu de la pile. A ce moment là on ajoute 1 au nombre d'unités présente.
Exemple:
000 addSandUnit() 000
000 ----------------> 010
000 000
L'ajout d'unités de sable suit les règles suivantes :
- Si une portion de la pile possède 4 unités de sable ou plus, la pile s'effondre et distribue équitablement ses unités de sables entre ses plus proches voisins (au-dessus, au-dessous, à droite et à gauche).
- Si la distribution conduit au fait qu'une unités se retrouve en dehors de la pile, elle est perdue.
- Le processsus de distribution s'arrête lorsque la pile est stable (c'est-à-dire que toutes les portions possèdent au maximum 3 unités).
Exemple:
000 addSandUnit() 010
030 ----------------> 101
000 010
-----------------------------------------
000 addSandUnit() 000 010 011
033 ----------------> 043 ---> 104 ---> 110 *(perdu)
000 000 010 011
Pour aller plus loin, il est possible de visualiser l'évolution d'une pile de sable au fil du temps, c'est très…. symétrique et hypnotisant.
Saurez-vous résoudre le problème ?
Bon courage !
Et voici une solution proposée par l'auteur en JavaScript:
/**
* Ajouter une unité de sable à la pile
* @param pile {number[][]} la pile à mettre à jour
* @returns number[][], la pile à jour
*/
function addSand(pile: Array<Array<number>>): Array<Array<number>> {
const middle = Math.ceil(pile.length / 2);
// on ajoute l'unité au milieu de la pile
pile[middle-1][middle-1]++;
return processPile(pile);
}
/**
* Mise à jour de la pile jusqu'à stabilisation
* Si une cellule contient 4 unités ou plus, elle en perd 4
* Les 4 unités sont réparties entre les plus proches voisin (au-dessus, en-dessous, à gauche, à droite)
* Si une unités sort de la pile après la répartition elle est perdue
* @param pile {number[][]}, la pile à process
* @return {number[][]}, la pile stable
*/
function processPile(pile: Array<Array<number>>): Array<Array<number>> {
let shouldUpdate;
do {
for (let i = 0; i < pile.length; i++) {
shouldUpdate = false;
const line = pile[i];
for (let j = 0; j < line.length; j++) {
if (line[j] >= 4){
shouldUpdate = true;
pile[i][j] -= 4;
if (i-1 >= 0){
pile[i-1][j]++;
}
if (i+1 < pile.length) {
pile[i+1][j]++;
}
if (j-1 >= 0) {
pile[i][j-1]++;
}
if(j+1 < pile.length) {
pile[i][j+1]++;
}
}
}
}
} while(shouldUpdate);
return pile;
}
/*-----------------------------------------------------------*/
let pile1 = [
[0,0,0],
[0,0,0],
[0,0,0]
];
addSand(pile1);
console.log("pile 1 : ", pile1); // [[0,0,0],[0,1,0],[0,0,0]]
let pile2 = [
[0,0,0],
[0,3,0],
[0,0,0],
];
addSand(pile2);
console.log("pile 2 : ",pile2); // [[0,1,0],[1,0,1],[0,1,0]]
let pile3 = [
[3,3,3],
[3,3,3],
[3,3,3],
];
addSand(pile3);
console.log("pile 3 : ", pile3); // [[1,3,1],[3,0,3],[1,3,1]]
/*-----------------------------------------------------------*/
Votre équipe TakiVeille
