Решение на Dungeons and Compilers от Георги Шавов
Резултати
- 19 точки от тестове
- 0 бонус точки
- 19 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
use std::collections::{HashMap, VecDeque};
use std::convert::{TryFrom, TryInto};
use std::io::BufRead;
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
#[repr(i32)]
#[derive(Clone, Copy, Debug)]
pub enum Direction {
North = 0,
South = 1,
East = 2,
West = 3,
}
impl TryFrom<&str> for Direction {
type Error = Errors;
fn try_from(value: &str) -> Result<Self, Self::Error> {
match value {
x if x == "North" => Ok(Direction::North),
x if x == "South" => Ok(Direction::South),
x if x == "East" => Ok(Direction::East),
x if x == "West" => Ok(Direction::West),
x => Err(Errors::DirectionParseError(x.to_string())),
}
}
}
type Link = Option<Box<Room>>;
pub struct Room {
pub name: String,
pub adjacent_rooms: [Option<String>; 4],
}
pub struct Dungeon {
pub rooms: HashMap<String, Link>,
}
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) {
Result::Err(Errors::DuplicateRoom(name.to_string()))
} else {
self.rooms.insert(
name.to_string(),
Some(Box::new(Room {
name: name.to_string(),
adjacent_rooms: [None, None, None, None],
})),
);
Result::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) {
let room = self.rooms[room_name]
.as_ref()
.map(|boxed_room| boxed_room.as_ref())
.unwrap();
Result::Ok(room)
} else {
Result::Err(Errors::UnknownRoom(room_name.to_string()))
}
}
/// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
/// `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) == false {
Result::Err(Errors::UnknownRoom(room_name.to_string()))
} else if self.rooms.contains_key(other_room_name) == false {
Result::Err(Errors::UnknownRoom(other_room_name.to_string()))
} else {
match direction.try_into() {
Ok(Direction::North) => {
let first_room = self
.rooms
.get(room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(second_room) = self
.rooms
.get_mut(other_room_name)
.and_then(|sroom| sroom.as_mut())
{
second_room.adjacent_rooms[1] = first_room;
}
let second_room = self
.rooms
.get(other_room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(first_room) = self
.rooms
.get_mut(room_name)
.and_then(|froom| froom.as_mut())
{
first_room.adjacent_rooms[0] = second_room;
}
}
Ok(Direction::South) => {
let first_room = self
.rooms
.get(room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(second_room) = self
.rooms
.get_mut(other_room_name)
.and_then(|sroom| sroom.as_mut())
{
second_room.adjacent_rooms[0] = first_room;
}
let second_room = self
.rooms
.get(other_room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(first_room) = self
.rooms
.get_mut(room_name)
.and_then(|froom| froom.as_mut())
{
first_room.adjacent_rooms[1] = second_room;
}
}
Ok(Direction::East) => {
let first_room = self
.rooms
.get(room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(second_room) = self
.rooms
.get_mut(other_room_name)
.and_then(|sroom| sroom.as_mut())
{
second_room.adjacent_rooms[3] = first_room;
}
let second_room = self
.rooms
.get(other_room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(first_room) = self
.rooms
.get_mut(room_name)
.and_then(|froom| froom.as_mut())
{
first_room.adjacent_rooms[2] = second_room;
}
}
Ok(Direction::West) => {
let first_room = self
.rooms
.get(room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(second_room) = self
.rooms
.get_mut(other_room_name)
.and_then(|sroom| sroom.as_mut())
{
second_room.adjacent_rooms[2] = first_room;
}
let second_room = self
.rooms
.get(other_room_name)
.and_then(|room| room.as_ref().and_then(|r| Some(r.name.clone())));
if let Some(first_room) = self
.rooms
.get_mut(room_name)
.and_then(|froom| froom.as_mut())
{
first_room.adjacent_rooms[3] = second_room;
}
}
Err(_) => unreachable!("Not existing direction!\n"),
}
Result::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) == false {
Result::Err(Errors::UnknownRoom(room_name.to_string()))
} else {
let dir;
match direction.try_into() {
Ok(Direction::North) => dir = 0,
Ok(Direction::South) => dir = 1,
Ok(Direction::East) => dir = 2,
Ok(Direction::West) => dir = 3,
Err(_) => unreachable!("Not existing direction!\n"),
}
if let Some(direction_room) = self.rooms
.get(room_name)
.and_then(|room| {
room.as_ref()
.and_then(|r| r.as_ref().adjacent_rooms[dir].clone())
})
{
Ok(Some(self.get_room(direction_room.as_str()).unwrap()))
} else {
Ok(None)
}
}
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dungeon = Dungeon::new();
let mut is_room_name = true;
let mut is_link = false;
let mut is_empty = true;
for (line_number, line) in reader.lines().enumerate()
{
if line.is_err()
{
return Result::Err(Errors::IoError(line.unwrap_err()));
}
let line_content = line.unwrap();
if line_number == 0
{
is_empty = false;
if line_content != "## Rooms" {
return Result::Err(Errors::LineParseError{ line_number: line_number + 1 });
}
}
if line_number > 0 && line_content != "" && is_room_name {
if let Some(room_name) = match_prefix("- ", &line_content)
{
if let Err(result) = dungeon.add_room(room_name)
{
return Result::Err(result);
}
}
else {
return Result::Err(Errors::LineParseError{ line_number: line_number + 1 });
}
}
else if line_number > 0 && line_content == "" && is_room_name {
is_room_name = false;
}
else if line_number > 0 && line_content != "" && is_room_name == false && is_link == false {
if line_content != "## Links" {
return Result::Err(Errors::LineParseError{ line_number: line_number + 1 });
}
is_link = true;
}
else if line_number > 0 && line_content != "" && is_link == true {
if let Some(data) = match_prefix("- ", &line_content)
{
let split:Vec<&str> = data.split(" -> ").collect();
if split.len() != 3 {
return Result::Err(Errors::LineParseError{ line_number: line_number + 1 });
}
let dir = Direction::try_from(split[1]);
if dir.is_err() {
return Result::Err(dir.unwrap_err());
}
let dir = dir.unwrap();
if let Err(result) = dungeon.set_link(split[0], dir, split[2])
{
return Result::Err(result);
}
}
else {
return Result::Err(Errors::LineParseError{ line_number: line_number + 1 });
}
}
}
if is_empty {
return Result::Err(Errors::LineParseError{ line_number: 0 });
}
Result::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 = Vec::new();
let mut parent = HashMap::new();
queue.push_back(start_room_name);
visited.push(start_room_name);
parent.insert(start_room_name, start_room_name);
while !queue.is_empty()
{
if let Some(current) = queue.pop_front()
{
let current_room = self.get_room(current);
match current_room {
Err(e) => return Err(e),
Ok(room) => {
for adj in &room.adjacent_rooms {
match adj {
Some(x) => {
let adj_room = x.as_str();
if visited.contains(&adj_room) == false {
visited.push(adj_room);
queue.push_back(adj_room);
parent.insert(adj_room, room.name.as_str());
}
}
None => {}
}
}
}
}
}
}
if parent.contains_key(end_room_name) == false {
return Ok(None);
}
let mut path = Vec::new();
path.push(self.get_room(end_room_name).unwrap());
let mut current = end_room_name.clone();
while current != parent.get(current).unwrap().clone() {
current = parent.get(current).unwrap().clone();
path.push(self.get_room(current).unwrap());
}
path.reverse();
Ok(Some(path))
}
}
fn match_prefix<'a, 'b>(prefix: &'a str, input: &'b str) -> Option<&'b str> {
input.strip_prefix(prefix)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn add_room() {
let mut dungeon = Dungeon::new();
assert_eq!(dungeon.add_room("Мачическа стая").is_ok(), true);
assert_eq!(dungeon.add_room("Мачическа стая").is_err(), true);
assert_eq!(dungeon.add_room("Стаята на тайните").is_ok(), true);
}
#[test]
fn get_room() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Мачическа стая").unwrap();
dungeon.add_room("Стаята на тайните").unwrap();
assert_eq!(dungeon.get_room("Мачическа стая").is_ok(), true);
assert_eq!(dungeon.get_room("Стаята на тайните").is_ok(), true);
assert_eq!(dungeon.get_room("Sus").is_err(), true);
}
#[test]
fn set_link() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Hallway").unwrap();
assert_eq!(dungeon.set_link("Entrance", Direction::East, "Hallway").is_ok(), true);
assert_eq!(dungeon.set_link("Random room", Direction::East, "Hallway").is_err(), true);
assert_eq!(dungeon.set_link("Entrance", Direction::East, "Random room").is_err(), true);
assert_eq!(dungeon.set_link("Some room", Direction::East, "Random room").is_err(), true);
}
#[test]
fn get_next_room() {
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_next_room("Entrance", Direction::East).unwrap().unwrap().name, "Hallway");
assert_eq!(dungeon.get_next_room("Hallway", Direction::West).unwrap().unwrap().name, "Entrance");
assert_eq!(dungeon.get_next_room("Some room", Direction::West).is_err(), true);
assert_eq!(dungeon.get_next_room("Entrance", Direction::West).unwrap().is_none(), true);
}
#[test]
fn overriding_links() {
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");
}
const TEST_INPUT_1: &str = "
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_2: &str = "
## Rooms
- Entrance
- Hallway
- Entrance -> East -> Hallway
";
const TEST_INPUT_3: &str = "
## Rooms
- Entrance
- Hallway
- Entrance
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_4: &str = "
## Rooms
Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_5: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance East -> Hallway
";
const TEST_INPUT_6: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> Dir -> Hallway
";
const TEST_INPUT_7: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
#[test]
fn from_reader() {
assert_eq!(Dungeon::from_reader(TEST_INPUT_1.trim().as_bytes()).is_err(), true);
assert_eq!(Dungeon::from_reader(TEST_INPUT_2.trim().as_bytes()).is_err(), true);
assert_eq!(Dungeon::from_reader(TEST_INPUT_3.trim().as_bytes()).is_err(), true);
assert_eq!(Dungeon::from_reader(TEST_INPUT_4.trim().as_bytes()).is_err(), true);
assert_eq!(Dungeon::from_reader(TEST_INPUT_5.trim().as_bytes()).is_err(), true);
assert_eq!(Dungeon::from_reader(TEST_INPUT_6.trim().as_bytes()).is_err(), true);
assert_eq!(Dungeon::from_reader("".as_bytes()).is_err(), true);
let dungeon = Dungeon::from_reader(TEST_INPUT_7.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 find_path() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Entrance").unwrap();
dungeon.add_room("Treasure Room").unwrap();
assert_eq!(dungeon.find_path("Entrance", "Treasure Room").unwrap().is_none(), true);
let path = dungeon.find_path("Treasure Room", "Treasure Room").unwrap().unwrap();
assert!(path.len() == 1);
assert_eq!(path[0].name, "Treasure Room");
dungeon.set_link("Entrance", Direction::West, "Treasure Room").unwrap();
let path = dungeon.find_path("Entrance", "Treasure Room").unwrap().unwrap();
assert!(path.len() == 2);
assert_eq!(path[0].name, "Entrance");
assert_eq!(path[1].name, "Treasure Room");
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20220116-3533338-1u14flb/solution)
Finished test [unoptimized + debuginfo] target(s) in 3.78s
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'