Rosetta Code

Abelian sandpile model: Difference between revisions

Page Discussion

Abelian sandpile model (view source)

Revision as of 19:35, 6 January 2020

949 bytes added ,  4 years ago
Rewrote the Rust version. This one has no recursion (and thus requires no thread magic), is much faster and contains less actual lines of code.
(Added C implementation)
(Rewrote the Rust version. This one has no recursion (and thus requires no thread magic), is much faster and contains less actual lines of code.)
Line 1,426:
 
=={{header|Rust}}==
<lang rust>// SetThis imageis sizethe main algorithm.
//
const DIM: usize = 16;
// It loops over the current state of the sandpile and updates it on-the-fly.
fn advance(field: &mut Vec<Vec<usize>>, boundary: &mut [usize; 4]) -> bool
{
// This variable is used to check whether we changed anything in the array. If no, the loop terminates.
let mut done = false;
 
for y in boundary[0]..boundary[2]
// This function outputs the result to the console using UTF-8 block characters.
{
fn draw_pile(pile: &Vec<Vec<usize>>) {
for rowx in pile {boundary[1]..boundary[3]
{
let mut line = String::with_capacity(row.len());
for elem in row {if field[y][x] >= 4
line.push(match elem {
// This part was heavily inspired by the Pascal version. We subtract 4 as many times as we can
// and distribute it to the neighbors. Also, in case we have outgrown the current boundary, we
// update it to once again contain the entire sandpile.
 
// The amount that gets added to the neighbors is the amount here divided by four and (implicitly) floored.
// The remaining sand is just current modulo 4.
let rem: usize = field[y][x] / 4;
field[y][x] %= 4;
 
// The isize casts are necessary because usize can not go below 0.
// Also, the reason why x and y are compared to boundary[2]-1 and boundary[3]-1 is because for loops in
// Rust are upper bound exclusive. This means a loop like 0..5 will only go over 0,1,2,3 and 4.
if y as isize - 1 >= 0 {field[y-1][x] += rem; if y == boundary[0] {boundary[0]-=1;}}
if x as isize - 1 >= 0 {field[y][x-1] += rem; if x == boundary[1] {boundary[1]-=1;}}
if y+1 < field.len() {field[y+1][x] += rem; if x == boundary[2]-1 {boundary[2]+=1;}}
if x+1 < field.len() {field[y][x+1] += rem; if y == boundary[3]-1 {boundary[3]+=1;}}
 
done = true;
}
}
}
 
done
}
 
// This function can be used to display the sandpile in the console window.
//
// Each row is mapped onto chars and those characters are then collected into a string.
// These are then printed to the console.
//
// Eg.: [0,1,1,2,3,0] -> [' ','░','░','▒','▓',' ']-> " ░░▒▓ "
fn display(field: &Vec<Vec<usize>>)
{
for row in field
{
let char_row = {
row.iter().map(|c| {match c {
0 => ' ',
1 => '░',
Line 1,440 ⟶ 1,482:
3 => '▓',
_ => '█'
}});.collect::<String>()
};
println!("{}", char_row);
 
println!("{}", line);
}
}
 
// This function createswrites the end result to a file called "output.ppm" in the directory the program was run, which contains.
//
// a colored image of the pile.
// PPM is a very simple image format, however, it entirely uncompressed which leads to huge image sizes.
// Even so, for demonstrative purposes it's perfectly good to use. For something more robust, look into PNG libraries.
//
// Read more about the format here: http://netpbm.sourceforge.net/doc/ppm.html
fn write_pile(pile: &Vec<Vec<usize>>) {
use std::fs::File; // Used for opening the file.
use std::io::Write; // Used for writing to the file.
 
// We first create the file (or erase its contents if it already existed).
// Learn more about PPM here: http://netpbm.sourceforge.net/doc/ppm.html
let mut file = File::create("./output.ppm").unwrap();
 
// WeThen writewe add the image signature, imagewhich dimensionsis and"P3 maximum[width colorof valueimage] to[height theof fileimage]".
let _ = write!(file, "P3\n {} {}\n255\n", DIMpile.len(), DIMpile.len()).unwrap();
 
for row in pile {
// For each row, we create a new string which has more or less enough capacity to hold the entire row.
let mut line = String::with_capacity(row.len()*6);
// This is for performance purposes, but shouldn't really matter much.
let mut line = String::with_capacity(row.len() * 14);
 
// We map each value in the field to a color.
// These are just simple RGB values, 0 being the background, the rest being the "sand" itself.
for elem in row {
line.push_str(match elem {
0 => "125100 040 2515 ", // Background color for cells that have no "sand" in them.
1 => "117 87 30 ",
 
2 => "181 134 47 ",
// Depending on how many particles of sand is there in the cell we use a different shade of yellow.
13 => "125245 80182 066 ",
2_ => "186 118 0 "unreachable!(),
3 => "224 142 0 ",
 
// It is impossible to have more than 3 particles of sand in one cell after the program has run,
// however, Rust demands that all branches have to be considered in a match statement, so we
// explicitly tell the compiler, that this is an unreachable branch.
_ => unreachable!()
});
}
 
let// _Finally =we write!(file, "{}",this line)string into the file.unwrap();
write!(file, "{}\n", line).unwrap();
}
}
 
// This is the main part of the algorithm, a simple, recursive implementation of the model.
fn handle_pile(x: usize, y: usize, pile: &mut Vec<Vec<usize>>) {
if pile[y][x] >= 4 {
pile[y][x] -= 4;
 
// We check each neighbor, whether they have enough "sand" to collapse and if they do,
// we recursively call handle_pile on them.
if y > 0 {
pile[y-1][x] += 1;
if pile[y-1][x] >= 4 {handle_pile(x, y-1, pile)}}
 
if x > 0 {
pile[y][x-1] += 1;
if pile[y][x-1] >= 4 {handle_pile(x-1, y, pile)}}
 
if y < DIM-1 {
pile[y+1][x] += 1;
if pile[y+1][x] >= 4 {handle_pile(x, y+1, pile)}}
 
if x < DIM-1 {
pile[y][x+1] += 1;
if pile[y][x+1] >= 4 {handle_pile(x+1, y, pile)}}
 
// Uncomment this line to show every iteration of the program. Not recommended with large input values.
//draw_pile(&pile);
 
// Finally we call the function on the current cell again, in case it had more than 4 particles.
handle_pile(x,y,pile);
}
}
 
 
fn main() {
// This is how big the final image will be. Currently the end result would be a 16x16 picture.
use std::thread::Builder; // Used to spawn a new thread.
let field_size = 16;
 
let mut playfield = vec![vec![0; field_size]; field_size];
/* Rust by default uses a 2Mb stack, which gets quickly filled (resulting in a stack overflow) if we use any value larger than
* about 30,000 as our input value. To circumvent this, we spawn a thread with 32Mbs of stack memory, which can easily handle
* hundreds of thousands of sand particles. I tested the program using 256,000, but it should theoretically work with larger
* values too.
*/
 
let _ = Builder::new().stack_size(33554432).spawn(|| {
// This is our 2D grid. It's size can be set using the DIM constant found at the top of the code.
let mut pile: Vec<Vec<usize>> = vec![vec![0;DIM]; DIM];
 
// We placeput thisthe muchinitial sand in the centerexact middle of the gridfield.
// This isn't necessary per se, but it ensures that sand can fully topple.
pile[DIM/2 - 1][DIM/2 - 1] = 16;
//
// The boundary is initially just the single tile which has the sand in it, however, as the algorithm
// progresses, this will grow larger too.
let mut boundary = [field_size/2-1, field_size/2-1, field_size/2, field_size/2];
playfield[field_size/2 - 1][field_size/2 - 1] = 16;
 
// This is the //main loop. We startupdate the algorithmfield onuntil it returns false, signalling that the pile wereached just created.its
// final state.
handle_pile(DIM/2 - 1, DIM/2 - 1, &mut pile);
while advance(&mut playfield, &mut boundary) {};
 
// Once this happens, we simply display the result. Uncomment the line below to write it to a file.
// Calling display with large field sizes is not recommended as it can easily become too large for the console.
draw_pile(&pile)
display(&playfield);
//write_pile(&playfield);
// Uncomment this to save the image to a file after the recursive algorithm has ended.
//write_pile(&pile)
}).unwrap().join();
}</lang>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/293117"