Abelian sandpile model: Difference between revisions

Line 1,426:

=={{header|Rust}}==

<lang rust>// ~~Set~~ ~~image~~ ~~size~~.

<lang rust>// This is the 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 ~~row~~ in ~~pile {~~

for x in 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:

Line 1,482:

3 => '▓',

_ => '█'

});

}}).collect::<String>()

}

};

println!("{}", char_row);

println!("{}", line);

}

// This function ~~creates~~ a file called "output.ppm" ~~in the directory the program was run, which contains~~

// This function writes the end result to a file called "output.ppm".

//

// 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::fs::File;

use std::io::Write; ~~// Used for writing to the file.~~

use std::io::Write;

// 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();

// We ~~write~~ the signature, ~~image~~ ~~dimensions~~ ~~and~~ ~~maximum~~ ~~color~~ ~~value~~ to ~~the~~ ~~file~~.

// Then we add the image signature, which is "P3 [width of image] [height of image]".

~~let _ =~~ write!(file, "P3\n {} {}\n255\n", ~~DIM~~, ~~DIM~~).unwrap();

write!(file, "P3\n {} {}\n255\n", pile.len(), pile.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 => "~~125~~ 0 25 ", ~~// Background color for cells that have no "sand" in them.~~

0 => "100 40 15 ",

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.

1 => "~~125~~ 80 0 ",

3 => "245 182 66 ",

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~~ _ = write~~!(file,~~ ~~"{}",~~ ~~line)~~.~~unwrap();~~

// Finally we write this string into the file.

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 ~~place~~ ~~this~~ ~~much~~ sand in the ~~center~~ of the ~~grid~~.

// We put the initial sand in the exact middle of the field.

// 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;

// We ~~start~~ the ~~algorithm~~ on the pile we ~~just created.~~

// This is the main loop. We update the field until it returns false, signalling that the pile reached 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>