Simulate M random walkers N times and visualize relationship between walker number and grid size

Problem statement: Suppose that n random walkers, starting in the center of an n-by-n grid, move one step at a time, choosing to go left, right, up, or down with equal probability at each step. Write a program to help formulate and test a hypothesis about the number of steps taken before all cells are touched.

This is one of my self-imposed challenges in Rust to become better at it. The problem was taken from Sedgewick Exercise 1.4.36.

Here is my code:

use clap::Parser;
use plotly::common::Title;
use plotly::layout::{Axis, Layout};
use plotly::{HeatMap, Plot};
use rand::Rng;

#[derive(Debug, Parser)]
struct Arguments {
#[arg(index = 1)]
number_of_trials: usize,
#[arg(index = 2)]
walker_number_range_start: usize,
#[arg(index = 3)]
walker_number_range_end: usize,
#[arg(index = 4)]
walker_number_range_step: usize,
#[arg(index = 5)]
grid_size_range_start: usize,
#[arg(index = 6)]
grid_size_range_end: usize,
#[arg(index = 7)]
grid_size_range_step: usize,
#[arg(index = 8)]
grid_type: String,
}

fn main() -> Result<(), String> {
let arguments = Arguments::parse();
let number_of_trials = arguments.number_of_trials;
let walker_number_range_start = arguments.walker_number_range_start;
let walker_number_range_end = arguments.walker_number_range_end;
let walker_number_range_step = arguments.walker_number_range_step;
let grid_size_range_start = arguments.grid_size_range_start;
let grid_size_range_end = arguments.grid_size_range_end;
let grid_size_range_step = arguments.grid_size_range_step;
let grid_type = arguments.grid_type;

let walker_number_range = (
walker_number_range_start,
walker_number_range_end,
walker_number_range_step,
);
let grid_size_range = (
grid_size_range_start,
grid_size_range_end,
grid_size_range_step,
);

let heat_map = run_parametric_experiment(
number_of_trials,
walker_number_range,
grid_size_range,
&grid_type,
&mut rng,
)?;

let heat_map_row_indices: Vec<usize> = (walker_number_range.0..walker_number_range.1)
.step_by(walker_number_range.2)
.collect();
let heat_map_column_indices: Vec<usize> = (grid_size_range.0..grid_size_range.1)
.step_by(grid_size_range.2)
.collect();
let mut plot = Plot::new();
let trace = HeatMap::new(heat_map_row_indices, heat_map_column_indices, heat_map);
let layout = Layout::new()
.x_axis(Axis::new().title(Title::from("Grid Size")))
.y_axis(Axis::new().title(Title::from("Walker Number")));
plot.set_layout(layout);
plot.show();

Ok(())
}

#[derive(Clone, Debug)]
struct Walker {
x: usize,
y: usize,
grid_size: usize,
grid_type: String,
}

impl Walker {
fn new(x: usize, y: usize, grid_size: usize, grid_type: &str) -> Result<Self, String> {
if grid_size < 1 {
return Err("Grid size must be at least 1".to_string());
}

if x >= grid_size {
return Err(format!(
"X coordinate: {} greater than or equal to grid size: {}",
x, grid_size
));
} else if y >= grid_size {
return Err(format!(
"Y coordinate: {} greater than or equal to grid size: {}",
y, grid_size
));
}

if grid_type != "plane" && grid_type != "torus" {
return Err("Defined grid types are plane and torus".to_string());
}

Ok(Walker {
x,
y,
grid_size,
grid_type: grid_type.to_string(),
})
}

fn get_x_coordinate(&self) -> usize {
self.x
}

fn get_y_coordinate(&self) -> usize {
self.y
}

fn walk_on_plane(&mut self, rng: &mut ThreadRng) {
let r = rng.gen_range(0.0..1.0);

// Unit case
if self.grid_size == 1 {
}
// Corner cases
else if self.x == 0 && self.y == 0 {
if r < 1.0 / 2.0 {
self.x += 1;
} else {
self.y += 1;
}
} else if self.x == 0 && self.y == self.grid_size - 1 {
if r < 1.0 / 2.0 {
self.x += 1;
} else {
self.y -= 1;
}
} else if self.x == self.grid_size - 1 && self.y == self.grid_size - 1 {
if r < 1.0 / 2.0 {
self.x -= 1;
} else {
self.y -= 1;
}
} else if self.x == self.grid_size - 1 && self.y == 0 {
if r < 1.0 / 2.0 {
self.x -= 1;
} else {
self.y += 1;
}
}
// Edge cases
else if self.x == 0 {
if r < 1.0 / 3.0 {
self.x += 1;
} else if r < 2.0 / 3.0 {
self.y += 1;
} else {
self.y -= 1;
}
} else if self.x == self.grid_size - 1 {
if r < 1.0 / 3.0 {
self.x -= 1;
} else if r < 2.0 / 3.0 {
self.y += 1;
} else {
self.y -= 1;
}
} else if self.y == 0 {
if r < 1.0 / 3.0 {
self.x += 1;
} else if r < 2.0 / 3.0 {
self.x -= 1;
} else {
self.y += 1;
}
} else if self.y == self.grid_size - 1 {
if r < 1.0 / 3.0 {
self.x += 1;
} else if r < 2.0 / 3.0 {
self.x -= 1;
} else {
self.y -= 1;
}
// Regular case
} else if r < 1.0 / 4.0 {
self.x += 1;
} else if r < 2.0 / 4.0 {
self.x -= 1;
} else if r < 3.0 / 4.0 {
self.y += 1;
} else {
self.y -= 1;
}
}

fn walk_on_torus(&mut self, rng: &mut ThreadRng) {
let r = rng.gen_range(0.0..1.0);

if r < 1.0 / 4.0 {
self.x = (((self.x + 1) % self.grid_size) + self.grid_size) % self.grid_size;
} else if r < 2.0 / 4.0 {
if self.x == 0 {
self.x = self.grid_size - 1;
} else {
self.x = (((self.x - 1) % self.grid_size) + self.grid_size) % self.grid_size;
}
} else if r < 3.0 / 4.0 {
self.y = (((self.y + 1) % self.grid_size) + self.grid_size) % self.grid_size;
} else if self.y == 0 {
self.y = self.grid_size - 1;
} else {
self.y = (((self.y - 1) % self.grid_size) + self.grid_size) % self.grid_size;
}
}

fn walk(&mut self, rng: &mut ThreadRng) {
if self.grid_type == "plane" {
self.walk_on_plane(rng);
} else if self.grid_type == "torus" {
self.walk_on_torus(rng);
}
}
}

fn simulate_n_walkers_1_time(
walker_number: usize,
grid_size: usize,
grid_type: &str,
) -> Result<usize, String> {
if walker_number < 1 {
return Err("Number of walkers must be at least 1".to_string());
}

let x: usize = grid_size / 2;
let y: usize = grid_size / 2;

let mut walkers = vec![Walker::new(x, y, grid_size, grid_type)?; walker_number];
let mut grid = vec![vec![false; grid_size]; grid_size];

grid[x][y] = true;

let total_grid_cell_number: usize = grid_size * grid_size;
let mut walked_grid_cell_number: usize = 1;
let mut number_of_steps: usize = 0;

while walked_grid_cell_number < total_grid_cell_number {
number_of_steps += 1;

for walker in walkers.iter_mut().take(walker_number) {
walker.walk(rng);
let x_coordinate = walker.get_x_coordinate();
let y_coordinate = walker.get_y_coordinate();

if !grid[x_coordinate][y_coordinate] {
grid[x_coordinate][y_coordinate] = true;
walked_grid_cell_number += 1;
}
}
}

Ok(number_of_steps)
}

fn simulate_m_walkers_n_times(
number_of_trials: usize,
walker_number: usize,
grid_size: usize,
grid_type: &str,
) -> Result<usize, String> {
if number_of_trials < 1 {
return Err("Number of trials must be at least 1".to_string());
}

let mut number_of_steps = 0;

for _ in 0..number_of_trials {
number_of_steps += simulate_n_walkers_1_time(walker_number, grid_size, grid_type, rng)?;
}

Ok(number_of_steps / number_of_trials)
}

fn run_parametric_experiment(
number_of_trials: usize,
walker_number_range: (usize, usize, usize),
grid_size_range: (usize, usize, usize),
grid_type: &str,
) -> Result<Vec<Vec<usize>>, String> {
let number_of_walker_numbers =
(walker_number_range.1 - walker_number_range.0) / walker_number_range.2;
let number_of_grid_sizes = (grid_size_range.1 - grid_size_range.0) / grid_size_range.2;

let mut heat_map = vec![vec![0; number_of_walker_numbers]; number_of_grid_sizes];

let walker_number_iterator_start = walker_number_range.0;
let walker_number_iterator_end =
number_of_walker_numbers * walker_number_range.2 + walker_number_range.0;
let walker_number_iterator =
(walker_number_iterator_start..walker_number_iterator_end).step_by(walker_number_range.2);

let grid_size_iterator_start = grid_size_range.0;
let grid_size_iterator_end = number_of_grid_sizes * grid_size_range.2 + grid_size_range.0;
let grid_size_iterator =
(grid_size_iterator_start..grid_size_iterator_end).step_by(grid_size_range.2);

for (i, walker_number) in walker_number_iterator.enumerate() {
for (j, grid_number) in grid_size_iterator.clone().enumerate() {
heat_map[i][j] = simulate_m_walkers_n_times(
number_of_trials,
walker_number,
grid_number,
grid_type,
rng,
)?;
}
}

Ok(heat_map)
}


Example input:

cargo run --release 1000 11 111 10 11 111 10 torus


Example output:

Is there any way that I can improve my code?

• You appear to support only a fixed set of grid types, namely torus and plane. You should represent those as variants of an enum, not as strings. Aug 19 at 15:39

fn get_x_coordinate(&self) -> usize {
self.x
}

fn get_y_coordinate(&self) -> usize {
self.y
}


This code breaks C-GETTERS:

With a few exceptions, the get_ prefix is not used for getters in Rust code.

The get naming is used only when there is a single and obvious thing that could reasonably be gotten by a getter. For example Cell::get accesses the content of a Cell.

When dealing with coordinates, it's useful to have a Point2 or Vec2 type. You can implement Add, Sub and other useful traits for that struct.

#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
struct Point {
x: i32,
y: i32,
}

type Output = Self;

fn add(self, rhs: Point) -> Self::Output {
Point { x: self.x + rhs.x, y: self.y + rhs.y }
}
}

impl Sub<Point> for Point {
type Output = Self;

fn sub(self, rhs: Point) -> Self::Output {
Point { x: self.x + rhs.x, y: self.y + rhs.y }
}
}


With the aforementioned type, you can define possible directions to walk:

const NORTH: Point = Point { x: 0, y: -1 };
const EAST: Point = Point { x: 1, y: 0 };
const SOUTH: Point = Point { x: 0, y: 1 };
const WEST: Point = Point { x: -1, y: 0 };

const CARDINAL_DIRECTIONS: [Point; 4] = [NORTH, EAST, SOUTH, WEST];


You can also define a translate method that returns None when a Point is translated off the board and Some(Point) when it's on the board:

pub const fn translate(p1: Point, p2: Point) -> Option<Point> {
let result = p1 + p2;

if result.x < 0 || result.y < 0 || result.x > self.max.x || result > self.max.y {
None
} else {
Some(result)
}
}


Combined with rand::seq::SliceRandom::choose, you can condense your walk_on_plane method to this:

fn walk_on_plane(&mut self, rng: &mut ThreadRng) {
loop {
let delta = *CARDINAL_DIRECTIONS.choose(rng).expect("we can safely unwrap, CARDINAL_DIRECTIONS is not empty");

if let Some(next_position) = translate(self.position, delta) {
self.position = next_position
}
}
}


I don't think you need Walker at all. What you could do is manage your walkers as a Vec<Point> on your board. You could have a trait Grid like so, with specific implementations defining how to walk on it:

trait Grid {
fn walk_once(&mut self, position: Point) -> Point;
fn walkers(&mut self) -> &mut Vec<Point>;
fn iterate(&mut self) {
*self.walkers() =
self.walkers()
.into_iter()
.map(|p| self.walk_once(*p))
.collect::<Vec<_>>()
}
}

struct Euclidian {
walkers: Vec<Point>,
min: Point,
max: Point,
rng: Box<dyn RngCore>,
}

impl Grid for Euclidian {
fn walk_once(&mut self, position: Point) -> Point {
loop {
let delta = *CARDINAL_DIRECTIONS.choose(&mut self.rng).expect("we can safely unwrap, CARDINAL_DIRECTIONS is not empty");
if let Some(next_position) = translate(position, delta) {
return next_position;
}
}
}

fn walkers(&mut self) -> &mut Vec<Point> {
&mut self.walkers
}
}


String as an Error type is marginal at best. Follow C-GOOD-ERR. Generally, it's a good idea to make your errors enums and have them be Error + Send + Sync + 'static. When naming errors, keep in mind C-WORD-ORDER. Please note that, as discussed, the Walker type is flawed in other ways, this is just to demonstrate an example of error handling.

#[derive(Debug)]
enum InitWalkerError {
GridSizeIsZero,
XOutOfBounds { actual: usize, expected: usize },
YOutOfBounds { actual: usize, expected: usize },
UnknownGrid { actual: String, expected: Vec<String> },
}

impl Display for InitWalkerError {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
match self {
InitWalkerError::GridSizeIsZero => write!(f, "grid size is zero"),
InitWalkerError::XOutOfBounds { expected, actual } => write!(f, "x should be smaller or equal to {}, was {}", expected, actual),
InitWalkerError::YOutOfBounds { expected, actual } => write!(f, "y should be smaller or equal to {}, was {}", expected, actual),
InitWalkerError::UnknownGrid { expected, actual } => write!(f, "grid should be one of {:?}, was \"{}\"", expected, actual),
}
}
}

impl Error for InitWalkerError {}

impl Walker {
fn new(x: usize, y: usize, grid_size: usize, grid_type: &str) -> Result<Self, InitWalkerError> {
if grid_size < 1 {
Err(InitWalkerError::GridSizeIsZero)
} else if x >= grid_size {
Err(InitWalkerError::XOutOfBounds { expected: grid_size, actual: x })
} else if y >= grid_size {
Err(InitWalkerError::YOutOfBounds { expected: grid_size, actual: y })
} else if grid_type != "plane" && grid_type != "torus" {
Err(InitWalkerError::UnknownGrid { expected: vec!["plane".to_string(), "torus".to_string()], actual: grid_type.to_string() })
} else {
Ok(Walker {
...
})
}
}
...
}


There are probably more things to discuss, but here are some of my thoughts. Please excuse me for being a bit all over the place with this, I hope it's still helpful. I haven't ran the example code, so it might have some issues, but I hope you get the gist.