Пошук в глибину на прикладі задачі Ханойської вежі використовуючи Rust
Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Привіт, мене звати Ярослав, займаюсь розробкою в компанії Evrius.
Стаття орієнтована на спеціалістів які хочуть ознайомитись з Rust-ом або в майбутньому перекваліфікуватись на Rust-розробників, як і я.
Короткий переказ
Стаття буде про вирішення задачі «Ханойські вежі» через пошук в глибину, з використанням стандартних структур даних наявних в Rust з детальним описом що роблю і тому буде зрозуміла спеціалістам без досвіду з Rust-ом.Будуть ілюстрації, налаштування Rust та створення першого проекту, а також написання тестів та пояснення деталей.
В кінці статті будуть посилання на навчальні матеріали а в коментарях відповім на питання стосовно статті.
За бажання можете відразу глянути репозиторій, а потім повернутись до читання.
Оригінальна стаття також українською мовою та з ілюстраціями на dev.to, рекомендую читати оригінал із-за ілюстрацій а також кращого форматування коду.
Ханойські вежі
Ханойські вежі — математична гра, де є три стержні і диски різних розмірів,на першому стержні розміщені диски у вигляді вежі яка збільшується зверху вниз,
інші два стержні порожні,
ціль задачі перенести диски з першого на третій стержень використовуючи другий,
можна переносити тільки один диск за раз,
забороняється класти диски більшого розміру на менший.
Щоб зрозуміти рішення задачі то почнемо з одного диску який перекладаємо з першого на третій стержень.
Для двох дисків:
перекладаємо верхній перший диск на другий стержень,
другий диск з першого на третій стержень,
перший диск з другого на третій стержень,
ось і все.
Для трьох дисків рішення рекурсивне: важаємо нижній диск за другий, а всі верхні диск за «один» і так само вирішуємо для них рекурсивно.
Число рухів для 1 диску = 1 раз перекладаємо диск
Число рухів для 2 дисків = 3, де 2 рази перекладаємо верхній диск і 1 раз нижній
Число рухів для N дисків має відносну формулу TN = 2 × TN-1 + 1
Число рухів для N дисків має абсолютну формулу TN = 2N — 1
Пошук в глибину на прикладі задачі Ханойської вежі
Пошук у глибину (або Depth-first search або DFS) — алгоритм для обходу дерева, це класичне визначення з вікіпедії.Пошук у глибину можна адаптувати для рішення задачі «Ханойської вежі», це одна з лабораторних робіт у студентів з напряму комп’ютерні науки.
Ми беремо початковий стан де N-дисків лежать на першому стержні та використовуючи правила гри будуємо всі можливі стани і так до досягнення стану коли всі диски будуть на третьому стержні.
Rust та створення першого проекту
Встановлення з офіційної сторінки Install Rust:sudo apt update curl https://sh.rustup.rs -sSf | sh source $HOME/.cargo/env
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 --bin dfs-tower-of-hahoi # Created binary (application) package
tree dfs-tower-of-hahoi
dfs-tower-of-hahoi ├── Cargo.toml └── src └── main.rs
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]
розширення файлу *.toml викорстовується для збереження налаштувань у форматі TOML (Tom’s Obvious, Minimal Language)
тепер перейдемо в папку проекту і запустимо проект:
cd ./dfs-tower-of-hahoi cargo run
Hello, world!
fn main() {
println!("Hello, world!");
}а от конструкція println! є новою, println! це макрос, це помітно з того що завершуються символом оклику «!»
макроси будуть знайомі C та C++ розробникам, в Rust-і макроси теж є, писати їх складніше, зате безпечніше із-за гігієни макросів.
Починаємо рішення з вибору структур
Вже писав раніше, та повторюсь, нам треба описати початковий стан де N-дисків лежать на першому стержні SBEGIN та кінцевий стан де всі диски на останньому стержні SEND.Потім на основі початкового стану SBEGIN формуємо всі можливі стани SNEXT
Для початку нам треба описати стержень з якого будемо брати або класти верхній диск, як бачимо це опис структури 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);
}ключове слово let потрібно щоб об’явити змінну (так само як і в JavaScript)
тепер через 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`
note: add `#[derive(Debug)]` or manually implement `std::fmt::Debug`
типаж std::fmt::Debug, як і інші типажі, схожий на інтерфейс в інших мовах програмування
pub trait Debug {
fn fmt(&self, f: &mut Formatter<'_>) -> Result;
}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());
}
}так в цьому коді ще багато нових конструкцій, але в данному випадку цей код є лише прикладом реалізації типажу через 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)]
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] }] }
Рефакторинг: виносимо число дисків в константу
Зараз в коді зашито число дисків у векторі 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);
}в коді 1..=TOWER_SIZE використовується конструкція ..= та створює послідовність від 1 до TOWER_SIZE включно, або start..=end це start ≤ x ≤ end, докладніше в документації range expressions
(1..=TOWER_SIZE).rev() (rev скорочення reverse) для перетворення послідовності від 1 до TOWER_SIZE включно на зворотню послідовність
і пояснення 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<u8>
І залишилось розібрати тільки 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;
}хоч ми й використовували макрос vec! раніше, але в цьому прикладі коду гарно видно що Rust вміє самостійно розраховувати типи змінних
тепер реалізуємо @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;
}
- ми передаємо в функцію вказівник &State бо передаючи просто State ми б передавали володіння
- функція повертає Option<State>, де Option це обгортка всередині якої може бути значення заданого типу, в данному випадку типу State
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);
}
}у випадку коли можемо перемістити то створюємо новий стан 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);
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<T>, у випадку вектору дисків це Option<u8>
далі метод 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(Debug, Clone)]
struct Rod {
disks: Vec<u8>,
}
#[derive(Debug, Clone)]
struct State {
rods: Vec<Rod>,
}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;
}якщо ви дочитали до цього місця то якось натякніть в коментарях
я трохи скоротив код і ось вам повна картина:
#[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 в
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());
}
}
}cargo test
running 1 test test state_test::serialize ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
тепер використаємо новий метод State.serialize та структуру HashSet для збереження повернутих раніше станів:
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
#[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;
}
}Епілог
Основна ціль статті це знайомство з Rust-ом на простому прикладі.Написання статті і мені було корисно бо краще зміг структурувати свої знання.
Статтю хотів написати давно, але випередили.
Для написання статті використовував безкоштовну IntelliJ IDEA Community Edition для якої також є безкоштовний Rust плагін.
За перевірку статті на помилки дякую Олексію, який працює 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
- Класичне рішення «Ханойської вежі»
Victor Musienkо
Victor Musienkо
Dmitry
Denys Poltorak
Denys Poltorak
ssolov
Sergii Voloshyn
17 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів