Решение на Dungeons and Compilers от Никола Николов
Резултати
- 19 точки от тестове
- 1 бонус точка
- 20 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
use std::{
collections::{HashMap, VecDeque},
io::BufRead,
str::FromStr,
};
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
impl From<std::io::Error> for Errors {
fn from(err: std::io::Error) -> Self {
Errors::IoError(err)
}
}
/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Clone, Copy, Hash, PartialEq, Eq)]
pub enum Direction {
North,
South,
East,
West,
}
impl FromStr for Direction {
type Err = Errors;
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
"South" => Ok(Direction::South),
"North" => Ok(Direction::North),
_ => Err(Errors::DirectionParseError(String::from(s))),
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
pub struct Room {
pub name: String,
// Каквито други полета ви трябват
}
impl Room {
pub fn new(name: &str) -> Self {
Room {
name: String::from(name),
}
}
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
pub struct Dungeon {
pub rooms: HashMap<String, Room>,
pub links: HashMap<(String, Direction), Room>, // Каквито полета ви трябват
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
Dungeon {
rooms: HashMap::new(),
links: HashMap::new(),
}
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
if self.rooms.contains_key(&String::from(name)) {
return Err(Errors::DuplicateRoom(String::from(name)));
}
self.rooms.insert(
String::from(name),
Room {
name: String::from(name),
},
);
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
match self.rooms.get(&String::from(room_name)) {
Some(room) => Ok(room),
None => Err(Errors::UnknownRoom(String::from(room_name))),
}
}
/// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
/// `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> {
if !self.rooms.contains_key(&String::from(room_name)) {
return Err(Errors::UnknownRoom(String::from(room_name)));
}
if !self.rooms.contains_key(&String::from(other_room_name)) {
return Err(Errors::UnknownRoom(String::from(other_room_name)));
}
self.links.insert(
(String::from(room_name), direction),
Room::new(other_room_name),
);
self.links.insert(
(
String::from(other_room_name),
Self::get_oposite_direction(direction),
),
Room::new(room_name),
);
Ok(())
}
fn get_oposite_direction(direction: Direction) -> Direction {
match direction {
Direction::East => Direction::West,
Direction::West => Direction::East,
Direction::North => Direction::South,
Direction::South => Direction::North,
}
}
/// Четене на съседа на стаята с име `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> {
if !self.rooms.contains_key(&String::from(room_name)) {
return Err(Errors::UnknownRoom(String::from(room_name)));
}
if !self
.links
.contains_key(&(String::from(room_name), direction))
{
return Ok(None);
}
Ok(self.links.get(&(String::from(room_name), direction)))
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dungeon = Self::new();
let mut lines = reader.lines();
let first_line = lines.next();
if first_line.is_none() {
return Err(Errors::LineParseError { line_number: 0 });
}
if first_line.unwrap()? != String::from("## Rooms") {
return Err(Errors::LineParseError { line_number: 1 });
}
let mut line_number = 2;
// read rooms
for line in lines.by_ref() {
let mut content = line?;
// separator between rooms and links
if content.trim().is_empty() {
line_number += 1;
break;
}
if !content.starts_with("- ") {
return Err(Errors::LineParseError { line_number });
}
content.remove(0);
dungeon.add_room(content.trim())?;
line_number += 1;
}
let links_line = lines.next();
if links_line.is_none() || links_line.unwrap()? != String::from("## Links") {
return Err(Errors::LineParseError { line_number });
}
line_number += 1;
// read links
for line in lines {
let content = line?;
if !content.starts_with("- ") {
return Err(Errors::LineParseError { line_number });
}
line_number += 1;
let link_info: Vec<&str> = content.split("->").collect();
let first_room_name = link_info[0].split("- ").collect::<Vec<&str>>()[1].trim();
let second_room_name = link_info[2].trim();
let direction = Direction::from_str(link_info[1].trim())?;
dungeon.set_link(first_room_name, direction, second_room_name)?;
}
Ok(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> {
let mut queue = VecDeque::new();
let mut visited_rooms = Vec::new();
let mut rooms_parents: HashMap<&str, &str> = HashMap::new();
let directions = [
Direction::East,
Direction::West,
Direction::North,
Direction::South,
];
queue.push_back(start_room_name);
while !queue.is_empty() {
let current_room = queue.pop_front().unwrap();
visited_rooms.push(current_room);
if current_room == end_room_name {
break;
}
for direction in directions {
if let Some(room) = self.get_next_room(current_room, direction)? {
if !visited_rooms.contains(&&*room.name) {
queue.push_back(&room.name);
rooms_parents.insert(&room.name, current_room);
}
}
}
}
if !visited_rooms.contains(&end_room_name) {
return Ok(None);
}
let mut path: Vec<&Room> = Vec::new();
path.push(self.get_room(end_room_name)?);
let mut current_first;
while path.last().unwrap().name != start_room_name {
current_first = path.last().unwrap();
let parent = rooms_parents.get(&*current_first.name).unwrap();
let parent_as_room = self.get_room(parent)?;
path.push(parent_as_room);
}
path.reverse();
return Ok(Some(path));
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn add_room_returns_duplicate_room_error() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
let res = dungeon.add_room("Entrance");
let room_name = match res {
Err(Errors::DuplicateRoom(r_name)) => r_name,
_ => panic!(),
};
assert_eq!(room_name, "Entrance")
}
#[test]
fn get_room_returns_unknown_room_error() {
let dungeon = Dungeon::new();
let res = dungeon.get_room("Entrance");
let room_name = match res {
Err(Errors::UnknownRoom(r_name)) => r_name,
_ => panic!(),
};
assert_eq!(room_name, "Entrance")
}
#[test]
fn set_link_returns_unkown_room_error() {
let mut dungeon = Dungeon::new();
let res = dungeon.set_link("Entrance", Direction::East, "Hallway");
let room_name = match res {
Err(Errors::UnknownRoom(r_name)) => r_name,
_ => panic!(),
};
assert_eq!(room_name, "Entrance")
}
#[test]
fn get_next_room_returns_unknown_room_error() {
let dungeon = Dungeon::new();
let res = dungeon.get_next_room("Entrance", Direction::East);
let room_name = match res {
Err(Errors::UnknownRoom(r_name)) => r_name,
_ => panic!(),
};
assert_eq!(room_name, "Entrance")
}
#[test]
fn get_next_room_returns_none() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
let res = dungeon.get_next_room("Entrance", Direction::East).unwrap();
assert!(res.is_none())
}
#[test]
fn add_room_successfully_adds_room_and_links() {
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"
);
assert_eq!(
dungeon
.get_next_room("Entrance", Direction::East)
.unwrap()
.unwrap()
.name,
"Hallway"
);
}
#[test]
fn from_reader_returns_parser_error_on_empty_file() {
let data = "";
let result = Dungeon::from_reader(data.as_bytes());
match result {
Err(Errors::LineParseError { line_number: 0 }) => {}
_ => panic!(),
}
}
#[test]
fn from_reader_returns_parser_error_on_incorrect_rooms_line() {
let data = "## Shrooms";
let result = Dungeon::from_reader(data.as_bytes());
match result {
Err(Errors::LineParseError { line_number: 1 }) => {}
_ => panic!(),
}
}
#[test]
fn from_reader_returns_parser_error_on_incorrect_room_line() {
let data = "## Rooms
- Entrance
-Hallway";
let result = Dungeon::from_reader(data.as_bytes());
match result {
Err(Errors::LineParseError { line_number: 3 }) => {}
_ => panic!(),
}
}
#[test]
fn from_reader_returns_duplicate_room_error_on_duplicating_room() {
let data = "## Rooms
- Entrance
- Entrance";
let result = Dungeon::from_reader(data.as_bytes());
let room_name = match result {
Err(Errors::DuplicateRoom(room_name)) => room_name,
_ => panic!(),
};
assert_eq!(room_name, String::from("Entrance"))
}
#[test]
fn from_reader_returns_parser_error_on_missing_links_line() {
let data = "## Rooms
- Entrance
- Hallway
";
let result = Dungeon::from_reader(data.as_bytes());
match result {
Err(Errors::LineParseError { line_number: 5 }) => {}
_ => panic!(),
}
}
#[test]
fn from_reader_returns_parser_error_on_incorrect_links_line() {
let data = "## Rooms
- Entrance
- Hallway
## Limes";
let result = Dungeon::from_reader(data.as_bytes());
match result {
Err(Errors::LineParseError { line_number: 5 }) => {}
_ => panic!(),
}
}
#[test]
fn from_reader_returns_parser_error_on_incorrect_link_line() {
let data = "## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
-Entrance -> West -> Hallway";
let result = Dungeon::from_reader(data.as_bytes());
match result {
Err(Errors::LineParseError { line_number: 7 }) => {}
_ => panic!(),
}
}
#[test]
fn from_reader_returns_unknown_room_error_on_link_with_unknown_room() {
let data = "## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
- Alabala -> West -> Hallway";
let result = Dungeon::from_reader(data.as_bytes());
let room_name = match result {
Err(Errors::UnknownRoom(room_name)) => room_name,
_ => panic!(),
};
assert_eq!(room_name, String::from("Alabala"))
}
#[test]
fn from_reader_returns_direction_parser_error_on_link_with_invalid_direction() {
let data = "## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
- Alabala -> Up -> Hallway";
let result = Dungeon::from_reader(data.as_bytes());
let direction = match result {
Err(Errors::DirectionParseError(direction)) => direction,
_ => panic!(),
};
assert_eq!(direction, String::from("Up"))
}
#[test]
fn from_reader_parses_the_file_correctly() {
let data = "## Rooms
- Entrance
- Hallway
- Magic Lab
- Недостижима стая
## Links
- Entrance -> East -> Hallway
- Hallway -> West -> Magic Lab";
let dungeon = Dungeon::from_reader(data.as_bytes()).unwrap();
assert_eq!(dungeon.get_room("Hallway").unwrap().name, "Hallway");
assert_eq!(dungeon.get_room("Entrance").unwrap().name, "Entrance");
assert_eq!(dungeon.get_room("Magic Lab").unwrap().name, "Magic Lab");
assert_eq!(
dungeon.get_room("Недостижима стая").unwrap().name,
"Недостижима стая"
);
assert_eq!(
dungeon
.get_next_room("Hallway", Direction::West)
.unwrap()
.unwrap()
.name,
"Magic Lab"
);
assert_eq!(
dungeon
.get_next_room("Magic Lab", Direction::East)
.unwrap()
.unwrap()
.name,
"Hallway"
);
}
#[test]
fn find_path_returns_unknown_room_on_empty_dungeon() {
let dungeon = Dungeon::new();
let result = dungeon.find_path("Entrance", "Magic Lab");
let room_name = match result {
Err(Errors::UnknownRoom(r_name)) => r_name,
_ => panic!(),
};
assert_eq!(room_name, "Entrance")
}
#[test]
fn find_path_returns_none_when_there_is_no_path() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Treasure Room").unwrap();
dungeon.add_room("Magic Lab").unwrap();
dungeon
.set_link("Entrance", Direction::West, "Treasure Room")
.unwrap();
let path = dungeon.find_path("Entrance", "Magic Lab").unwrap();
assert!(path.is_none());
}
#[test]
fn find_path_returns_none_when_there_is_a_cycle() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Hallway").unwrap();
dungeon.add_room("Entrance").unwrap();
dungeon
.set_link("Hallway", Direction::South, "Hallway")
.unwrap();
let path = dungeon.find_path("Hallway", "Entrance").unwrap();
assert!(path.is_none());
}
#[test]
fn find_path_returns_a_path_when_there_is_a_cycle() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Hallway").unwrap();
dungeon
.set_link("Hallway", Direction::South, "Hallway")
.unwrap();
let path = dungeon.find_path("Hallway", "Hallway").unwrap().unwrap();
let path_room_names: Vec<&str> = path.into_iter().map(|r| &*r.name).collect();
assert_eq!(path_room_names, vec!["Hallway"]);
}
#[test]
fn find_path_returns_a_path() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Hallway").unwrap();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Treasure Room").unwrap();
dungeon.add_room("Magic Lab").unwrap();
dungeon
.set_link("Hallway", Direction::South, "Entrance")
.unwrap();
dungeon
.set_link("Entrance", Direction::West, "Treasure Room")
.unwrap();
dungeon
.set_link("Treasure Room", Direction::East, "Magic Lab")
.unwrap();
let path = dungeon.find_path("Hallway", "Magic Lab").unwrap().unwrap();
let path_room_names: Vec<&str> = path.into_iter().map(|r| &*r.name).collect();
assert_eq!(
path_room_names,
vec!["Hallway", "Entrance", "Treasure Room", "Magic Lab"]
);
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20220116-3533338-1ddkirv/solution)
Finished test [unoptimized + debuginfo] target(s) in 4.50s
Running tests/solution_test.rs (target/debug/deps/solution_test-2e292b23ac75572c)
running 15 tests
test solution_test::test_adding_rooms_1 ... ok
test solution_test::test_adding_rooms_2 ... ok
test solution_test::test_cyrillic_room_names ... ok
test solution_test::test_finding_a_direct_path ... ok
test solution_test::test_finding_a_reflexive_path ... ok
test solution_test::test_finding_an_indirect_path ... ok
test solution_test::test_finding_no_path ... FAILED
test solution_test::test_invalid_parsing ... ok
test solution_test::test_io_error ... ok
test solution_test::test_overwriting_a_room_link ... ok
test solution_test::test_parsing_cyrillic_rooms ... ok
test solution_test::test_parsing_no_rooms_or_links ... ok
test solution_test::test_parsing_rooms ... ok
test solution_test::test_room_errors ... ok
test solution_test::test_room_links ... ok
failures:
---- solution_test::test_finding_no_path stdout ----
thread '<unnamed>' panicked at 'assertion failed: path.is_err()', tests/solution_test.rs:382:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:372:5
failures:
solution_test::test_finding_no_path
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass '--test solution_test'