Решение на Dungeons and Compilers от Тодор Тодоров
Резултати
- 16 точки от тестове
- 0 бонус точки
- 16 точки общо
- 12 успешни тест(а)
- 3 неуспешни тест(а)
Код
use std::{
collections::HashMap,
collections::VecDeque,
hash::Hash, hash::Hasher,
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, PartialEq, Eq)]
pub enum Direction {
North,
South,
East,
West,
Invalid,
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Room {
pub name: String,
// Каквито други полета ви трябват
}
impl Room {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new(room_name: String) -> Self {
Self{
name: room_name.clone(),
}
}
}
impl Hash for Room {
fn hash<H: Hasher>(&self, state: &mut H) {
self.name.hash(state);
}
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
pub struct Dungeon {
pub rooms: HashMap<Room, Vec<(Direction, Room)>>,
// Каквито полета ви трябват
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
Self{
rooms: HashMap::new()
}
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
let room = Room::new(name.to_string());
if !self.rooms.contains_key(&room) {
self.rooms.insert(room, Vec::new());
}
else {
return Err(Errors::DuplicateRoom(name.to_string()));
}
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let res = self.rooms.get_key_value(&Room::new(room_name.to_string()));
if res.is_none() {
return Err(Errors::UnknownRoom(room_name.to_string()));
}
Ok(res.unwrap().0)
}
/// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
/// `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> {
let room1 = Room::new(room_name.to_string());
let room2 = Room::new(other_room_name.to_string());
let has_room1 = self.rooms.contains_key(&room1.clone());
let has_room2 = self.rooms.contains_key(&room2.clone());
if has_room1 && has_room2 {
let rooms_vec = self.rooms.get_mut(&room1.clone()).unwrap();
if !rooms_vec.iter_mut().any(|x| {
if x.0 == direction {
x.1 = room2.clone();
}
x.0 == direction
}){
rooms_vec.push((direction, room2.clone()));
}
let new_dir: Direction;
match direction {
Direction::North => new_dir = Direction::South,
Direction::South => new_dir = Direction::North,
Direction::East => new_dir = Direction::West,
Direction::West => new_dir = Direction::East,
_ => return Err(Errors::UnknownRoom(room1.name)),
}
let rooms_vec2 = self.rooms.get_mut(&room2.clone()).unwrap();
if !rooms_vec2.iter_mut().any(|x| {
if x.0 == new_dir {
x.1 = room1.clone();
}
x.0 == direction
}){
rooms_vec2.push((new_dir, room1));
}
}
else if !has_room1 {
return Err(Errors::UnknownRoom(room1.name));
}
else {
return Err(Errors::UnknownRoom(room2.name));
}
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> {
let room = Room::new(room_name.to_string());
if self.rooms.contains_key(&room.clone()) {
let neighbours = self.rooms.get(&room.clone()).unwrap();
let the_neighbour = neighbours.iter().find(|&x| x.0 == direction);
if the_neighbour.is_some() {
return Ok(Some(&the_neighbour.unwrap().1));
}
else {
return Ok(None);
}
}
else {
return Err(Errors::UnknownRoom(room.name));
}
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dungeon = Dungeon::new();
let mut state = ReadState::ReadRoomsHeader;
let mut i:usize = 1;
let mut err = 0;
for line in reader.lines() {
match state {
ReadState::ReadRoomsHeader => {
if line.unwrap().trim().ne("## Rooms") {
err = i;
}
state = ReadState::ReadRooms;
},
ReadState::ReadRooms => {
if !line.as_ref().unwrap().trim().is_empty() {
let room_name = line.as_ref().unwrap().split_once('-');
if room_name.is_some() {
if (dungeon.add_room(room_name.unwrap().1.trim())).is_err() {
err = i;
}
}
else {
err = i;
}
}
else {
state = ReadState::ReadLinksHeader;
}
},
ReadState::ReadLinksHeader => {
if line.unwrap().trim().ne("## Links") {
err = i;
}
state = ReadState::ReadLinks;
},
ReadState::ReadLinks => {
let link = line.as_ref().unwrap().trim().split_once("-").unwrap();
if link.0.trim().len() > 0 {
return Err(Errors::LineParseError { line_number: err });
}
let links:Vec<&str> = link.1.trim().split("->").collect();
if links.len() != 3 { return Err(Errors::LineParseError { line_number: err });}
let room1 = Room{name: links[0].trim().to_string()};
let room2 = Room{name: links[2].trim().to_string()};
let direction = get_direction(links[1].trim());
if links.len() == 3
&& dungeon.rooms.contains_key(&room1.clone())
&& dungeon.rooms.contains_key(&room2.clone())
&& direction != Direction::Invalid{
let res = dungeon.set_link(links[0].trim(), direction, links[2].trim());
if res.is_err() {
return Err(res.err().unwrap());
}
}
else {
err = i;
}
},
ReadState::End => {
err = i;
},
}
i = i + 1;
if err != 0 {
return Err(Errors::LineParseError { line_number: err });
}
};
Ok(dungeon)
}
fn _find_path<'a>(
&'a self,
start_room: &'a Room,
end_room: &'a Room
) -> Result<Option<Vec<&'a Room>>, Errors> {
let mut visited = HashMap::new();
let mut parents = HashMap::new();
for room in self.rooms.keys() {
visited.insert(room, false);
parents.insert(room, room);
}
let mut q = VecDeque::new();
q.push_back(start_room);
while !q.is_empty() {
let room = q.pop_front().unwrap();
if room.name == end_room.name {
// build path
let mut path = Vec::new();
let mut curr_room = end_room;
while curr_room != start_room {
path.push(curr_room);
curr_room = parents[curr_room];
}
path.push(start_room);
path.reverse();
return Ok(Some(path));
}
let neighbours_opt = self.rooms.get(room);
let neighbours;
if neighbours_opt.is_some() {
neighbours = neighbours_opt.unwrap();
for n in neighbours {
if !visited.get(&n.1).unwrap() {
*visited.get_mut(&n.1).unwrap() = true;
*parents.get_mut(&n.1).unwrap() = room;
q.push_back(&n.1);
}
}
}
}
return Ok(None);
}
/// Търси път от `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.rooms.get_key_value(&Room::new(start_room_name.to_string())).unwrap().0;
let end_room = self.rooms.get_key_value(&Room::new(end_room_name.to_string())).unwrap().0;
return self._find_path(start_room, end_room);
}
}
#[derive(Debug)]
pub enum ReadState {
ReadRoomsHeader,
ReadRooms,
ReadLinksHeader,
ReadLinks,
End,
}
pub fn get_direction(str: &str) -> Direction {
return match str {
"North" => Direction::North,
"South" => Direction::South,
"East" => Direction::East,
"West" => Direction::West,
_ => Direction::Invalid,
}
}
#[cfg(test)]
mod tests {
use std::{fs::File, io::BufReader};
use crate::{Dungeon, Direction, Room};
#[test]
fn it_works() {
let result = 2 + 2;
assert_eq!(result, 4);
}
#[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);
}
#[test]
fn test_basic_4() {
let f = File::open("dungeon.txt").unwrap();
let f = BufReader::new(f);
let dungeon_res = Dungeon::from_reader(f);
if dungeon_res.is_ok() {
let dungeon = dungeon_res.unwrap();
let path = dungeon.find_path("Entrance", "Magic Lab").unwrap().unwrap();
assert_eq!(path, vec![&Room::new("Entrance".to_string()), &Room::new("Hallway".to_string()), &Room::new("Magic Lab".to_string())]);
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20220116-3533338-hqqszd/solution)
Finished test [unoptimized + debuginfo] target(s) in 3.84s
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 ... FAILED
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 'called `Option::unwrap()` on a `None` value', src/lib.rs:325:88
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_invalid_parsing stdout ----
thread 'main' panicked at 'assertion failed: matches!(Dungeon :: from_reader(\"\".as_bytes()),\n Err(Errors :: LineParseError { line_number : 0 }))', tests/solution_test.rs:276: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-hqqszd/solution/src/lib.rs:202:29
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_invalid_parsing
solution_test::test_io_error
test result: FAILED. 12 passed; 3 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass '--test solution_test'