Пошук в глибину на прикладі задачі Ханойської вежі
Tags: ukrainian, rust
Published: 2020-07-22 16:25:43

Стаття орієнтована на спеціалістів які хочуть ознайомитись з Rust-ом або в майбутньому перекваліфікуватись на Rust-розробників, як і я.

# Короткий переказ
Стаття буде про вирішення задачі ["Ханойські вежі"](https://uk.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D1%8C%D0%BA%D0%B0_%D0%B2%D0%B5%D0%B6%D0%B0) через пошук в глибину, з використанням стандартних структур даних наявних в Rust з детальним описом що роблю і тому буде зрозуміла спеціалістам без досвіду з Rust-ом.
Будуть ілюстрації, налаштування Rust та створення першого проекту, а також написання тестів та пояснення деталей.
В кінці статті будуть посилання на навчальні матеріали а в коментарях відповім на питання стосовно статті.

За бажання можете відразу глянути [репозиторій](https://gitlab.com/rs-yp/dfs-tower-of-hahoi/-/blob/master/src/main.rs), а потім повернутись до читання статті.

# Ханойські вежі
Ханойські вежі — математична гра, де є три стержні і диски різних розмірів, на першому стержні розміщені диски у вигляді вежі яка збільшується зверху вниз, інші два стержні порожні,
ціль задачі перенести диски з першого на третій стержень використовуючи другий, можна переносити тільки один диск за раз, забороняється класти диски більшого розміру на менший.

Щоб зрозуміти рішення задачі то почнемо з одного диску який перекладаємо з першого на третій стержень
<blockquote>тут мала б бути gif, але dev.to має обмеження</blockquote>

Для двох дисків:
перекладаємо верхній перший диск на другий стержень,
другий диск з першого на третій стержень,
перший диск з другого на третій стержень,
ось і все.
![Tower of Hanoi with two disk](https://dev-to-uploads.s3.amazonaws.com/i/kh00h21pxo5l1ukprqci.gif)

Для трьох дисків рішення рекурсивне: важаємо нижній диск за другий, а всі верхні диск за "один" і так само вирішуємо для них рекурсивно.
<blockquote>тут також мала б бути gif, але dev.to має обмеження</blockquote>

Число рухів для 1 диску = 1 раз перекладаємо диск
Число рухів для 2 дисків = 3, де 2 рази перекладаємо верхній диск і 1 раз нижній
Число рухів для N дисків має відносну формулу T<sub>N</sub> = 2 × T<sub>N-1</sub> + 1
Число рухів для N дисків має абсолютну формулу T<sub>N</sub> = 2<sup>N</sup> - 1

Звісно є й альтернативне рішення — просто перевернути картинку.
![Tower of Hanoi with three disk hack](https://dev-to-uploads.s3.amazonaws.com/i/p3dx189fm4folzqmlb6d.gif)

# Пошук в глибину на прикладі задачі Ханойської вежі
Пошук у глибину (або Depth-first search або DFS) — алгоритм для обходу дерева, це класичне визначення з [вікіпедії](https://uk.wikipedia.org/wiki/%D0%9F%D0%BE%D1%88%D1%83%D0%BA_%D1%83_%D0%B3%D0%BB%D0%B8%D0%B1%D0%B8%D0%BD%D1%83).
Пошук у глибину можна адаптувати для рішення задачі "Ханойської вежі", це одна з лабораторних робіт у студентів з напряму комп'ютерні науки.

Ми беремо початковий стан де N-дисків лежать на першому стержні та використовуючи правила гри будуємо всі можливі стани і так до досягнення стану коли всі диски будуть на третьому стержні.
![Tower of Hanoi with depth-first search](https://dev-to-uploads.s3.amazonaws.com/i/bb3va7a8x2opgn8i8dg6.gif)

# Rust та створення першого проекту
Встановлення з офіційної сторінки [Install Rust](https://www.rust-lang.org/tools/install):
```bash
sudo apt update
curl https://sh.rustup.rs -sSf | sh
source $HOME/.cargo/env
```
І перевіряємо що був встановлений сам installer **rustup**, компілятор **rustc** та менеджер пакетів **cargo**:
```bash
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](https://doc.rust-lang.org/cargo/commands/cargo-init.html) з назвою **dfs-tower-of-hahoi**:
```bash
cargo init --bin dfs-tower-of-hahoi
# Created binary (application) package
```
Проект створений і тепер глянемо що в ньому є:
```bash
tree dfs-tower-of-hahoi
```
```text
dfs-tower-of-hahoi
├── Cargo.toml
└── src
    └── main.rs
```
бачимо два файли, перший **main.rs** з мініальним кодом для запуску, та другий **Cargo.toml** з налаштуванням залежностей:
```bash
cat dfs-tower-of-hahoi/src/main.rs dfs-tower-of-hahoi/Cargo.toml
```
```rust
fn main() {
    println!("Hello, world!");
}
```
```toml
[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]
```
розширення файлу <b>*.rs</b> є скороченням від Rust, також є домен <b>.rs</b> який належить [Сербії](https://uk.wikipedia.org/wiki/%D0%A1%D0%B5%D1%80%D0%B1%D1%96%D1%8F) та із-за схожості часто використовуються для Rust проектів, один з таких проектів це [Actix.rs](https://actix.rs)
розширення файлу <b>*.toml</b> викорстовується для збереження налаштувань у форматі [TOML](https://github.com/toml-lang/toml) (Tom's Obvious, Minimal Language)
тепер перейдемо в папку проекту і запустимо проект:
```bash
cd ./dfs-tower-of-hahoi
cargo run
```
і отримаємо в терміналі:
```text
Hello, world!
```
як бачимо програма <b>Hello, world!</b> на Rust займає всього 3 лінії коду:
```rust
fn main() {
    println!("Hello, world!");
}
```
для вас знайомим буде функція <b>main</b> яка є в частині з C-подібних мов програмування: C, C++, Objective-C, Java, C#, а також Go

а от конструкція <b>println!</b> є новою, <b>println!</b> це макрос, це помітно з того що завершуються символом оклику "<b>!</b>"

макроси будуть знайомі C та C++ розробникам, в Rust-і <a href="https://doc.rust-lang.org/1.7.0/book/macros.html" target="_blank">макроси</a> теж є, писати їх складніше, зате безпечніше із-за <a href="https://doc.rust-lang.org/1.7.0/book/macros.html#hygiene" target="_blank">гігієни макросів</a>

# Починаємо рішення з вибору структур
Вже писав раніше, та повторюсь, нам треба описати початковий стан де N-дисків лежать на першому стержні <b>S<sub>BEGIN</sub></b> та кінцевий стан де всі диски на останньому стержні <b>S<sub>END</sub></b>.

Потім на основі початкового стану <b>S<sub>BEGIN</sub></b> формуємо всі можливі стани <b>S<sub>NEXT 1-N</sub></b> (де N число стержнів), потім на основі станів <b>S<sub>NEXT 1-N</sub></b> формуємо наступні стани і так далі, до моменту досягнення <b>S<sub>END</sub></b>.

Для початку нам треба описати стержень з якого будемо брати або класти верхній диск, як бачимо це опис структури <a href="https://uk.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BA" target="_blank">LIFO</a>.
В Rust є <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html" target="_blank">Vector</a> який має потрібні нам методи <b>pop()</b> та <b>push()</b>, отож маємо структуру для стержня <b>Rod</b>:
```rust
struct Rod {
    disks: Vec<u8>,
}
```
А також структуру для опису стану стержнів (для простоти виберемо також Vector):
```rust
struct State {
    rods: Vec<Rod>,
}
```
тепер можемо об'явити початковий і кінцевий стан і спробуємо вивести в терміналі:
```rust
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);
}
```
тут для нас дві нові конструкції, перша це макрос <b>vec!</b>, а друга це заповнювач (placeholder) <b>{:?}</b> для виведення детальної інформації про зміну

ключове слово <a href="https://doc.rust-lang.org/std/keyword.let.html" target="_blank">let</a> потрібно щоб об'явити змінну (так само як і в JavaScript)

тепер через <b>cargo run</b> запустимо і отримаємо помилку в терміналі:
```text
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`
```

як бачимо компітялор rustc каже що для виведення налагоджувальної інформації нам потрібно реалізувати типаж (trait) <a href="https://doc.rust-lang.org/std/fmt/trait.Debug.html" target="_blank">std::fmt::Debug</a>, а також запропонував два варіанти рішення:
<blockquote>note: add `#[derive(Debug)]` or manually implement `std::fmt::Debug`</blockquote>

типаж <b>std::fmt::Debug</b>, як і інші типажі, схожий на інтерфейс в інших мовах програмування
```rust
pub trait Debug {
    fn fmt(&self, f: &mut Formatter<'_>) ->; Result;
}
```
почнемо з ручної (manually) реалізації типажу <b>std::fmt::Debug</b>:
```rust
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());
    }
}
```
в цьому коді ми імпортували потрібні нам пакети за допомогою конструкції <b>use</b> та реалізували типаж <b>Debug</b>
так в цьому коді ще багато нових конструкцій, але в данному випадку цей код є лише прикладом реалізації типажу через <b>impl Debug for State</b>
запустивши програму отримаємо очікуваний результат:
```text
Tower of Hanoi begin state `manually debug with rods 3`
Tower of Hanoi end state `manually debug with rods 3`
```

Але можна зробити простіше, як і рекомендував компілятор, додавши <a href="https://doc.rust-lang.org/reference/attributes.html" target="_blank">атрибут</a> derive з налаштуванням Debug <b>`#[derive(Debug)]`</b> і це буде підказкою компілятору rustc згенерувати рутиний код за нас:
```rust
#[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);
}
```
```bash
cargo run
```
```text
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] }] }
```
новий атрибут <a href="https://doc.rust-lang.org/stable/rust-by-example/trait/derive.html" target="_blank">derive</a> здатний реалізувати частину базових типажів за нас

# Рефакторинг: виносимо число дисків в константу
Зараз в коді зашито число дисків у векторі <b>disks: vec![3, 2, 1]</b>, і при збільшенні числа дисків треба буде змінювати налаштування в двох місцях в коді, тому винесемо в константу:
```rust
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);
}
```
що ж давайте розбиратись, з <b>const</b> це зрозуміло
в коді <b>1..=TOWER_SIZE</b> використовується конструкція <b>..=</b> та створює послідовність від 1 до TOWER_SIZE включно, або <b>start..=end</b> це <b>start ≤ x ≤ end</b>, докладніше в документації <a href="https://doc.rust-lang.org/reference/expressions/range-expr.html" target="_blank">range expressions</a>
<b>(1..=TOWER_SIZE).rev()</b> (rev скорочення reverse) для перетворення послідовності від 1 до TOWER_SIZE включно на зворотню послідовність
і пояснення <a href="https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.collect" target="_blank">collect з документації</a> для перетворення однієї колекції в іншу:
<blockquote>Transforms 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.</blockquote>
в нашому випадку collect перетворює послідовність типу RangeInclusiveExpr в Vec&lt;u8&gt;

І залишилось розібрати тільки <b>disks.clone()</b> який потрібний для повного копіювання бо інакше відбувається передача володіння над змінною disks і подальше використання disks буде помилкою про яку повідомить компілятор, володіння — це така особливість Rust яка підвищує безпеку.

# Формуємо всі можливі стани з початкового
Ось дуже простий код з перебором:
```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;
}
```
<b>0..rods</b> теж послідовність де <b>start..end = start ≤ x < end</b>
хоч ми й використовували макрос <b>vec!</b> раніше, але в цьому прикладі коду гарно видно що Rust вміє самостійно розраховувати типи змінних
тепер реалізуємо <b>@TODO</b> як функцію <b>create_state_by_move_disk</b> яка повертає новий стан на основі поточного і перекладання диску між стержнями:
```rust
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;
}
```
в функції <b>create_state_by_move_disk</b> є нові для нас конструкції
<ol>
<li>ми передаємо в функцію вказівник <b>&State</b> бо передаючи просто <b>State</b> ми б передавали володіння</li>
<li>функція повертає <b>Option<State></b>, де Option це обгортка всередині якої може бути значення заданого типу, в данному випадку типу State</li>
</ol>
щоб краще зрозуміти <a href="https://doc.rust-lang.org/rust-by-example/std/option.html" target="_blank">Option</a> ось адаптований приклад з документації:
```rust
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);
    }
}
```
повернемось до логіки функції <b>create_state_by_move_disk</b> де ми перевіряємо чи можемо ми перемістити диск між стержнями за правилами гри
у випадку коли можемо перемістити то створюємо новий стан <b>result</b> і переміщаємо диск, а інакше повертаємо <b>Option::None</b>
а тепер давайте розглянемо детальніше блок коду зі створенням нового стану та переміщення:
```rust
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);
```
в документації про об'явлення змінної через ключове слово <a href="https://doc.rust-lang.org/std/keyword.let.html" target="_blank">let</a> сказано:
<blockquote>Variables in Rust are immutable by default, and require the mut keyword to be made mutable.</blockquote>
тому ми об'являємо <b>let mut result</b>, щоб мати змогу змінювати змінну <b>result</b>
друге це метод <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop" target="_blank">pop()</a> структури <b>std::vec::Vec</b>, pop() видаляє і повертає останній елемент вектору, якщо останній елемент є
звісно вектор може бути пустий і тому pop() повертає Option&lt;T&gt;, у випадку вектору дисків це Option&lt;u8&gt;
далі метод <a href="https://doc.rust-lang.org/std/option/enum.Option.html#method.unwrap" target="_blank">unwrap()</a> обгортки Option, unwrap() повертає збережене всередині значення, а воно є бо ми це перевірили раніше
якби вектор був пустий і ми виконали <b>.pop().unwrap()</b> то отримали б паніку, майте це на увазі
якщо ви були уважні то помітили що у структури <b>State</b> відсутній метод <b>clone</b> який використовую
метод clone потрібний для копіювання стержнів а також дисків і це дуже просто зробити перебором:
```rust
#[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&gt,
}

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 };
    }
}
```
або ж правильно використати ще раз <b>derive</b> в який ми додамо типаж <a href="https://doc.rust-lang.org/std/clone/trait.Clone.html" target="_blank">Clone</a> і дати компілятору попрацювати за нас знову
```rust
#[derive(Debug, Clone)]
struct Rod {
    disks: Vec<u8>,
}

#[derive(Debug, Clone)]
struct State {
    rods: Vec<Rod&gt,
}
```
тепер час використати функцію <b>create_state_by_move_disk</b> для генерації можливих станів:
```rust
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;
}
```
констуркція <a href="https://doc.rust-lang.org/stable/rust-by-example/flow_control/match.html" target="_blank">match</a> схожа на switch в інших мовах програмування, але <b>match</b> потужніша
якщо ви дочитали до цього місця то якось натякніть в коментарях
я трохи скоротив код і ось вам повна картина:
```rust
#[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;
}
```

# Повертаємо тільки унікальні стани
Переклавши диск з першого стежня на другий, ми так само можемо повернути його назад, і щоб прибрати подібне зациклення ми будемо зберігати пройдені стани використовуючи стандартну структуру <a href="https://doc.rust-lang.org/std/collections/struct.HashSet.html" target="_blank">HashSet</a>.

Отож так само генеруємо можливі стани та відфільтровуємо вже повернуті раніше, які були збережені в HashSet.

Елементи HashSet мають реалізувати типаж <a href="https://doc.rust-lang.org/std/hash/trait.Hash.html" target="_blank">Hash</a> (який в Rust-і вже реалізований для багатьох типів даних, строкових та числових).
І ми можемо реалівувати типаж Hash для структури <b>State</b> або серіалізувати структуру <b>State</b> в строку або число (які реалізують Hash).
Отже серіалізуємо <b>State</b> в 128-бітне число <a href="https://doc.rust-lang.org/std/u128/index.html" target="_blank">u128</a> і напишемо тест:
```rust
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;
    }
}
```
звісно використовуючи u128 ми накладаємо обмеження на число дисків та стержнів які зможемо серіалізувати правильно але нам цього обмеження достатньо
для написання тестів ми скористаємось прикладом з документації <a href="https://doc.rust-lang.org/stable/rust-by-example/testing/unit_testing.html" target="_blank">unit testing</a> і зробимо так само:
```rust
#[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());
        }
    }
}
```
новими для нас є атрибути <b>#[cfg(test)]</b> та <b>#[test]</b>, а також макрос <b>assert_eq!</b>, з назви зрозуміло навіщо вони потрібні, отож запустимо тести:
```bash
cargo test
```
```text
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 для збереження повернутих раніше станів:
```rust
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);
        }
    }
}
```
метод HashSet.insert повертає true якщо був вставлений новий елемент
після запуску через <b>cargo run</b> в терміналі отримаємо що дійсно фільтрує:
```text
Tower of Hanoi next states 2
Tower of Hanoi next states 0
```

# Реалізація пошуку в глибину
Всі попередні приклади в статті були потрібні для об'єднання в пошук в глибину, нарешті:
```rust
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()
    );
}
```
```bash
cargo run
```
```text
Tower of Hanoi with size 7
Tower of Hanoi deep first search result true
```
щоб порівняти два стани в коді через просту операцію "==" <b>state == self.end</b> додали типаж PartialEq
```rust
#[derive(Debug, Clone, PartialEq)]
struct Rod {
    disks: Vec<u8>,
}

#[derive(Debug, Clone, PartialEq)]
struct State {
    rods: Vec<Rod>,
}
```

# Перевірка правильності рішення
Для перевірки рішення треба зберігати в журнал дії переміщення диска між стержнями,а потім використавши журнал повторити дії починаючи від початкового стану і перевірити що кінцевий стан буде очікуваним.

Цю просту перевірку спробуйте написати самостійно, а весь код для повної картини можете глянути у відкритому <a href="https://gitlab.com/rs-yp/dfs-tower-of-hahoi/-/blob/master/src/main.rs" target="_blank">репозиторії</a>.

# Пошук у ширину на прикладі задачі Ханойської вежі
Раз ми вже з одним пошуком познайомились, то легко побачимо відмінність <a href="https://uk.wikipedia.org/wiki/%D0%9F%D0%BE%D1%88%D1%83%D0%BA_%D1%83_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83" target="_blank">пошуку у ширину</a>
Якщо в пошуці в глибину ми рекурсивно заглиблювались, то в пошуці в ширину ми просто додаємо в чергу:
```rust
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(&amp;current_state));
        }

        return false;
    }
}
```

# Епілог
Основна ціль статті це знайомство з Rust-ом на простому прикладі.
Написання статті і мені було корисно бо краще зміг структурувати свої знання.
Статтю хотів написати давно, але <a href="https://dou.ua/forums/topic/30864/" target="_blank">випередили.</a>
Для написання статті використовував безкоштовну IntelliJ IDEA Community Edition для якої також є безкоштовний Rust плагін.

За перевірку статті на помилки дякую <a href="https://www.linkedin.com/in/ilammy/" target="_blank">Олексію</a>, який працює [Cossack Labs](https://dev.to/cossacklabs) і шукає до себе в команду спеціалістів з <a href="https://www.cossacklabs.com/jobs/c-engineer.html" target="_blank">Rust</a>.
За ілюстрації дякую <a href="https://www.linkedin.com/in/liudmila-titorenko/" target="_blank">Людмилі Тіторенко</a>

# Навчальні матеріали:
<ul>
<li><a href="https://www.youtube.com/watch?v=vOMJlQ5B-M0&list=PLVvjrrRCBy2JSHf9tGxGKJ-bYAN_uDCUL" target="_blank">[YouTube] Rust Programming Tutorial</a></li>
<li><a href="https://www.goodreads.com/book/show/25550614-programming-rust" target="_blank">[Book] Programming Rust: Fast, Safe Systems Development</a></li>
<li><a href="https://tourofrust.com/" target="_blank">Tour of Rust</a></li>
<li><a href="https://doc.rust-lang.org/rust-by-example/" target="_blank">Rust by Example</a></li>
<li><a href="https://doc.rust-lang.org/book/" target="_blank">[Book] The Rust Programming Language</a></li>
<li><a href="https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/" target="_blank">Класичне рішення "Ханойської вежі"</a></li>
</ul>

Також є класний YouTube канал <a href="https://www.youtube.com/c/HelloRust/videos" target="_blank">Hello Rust!</a>, але останнє відео там публікували рік тому.