On va empiler du sable ;)

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 ! Retrouvez la solution dans cet article 😉