As a learning exercise I wrote a small module that solves the Knight's tour problem. Please review my code.
this is the module code from knights\mod.rs
file:
use std::fmt;
pub struct Desk {
x: i32,
y: i32,
max_step: i32,
desk: Vec<Vec<i32>>,
}
impl Desk {
pub fn new(x: i32, y: i32) -> Self {
Desk {
x: x,
y: y,
max_step: x * y,
desk: vec![vec![0; x as usize]; y as usize]
}
}
pub fn find_first(&mut self, x: i32, y: i32) -> bool {
self.find_first_internal(x, y, 1)
}
fn find_first_internal(&mut self, x: i32, y: i32, mut step: i32) -> bool {
if x < 0 || y < 0 || x >= self.x || y >= self.y || self.desk[y as usize][x as usize] > 0 {
false
} else {
self.desk[y as usize][x as usize] = step;
step += 1;
let res = step > self.max_step
|| self.find_first_internal(x + 1, y + 2, step)
|| self.find_first_internal(x + 1, y - 2, step)
|| self.find_first_internal(x - 1, y + 2, step)
|| self.find_first_internal(x - 1, y - 2, step)
|| self.find_first_internal(x + 2, y + 1, step)
|| self.find_first_internal(x + 2, y - 1, step)
|| self.find_first_internal(x - 2, y + 1, step)
|| self.find_first_internal(x - 2, y - 1, step)
;
if !res {
self.desk[y as usize][x as usize] = 0;
}
res
}
}
}
impl fmt::Display for Desk {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let mut s = String::new();
for y in 0..self.y {
for x in 0..self.x {
s.push_str(&format!("{:02} ", self.desk[y as usize][x as usize]));
}
s.push_str("\n\n");
}
write!(f, "{}", s)
}
}
and this is how I use it in the main.rs
mod knights;
use std::time::Instant;
use std::io;
fn main() {
println!("Enter four numbers: desk dimensions and first step coordinates");
let mut input = String::new();
io::stdin().read_line(&mut input).expect("Failed to read line");
let mut iter = input.split_whitespace();
let mut desk = {
let x: i32 = iter.next().unwrap().parse().unwrap();
let y: i32 = iter.next().unwrap().parse().unwrap();
knights::Desk::new(x, y)
};
let start;
let res = {
let x: i32 = iter.next().unwrap().parse().unwrap();
let y: i32 = iter.next().unwrap().parse().unwrap();
start = Instant::now();
desk.find_first(x, y)
};
let elapsed = start.elapsed();
if res {
println!("\n{}", desk);
} else {
println!("Can't knight all desk");
}
println!("Working time {:?} milliseconds.", (elapsed.as_secs() * 1_000) + (elapsed.subsec_nanos() / 1_000_000) as u64);
}
Questions:
-
I see a big performance gap between debug and release builds. I suspect this is mainly because of using vector of vectors instead of two dimensional array or a slice of slices. Is it true? How can I make such an array or a slice of slices with variable size by a one line code? When I tried to init it like
&mod vec![&mod vec![0; y as usize]; x as usize]
I got a compilation error saying that &mod of Vec doesn't implement Clone. Is there some other macro that allows to make&mod [&mod [<T>]]
? -
There is a warning (or just a suggestion from the intellij-rust plugin) that following two lines of the constructor could be simplified but I don't understand how.
x: x, y: y,
It points to this https://github.com/rust-lang/rfcs/blob/master/text/1682-field-init-shorthand.md
- Why Rust doesn't support function overloading, i.e. having two functions with the same name but with different signatures? I prefer the
find_first_internal()
function to be named asfind_first
too.
Any other comments about the code are welcome.
P.S. how to make a preformatted text in this message colored according to Rust or other programming language syntax?