3
\$\begingroup\$

What do you think of using struct Board(Vec<Vec<Cell>>)? It's nice that I can attach the Display trait, and just print the board.

But on the flip-side, we have things that seem wrong, like:

fn next_step(b: Board) -> Board {
    let Board(mut board) = b;
    // ...
    Board(board)
}

And I couldn't find a way to pass a Board (or a reference to one) to nr_of_neighbors. Moving the Vec out in next_step (or similarly when using a mutable reference there), prevented me from doing that. Or am I missing something?

Any additional feedback welcome as well!

  • Note: it's a Vec instead of an array in case I add the feature that the player can choose the board size interactively.
  • I know the as i64 isn't that great. Not sure though what's a nice, practical and concise way of dealing with that though.

Complete working code

Should run in any ANSI-compatible terminal.

use itertools::join;
use std::fmt;
use std::{thread, time};

#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Cell { Aliv, Dead }
impl fmt::Display for Cell {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Cell::Aliv => write!(f, "x"),
            Cell::Dead => write!(f, " "),
        }
    }
}

struct Board(Vec<Vec<Cell>>);
impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let Board(vec) = self;
        let str = join(vec.into_iter().map(|row| join(row, "|")), "\n");
        write!(f, "{}", str)
    }
}


fn main() {
    let mut board = Board(vec![
        vec![Cell::Aliv, Cell::Aliv, Cell::Aliv, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Aliv, Cell::Dead, Cell::Aliv, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Aliv, Cell::Aliv, Cell::Aliv, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Dead, Cell::Aliv, Cell::Aliv, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        vec![Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
    ]);

    loop {
        print!("{esc}[2J{esc}[1;1H", esc = 27 as char); // clear ANSI-compatible terminal
        println!("{}", board);
        board = next_step(board);
        thread::sleep(time::Duration::from_secs(1));
    }
}

fn next_step(b: Board) -> Board {
    let Board(mut board) = b;
    for x in 0..board.len() {
        for y in 0..board[x].len() {
            let n = nr_of_neighbors(&board, x, y);
            let cell = board[x][y];
            if cell == Cell::Aliv && (n == 2 || n == 3) {
                // survives
            } else if cell == Cell::Dead && n == 3 {
                board[x][y] = Cell::Aliv;
            } else {
                board[x][y] = Cell::Dead;
            }
        }
    }
    Board(board)
}

fn nr_of_neighbors(board: &Vec<Vec<Cell>>, current_x: usize, current_y: usize) -> u32 {
    let cur_x = current_x as i64;
    let cur_y = current_y as i64;
    let mut count: u32 = 0;
    for x in cur_x-1..cur_x+2 {
        for y in cur_y-1..cur_y+2 {
            if x >=0 && y >= 0
                    && x < board.len() as i64 && y < board[x as usize].len() as i64
                    && !(x == cur_x && y == cur_y)
                    && board[x as usize][y as usize] == Cell::Aliv {
                count = count + 1;
            }
        }
    }
    count
}

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

On your notes:

  • Problems with u64/u32 got fixed once I started using usize everywhere.

  • Board shouldn't be copied every time in next_step, &mut Board could be used instead.

  • next_step, as well as nr_of_neighbors could be a methods.

Bugs:

  • There is a bug in calculating number of neighbors: your condition !(x == cur_x && y == cur_y) is equivalent to x != cur_x || y != cur_y, which is not intended.

  • There is a problem with your algorithm: it depends on the order of the iteration, when you should really apply changes to the new board.

Notes about the code below

  • You are using newtype pattern to implement traits that you need on the type that doesn't do it itself. I advise you to look into derive_more crate. Basically, I derived a Deref implementation in order not to write it myself. That way, everywhere where &Board is used, it can be coerced to &Vec> so you don't have to write self.0[x] to access a row.

Resulting code

use std::fmt;
use std::{thread, time};

use itertools::join;
use itertools::Itertools;

use derive_more::Deref;

#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Cell {
    Alive,
    Dead,
}

impl fmt::Display for Cell {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Cell::Alive => write!(f, "x"),
            Cell::Dead => write!(f, " "),
        }
    }
}

#[derive(Deref)]
struct Board(Vec<Vec<Cell>>);

impl Board {
    fn nr_of_neighbors(&self, cur_x: usize, cur_y: usize) -> usize {
        let x_min = cur_x.saturating_sub(1);
        let y_min = cur_y.saturating_sub(1);

        let x_max = (cur_x + 2).min(self.len() - 1);
        let y_max = (cur_y + 2).min(self.len() - 1);

        (x_min..x_max)
            .cartesian_product(y_min..y_max)
            .filter(|&(x, y)| x != cur_x && y != cur_y && self[x][y] == Cell::Alive)
            .count()
    }

    fn next_step(&mut self) {
        let mut new_board = self.clone();

        for x in 0..self.len() {
            for y in 0..self[x].len() {
                let n = self.nr_of_neighbors(x, y);
                let cell = self[x][y];

                if cell == Cell::Alive && (n == 2 || n == 3) {
                    // survives
                } else if cell == Cell::Dead && n == 3 {
                    new_board[x][y] = Cell::Alive;
                } else {
                    new_board[x][y] = Cell::Dead;
                }
            }
        }

        self.0 = new_board;
    }
}

impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", join(self.iter().map(|row| join(row, "|")), "\n"))
    }
}

fn main() {
    #[rustfmt::skip]
        let mut board = Board(vec![
            vec![Cell::Alive, Cell::Alive, Cell::Alive, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Alive, Cell::Dead,  Cell::Alive, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Alive, Cell::Alive, Cell::Alive, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Dead,  Cell::Alive, Cell::Alive, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Dead,  Cell::Dead,  Cell::Dead,  Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Dead,  Cell::Dead,  Cell::Dead,  Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Dead,  Cell::Dead,  Cell::Dead,  Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Dead,  Cell::Dead,  Cell::Dead,  Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Dead,  Cell::Dead,  Cell::Dead,  Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
            vec![Cell::Dead,  Cell::Dead,  Cell::Dead,  Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead, Cell::Dead],
        ]);

    loop {
        print!("{esc}[2J{esc}[1;1H", esc = 27 as char); // clear ANSI-compatible terminal
        println!("{}\n", board);
        board.next_step();
        thread::sleep(time::Duration::from_secs(1));
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ very cool thanks! I didn't know about saturating_sub and derive_more of course... hm.. but you still have to copy the whole board new_board = self.clone(); which doesn't seem very efficient? or is it some lazy cloning? couldn't find what clone does for Vec in the docs... \$\endgroup\$
    – mb21
    Apr 14, 2020 at 15:45
  • \$\begingroup\$ @mb21, that's not about efficiency, but correctness of algorithm - you can't mutate the board you are currently working on. I believe there is a dynamic programming solution, but I'm not sure. There could be 2 Vecs inside the Board, so that you don't reallocate every iteration and at the end of next_step you just make a swap. Or a cell can contain two states - current and future, which will improve data locality. If you care about efficiency I recommend using Vec<Cell> instead of Vec<Vec<Cell>>, so that there's no extra indirection. \$\endgroup\$
    – rogday
    Apr 14, 2020 at 16:18
  • \$\begingroup\$ Ah, of course. Can't believe I missed that... have been working too much with immutable structures (in other langs). One last question: is using methods instead of functions generally favoured in Rust? or is it more of a stylistic choice, where OOP people use methods and functional people use functions? \$\endgroup\$
    – mb21
    Apr 15, 2020 at 7:01
  • \$\begingroup\$ @mb21 I think it's a choice, but I'm learning rust just like you. \$\endgroup\$
    – rogday
    Apr 15, 2020 at 14:27
3
\$\begingroup\$

Generally, you should only put a Vec inside of a Vec if the inner Vec will have a dynamic size. Otherwise, you lose a lot of performance due to indirection (you have a pointer to an array of pointers, which points to each row), which screws with the CPU cache. Instead, you should use a single Vec which has a size of width * height. This pattern is so common that there's a crate to do just that—ndarray (see also this). However, you could also write your own wrapper functions that multiply the column by the width and add the height.

is using methods instead of functions generally favoured in Rust? or is it more of a stylistic choice, where OOP people use methods and functional people use functions?

It really depends. When using the newtype pattern (which you are), absolutely use methods—it's the most ergonomic option. However, using free functions is a great idea when working with other types where it doesn't make sense to have a struct. You should think of structs as data, not logic. Using a struct to hold data and using functions to operate on that data is great. However, using a struct to hold logic generally means that you should rethink your layout. That's not always the case, but is a good start.

\$\endgroup\$
0

Your Answer

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

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