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

Question

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::rngs::ThreadRng;
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 mut rng = rand::thread_rng();

    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.add_trace(trace);
    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,
    rng: &mut ThreadRng,
) -> 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,
    rng: &mut ThreadRng,
) -> 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,
    rng: &mut ThreadRng,
) -> 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?

Answer 1

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,
}

impl Add<Point> for Point {
    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.