Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Dungeons and Compilers

Предадени решения

Краен срок:
11.01.2022 17:00
Точки:
20

Срокът за предаване на решения е отминал

use solution::*;
use std::io::{self, Read, BufRead};
macro_rules! timeout {
($time:expr, $body:block) => {
use std::panic::catch_unwind;
let (sender, receiver) = std::sync::mpsc::channel();
std::thread::spawn(move || {
if let Err(e) = catch_unwind(|| $body) {
sender.send(Err(e)).unwrap();
return;
}
match sender.send(Ok(())) {
Ok(()) => {}, // everything good
Err(_) => {}, // we have been released, don't panic
}
});
if let Err(any) = receiver.recv_timeout(std::time::Duration::from_millis($time)).unwrap() {
panic!("{}", any.downcast_ref::<String>().unwrap());
}
}
}
const ALL_DIRECTIONS: [Direction; 4] = [
Direction::North,
Direction::South,
Direction::East,
Direction::West
];
fn all_links<'a>(dungeon: &'a Dungeon, room: &'a Room) -> Vec<&'a str> {
ALL_DIRECTIONS.iter().
flat_map(|dir| dungeon.get_next_room(&room.name, *dir).unwrap()).
map(|r| r.name.as_str()).
collect::<Vec<&'a str>>()
}
struct ErroringReader {}
impl Read for ErroringReader {
fn read(&mut self, _buf: &mut [u8]) -> io::Result<usize> {
Err(io::Error::new(io::ErrorKind::Other, "read error!"))
}
}
impl BufRead for ErroringReader {
fn fill_buf(&mut self) -> io::Result<&[u8]> {
Err(io::Error::new(io::ErrorKind::Other, "fill_buf error!"))
}
fn consume(&mut self, _amt: usize) { }
}
#[test]
fn test_adding_rooms_1() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Hallway").unwrap();
dungeon.add_room("Laboratory").unwrap();
assert_eq!(dungeon.get_room("Entrance").unwrap().name, "Entrance");
assert_eq!(dungeon.get_room("Hallway").unwrap().name, "Hallway");
assert_eq!(dungeon.get_room("Laboratory").unwrap().name, "Laboratory");
}
#[test]
fn test_adding_rooms_2() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Hallway 1").unwrap();
dungeon.add_room("Side Closet").unwrap();
dungeon.add_room("Hallway 2").unwrap();
dungeon.add_room("Treasure Room").unwrap();
dungeon.set_link("Entrance", Direction::East, "Hallway 1").unwrap();
dungeon.set_link("Hallway 1", Direction::East, "Side Closet").unwrap();
dungeon.set_link("Hallway 1", Direction::North, "Hallway 2").unwrap();
dungeon.set_link("Hallway 2", Direction::South, "Side Closet").unwrap();
dungeon.set_link("Hallway 2", Direction::West, "Treasure Room").unwrap();
dungeon.set_link("Side Closet", Direction::South, "Entrance").unwrap();
assert_eq!(dungeon.get_room("Entrance").unwrap().name, "Entrance");
assert_eq!(dungeon.get_room("Hallway 1").unwrap().name, "Hallway 1");
assert_eq!(dungeon.get_room("Side Closet").unwrap().name, "Side Closet");
assert_eq!(dungeon.get_room("Hallway 2").unwrap().name, "Hallway 2");
assert_eq!(dungeon.get_room("Treasure Room").unwrap().name, "Treasure Room");
assert_eq!(dungeon.get_next_room("Entrance", Direction::East).unwrap().unwrap().name, "Hallway 1");
assert_eq!(dungeon.get_next_room("Hallway 1", Direction::West).unwrap().unwrap().name, "Entrance");
assert_eq!(dungeon.get_next_room("Hallway 1", Direction::North).unwrap().unwrap().name, "Hallway 2");
// Overwrite "South" link:
assert_eq!(dungeon.get_next_room("Hallway 2", Direction::South).unwrap().unwrap().name, "Side Closet");
assert_eq!(dungeon.get_next_room("Side Closet", Direction::South).unwrap().unwrap().name, "Entrance");
assert_eq!(dungeon.get_next_room("Entrance", Direction::North).unwrap().unwrap().name, "Side Closet");
}
#[test]
fn test_room_links() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
assert_eq!(all_links(&dungeon, dungeon.get_room("Entrance").unwrap()), Vec::<&str>::new());
dungeon.add_room("Hallway 1").unwrap();
dungeon.set_link("Entrance", Direction::North, "Hallway 1").unwrap();
assert_eq!(
all_links(&dungeon, dungeon.get_room("Entrance").unwrap()),
vec!["Hallway 1"]
);
dungeon.add_room("Hallway 2").unwrap();
dungeon.set_link("Entrance", Direction::South, "Hallway 2").unwrap();
assert_eq!(
all_links(&dungeon, dungeon.get_room("Entrance").unwrap()),
vec!["Hallway 1", "Hallway 2"]
);
dungeon.add_room("Hallway 3").unwrap();
dungeon.set_link("Entrance", Direction::East, "Hallway 3").unwrap();
assert_eq!(
all_links(&dungeon, dungeon.get_room("Entrance").unwrap()),
vec!["Hallway 1", "Hallway 2", "Hallway 3"]
);
dungeon.add_room("Hallway 4").unwrap();
dungeon.set_link("Entrance", Direction::West, "Hallway 4").unwrap();
assert_eq!(
all_links(&dungeon, dungeon.get_room("Entrance").unwrap()),
vec!["Hallway 1", "Hallway 2", "Hallway 3", "Hallway 4"]
);
}
#[test]
fn test_overwriting_a_room_link() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
assert_eq!(all_links(&dungeon, dungeon.get_room("Entrance").unwrap()), Vec::<&str>::new());
dungeon.add_room("Hallway 1").unwrap();
dungeon.set_link("Entrance", Direction::North, "Hallway 1").unwrap();
assert_eq!(
all_links(&dungeon, dungeon.get_room("Entrance").unwrap()),
vec!["Hallway 1"]
);
dungeon.add_room("Hallway 2").unwrap();
dungeon.set_link("Entrance", Direction::North, "Hallway 2").unwrap();
assert_eq!(
all_links(&dungeon, dungeon.get_room("Entrance").unwrap()),
vec!["Hallway 2"]
);
}
#[test]
fn test_cyrillic_room_names() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Антре").unwrap();
dungeon.add_room("Хол").unwrap();
dungeon.set_link("Антре", Direction::North, "Хол").unwrap();
assert_eq!(dungeon.get_room("Антре").unwrap().name, "Антре");
assert_eq!(dungeon.get_room("Хол").unwrap().name, "Хол");
assert!(matches!(dungeon.get_room("Кухня"), Err(Errors::UnknownRoom(_))));
assert_eq!(dungeon.get_next_room("Антре", Direction::North).unwrap().unwrap().name, "Хол");
assert_eq!(dungeon.get_next_room("Хол", Direction::South).unwrap().unwrap().name, "Антре");
}
#[test]
fn test_room_errors() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
assert!(matches!(dungeon.add_room("Entrance"), Err(Errors::DuplicateRoom(_))));
assert!(matches!(dungeon.get_room("Exit"), Err(Errors::UnknownRoom(_))));
}
#[test]
fn test_io_error() {
timeout!(1000, {
let dungeon = Dungeon::from_reader(ErroringReader {});
assert!(matches!(dungeon, Err(Errors::IoError(_))));
});
}
const TEST_INPUT_1: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
- Hallway -> West -> Entrance
";
#[test]
fn test_parsing_rooms() {
let dungeon = Dungeon::from_reader(TEST_INPUT_1.trim().as_bytes()).unwrap();
assert_eq!(dungeon.get_room("Entrance").unwrap().name, "Entrance");
assert_eq!(dungeon.get_room("Hallway").unwrap().name, "Hallway");
assert_eq!(dungeon.get_next_room("Entrance", Direction::East).unwrap().unwrap().name, "Hallway");
assert_eq!(dungeon.get_next_room("Hallway", Direction::West).unwrap().unwrap().name, "Entrance");
}
const TEST_INPUT_2: &str = "
## Rooms
## Links
";
const TEST_INPUT_3: &str = "
## Rooms
- Pantry
- Kitchen
## Links
";
#[test]
fn test_parsing_no_rooms_or_links() {
let dungeon = Dungeon::from_reader(TEST_INPUT_2.trim().as_bytes()).unwrap();
assert!(matches!(dungeon.get_room("Entrance"), Err(Errors::UnknownRoom(_))));
let dungeon = Dungeon::from_reader(TEST_INPUT_3.trim().as_bytes()).unwrap();
assert_eq!(all_links(&dungeon, dungeon.get_room("Pantry").unwrap()), Vec::<&str>::new());
}
const TEST_INPUT_4: &str = "
## Chambers
## Links
";
const TEST_INPUT_5: &str = "
## Rooms
## Neighbours
";
const TEST_INPUT_6: &str = "
## Rooms
- Entrance
- Treasure Room
## Links
- Closet -> North -> Bathroom
";
const TEST_INPUT_7: &str = "
## Rooms
- Entrance
- Treasure Room
## Links
- Entrance -> North-west -> Treasure Room
";
#[test]
fn test_invalid_parsing() {
assert!(matches!(Dungeon::from_reader("".as_bytes()), Err(Errors::LineParseError { line_number: 0 })));
assert!(matches!(Dungeon::from_reader(TEST_INPUT_4.trim().as_bytes()), Err(Errors::LineParseError { line_number: 1 })));
assert!(matches!(Dungeon::from_reader(TEST_INPUT_5.trim().as_bytes()), Err(Errors::LineParseError { line_number: 3 })));
assert!(matches!(Dungeon::from_reader(TEST_INPUT_6.trim().as_bytes()), Err(Errors::UnknownRoom(_))));
assert!(matches!(Dungeon::from_reader(TEST_INPUT_7.trim().as_bytes()), Err(Errors::DirectionParseError(_))));
}
const TEST_INPUT_8: &str = "
## Rooms
- Вход
- Хол
## Links
- Вход -> West -> Хол
";
#[test]
fn test_parsing_cyrillic_rooms() {
let dungeon = Dungeon::from_reader(TEST_INPUT_8.trim().as_bytes()).unwrap();
assert_eq!(dungeon.get_room("Вход").unwrap().name, "Вход");
assert_eq!(dungeon.get_room("Хол").unwrap().name, "Хол");
assert!(matches!(dungeon.get_room("Кухня"), Err(Errors::UnknownRoom(_))));
assert_eq!(dungeon.get_next_room("Вход", Direction::West).unwrap().unwrap().name, "Хол");
assert_eq!(dungeon.get_next_room("Хол", Direction::East).unwrap().unwrap().name, "Вход");
}
#[test]
fn test_finding_a_direct_path() {
timeout!(1000, {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Treasure Room").unwrap();
dungeon.set_link("Entrance", Direction::West, "Treasure Room").unwrap();
let path = dungeon.find_path("Entrance", "Treasure Room").unwrap().unwrap();
assert_eq!(path.into_iter().map(|p| &p.name).collect::<Vec<_>>(), ["Entrance", "Treasure Room"]);
});
}
#[test]
fn test_finding_an_indirect_path() {
timeout!(1000, {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Hallway 1").unwrap();
dungeon.add_room("Side Closet").unwrap();
dungeon.add_room("Hallway 2").unwrap();
dungeon.add_room("Treasure Room").unwrap();
dungeon.set_link("Entrance", Direction::East, "Hallway 1").unwrap();
dungeon.set_link("Hallway 1", Direction::East, "Side Closet").unwrap();
dungeon.set_link("Hallway 1", Direction::North, "Hallway 2").unwrap();
dungeon.set_link("Hallway 2", Direction::South, "Side Closet").unwrap();
dungeon.set_link("Hallway 2", Direction::West, "Treasure Room").unwrap();
dungeon.set_link("Side Closet", Direction::South, "Entrance").unwrap();
let path = dungeon.find_path("Entrance", "Treasure Room").unwrap().unwrap();
let mut path_iter = path.iter();
let mut first = path_iter.next().unwrap();
while let Some(second) = path_iter.next() {
let first_neighbours = all_links(&dungeon, &first);
assert!(first_neighbours.contains(&second.name.as_str()));
first = second;
}
assert_eq!(path[0].name, "Entrance");
assert_eq!(path[path.len() - 1].name, "Treasure Room");
});
}
#[test]
fn test_finding_a_reflexive_path() {
timeout!(1000, {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Treasure Room").unwrap();
let path = dungeon.find_path("Entrance", "Entrance").unwrap().unwrap();
assert_eq!(path[0].name, "Entrance");
assert_eq!(path.len(), 1);
let path = dungeon.find_path("Treasure Room", "Treasure Room").unwrap().unwrap();
assert_eq!(path[0].name, "Treasure Room");
assert_eq!(path.len(), 1);
});
}
#[test]
fn test_finding_no_path() {
timeout!(1000, {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Treasure Room").unwrap();
let path = dungeon.find_path("Entrance", "Treasure Room");
assert!(path.unwrap().is_none());
let path = dungeon.find_path("Entrance", "Mystery Room");
assert!(path.is_err());
let path = dungeon.find_path("Mystery Room", "Treasure Room");
assert!(path.is_err());
});
}

Zork е една от класическите компютърни игри -- намирате се в стая в подземията, избирате дали да пътувате на север, на изток, и т.н.. Стаите си имат съкровища, противници, и разнообразен flavor text. Ще напишем основите на някаква такава игра.

Първо, базовите дефиниции на типове, с които ще работим:

/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
    DuplicateRoom(String),
    UnknownRoom(String),
    IoError(std::io::Error),
    LineParseError { line_number: usize },
    DirectionParseError(String),
}

/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Clone, Copy)]
pub enum Direction {
    North,
    South,
    East,
    West,
}

/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
pub struct Room {
    pub name: String,
    // Каквито други полета ви трябват
}

/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
pub struct Dungeon {
    // Каквито полета ви трябват
}

Изграждане на Dungeon

Имаме структура Dungeon, какво да правим с нея?

impl Dungeon {
    /// Конструиране на празен Dungeon, в който няма никакви стаи.
    ///
    pub fn new() -> Self {
        todo!()
    }

    /// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
    /// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
    ///
    pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
        todo!()
    }

    /// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
    /// структурата с това име.
    ///
    /// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
    ///
    pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
        todo!()
    }

    /// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
    /// `room_name` да има връзка в посока `direction` със стаята с име `other_room_name`.
    ///
    /// Също така очакваме `other_room_name` да има връзка с `room_name` в *обратната* посока.
    ///
    /// Успешен резултат е `Ok(())`. В случай, че която от двете стаи не същестува, очакваме грешка
    /// `Errors::UnknownRoom` със съответното име на липсваща стая. Ако и двете липсват, спокойно
    /// върнете тази, която проверявате първо.
    ///
    pub fn set_link(
        &mut self,
        room_name: &str,
        direction: Direction,
        other_room_name: &str,
    ) -> Result<(), Errors> {
        todo!()
    }

    /// Четене на съседа на стаята с име `room_name` в посока `direction`. Тук има няколко
    /// варианта на изход:
    ///
    /// - Ако подадената стая не съществува, очакваме грешка `Errors::UnknownRoom`
    /// - Ако подадената стая няма съсед в тази посока, Ok(None) е смисления резултат
    /// - Иначе, чакаме reference към `Room` структурата на въпросния съсед, опакована в `Ok(Some(`.
    ///
    pub fn get_next_room(&self, room_name: &str, direction: Direction) -> Result<Option<&Room>, Errors> {
        todo!()
    }
}

Ето едно примерно изграждане на dungeon:

let mut dungeon = Dungeon::new();

dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Hallway").unwrap();
dungeon.set_link("Entrance", Direction::East, "Hallway").unwrap();

assert_eq!(dungeon.get_room("Hallway").unwrap().name, "Hallway");
assert_eq!(dungeon.get_next_room("Hallway", Direction::West).unwrap().unwrap().name, "Entrance");

Забележете какво отбелязахме по-горе -- добавянето на връзка от "Entrance" към "Hallway" на изток означава добавяне на обратната връзка на запад.

Възможно ли е да конструираме две връзки, които се overwrite-ват? Да, няма проблеми:

let mut dungeon = Dungeon::new();

dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Hallway").unwrap();
dungeon.add_room("Magic Lab").unwrap();

dungeon.set_link("Entrance", Direction::East, "Hallway").unwrap();
dungeon.set_link("Hallway", Direction::West, "Magic Lab").unwrap();

assert_eq!(dungeon.get_next_room("Entrance", Direction::East).unwrap().unwrap().name, "Hallway");
assert_eq!(dungeon.get_next_room("Hallway", Direction::West).unwrap().unwrap().name, "Magic Lab");

Отиваме на изток от входа и се озоваваме в коридор. Връщаме се на запад и изведнъж сме в някаква магическа лаборатория. That's just how magic dungeons roll, go with it. Когато казваме ".set_link добавя връзки в двете посоки", просто си го направете, пък ако по-нататъшни извиквания променят нещо, няма проблеми. Няма проблеми и .set_link да пренапише предни връзки в процеса на работа.

Напълно възможно е и да се създаде връзка от една стая към същата стая. It's magic, може да loop-не.

(Hint: Ако се чудите как точно да съхраните данните на Room структурите така че лесно да ги достъпвате по име, HashMap вероятно е най-лесния вариант. Низовите имена спокойно могат да репрезентират и връзките между стаи, което сигурно ще е по-лесно, отколкото да се мъчите с Rc-та и RefCell-ове примерно.)

Разбира се, дизайнерите на dungeon-а няма да им се занимава да пишат rust код, твърде много скоби и амперсанди. Нека да изпарсим структурата от прост файл.

Парсене

Ето един примерен файл, който ще искаме да можем да четем, който отговаря на горната структура:

## Rooms
- Entrance
- Hallway
- Magic Lab

## Links
- Entrance -> East -> Hallway
- Hallway -> West -> Magic Lab

Ето и структурата на функцията, която ще ползваме:

impl Dungeon {
    /// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
    /// файл, или, ако тестваме, може да е просто колекция от байтове.
    ///
    /// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
    ///
    /// Вижте по-долу за обяснение на грешките, които очакваме.
    ///
    pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
        todo!()
    }
}

Първия ред винаги трябва да е ## Rooms. Иначе, върнете LineParseError с line_number 1. След това, всеки следващ ред се очаква или да започне с - и име на стая за добавяне (add_room), или да е празен ред, което означава, че сме приключили с добавянето на стаи. Ако е нещо друго, LineParseError със съответния ред (първия ред е 1).

Всякакви грешки, които могат да случат при извикване на add_room се очаква да се върнат от тази функция ако се случат.

Всякакви std::io::Error грешки при четене на reader-а се очаква да се пакетират във Errors::IoError и да се върнат.

Следващия ред се очаква да бъде точно ## Links. Иначе, очакваме LineParseError с реда. Оттам нататък всички следващи редове трябва да имат формата:

- <име на стая> -> <посока> -> <друга стая>

Тоест, реда започва с низа "- ", и отделните стаи са разделени с низа " -> ". Приемете, че в имената на стаите няма да съдържат -> и даже ->. Дали да изчистите интервалите около името е ваш избор, няма да тестваме с имена на стаи, които започват или завършват на whitespace.

Както може да се сетите, изпарсеното съдържание на този ред си го подайте на set_link. Ако посоката не е една от North/South/East/West, очакваме грешка Errors::DirectionParseError с низа, който се опитвате да изпарсите в посока. Ако има каквато и да е грешка във формата на този ред, LineParseError със съответния номер на ред.

Ако set_link върне грешка, очакваме да я върнете от тази функция.

В случай, че на функцията се подаде празен reader, очакваме LineParseError с номер на ред 0.

Ето прототипа на една помощна функция, която няма да тестваме директно (не е pub, няма да я викаме в тестовете), но може да ви улесни живота:

/// match_prefix("- ", "- Foo") //=> Some("Foo")
/// match_prefix("- ", "Bar")   //=> None
///
fn match_prefix<'a, 'b>(prefix: &'a str, input: &'b str) -> Option<&'b str> {
    todo!()
}

Свободни сте да я ползвате или не, свободни сте да напишете различна подобна функция. Ако ви притесняват lifetime анотациите, със сигурност ви съветваме да я имплементирате и ползвате, и да прочетете "Lifetimes" лекцията, докато спрат да ви притесняват. Имаме точно такъв пример някъде из слайдовете.

Накрая, след като сме си конструирали dungeon, да направим и нещо интересно с него.

Намиране на път

Би било смислено да правим неща като намиране на път към съкровището, който заобикаля противници, или може би търсене на противници за максимален конфликт и вдигане на level-и. Разбира се, тук нямаме съкровище, противници, или level-и, така че нека напишем просто намиране на път от една стая към друга:

impl Dungeon {
    /// Търси път от `start_room_name` до `end_room_name` и го връща във вектор, пакетиран във
    /// `Ok(Some(` ако намери.
    ///
    /// Ако няма път между тези две стаи, връща `Ok(None)`.
    ///
    /// Ако четенето на стаи в един момент върне грешка, очакваме да върнете грешката нагоре.
    ///
    pub fn find_path(
        &self,
        start_room_name: &str,
        end_room_name: &str
    ) -> Result<Option<Vec<&Room>>, Errors> {
        todo!()
    }
}

Какъв алгоритъм да ползвате? Какъвто искате -- няма да проверяваме резултатния път директно, ще проверим:

  • Дали е път -- всяка стая трябва да има директна връзка със следващата в някаква посока
  • Дали началото и края са правилните стаи

Нещо лесно, което може да ползвате, е Breadth-first search. Алгоритъма е доста добре описан в уикипедия, макар че няма логика за намиране на пълния път, само се намира node. Споменават, че може да държите parents, но не показват къде пасва в кода. Ето обобщение:

  • Подготвяте си опашка, в която слагате началната стая (опашката може да е вектор, а може да има и друга удачна структура в std::collections, която да ви свърши работа)
  • Маркирате началната стая като "посетена" (може би във вектор от посетени стаи, а може би нещо друго от std::collections)
  • Подготвяте си един HashMap от връзки от стая към нейния родител.
  • Започвате да вадите стаи от края на опашката за посещаване, докато има стаи в нея:
    • Ако стигнете до крайната стая, може да приключите с цикъла
    • Ако не, минавате през всички комшии на една стая, записвате че родителя им е текущата, маркирате ги като "посетени" и ги добавяте в началото на опашката.
  • Приключили сме цикъла. Има ли маркиран родител за крайната стая?
    • Ако не, значи не сме стигнали до крайната стая, може спокойно да върнем Ok(None)
    • Ако да, трябва да си конструираме път обратно до началото, родител по родител. Започваме от крайната стая и нейния родител, и ги пъхаме в един вектор, продължаваме да вземаме предния родител и предния родител, докато не стигнем до стая без родител -- това ще е началната. Връщаме пътя в "прав" ред -- начална до крайна стая.

Ако ви изглежда притеснително сложно -- пробвайте, карайте стъпка по стъпка, ще стане. Ако ви изглежда досадно просто, by all means имплементирайте си каквото търсене ви е интересно.

Съвети

  • Има доста error handling, който може да се опрости с употреба на някои методи от Result или от Option. Споменавали сме ги, но също така просто разгледайте документацията.
  • Нищо не пречи да търсим път от една стая към същата стая -- това е просто път с тази една стая. Също нищо учудващо няма в това да има цикъл от стаи. Ако си имплементирате горния алгоритъм, не би трябвало да имате проблеми, но определено е добра идея да тествате.
  • HashMap е ужасно удобна структура, която се използва за супер много неща и в доста езици е вградена. Това е речник, в който ключа е нещо, което имплементира Hash trait-а (много често е String), а стойността може да е каквото и да е. Документацията има чудесни примери, но може и да направим едно бонус демо видео, в което показваме употреба.

Задължително прочетете (или си припомнете): Указания за предаване на домашни

Погрижете се решението ви да се компилира с базовия тест:

#[test]
fn test_basic_1() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Hallway").unwrap();
dungeon.set_link("Entrance", Direction::East, "Hallway").unwrap();
assert_eq!(dungeon.get_room("Entrance").unwrap().name, "Entrance");
assert_eq!(dungeon.get_next_room("Entrance", Direction::East).unwrap().unwrap().name, "Hallway");
}
const TEST_INPUT_1: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
#[test]
fn test_basic_2() {
// .trim() за да премахнем първия и последния ред:
let dungeon = Dungeon::from_reader(TEST_INPUT_1.trim().as_bytes()).unwrap();
assert_eq!(dungeon.get_room("Entrance").unwrap().name, "Entrance");
assert_eq!(dungeon.get_room("Hallway").unwrap().name, "Hallway");
assert_eq!(dungeon.get_next_room("Entrance", Direction::East).unwrap().unwrap().name, "Hallway");
}
#[test]
fn test_basic_3() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Treasure Room").unwrap();
dungeon.set_link("Entrance", Direction::West, "Treasure Room").unwrap();
let path = dungeon.find_path("Entrance", "Treasure Room").unwrap().unwrap();
assert!(path.len() > 0);
}