loading...
Cover image for Daily Challenge #279 - Playing with Sandpiles

Daily Challenge #279 - Playing with Sandpiles

thepracticaldev profile image dev.to staff ・3 min read


A sandpile is a grid of piles of sand ranging from 0 to some max integer value. For simplicity's sake, we'll look at a 3x3 grid containing 0, 1, 2, or 3 grains of sand.

An example of this sort of sandpile might look like this:

1 3 0     . ∴ 
1 2 1  =  . : .
3 2 2     ∴ : :

Sandpiles are a form of number, and as numbers, they support a single operation: addition. To add two sandpiles, simply add the number of grains of sand within each cell with the matching cell in the second value:

1 3 0   2 0 2   (1+2) (3+0) (0+2)   3 3 2
1 2 1 + 2 1 0 = (1+2) (2+1) (1+0) = 3 3 1
3 2 2   0 0 1   (3+0) (2+0) (2+1)   3 2 3

You probably already have wondered, what happens if the number of grains goes above our max value of 3? The answer is, that pile topples over. If the pile is in the middle, it dumps one grain of sand to each neighbor, keeping whatever is left over. If it's on the edge, it loses one grain to each direct neighbor and also loses one grain for any edges that are on the side, which just disappear. This means that, no matter what, the over-sized cell loses 4 grains of sand, while any neighboring cells gain 1 grain of sand.

This repeats until we've reached a state or equilibrium, like so:

                           *            *
1 3 0   3 0 2   4 3 2    * 0 5 2      2 1 3      2 1 3
1 2 1 + 2 3 0 = 3 5 1 =>   5 1 2 => * 1 3 2 =>   2 3 2 =>
3 2 2   0 0 1   3 2 3      3 3 3      4 3 3    * 0 4 3
                                                 *

                                                   *
                2 1 3    2 2 3      2 2 4      2 3 0 *
             => 2 4 2 => 3 0 4   => 3 1 0 * => 3 1 1
                1 0 4    1 2 0 *    1 2 1      1 2 1
                  *          *

So the final sum looks like this.

1 3 0   3 0 2   2 3 0
1 2 1 + 2 3 0 = 3 1 1
3 2 2   0 0 1   1 2 1

We want to create a class, Sandpile, that simulates the 3x3, max 3 sandpile. This class should have the following properties:

  • The constructor optionally takes a string, which is 3 groups of 3 integers (0-9), separated by a newline. If any of the values of the integers are over 3, then immediately topple each pile until the Sandpile is at rest. If no argument is provided, initialize the piles with all zeros.
  • There should be a toString method, which prints the sandpile the same way as the constructor. This will be used to validate your results.
  • There should be an add method, which takes another Sandpile as an argument. This method returns a new Sandpile, with the sum of the previous Sandpiles.
  • Sandpiles are immutable after creation
  • The add function will only ever receive another Sandpile instance.

Tests

Add sp1 with sp2 (no topple):

let sp1 = new Sandpile('130\n121\n322');
let sp2 = new Sandpile('202\n210\n001');

Add sp1 with sp2 (with topple):

let sp1 = new Sandpile('333\n333\n333');
let sp2 = new Sandpile('000\n010\n000');

Good luck!


This challenge comes from OverZealous on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

markdown guide
 

This is part of a solution using numpy and recursion, maybe I'll write the whole class later.

import numpy as np
overlays = np.array(
    [[-4, 1, 0, 1, 0, 0, 0, 0, 0],
     [1, -4, 1, 0, 1, 0, 0, 0, 0],
     [0, 1, -4, 0, 0, 1, 0, 0, 0],
     [1, 0, 0, -4, 1, 0, 1, 0, 0],
     [0, 1, 0, 1, -4, 1, 0, 1, 0],
     [0, 0, 1, 0, 1, -4, 0, 0, 1],
     [0, 0, 0, 1, 0, 0, -4, 1, 0],
     [0, 0, 0, 0, 1, 0, 1, -4, 1],
     [0, 0, 0, 0, 0, 1, 0, 1, -4]]
)

zero_overlay = np.array([0, 0, 0, 0, 0, 0, 0, 0, 0])


def topple(piles):
    if not any(x > 3 for x in piles):
        return piles
    else:
        overlay = zero_overlay
        for i in range(len(piles)):
            if piles[i] > 3:
                overlay = overlay + overlays[i]
        return topple(piles + overlay)

from the example:

In [10]: topple(np.array([4,3,2,3,5,1,3,2,3]))
Out[10]: array([2, 3, 0, 3, 1, 1, 1, 2, 1])
 

APL (using Dyalog APL):

add←{{(+/4≤⊢/4 2⍴⍵)+4|⍵[2;2]}⌺3 3⍣≡⍺+⍵}

(Use the bookmarklet on this post to see the code with APL font and syntax highlighting.)

Takes two 3-by-3 matrices as the left and right arguments. Full demo can be found here. The task is a great showcase for APL's array manipulation abilities.

Explanation:

add←{{(+/4≤⊢/4 2⍴⍵)+4|⍵[2;2]}⌺3 3⍣≡⍺+⍵}
{...}      ⍝ Function definition
⍺+⍵        ⍝ Add two arguments, element-wise
...⍣≡      ⍝ Repeat until converges...
{...}⌺3 3  ⍝  Apply the subfunction to 3×3 submatrices...
4|⍵[2;2]   ⍝   The center value, minus 4 if too high
(...)+     ⍝   Add topples from its neighbors...
4 2⍴⍵      ⍝    Reshape to 4×2 matrix,
           ⍝    putting all 4-neighbors on the right column
4≤⊢/       ⍝    Extract right column, test each number for 4≤
+/         ⍝    Sum the ones (count the topples)
 

Oh! I did a sandpile thing in javascript and canvas years ago. I was inspired by the same youtube video ^_^

Gist