Yaroslav Podorvanov

Posted on Jul 22, 2020 • Edited on Jul 31, 2020

Пошук в глибину на прикладі задачі Ханойської вежі

#ukrainian #rust

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

Короткий переказ

Стаття буде про вирішення задачі "Ханойські вежі" через пошук в глибину, з використанням стандартних структур даних наявних в Rust з детальним описом що роблю і тому буде зрозуміла спеціалістам без досвіду з Rust-ом.
Будуть ілюстрації, налаштування Rust та створення першого проекту, а також написання тестів та пояснення деталей.
В кінці статті будуть посилання на навчальні матеріали а в коментарях відповім на питання стосовно статті.

За бажання можете відразу глянути репозиторій, а потім повернутись до читання статті.

Ханойські вежі

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

Щоб зрозуміти рішення задачі то почнемо з одного диску який перекладаємо з першого на третій стержень

тут мала б бути gif, але dev.to має обмеження

Для двох дисків:
перекладаємо верхній перший диск на другий стержень,
другий диск з першого на третій стержень,
перший диск з другого на третій стержень,
ось і все.

Для трьох дисків рішення рекурсивне: важаємо нижній диск за другий, а всі верхні диск за "один" і так само вирішуємо для них рекурсивно.

тут також мала б бути gif, але dev.to має обмеження

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

Звісно є й альтернативне рішення — просто перевернути картинку.

Пошук в глибину на прикладі задачі Ханойської вежі

Пошук у глибину (або Depth-first search або DFS) — алгоритм для обходу дерева, це класичне визначення з вікіпедії.
Пошук у глибину можна адаптувати для рішення задачі "Ханойської вежі", це одна з лабораторних робіт у студентів з напряму комп'ютерні науки.

Ми беремо початковий стан де N-дисків лежать на першому стержні та використовуючи правила гри будуємо всі можливі стани і так до досягнення стану коли всі диски будуть на третьому стержні.

Rust та створення першого проекту

Встановлення з офіційної сторінки Install Rust:

sudo apt update
curl https://sh.rustup.rs -sSf | sh
source $HOME/.cargo/env

І перевіряємо що був встановлений сам installer 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 є скороченням від Rust, також є домен .rs який належить Сербії та із-за схожості часто використовуються для Rust проектів, один з таких проектів це Actix.rs
розширення файлу .toml викорстовується для збереження налаштувань у форматі TOML (Tom's Obvious, Minimal Language)
тепер перейдемо в папку проекту і запустимо проект:

cd ./dfs-tower-of-hahoi
cargo run

і отримаємо в терміналі:

Hello, world!

як бачимо програма Hello, world! на Rust займає всього 3 лінії коду:

fn main() {
    println!("Hello, world!");
}

для вас знайомим буде функція main яка є в частині з C-подібних мов програмування: C, C++, Objective-C, Java, C#, а також Go

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

макроси будуть знайомі C та C++ розробникам, в Rust-і макроси теж є, писати їх складніше, зате безпечніше із-за гігієни макросів

Починаємо рішення з вибору структур

Вже писав раніше, та повторюсь, нам треба описати початковий стан де N-дисків лежать на першому стержні 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>,
}

А також структуру для опису стану стержнів (для простоти виберемо також Vector):

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!, а друга це заповнювач (placeholder) {:?} для виведення детальної інформації про зміну

ключове слово 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`

як бачимо компітялор rustc каже що для виведення налагоджувальної інформації нам потрібно реалізувати типаж (trait) 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;
}

почнемо з ручної (manually) реалізації типажу 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)] і це буде підказкою компілятору rustc згенерувати рутиний код за нас:

#[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 використовується конструкція ..= та створює послідовність від 1 до TOWER_SIZE включно, або start..=end це start ≤ x ≤ end, докладніше в документації range expressions
(1..=TOWER_SIZE).rev() (rev скорочення reverse) для перетворення послідовності від 1 до TOWER_SIZE включно на зворотню послідовність
і пояснення collect з документації для перетворення однієї колекції в іншу:

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.

в нашому випадку 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;
}

0..rods теж послідовність де start..end = start ≤ x < end
хоч ми й використовували макрос 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;
}

в функції 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<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&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 };
    }
}

або ж правильно використати ще раз derive в який ми додамо типаж Clone і дати компілятору попрацювати за нас знову

#[derive(Debug, Clone)]
struct Rod {
    disks: Vec<u8>,
}

#[derive(Debug, Clone)]
struct State {
    rods: Vec<Rod&gt,
}

тепер час використати функцію 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 схожа на switch в інших мовах програмування, але 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;
    }
}

звісно використовуючи u128 ми накладаємо обмеження на число дисків та стержнів які зможемо серіалізувати правильно але нам цього обмеження достатньо
для написання тестів ми скористаємось прикладом з документації 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

як бачимо тести пройшли успішно
тепер використаємо новий метод 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);
        }
    }
}

метод HashSet.insert повертає true якщо був вставлений новий елемент
після запуску через 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()
    );
}

cargo run

Tower of Hanoi with size 7
Tower of Hanoi deep first search result true

щоб порівняти два стани в коді через просту операцію "==" state == self.end додали типаж PartialEq

#[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(&amp;current_state));
        }

        return false;
    }
}

Епілог

Основна ціль статті це знайомство з Rust-ом на простому прикладі.
Написання статті і мені було корисно бо краще зміг структурувати свої знання.
Статтю хотів написати давно, але випередили.
Для написання статті використовував безкоштовну IntelliJ IDEA Community Edition для якої також є безкоштовний Rust плагін.

За перевірку статті на помилки дякую Олексію, який працює Cossack Labs і шукає до себе в команду спеціалістів з Rust.
За ілюстрації дякую Людмилі Тіторенко

Навчальні матеріали:

Також є класний YouTube канал Hello Rust!, але останнє відео там публікували рік тому.

Top comments (4)

butrunk42 • Apr 25 • Edited

Цікаво! Розв'язання задачі Ханойської вежі за допомогою пошуку в глибину може бути цікавим використанням цього алгоритму. Якщо вас цікавлять загадкові та навіть містичні історії, то на моє переконання вам стане у пригоді сайт про апокаліпсис та конспірологію. Бажаю тільки приємних емоцій.