3
\$\begingroup\$

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:

enter image description here

Is there any way that I can improve my code?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Aug 19, 2023 at 15:39

1 Answer 1

2
\$\begingroup\$
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.