Решение на Dungeons and Compilers от Чудомир Ченков
Резултати
- 17 точки от тестове
- 0 бонус точки
- 17 точки общо
- 13 успешни тест(а)
- 2 неуспешни тест(а)
Код
use std::collections::{HashMap, VecDeque};
use std::io::BufRead;
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Clone, Copy, Debug)]
pub enum Direction {
North,
South,
East,
West,
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
#[derive(Debug)]
pub struct Room {
pub name: String,
// Каквито други полета ви трябват
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
#[derive(Debug)]
pub struct Dungeon {
// Каквито полета ви трябват
pub rooms: HashMap<String, Room>,
}
impl std::fmt::Display for Direction {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{:?}", self)
}
}
impl std::str::FromStr for Direction {
type Err = Errors;
fn from_str(s: &str) -> Result<Self, Errors> {
match s {
"North" => Ok(Direction::North),
"South" => Ok(Direction::South),
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
_ => Err(Errors::DirectionParseError(s.to_string()))
}
}
}
/// Trait за откриване на противоположната на дадена посока
trait Opposite {
fn opposite(self) -> Self;
}
impl Opposite for Direction {
fn opposite(self) -> Direction {
match self {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::East => Direction::West,
Direction::West => Direction::East,
}
}
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
Dungeon {
rooms: HashMap::new()
}
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
if self.rooms.contains_key(name) {
Err(Errors::DuplicateRoom(name.to_owned()))
} else {
self.rooms.insert(name.to_owned(), Room {name: name.to_owned()});
Ok(())
}
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
if !self.rooms.contains_key(room_name) {
Err(Errors::UnknownRoom(room_name.to_owned()))
} else {
Ok(self.rooms.get(room_name).unwrap())
}
}
/// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
/// `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(room_name) {
Err(Errors::UnknownRoom(room_name.to_owned()))
} else if !self.rooms.contains_key(other_room_name) {
Err(Errors::UnknownRoom(other_room_name.to_owned()))
} else {
let normal_direction = format!("{} {}", room_name, direction.to_string());
let opposite_direction = format!("{} {}", other_room_name, direction.opposite().to_string());
self.rooms.insert(normal_direction, Room {name: other_room_name.to_owned()});
self.rooms.insert(opposite_direction, Room {name: room_name.to_owned()});
Ok(())
}
}
/// Четене на съседа на стаята с име `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(room_name) {
Err(Errors::UnknownRoom(room_name.to_owned()))
} else {
let next_room_name = format!("{} {}", room_name, direction.to_string());
if self.rooms.contains_key(&next_room_name) {
Ok(Some(self.rooms.get(&next_room_name).unwrap()))
} else {
Ok(None)
}
}
}
/// Помощни функции за функцията from_reader
fn read_rooms<B: BufRead>(
reader: &mut B,
dungeon: &mut Dungeon,
count: &mut usize
) -> Result<usize, Errors> {
let mut room_line: String = String::new();
loop {
*count += 1;
reader.read_line(&mut room_line).map_err(|e| Errors::IoError(e))?;
room_line = room_line.trim().to_string();
if room_line.is_empty() {
break;
}
if !room_line.starts_with("- ") {
return Err(Errors::LineParseError { line_number: *count });
}
let room_name = &room_line[2..room_line.len()];
dungeon.add_room(room_name)?;
room_line.clear();
}
Ok(*count)
}
fn read_links<B: BufRead>(
reader: &mut B,
dungeon: &mut Dungeon,
count: &mut usize
) -> Result<usize, Errors> {
let mut link_line = String::new();
loop {
*count += 1;
let bytes = reader.read_line(&mut link_line).map_err(|e| Errors::IoError(e))?;
if bytes == 0 {
break;
}
link_line = link_line.trim().to_string();
if !link_line.starts_with("- ") {
return Err(Errors::LineParseError { line_number: *count });
}
link_line = link_line[2..link_line.len()].to_string();
let link_params : Vec<&str> = link_line.split(" -> ").collect();
if link_params.len() != 3 {
return Err(Errors::LineParseError { line_number: *count });
}
let direction = link_params[1].parse()?;
dungeon.set_link(link_params[0], direction, link_params[2])?;
link_line.clear();
}
Ok(*count)
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(mut reader: B) -> Result<Self, Errors> {
let mut dungeon: Dungeon = Dungeon::new();
let mut line_counter: usize = 0;
if reader.fill_buf().unwrap().is_empty() {
return Err(Errors::LineParseError { line_number: 0 });
}
line_counter += 1;
let mut rooms_label_line = String::new();
reader.read_line(&mut rooms_label_line).map_err(|e| Errors::IoError(e))?;
if !rooms_label_line.trim().to_string().eq("## Rooms") {
return Err(Errors::LineParseError { line_number: line_counter });
}
Dungeon::read_rooms(&mut reader, &mut dungeon, &mut line_counter)?;
line_counter += 1;
let mut links_label_line = String::new();
reader.read_line(&mut links_label_line).map_err(|e| Errors::IoError(e))?;
if !links_label_line.trim().to_string().eq("## Links") {
return Err(Errors::LineParseError { line_number: line_counter });
}
Dungeon::read_links(&mut reader, &mut dungeon, &mut line_counter)?;
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 start_room = self.get_room(start_room_name).unwrap();
if start_room_name.eq(end_room_name) {
return Ok(Some(vec![start_room]));
}
let directions: Vec<Direction> = vec![Direction::North, Direction::South, Direction::East, Direction::West];
let mut queue: VecDeque<&Room> = VecDeque::new();
let mut visited: Vec<String> = Vec::new();
let mut parents: HashMap<String, &Room> = HashMap::new();
let mut path: Vec<&Room> = Vec::new();
queue.push_back(start_room);
visited.push(start_room.name.clone());
while !queue.is_empty() {
let curr = queue.pop_front().unwrap();
if curr.name.eq(end_room_name) {
break;
}
for direction in directions.iter() {
let next_room = self.get_next_room(&curr.name, *direction)?;
if next_room.is_some() && !visited.contains(&next_room.unwrap().name) {
visited.push(next_room.unwrap().name.clone());
queue.push_back(next_room.unwrap());
parents.insert(next_room.unwrap().name.clone(), curr);
}
}
}
if !parents.contains_key(end_room_name) {
return Ok(None);
}
let mut curr = self.get_room(end_room_name).unwrap();
path.push(curr);
while parents.contains_key(&curr.name) {
curr = parents.get(&curr.name).unwrap();
path.push(curr);
}
path.reverse();
Ok(Some(path))
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20220116-3533338-ywxce9/solution)
Finished test [unoptimized + debuginfo] target(s) in 3.80s
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 ... FAILED
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
---- solution_test::test_io_error stdout ----
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: Custom { kind: Other, error: "fill_buf error!" }', /tmp/d20220116-3533338-ywxce9/solution/src/lib.rs:250:30
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Custom { kind: Other, error: "fill_buf error!" }', tests/solution_test.rs:194:5
failures:
solution_test::test_finding_no_path
solution_test::test_io_error
test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass '--test solution_test'