Пошук в глибину на прикладі задачі Ханойської вежі використовуючи Rust
Повна версія
Пошук в глибину на прикладі задачі Ханойської вежі використовуючи Rust
Підписуйтеся наTelegram-канал «DOU #tech», щоб не пропустити нові технічні статті.
Привіт, мене звати Ярослав, займаюсь розробкою в компанії Evrius.
Стаття орієнтована на спеціалістів які хочуть ознайомитись з Rust-ом або в
майбутньому перекваліфікуватись на Rust-розробників, як і я.
Короткий переказ
«Ханойські вежі»
Будуть ілюстрації, налаштування Rust та створення першого проекту, а також
написання тестів та пояснення деталей.
В кінці статті будуть посилання на навчальні матеріали а в коментарях відповім
на питання стосовно статті.
За бажання можете відразу глянути репозиторій, а потім повернутись до читання.
Оригінальна стаття також українською мовою та з ілюстраціями на dev.to, рекомендую читати оригінал із-за ілюстрацій а також кращого форматування коду.
Ханойські вежі
Щоб зрозуміти рішення задачі то почнемо з одного диску який перекладаємо з першого на третій стержень.
Для двох дисків:
перекладаємо верхній перший диск на другий стержень,
другий диск з першого на третій стержень,
перший диск з другого на третій стержень,
ось і все.
Для трьох дисків рішення рекурсивне: важаємо нижній диск за другий, а всі
верхні диск за «один» і так само вирішуємо для них рекурсивно.
Число рухів для 1 диску = 1 раз перекладаємо диск
Число рухів для 2 дисків = 3, де 2 рази перекладаємо верхній диск і 1 раз
нижній
Число рухів для N дисків має відносну формулу TN = 2 × TN-1 + 1
Число рухів для N дисків має абсолютну формулу TN = 2N — 1
Пошук в глибину на прикладі задачі Ханойської вежі
вікіпедії
Rust та створення першого проекту
Install Rust
sudo apt update
curl https://sh.rustup.rs -sSf | sh
source $HOME/.cargo/env
rustup rustc cargo
rustup --version
# rustup 1.21.1 (7832b2ebe 2019-12-20)
rustc --version
# rustc 1.44.1 (c7087fe00 2020-06-17)
cargo --version
# cargo 1.44.1 (88ba85757 2020-06-11)
cargo init dfs-tower-of-hahoi
cargo init --bin dfs-tower-of-hahoi
# Created binary (application) package
tree dfs-tower-of-hahoi
dfs-tower-of-hahoi
├── Cargo.toml
└── src
└── main.rs
main rs Cargo.toml
cat dfs-tower-of-hahoi/src/main.rs dfs-tower-of-hahoi/Cargo.toml
fn main() {
println!("Hello, world!");
}
[package]
name = "dfs-tower-of-hahoi"
version = "0.1.0"
authors = ["Yaroslav"]
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
.rs* .rs Сербії Actix.rs
.toml* TOML
cd ./dfs-tower-of-hahoi
cargo run
Hello, world!
Hello, world!
fn main() {
println!("Hello, world!");
}
main C-подібних
println! println! !
макроси гігієни макросів
Починаємо рішення з вибору структур
S BEGIN S END
Потім на основі початкового стану S BEGIN формуємо всі можливі стани S NEXT 1-N (де N число стержнів), потім на основі станів S NEXT 1-N формуємо наступні стани і так далі, до моменту досягнення S END.
Для початку нам треба описати стержень з якого будемо брати або класти верхній
диск, як бачимо це опис структури LIFO.
В Rust є Vector який має потрібні нам методи pop() та push() , отож
маємо структуру для стержня Rod :
struct Rod {
disks: Vec<u8>,
}
struct State {
rods: Vec<Rod>,
}
fn main() {
let begin = State {
rods: vec![
Rod {
disks: vec![3, 2, 1],
},
Rod { disks: vec![] },
Rod { disks: vec![] },
],
};
let end = State {
rods: vec![
Rod { disks: vec![] },
Rod { disks: vec![] },
Rod {
disks: vec![3, 2, 1],
},
],
};
println!("Tower of Hanoi begin state {:?}", begin);
println!("Tower of Hanoi end state {:?}", end);
}
vec! {:?}
let
cargo run
error[E0277]: `State` doesn't implement `std::fmt::Debug`
--> src/main.rs:30:49
|
30 | println!("Tower of Hanoi begin state {:?}", begin);
| ^^^^^ `State` cannot be formatted using `{:?}`
|
= help: the trait `std::fmt::Debug` is not implemented for `State`
= note: add `#[derive(Debug)]` or manually implement `std::fmt::Debug`
std::fmt::Debug
note: add
#[derive(Debug)]or manually implementstd::fmt::Debug
типаж std::fmt::Debug , як і інші типажі, схожий на інтерфейс в інших мовах програмування
pub trait Debug {
fn fmt(&self, f: &mut Formatter<'_>) -> Result;
}
std::fmt::Debug
use std::fmt::{Debug, Formatter, Result};
struct State {
rods: Vec<Rod>,
}
impl Debug for State {
fn fmt(&self, f: &mut Formatter) -> Result {
return write!(f, "`manually debug with rods {}`", self.rods.len());
}
}
use Debug
impl Debug for State
Tower of Hanoi begin state `manually debug with rods 3`
Tower of Hanoi end state `manually debug with rods 3`
атрибут #[derive(Debug)]
#[derive(Debug)]
struct Rod {
disks: Vec<u8>,
}
#[derive(Debug)]
struct State {
rods: Vec<Rod>,
}
fn main() {
let begin = State {
rods: vec![
Rod {
disks: vec![3, 2, 1],
},
Rod { disks: vec![] },
Rod { disks: vec![] },
],
};
let end = State {
rods: vec![
Rod { disks: vec![] },
Rod { disks: vec![] },
Rod {
disks: vec![3, 2, 1],
},
],
};
println!("Tower of Hanoi begin state {:?}", begin);
println!("Tower of Hanoi end state {:?}", end);
}
cargo run
Tower of Hanoi begin state State { rods: [Rod { disks: [3, 2, 1] }, Rod { disks: [] }, Rod { disks: [] }] }
Tower of Hanoi end state State { rods: [Rod { disks: [] }, Rod { disks: [] }, Rod { disks: [3, 2, 1] }] }
derive
Рефакторинг: виносимо число дисків в константу
disks: vec![3, 2, 1]
const TOWER_SIZE: u8 = 7;
fn main() {
println!("Tower of Hanoi with size {}", TOWER_SIZE);
// alternative
// let disks: Vec<u8> = (1..=TOWER_SIZE).rev().collect();
// let disks: Vec<u8> = (1..=TOWER_SIZE).rev().collect::<Vec<u8>>();
let disks = (1..=TOWER_SIZE).rev().collect::<Vec<u8>>();
let begin = State {
rods: vec![
Rod {
disks: disks.clone(),
},
Rod { disks: vec![] },
Rod { disks: vec![] },
],
};
let end = State {
rods: vec![
Rod { disks: vec![] },
Rod { disks: vec![] },
Rod { disks: disks },
],
};
println!("Tower of Hanoi begin state {:?}", begin);
println!("Tower of Hanoi end state {:?}", end);
}
const
1..=TOWER_SIZE ..= start..=end start ≤ x ≤ end range
expressions
(1..=TOWER_SIZE).rev()
collect з документації
ransforms an iterator into a collection.
collect() can take anything iterable, and turn it into a relevant collection. This is one of the more powerful methods in the standard library, used in a variety of contexts.
в нашому випадку collect перетворює послідовність типу RangeInclusiveExpr в
Vec
І залишилось розібрати тільки disks.clone() який потрібний для повного копіювання бо інакше відбувається передача володіння над змінною disks і подальше використання disks буде помилкою про яку повідомить компілятор, це така особливість Rust яка підвищує безпеку.
Формуємо всі можливі стани з початкового
fn get_next_states(state: &State) -> Vec<State> {
let rods = state.rods.len();
let result = vec![];
for from_index in 0..rods {
for to_index in 0..rods {
// @TODO create next state and push to vector
}
}
return result;
}
0..rods start..end = start ≤ x < end
vec!
@TODO create_state_by_move_disk
fn create_state_by_move_disk(
state: &State,
from_rod_index: usize,
to_rod_index: usize,
) -> Option<State> {
if from_rod_index == to_rod_index {
return Option::None;
}
let from_rod = &state.rods[from_rod_index];
let from_rod_length = from_rod.disks.len();
if from_rod_length == 0 {
// cannot move from empty rod
return Option::None;
}
let to_rod = &state.rods[to_rod_index];
let to_rod_length = to_rod.disks.len();
if to_rod_length == 0 || from_rod.disks[from_rod_length - 1] < to_rod.disks[to_rod_length - 1] {
let mut result = state.clone();
let disk = result.rods[from_rod_index].disks.pop().unwrap();
result.rods[to_rod_index].disks.push(disk);
return Option::Some(result);
}
return Option::None;
}
create_state_by_move_disk
- ми передаємо в функцію вказівник & State бо передаючи просто State ми б передавали володіння
- функція повертає Option
, де Option це обгортка всередині якої може бути значення заданого типу, в данному випадку типу State
Option
fn checked_division(dividend: i32, divisor: i32) -> Option<i32> {
if divisor == 0 {
// Failure is represented as the `None` variant
return Option::None;
} else {
// Result is wrapped in a `Some` variant
return Option::Some(dividend / divisor);
}
}
create_state_by_move_disk
result Option::None
let mut result = state.clone();
let disk = result.rods[from_rod_index].disks.pop().unwrap();
result.rods[to_rod_index].disks.push(disk);
return Option::Some(result);
let
Variables in Rust are immutable by default, and require the mut keyword to be made mutable.
тому ми об’являємо let mut result , щоб мати змогу змінювати змінну
result
друге це метод pop() структури std::vec::Vec , pop() видаляє і повертає
останній елемент вектору, якщо останній елемент є
звісно вектор може бути пустий і тому pop() повертає Option
далі метод unwrap() обгортки Option, unwrap() повертає збережене всередині
значення, а воно є бо ми це перевірили раніше
якби вектор був пустий і ми виконали .pop().unwrap() то отримали б паніку,
майте це на увазі
якщо ви були уважні то помітили що у структури State відсутній метод
clone який використовую
метод clone потрібний для копіювання стержнів а також дисків і це дуже просто
зробити перебором:
#[derive(Debug)]
struct Rod {
disks: Vec<u8>,
}
impl Rod {
fn clone(&self) -> Self {
return Rod {
disks: self.disks.clone(),
};
}
}
#[derive(Debug)]
struct State {
rods: Vec<Rod>,
}
impl State {
fn clone(&self) -> Self {
let mut rods = Vec::with_capacity(self.rods.len());
for rod in &self.rods {
rods.push(rod.clone());
}
return State { rods: rods };
}
}
derive Clone
#[derive(Debug, Clone)]
struct Rod {
disks: Vec<u8>,
}
#[derive(Debug, Clone)]
struct State {
rods: Vec<Rod>,
}
create_state_by_move_disk
fn get_next_states(state: &State) -> Vec<State> {
let rods = state.rods.len();
let mut result = vec![];
for from_index in 0..rods {
for to_index in 0..rods {
if from_index != to_index {
match create_state_by_move_disk(state, from_index, to_index) {
Option::Some(next) => {
result.push(next);
}
Option::None => {
// NOP
}
}
}
}
}
return result;
}
match match
#[derive(Debug, Clone)]
struct Rod {
disks: Vec<u8>,
}
#[derive(Debug, Clone)]
struct State {
rods: Vec<Rod>,
}
const TOWER_SIZE: u8 = 7;
fn main() {
println!("Tower of Hanoi with size {}", TOWER_SIZE);
let disks = (1..=TOWER_SIZE).rev().collect::<Vec<u8>>();
let begin = &State {
rods: vec![
Rod {
disks: disks.clone(),
},
Rod { disks: vec![] },
Rod { disks: vec![] },
],
};
let end = &State {
rods: vec![
Rod { disks: vec![] },
Rod { disks: vec![] },
Rod { disks: disks },
],
};
println!("Tower of Hanoi begin state {:?}", begin);
println!("Tower of Hanoi end state {:?}", end);
let next_states = get_next_states(&begin);
for next_state in next_states {
println!("Tower of Hanoi next state {:?}", next_state);
}
}
fn get_next_states(state: &State) -> Vec<State> {
let rods = state.rods.len();
let mut result = vec![];
for from_index in 0..rods {
for to_index in 0..rods {
if from_index != to_index {
match create_state_by_move_disk(state, from_index, to_index) {
Some(next) => {
result.push(next);
}
None => {
// NOP
}
}
}
}
}
return result;
}
fn create_state_by_move_disk(
state: &State,
from_rod_index: usize,
to_rod_index: usize,
) -> Option<State> {
if from_rod_index == to_rod_index {
return None;
}
let from_rod = &state.rods[from_rod_index];
let from_rod_length = from_rod.disks.len();
if from_rod_length == 0 {
// cannot move from empty rod
return None;
}
let to_rod = &state.rods[to_rod_index];
let to_rod_length = to_rod.disks.len();
if to_rod_length == 0 || from_rod.disks[from_rod_length - 1] < to_rod.disks[to_rod_length - 1] {
let mut result = state.clone();
let disk = result.rods[from_rod_index].disks.pop().unwrap();
result.rods[to_rod_index].disks.push(disk);
return Some(result);
}
return None;
}
Повертаємо тільки унікальні стани
HashSet
Отож так само генеруємо можливі стани та відфільтровуємо вже повернуті раніше, які були збережені в HashSet.
Елементи HashSet мають реалізувати типаж Hash (який в Rust-і вже реалізований
для багатьох типів даних, строкових та числових).
І ми можемо реалівувати типаж Hash для структури State або серіалізувати
структуру State в строку або число (які реалізують Hash).
Отже серіалізуємо State в 128-бітне число u128 і напишемо тест:
const DISK_BIT_SIZE: u8 = 4;
impl State {
fn serialize(&self) -> u128 {
let disk_bit_size: u128 = DISK_BIT_SIZE as u128;
let mut result: u128 = 0;
let mut shift: u128 = 0;
for rod in &self.rods {
for &disk in &rod.disks {
result |= (disk as u128) << shift;
shift += disk_bit_size;
}
// delimiter between rods
shift += disk_bit_size;
}
return result;
}
}
unit testing
#[cfg(test)]
mod state_test {
use super::*;
#[test]
fn serialize() {
{
let state = State { rods: vec![] };
assert_eq!(0, state.serialize());
}
{
let state = State {
rods: vec![Rod {
disks: vec![3, 2, 1],
}],
};
// alternatives
// assert_eq!(0b0001_0010_0011, state.serialize());
assert_eq!(0x1_2_3, state.serialize());
}
{
let state = State {
rods: vec![
Rod { disks: vec![5, 4] },
Rod { disks: vec![] },
Rod {
disks: vec![3, 2, 1],
},
],
};
// alternatives
// assert_eq!(0b0001_0010_0011_0000_0000_0100_0101, state.serialize());
assert_eq!(0x1_2_3_0_0_4_5, state.serialize());
}
}
}
#[cfg(test)] #[test] assert_eq!
cargo test
running 1 test
test state_test::serialize ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
struct UniqueStateGenerator {
past: HashSet<u128>,
}
impl UniqueStateGenerator {
fn new() -> UniqueStateGenerator {
return UniqueStateGenerator {
past: HashSet::new(),
};
}
fn get_next_states(&mut self, state: &State) -> Vec<State> {
let rods = state.rods.len();
let mut result = vec![];
for from_index in 0..rods {
for to_index in 0..rods {
match create_state_by_move_disk(state, from_index, to_index) {
Some(next) => {
if self.unique(next.serialize()) {
result.push(next);
}
}
None => {
// NOP
}
}
}
}
return result;
}
fn unique(&mut self, value: u128) -> bool {
return self.past.insert(value);
}
}
fn main() {
// ... unchanged code
let mut generator = UniqueStateGenerator::new();
{
let next_states = generator.get_next_states(&begin);
println!("Tower of Hanoi next states {}", next_states.len());
for next_state in next_states {
println!("Tower of Hanoi next state {:?}", next_state);
}
}
{
let next_states = generator.get_next_states(&begin);
println!("Tower of Hanoi next states {}", next_states.len());
for next_state in next_states {
println!("Tower of Hanoi next state {:?}", next_state);
}
}
}
cargo run
Tower of Hanoi next states 2
Tower of Hanoi next states 0
Реалізація пошуку в глибину
struct DeepFirstSearch {
begin: State,
end: State,
unique_state_generator: UniqueStateGenerator,
}
impl DeepFirstSearch {
fn new(begin: State, end: State, unique_state_generator: UniqueStateGenerator) -> Self {
return DeepFirstSearch {
begin,
end,
unique_state_generator,
};
}
fn search(&mut self) -> bool {
return self.search_by_state(self.begin.clone());
}
fn search_by_state(&mut self, state: State) -> bool {
if state == self.end {
return true;
}
for next_state in self.unique_state_generator.get_next_states(&state) {
if self.search_by_state(next_state) {
return true;
}
}
return false;
}
}
fn main() {
// ... unchanged code
let generator = UniqueStateGenerator::new();
let mut searcher = DeepFirstSearch::new(begin, end, generator);
println!(
"Tower of Hanoi deep first search result {}",
searcher.search()
);
}
Tower of Hanoi with size 7
Tower of Hanoi deep first search result true
state == self.end
#[derive(Debug, Clone, PartialEq)]
struct Rod {
disks: Vec<u8>,
}
#[derive(Debug, Clone, PartialEq)]
struct State {
rods: Vec<Rod>,
}
Перевірка правильності рішення
Для перевірки рішення треба зберігати в журнал дії переміщення диска між стержнями,а потім використавши журнал повторити дії починаючи від початкового стану і перевірити що кінцевий стан буде очікуваним.
Цю просту перевірку спробуйте написати самостійно, а весь код для повної картини можете глянути у відкритомувідкритому репозиторії.
Пошук у ширину на прикладі задачі Ханойської вежі
пошуку у ширину
struct BreadthFirstSearch {
begin: State,
end: State,
unique_state_generator: UniqueStateGenerator,
}
impl BreadthFirstSearch {
fn new(begin: State, end: State, unique_state_generator: UniqueStateGenerator) -> Self {
return BreadthFirstSearch {
begin,
end,
unique_state_generator,
};
}
fn search(&mut self) -> bool {
let mut queue = vec![];
self.unique_state_generator.unique(self.begin.serialize());
queue.push(self.begin.clone());
while queue.len() > 0 {
let current_state = queue.pop().unwrap();
if current_state == self.end {
return true;
}
queue.extend(self.unique_state_generator.get_next_states(¤t_state));
}
return false;
}
}
Епілог
випередили.
Олексію Cossack Labs Rust
Людмилі Тіторенко
Навчальні матеріали:
- [YouTube] Rust Programming Tutorial
- [Book] Programming Rust: Fast, Safe Systems Development
- Tour of Rust
- Rust by Example
- [Book] The Rust Programming Language
- Класичне рішення «Ханойської вежі»
Hello Rust!
Оригінал на dev.to
