Решение на Dungeons and Compilers от Михаил Енев
Резултати
- 17 точки от тестове
- 0 бонус точки
- 17 точки общо
- 13 успешни тест(а)
- 2 неуспешни тест(а)
Код
use std::collections::HashMap;
use std::collections::VecDeque;
use std::collections::HashSet;
use std::io::BufRead;
use std::str::FromStr;
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
#[derive(Clone, Copy)]
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),
"South" => Ok(Direction::South),
"West" => Ok(Direction::West),
"North" => Ok(Direction::North),
_ => Err(Errors::DirectionParseError(s.to_string()))
}
}
}
impl Direction {
fn to_number(&self) -> usize {
match self {
Direction::North => 0,
Direction::South => 1,
Direction::East => 2,
Direction::West => 3
}
}
}
#[derive(Debug)]
pub struct Room {
pub name: String,
neighbors: Vec<NeighborWrapper>
}
#[derive(Clone, Debug)]
enum NeighborWrapper {
Neighbor(String),
None,
}
pub struct Dungeon {
rooms: HashMap<String, Room>
}
impl Dungeon {
pub fn new() -> Self {
Dungeon {rooms: HashMap::new()}
}
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
let r = self.rooms.get(name);
let name_str = name.to_string();
match r {
Some(_) => return Err(Errors::DuplicateRoom(name_str)),
None => self.rooms.insert(name_str.clone(), Room{name: name_str, neighbors: vec![NeighborWrapper::None; 4]}),
};
Ok(())
}
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let r = self.rooms.get(room_name);
match r {
Some(room) => return Ok(room),
None => return Err(Errors::UnknownRoom(room_name.to_string()))
}
}
pub fn set_link(
&mut self,
room_name: &str,
direction: Direction,
other_room_name: &str,
) -> Result<(), Errors> {
let mut dir = direction.to_number();
self.rooms.get_mut(room_name)
.ok_or(Errors::UnknownRoom(room_name.to_string()))?
.neighbors[dir] = NeighborWrapper::Neighbor(other_room_name.to_string());
if dir % 2 == 0 {
dir += 1;
}
else {
dir -= 1;
}
self.rooms.get_mut(other_room_name)
.ok_or(Errors::UnknownRoom(other_room_name.to_string()))?
.neighbors[dir] = NeighborWrapper::Neighbor(room_name.to_string());
Ok(())
}
pub fn get_next_room(&self, room_name: &str, direction: Direction) -> Result<Option<&Room>, Errors> {
let r = self.rooms.get(room_name).ok_or(Errors::UnknownRoom(room_name.to_string()))?;
match &r.neighbors[direction.to_number()] {
NeighborWrapper::Neighbor(neighbor_name) => Ok(self.rooms.get(neighbor_name)),
NeighborWrapper::None => Ok(None)
}
}
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dung = Dungeon::new();
let mut lines_iter = reader.lines();
match lines_iter.next() {
Some(s) => {
if s.unwrap() != "## Rooms" {
return Err(Errors::LineParseError{ line_number: 1})
};
}
None => return Err(Errors::LineParseError{ line_number: 0})
}
let mut line = 2;
while let Some(Ok(mut s)) = lines_iter.next() {
s = s.trim().to_string();
if s.is_empty() {
line += 1;
break;
}
if !s.starts_with("- ") {
return Err(Errors::LineParseError{ line_number: line})
}
s = s.split_off(2);
dung.add_room(&s)?;
line += 1;
}
if lines_iter.next().unwrap().unwrap().trim() != "## Links" {
return Err(Errors::LineParseError{ line_number: line})
};
while let Some(Ok(mut s)) = lines_iter.next() {
s = s.trim().to_string();
if s.is_empty() {
//line+=1;
break;
}
if !s.starts_with("- ") {
return Err(Errors::LineParseError{ line_number: line})
}
s = s.split_off(2);
let vec : Vec<&str> = s.split(" -> ").collect();
let dir = Direction::from_str(vec[1])?;
dung.set_link(vec[0], dir, vec[2])?;
line += 1;
}
Ok(dung)
}
fn build_path_helper(&self, parents_map: HashMap<&str, &str>, start_room: &str, end_room: &str) -> Vec<&Room> {
let mut vec = Vec::new();
let mut r = self.rooms.get(start_room).unwrap();
vec.push(r);
while vec[vec.len() - 1].name != end_room {
let next_room = parents_map.get(r.name.as_str()).unwrap();
r = self.rooms.get(*next_room).unwrap();
vec.push(r);
}
vec.reverse();
vec
}
pub fn find_path(
&self,
start_room_name: &str,
end_room_name: &str
) -> Result<Option<Vec<&Room>>, Errors> {
let _start_room = self.rooms.get(start_room_name).ok_or(Errors::UnknownRoom(start_room_name.to_string()))?;
if !self.rooms.contains_key(end_room_name) {
return Err(Errors::UnknownRoom(end_room_name.to_string()))
};
let mut rooms_to_visit = VecDeque::new();
let mut parent_keys : HashMap<&str, &str> = HashMap::new();
let mut visited_rooms : HashSet<&str> = HashSet::new();
rooms_to_visit.push_back(start_room_name);
while !rooms_to_visit.is_empty() {
let mut n = rooms_to_visit.len();
while n > 0 {
let r = rooms_to_visit.pop_front().unwrap();
visited_rooms.insert(r);
for neighbor in self.get_room(r).unwrap().neighbors.iter() {
match neighbor {
NeighborWrapper::Neighbor(s) => {
if s == end_room_name {
parent_keys.insert(s, r);
return Ok(Some(self.build_path_helper(parent_keys, s, start_room_name)));
}
else if !visited_rooms.contains(&s.as_str()) {
rooms_to_visit.push_back(s);
parent_keys.insert(s, r);
}
},
NeighborWrapper::None => continue,
}
}
n -= 1;
}
}
Ok(None)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_neighbors() {
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");
assert_eq!(dungeon.get_next_room("Hallway", Direction::West).unwrap().unwrap().name, "Entrance");
dungeon.add_room("Chamber of secrets").unwrap();
dungeon.set_link("Hallway", Direction::West, "Chamber of secrets").unwrap();
assert_eq!(dungeon.get_next_room("Hallway", Direction::West).unwrap().unwrap().name, "Chamber of secrets");
}
#[test]
fn test_add_rooms() {
let mut dungeon = Dungeon::new();
dungeon.add_room("Slytherin common room").unwrap();
dungeon.add_room("Magic classroom").unwrap();
assert!(dungeon.add_room("Magic classroom").is_err());
}
#[test]
fn test_get_rooms() {
let mut dungeon = Dungeon::new();
let s = "Slytherin common room";
dungeon.add_room(s).unwrap();
dungeon.add_room("Magic classroom").unwrap();
assert_eq!(dungeon.get_room(s).unwrap().name, s);
assert!(dungeon.get_room("FMI 100").is_err());
}
#[test]
fn test_set_get_links() {
let mut dungeon = Dungeon::new();
let s = "Slytherin common room";
let mb = "My bedroom";
dungeon.add_room(s).unwrap();
dungeon.add_room("Magic classroom").unwrap();
dungeon.add_room(mb).unwrap();
dungeon.set_link(mb, Direction::West, s).unwrap();
//assert_eq!(dungeon.set_link(s, Direction::East, "Magic classroom"), Ok(()));
assert_eq!(dungeon.get_next_room(s, Direction::East).unwrap().unwrap().name, mb);
assert!(dungeon.set_link(s, Direction::North, "Chamber of secrets").is_err());
dungeon.set_link("Magic classroom", Direction::West, "Magic classroom").unwrap();
dungeon.set_link(s, Direction::East, "Magic classroom").unwrap();
assert_eq!(dungeon.get_next_room(s, Direction::East).unwrap().unwrap().name, "Magic classroom");
assert_eq!(dungeon.get_next_room(mb, Direction::West).unwrap().unwrap().name, s);
}
const INPUT : &str = "
## Rooms
- Slytherin common room
- Magic classroom
- My bedroom
## Links
- My bedroom -> West -> Slytherin common room
- Magic classroom -> North -> Magic classroom
- Slytherin common room -> East -> Magic classroom
";
const ERR_INPUT1 : &str = "
## Rooms
- Slytherin common room
- Magic classroom
- My bedroom
- Magic classroom
## Links
- My bedroom -> West -> Slytherin common room
- Magic classroom -> North -> Magic classroom
- Slytherin common room -> East -> Magic classroom
";
const ERR_INPUT2 : &str = "
## Rooms
- Slytherin common room
- Magic classroom
- My bedroom
## Links
- My bedroom -> West -> Slytherin common room
- Magic classroom -> North -> Magic classroom
- Slytherin common room -> East -> Magic classroom
- My bedroom -> South -> FMI 100
";
const ERR_INPUT3 : &str = "
## Rooms
- Slytherin common room
- Magic classroom
- My bedroom
## Links
- My bedroom -> West -> Slytherin common room
- Magic classroom -> Noooorth -> Magic classroom
- Slytherin common room -> East -> Magic classroom
";
#[test]
fn test_dungeon_parsing() {
let dung = Dungeon::from_reader(INPUT.trim().as_bytes()).unwrap();
let s = "Slytherin common room";
assert_eq!(dung.get_room(s).unwrap().name, s);
assert_eq!(dung.get_room("My bedroom").unwrap().name, "My bedroom");
assert_eq!(dung.get_next_room(s, Direction::East).unwrap().unwrap().name, "Magic classroom");
println!("{:?}", dung.get_next_room(s, Direction::East));
assert_eq!(dung.get_next_room("Magic classroom", Direction::West).unwrap().unwrap().name, s);
assert_eq!(dung.get_next_room("My bedroom", Direction::West).unwrap().unwrap().name, s);
assert_eq!(dung.get_next_room("Magic classroom", Direction::North).unwrap().unwrap().name, "Magic classroom");
}
#[test]
fn test_path_find() {
let dung = Dungeon::from_reader(INPUT.trim().as_bytes()).unwrap();
let s = "Slytherin common room";
let v = dung.find_path("My bedroom", "Magic classroom").unwrap().unwrap();
let mut v_str : Vec<&str> = Vec::new();
for r in v {
v_str.push(r.name.as_str());
}
assert_eq!(v_str, vec!["My bedroom", s, "Magic classroom"]);
}
#[test]
fn test_errors() {
//let dung = Dungeon::from_reader(INPUT.trim().as_bytes()).unwrap();
assert!((Dungeon::from_reader(ERR_INPUT1.trim().as_bytes())).is_err());
assert!((Dungeon::from_reader(ERR_INPUT2.trim().as_bytes())).is_err());
assert!((Dungeon::from_reader(ERR_INPUT3.trim().as_bytes())).is_err());
assert!((Dungeon::from_reader("".trim().as_bytes())).is_err());
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20220116-3533338-c1ggrv/solution)
Finished test [unoptimized + debuginfo] target(s) in 5.16s
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 ... FAILED
test solution_test::test_finding_an_indirect_path ... ok
test solution_test::test_finding_no_path ... ok
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_a_reflexive_path stdout ----
thread '<unnamed>' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:360:71
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:354: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-c1ggrv/solution/src/lib.rs:146:22
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_a_reflexive_path
solution_test::test_io_error
test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.01s
error: test failed, to rerun pass '--test solution_test'