On va empiler du sable ;)

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