Решение на Dungeons and Compilers от Ростислав Цачев

Обратно към всички решения

Към профила на Ростислав Цачев

Резултати

  • 19 точки от тестове
  • 1 бонус точка
  • 20 точки общо
  • 14 успешни тест(а)
  • 1 неуспешни тест(а)

Код

use std::io::BufRead;
use std::collections::{HashMap, VecDeque, HashSet};
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[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, Hash)]
pub enum Direction {
North,
South,
East,
West,
}
impl Direction {
pub fn new(direction: &str) -> Option<Self> {
match direction {
"North" => Some(Direction::North),
"South" => Some(Direction::South),
"East" => Some(Direction::East),
"West" => Some(Direction::West),
_ => None,
}
}
pub fn get_opposite(&self) -> Direction {
match self {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::West => Direction::East,
Direction::East => Direction::West,
_ => unreachable!()
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
pub struct Room {
pub name: String,
pub neighbours: HashMap<Direction, String>,
}
impl Room {
fn has_neighbour(&self, direction: &Direction) -> bool {
self.neighbours.contains_key(direction)
}
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
pub struct Dungeon {
pub rooms: HashMap<String, Room>,
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
Dungeon { rooms: HashMap::new() }
}
fn has_room(&self, name: &str) -> bool {
self.rooms.contains_key(name)
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
if self.has_room(name) {
return Err(Errors::DuplicateRoom(name.to_string()));
}
self.rooms.insert(
name.to_string(),
Room { name: name.to_string(), neighbours: HashMap::new() }
);
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
if !self.has_room(room_name) {
return Err(Errors::UnknownRoom(room_name.to_string()));
}
Ok(&self.rooms[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> {
self.get_room(room_name)?;
self.get_room(other_room_name)?;
self.rooms.get_mut(room_name).unwrap().neighbours.insert(
direction,
other_room_name.to_string()
);
self.rooms.get_mut(other_room_name).unwrap().neighbours.insert(
direction.get_opposite(),
room_name.to_string()
);
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 = self.get_room(room_name)?;
if !room.has_neighbour(&direction) {
return Ok(None);
}
let next_room_name = &room.neighbours[&direction];
Ok(Some(self.get_room(next_room_name).unwrap()))
}
}
fn match_prefix<'a, 'b>(prefix: &'a str, input: &'b str) -> Option<&'b str> {
input.strip_prefix(prefix)
}
fn unwrap_line(line: std::result::Result<std::string::String, std::io::Error>) -> std::string::String {
line.unwrap()
}
impl Dungeon {
fn load_rooms<B: BufRead>(
&mut self,
lines_iter: &mut std::iter::Map<
std::io::Lines<B>,
impl Fn(std::result::Result<std::string::String, std::io::Error>) -> std::string::String
>,
line_number: &mut usize,
) -> Result<(), Errors> {
let mut has_more_rooms = true;
while has_more_rooms {
let line = lines_iter.next();
*line_number += 1;
if line == None {
return Err(Errors::LineParseError { line_number: *line_number });
}
let line_str = line.unwrap();
let room_name = match_prefix("- ", &line_str);
match room_name {
Some(room_name_str) => {
self.add_room(room_name_str)?;
},
None => {
if line_str != "" {
return Err(Errors::LineParseError { line_number: *line_number });
}
has_more_rooms = false;
}
}
}
Ok(())
}
fn load_links<B: BufRead>(
&mut self,
lines_iter: &mut std::iter::Map<
std::io::Lines<B>,
impl Fn(std::result::Result<std::string::String, std::io::Error>) -> std::string::String
>,
line_number: &mut usize,
) -> Result<(), Errors> {
let mut has_more_links = true;
while has_more_links {
let line = lines_iter.next();
*line_number += 1;
if line == None {
has_more_links = false;
} else {
let line_str = line.unwrap();
let link_data = match_prefix("- ", &line_str);
match link_data {
Some(link_data_str) => {
let link_components: Vec<&str> = link_data_str.split("->").collect();
if link_components.len() != 3 {
return Err(Errors::LineParseError { line_number: *line_number });
}
let direction = Direction::new(link_components[1].trim());
if direction == None {
return Err(Errors::DirectionParseError(String::from(link_components[1].trim())));
}
self.set_link(link_components[0].trim(), direction.unwrap(), link_components[2].trim())?;
},
None => {
return Err(Errors::LineParseError { line_number: *line_number });
}
}
}
}
Ok(())
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut lines_iter = reader.lines().map(unwrap_line);
let mut line_number = 0;
let mut line = lines_iter.next();
if line == None {
return Err(Errors::LineParseError { line_number });
}
line_number += 1;
if line.unwrap() != String::from("## Rooms") {
return Err(Errors::LineParseError { line_number });
}
let mut dungeon = Dungeon::new();
dungeon.load_rooms(&mut lines_iter, &mut line_number)?;
line = lines_iter.next();
line_number += 1;
if line == None || line.unwrap() != String::from("## Links") {
return Err(Errors::LineParseError { line_number });
}
dungeon.load_links(&mut lines_iter, &mut line_number)?;
Ok(dungeon)
}
}
impl Dungeon {
fn restore_path(&self, parent_of: HashMap<String, &str>, start_room_name: &str, end_room_name: &str) -> Vec<&Room> {
let mut path = Vec::new();
path.push(self.get_room(end_room_name).unwrap());
let mut last_added_room_name = end_room_name;
loop {
if last_added_room_name == start_room_name {
break;
}
last_added_room_name = parent_of[last_added_room_name];
path.push(self.get_room(last_added_room_name).unwrap());
}
path.reverse();
path
}
/// Търси път от `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> {
self.get_room(start_room_name)?;
self.get_room(end_room_name)?;
if start_room_name == end_room_name {
return Ok(Some(vec![self.get_room(start_room_name).unwrap()]));
}
// Using BFS
let mut queue = VecDeque::new();
queue.push_back(start_room_name);
let mut visited = HashSet::new();
let mut parent_of = HashMap::new();
loop {
let current_room_name = queue.pop_front();
// The queue is empty
if current_room_name == None {
break;
}
visited.insert(current_room_name.unwrap().to_string());
if current_room_name.unwrap() == end_room_name {
break;
}
for direction in vec![Direction::North, Direction::South, Direction::East, Direction::West] {
let next_room_name = self.get_next_room(current_room_name.unwrap(), direction);
match next_room_name {
Ok(Some(next_room)) => {
if !visited.contains(&next_room.name) {
parent_of.insert(
String::from(&next_room.name),
current_room_name.unwrap()
);
queue.push_back(&next_room.name);
}
},
// There is no room in that direction
Ok(None) => {
continue;
},
_ => unreachable!(),
}
}
}
if !visited.contains(end_room_name) {
return Ok(None);
}
let path = self.restore_path(parent_of, start_room_name, end_room_name);
Ok(Some(path))
}
}
#[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);
}
const TEST_INPUT_WRONG_LINE_1: &str = "
Doesn't really matter what's here, just != ## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINE_3: &str = "
## Rooms
- Entrance
Room without prefix `- `
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINE_4: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_DUPLICATED_ROOMS: &str = "
## Rooms
- Entrance
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINKS_LINE: &str = "
## Rooms
- Entrance
- Hallway
Doesn't matter, != ## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINK_FORMAT: &str = "
## Rooms
- Entrance
- Hallway
## Links
-> Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINK_FORMAT2: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance - East - Hallway
";
const TEST_INPUT_WRONG_LINK_DIRECTION: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> InvalidDirection -> Hallway
";
const TEST_INPUT_TO_CHECK_FIND_PATH: &str = "
## Rooms
- A
- B
- C
- D
- E
- F
- G
## Links
- A -> South -> B
- B -> East -> C
- C -> West -> D
- D -> West -> E
- E -> North -> F
";
const TEST_INPUT_EMPTY: &str = "";
#[test]
fn test_from_reader_with_incorrect_data() {
let dungeon1 = Dungeon::from_reader(TEST_INPUT_EMPTY.as_bytes());
match dungeon1 {
Err(Errors::LineParseError { line_number: 0 }) => {},
_ => panic!()
}
let dungeon2 = Dungeon::from_reader(TEST_INPUT_WRONG_LINE_1.trim().as_bytes());
match dungeon2 {
Err(Errors::LineParseError { line_number: 1 }) => {},
_ => panic!()
}
let dungeon3 = Dungeon::from_reader(TEST_INPUT_WRONG_LINE_3.trim().as_bytes());
match dungeon3 {
Err(Errors::LineParseError { line_number: 3 }) => {},
_ => panic!()
}
let dungeon4 = Dungeon::from_reader(TEST_INPUT_WRONG_LINE_4.trim().as_bytes());
match dungeon4 {
Err(Errors::LineParseError { line_number: 4 }) => {},
_ => panic!()
}
let dungeon5 = Dungeon::from_reader(TEST_INPUT_DUPLICATED_ROOMS.trim().as_bytes());
let entrance_str = "Entrance".to_string();
match dungeon5 {
Err(Errors::DuplicateRoom(entrance_str)) => {},
_ => panic!()
}
let dungeon6 = Dungeon::from_reader(TEST_INPUT_WRONG_LINKS_LINE.trim().as_bytes());
match dungeon6 {
Err(Errors::LineParseError { line_number: 5 }) => {},
_ => panic!()
}
let dungeon7 = Dungeon::from_reader(TEST_INPUT_WRONG_LINK_FORMAT.trim().as_bytes());
match dungeon7 {
Err(Errors::LineParseError { line_number: 6 }) => {},
_ => panic!()
}
let dungeon8 = Dungeon::from_reader(TEST_INPUT_WRONG_LINK_FORMAT2.trim().as_bytes());
match dungeon8 {
Err(Errors::LineParseError { line_number: 6 }) => {},
_ => panic!()
}
let dungeon8 = Dungeon::from_reader(TEST_INPUT_WRONG_LINK_DIRECTION.trim().as_bytes());
let invalid_direction_str = "InvalidDirection".to_string();
match dungeon8 {
Err(Errors::DirectionParseError(invalid_direction_str)) => {},
_ => panic!()
}
}
#[test]
fn test_find_path() {
let dungeon1 = Dungeon::from_reader(TEST_INPUT_TO_CHECK_FIND_PATH.trim().as_bytes()).unwrap();
// Same dungeon, but not from reader
let mut dungeon2 = Dungeon::new();
dungeon2.add_room("A");
dungeon2.add_room("B");
dungeon2.add_room("C");
dungeon2.add_room("D");
dungeon2.add_room("E");
dungeon2.add_room("F");
dungeon2.add_room("G");
dungeon2.set_link("A", Direction::South, "B");
dungeon2.set_link("B", Direction::East, "C");
dungeon2.set_link("C", Direction::West, "D");
dungeon2.set_link("D", Direction::West, "E");
dungeon2.set_link("E", Direction::North, "F");
let path1 = dungeon1.find_path("A", "F").unwrap().unwrap();
let path2 = dungeon2.find_path("A", "F").unwrap().unwrap();
let path_len = path1.len();
for i in 0..path_len - 1 {
if path1[i].name != path2[i].name {
panic!();
}
}
assert_eq!(path1[0].name, "A");
assert_eq!(path1[path_len - 1].name, "F");
for i in 0..path_len - 2 {
let mut has_correct_next_element = false;
for direction in vec![Direction::North, Direction::South, Direction::East, Direction::West] {
let next_room_name = dungeon1.get_next_room(&path1[i].name, direction);
match next_room_name {
Ok(Some(next_room)) => {
if next_room.name == path1[i + 1].name {
has_correct_next_element = true;
}
},
// There is no room in that direction
Ok(None) => {
continue;
},
_ => unreachable!(),
}
}
if !has_correct_next_element {
panic!();
}
}
let empty_path1 = dungeon1.find_path("A", "G").unwrap();
let empty_path2 = dungeon2.find_path("A", "G").unwrap();
match empty_path1 {
None => {},
_ => panic!()
}
match empty_path2 {
None => {},
_ => panic!()
}
}

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20220116-3533338-1g2voc8/solution)
warning: unreachable pattern
  --> src/lib.rs:45:13
   |
45 |             _                => unreachable!()
   |             ^
   |
   = note: `#[warn(unreachable_patterns)]` on by default

warning: constant is never used: `TEST_INPUT_1`
   --> src/lib.rs:382:1
    |
382 | / const TEST_INPUT_1: &str = "
383 | | ## Rooms
384 | | - Entrance
385 | | - Hallway
...   |
388 | | - Entrance -> East -> Hallway
389 | | ";
    | |__^
    |
    = note: `#[warn(dead_code)]` on by default

warning: constant is never used: `TEST_INPUT_WRONG_LINE_1`
   --> src/lib.rs:416:1
    |
416 | / const TEST_INPUT_WRONG_LINE_1: &str = "
417 | | Doesn't really matter what's here, just != ## Rooms
418 | | - Entrance
419 | | - Hallway
...   |
422 | | - Entrance -> East -> Hallway
423 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_WRONG_LINE_3`
   --> src/lib.rs:425:1
    |
425 | / const TEST_INPUT_WRONG_LINE_3: &str = "
426 | | ## Rooms
427 | | - Entrance
428 | | Room without prefix `- `
...   |
432 | | - Entrance -> East -> Hallway
433 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_WRONG_LINE_4`
   --> src/lib.rs:435:1
    |
435 | / const TEST_INPUT_WRONG_LINE_4: &str = "
436 | | ## Rooms
437 | | - Entrance
438 | | - Hallway
439 | | ## Links
440 | | - Entrance -> East -> Hallway
441 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_DUPLICATED_ROOMS`
   --> src/lib.rs:443:1
    |
443 | / const TEST_INPUT_DUPLICATED_ROOMS: &str = "
444 | | ## Rooms
445 | | - Entrance
446 | | - Entrance
...   |
450 | | - Entrance -> East -> Hallway
451 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_WRONG_LINKS_LINE`
   --> src/lib.rs:453:1
    |
453 | / const TEST_INPUT_WRONG_LINKS_LINE: &str = "
454 | | ## Rooms
455 | | - Entrance
456 | | - Hallway
...   |
459 | | - Entrance -> East -> Hallway
460 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_WRONG_LINK_FORMAT`
   --> src/lib.rs:462:1
    |
462 | / const TEST_INPUT_WRONG_LINK_FORMAT: &str = "
463 | | ## Rooms
464 | | - Entrance
465 | | - Hallway
...   |
468 | | -> Entrance -> East -> Hallway
469 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_WRONG_LINK_FORMAT2`
   --> src/lib.rs:471:1
    |
471 | / const TEST_INPUT_WRONG_LINK_FORMAT2: &str = "
472 | | ## Rooms
473 | | - Entrance
474 | | - Hallway
...   |
477 | | - Entrance - East - Hallway
478 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_WRONG_LINK_DIRECTION`
   --> src/lib.rs:480:1
    |
480 | / const TEST_INPUT_WRONG_LINK_DIRECTION: &str = "
481 | | ## Rooms
482 | | - Entrance
483 | | - Hallway
...   |
486 | | - Entrance -> InvalidDirection -> Hallway
487 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_TO_CHECK_FIND_PATH`
   --> src/lib.rs:489:1
    |
489 | / const TEST_INPUT_TO_CHECK_FIND_PATH: &str = "
490 | | ## Rooms
491 | | - A
492 | | - B
...   |
504 | | - E -> North -> F
505 | | ";
    | |__^

warning: constant is never used: `TEST_INPUT_EMPTY`
   --> src/lib.rs:507:1
    |
507 | const TEST_INPUT_EMPTY: &str = "";
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: `solution` (lib) generated 12 warnings
    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 ... 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_io_error stdout ----
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: Custom { kind: Other, error: "fill_buf error!" }', src/lib.rs:160:10
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
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_io_error

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'

История (2 версии и 0 коментара)

Ростислав качи първо решение на 25.12.2021 17:34 (преди почти 4 години)

Ростислав качи решение на 25.12.2021 18:00 (преди почти 4 години)

use std::io::BufRead;
use std::collections::{HashMap, VecDeque, HashSet};
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[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, Hash)]
pub enum Direction {
North,
South,
East,
West,
}
impl Direction {
pub fn new(direction: &str) -> Option<Self> {
match direction {
"North" => Some(Direction::North),
"South" => Some(Direction::South),
"East" => Some(Direction::East),
"West" => Some(Direction::West),
_ => None,
}
}
pub fn get_opposite(&self) -> Direction {
match self {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::West => Direction::East,
Direction::East => Direction::West,
_ => unreachable!()
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
pub struct Room {
pub name: String,
pub neighbours: HashMap<Direction, String>,
}
impl Room {
fn has_neighbour(&self, direction: &Direction) -> bool {
self.neighbours.contains_key(direction)
}
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
pub struct Dungeon {
pub rooms: HashMap<String, Room>,
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
Dungeon { rooms: HashMap::new() }
}
fn has_room(&self, name: &str) -> bool {
self.rooms.contains_key(name)
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
if self.has_room(name) {
return Err(Errors::DuplicateRoom(name.to_string()));
}
self.rooms.insert(
name.to_string(),
Room { name: name.to_string(), neighbours: HashMap::new() }
);
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
if !self.has_room(room_name) {
return Err(Errors::UnknownRoom(room_name.to_string()));
}
Ok(&self.rooms[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> {
self.get_room(room_name)?;
self.get_room(other_room_name)?;
self.rooms.get_mut(room_name).unwrap().neighbours.insert(
direction,
other_room_name.to_string()
);
self.rooms.get_mut(other_room_name).unwrap().neighbours.insert(
direction.get_opposite(),
room_name.to_string()
);
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 = self.get_room(room_name)?;
if !room.has_neighbour(&direction) {
return Ok(None);
}
let next_room_name = &room.neighbours[&direction];
Ok(Some(self.get_room(next_room_name).unwrap()))
}
}
fn match_prefix<'a, 'b>(prefix: &'a str, input: &'b str) -> Option<&'b str> {
input.strip_prefix(prefix)
}
fn unwrap_line(line: std::result::Result<std::string::String, std::io::Error>) -> std::string::String {
line.unwrap()
}
impl Dungeon {
fn load_rooms<B: BufRead>(
&mut self,
lines_iter: &mut std::iter::Map<
std::io::Lines<B>,
impl Fn(std::result::Result<std::string::String, std::io::Error>) -> std::string::String
>,
line_number: &mut usize,
) -> Result<(), Errors> {
let mut has_more_rooms = true;
while has_more_rooms {
let line = lines_iter.next();
*line_number += 1;
if line == None {
return Err(Errors::LineParseError { line_number: *line_number });
}
let line_str = line.unwrap();
let room_name = match_prefix("- ", &line_str);
match room_name {
Some(room_name_str) => {
self.add_room(room_name_str)?;
},
None => {
if line_str != "" {
return Err(Errors::LineParseError { line_number: *line_number });
}
has_more_rooms = false;
}
}
}
Ok(())
}
fn load_links<B: BufRead>(
&mut self,
lines_iter: &mut std::iter::Map<
std::io::Lines<B>,
impl Fn(std::result::Result<std::string::String, std::io::Error>) -> std::string::String
>,
line_number: &mut usize,
) -> Result<(), Errors> {
let mut has_more_links = true;
while has_more_links {
let line = lines_iter.next();
*line_number += 1;
if line == None {
has_more_links = false;
} else {
let line_str = line.unwrap();
let link_data = match_prefix("- ", &line_str);
match link_data {
Some(link_data_str) => {
let link_components: Vec<&str> = link_data_str.split("->").collect();
if link_components.len() != 3 {
return Err(Errors::LineParseError { line_number: *line_number });
}
let direction = Direction::new(link_components[1].trim());
if direction == None {
return Err(Errors::DirectionParseError(String::from(link_components[1].trim())));
}
self.set_link(link_components[0].trim(), direction.unwrap(), link_components[2].trim())?;
},
None => {
return Err(Errors::LineParseError { line_number: *line_number });
}
}
}
}
Ok(())
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut lines_iter = reader.lines().map(unwrap_line);
let mut line_number = 0;
let mut line = lines_iter.next();
if line == None {
return Err(Errors::LineParseError { line_number });
}
line_number += 1;
if line.unwrap() != String::from("## Rooms") {
return Err(Errors::LineParseError { line_number });
}
let mut dungeon = Dungeon::new();
dungeon.load_rooms(&mut lines_iter, &mut line_number)?;
line = lines_iter.next();
line_number += 1;
if line == None || line.unwrap() != String::from("## Links") {
return Err(Errors::LineParseError { line_number });
}
dungeon.load_links(&mut lines_iter, &mut line_number)?;
Ok(dungeon)
}
}
impl Dungeon {
fn restore_path(&self, parent_of: HashMap<String, &str>, start_room_name: &str, end_room_name: &str) -> Vec<&Room> {
let mut path = Vec::new();
path.push(self.get_room(end_room_name).unwrap());
let mut last_added_room_name = end_room_name;
loop {
if last_added_room_name == start_room_name {
break;
}
last_added_room_name = parent_of[last_added_room_name];
path.push(self.get_room(last_added_room_name).unwrap());
}
path.reverse();
path
}
/// Търси път от `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> {
self.get_room(start_room_name)?;
self.get_room(end_room_name)?;
if start_room_name == end_room_name {
return Ok(Some(vec![self.get_room(start_room_name).unwrap()]));
}
// Using BFS
let mut queue = VecDeque::new();
queue.push_back(start_room_name);
let mut visited = HashSet::new();
let mut parent_of = HashMap::new();
- let mut current_room_name = Some("just to be != None");
- while current_room_name != None {
- current_room_name = queue.pop_front();
+ loop {
+ let current_room_name = queue.pop_front();
+
+ // The queue is empty
+ if current_room_name == None {
+ break;
+ }
+
visited.insert(current_room_name.unwrap().to_string());
if current_room_name.unwrap() == end_room_name {
break;
}
for direction in vec![Direction::North, Direction::South, Direction::East, Direction::West] {
let next_room_name = self.get_next_room(current_room_name.unwrap(), direction);
match next_room_name {
Ok(Some(next_room)) => {
if !visited.contains(&next_room.name) {
parent_of.insert(
String::from(&next_room.name),
current_room_name.unwrap()
);
queue.push_back(&next_room.name);
}
},
// There is no room in that direction
Ok(None) => {
continue;
},
_ => unreachable!(),
}
}
}
if !visited.contains(end_room_name) {
return Ok(None);
}
let path = self.restore_path(parent_of, start_room_name, end_room_name);
Ok(Some(path))
}
}
-
-
#[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);
}
const TEST_INPUT_WRONG_LINE_1: &str = "
Doesn't really matter what's here, just != ## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINE_3: &str = "
## Rooms
- Entrance
Room without prefix `- `
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINE_4: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_DUPLICATED_ROOMS: &str = "
## Rooms
- Entrance
- Entrance
- Hallway
## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINKS_LINE: &str = "
## Rooms
- Entrance
- Hallway
Doesn't matter, != ## Links
- Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINK_FORMAT: &str = "
## Rooms
- Entrance
- Hallway
## Links
-> Entrance -> East -> Hallway
";
const TEST_INPUT_WRONG_LINK_FORMAT2: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance - East - Hallway
";
const TEST_INPUT_WRONG_LINK_DIRECTION: &str = "
## Rooms
- Entrance
- Hallway
## Links
- Entrance -> InvalidDirection -> Hallway
";
const TEST_INPUT_TO_CHECK_FIND_PATH: &str = "
## Rooms
- A
- B
- C
- D
- E
- F
+- G
## Links
- A -> South -> B
- B -> East -> C
- C -> West -> D
- D -> West -> E
- E -> North -> F
";
const TEST_INPUT_EMPTY: &str = "";
#[test]
fn test_from_reader_with_incorrect_data() {
let dungeon1 = Dungeon::from_reader(TEST_INPUT_EMPTY.as_bytes());
match dungeon1 {
Err(Errors::LineParseError { line_number: 0 }) => {},
_ => panic!()
}
let dungeon2 = Dungeon::from_reader(TEST_INPUT_WRONG_LINE_1.trim().as_bytes());
match dungeon2 {
Err(Errors::LineParseError { line_number: 1 }) => {},
_ => panic!()
}
let dungeon3 = Dungeon::from_reader(TEST_INPUT_WRONG_LINE_3.trim().as_bytes());
match dungeon3 {
Err(Errors::LineParseError { line_number: 3 }) => {},
_ => panic!()
}
let dungeon4 = Dungeon::from_reader(TEST_INPUT_WRONG_LINE_4.trim().as_bytes());
match dungeon4 {
Err(Errors::LineParseError { line_number: 4 }) => {},
_ => panic!()
}
let dungeon5 = Dungeon::from_reader(TEST_INPUT_DUPLICATED_ROOMS.trim().as_bytes());
let entrance_str = "Entrance".to_string();
match dungeon5 {
Err(Errors::DuplicateRoom(entrance_str)) => {},
_ => panic!()
}
let dungeon6 = Dungeon::from_reader(TEST_INPUT_WRONG_LINKS_LINE.trim().as_bytes());
match dungeon6 {
Err(Errors::LineParseError { line_number: 5 }) => {},
_ => panic!()
}
let dungeon7 = Dungeon::from_reader(TEST_INPUT_WRONG_LINK_FORMAT.trim().as_bytes());
match dungeon7 {
Err(Errors::LineParseError { line_number: 6 }) => {},
_ => panic!()
}
let dungeon8 = Dungeon::from_reader(TEST_INPUT_WRONG_LINK_FORMAT2.trim().as_bytes());
match dungeon8 {
Err(Errors::LineParseError { line_number: 6 }) => {},
_ => panic!()
}
let dungeon8 = Dungeon::from_reader(TEST_INPUT_WRONG_LINK_DIRECTION.trim().as_bytes());
let invalid_direction_str = "InvalidDirection".to_string();
match dungeon8 {
Err(Errors::DirectionParseError(invalid_direction_str)) => {},
_ => panic!()
}
}
#[test]
fn test_find_path() {
let dungeon1 = Dungeon::from_reader(TEST_INPUT_TO_CHECK_FIND_PATH.trim().as_bytes()).unwrap();
// Same dungeon, but not from reader
let mut dungeon2 = Dungeon::new();
dungeon2.add_room("A");
dungeon2.add_room("B");
dungeon2.add_room("C");
dungeon2.add_room("D");
dungeon2.add_room("E");
dungeon2.add_room("F");
+ dungeon2.add_room("G");
dungeon2.set_link("A", Direction::South, "B");
dungeon2.set_link("B", Direction::East, "C");
dungeon2.set_link("C", Direction::West, "D");
dungeon2.set_link("D", Direction::West, "E");
dungeon2.set_link("E", Direction::North, "F");
let path1 = dungeon1.find_path("A", "F").unwrap().unwrap();
let path2 = dungeon2.find_path("A", "F").unwrap().unwrap();
let path_len = path1.len();
for i in 0..path_len - 1 {
if path1[i].name != path2[i].name {
panic!();
}
}
assert_eq!(path1[0].name, "A");
assert_eq!(path1[path_len - 1].name, "F");
for i in 0..path_len - 2 {
let mut has_correct_next_element = false;
for direction in vec![Direction::North, Direction::South, Direction::East, Direction::West] {
let next_room_name = dungeon1.get_next_room(&path1[i].name, direction);
match next_room_name {
Ok(Some(next_room)) => {
if next_room.name == path1[i + 1].name {
has_correct_next_element = true;
}
},
// There is no room in that direction
Ok(None) => {
continue;
},
_ => unreachable!(),
}
}
if !has_correct_next_element {
panic!();
}
+ }
+
+ let empty_path1 = dungeon1.find_path("A", "G").unwrap();
+ let empty_path2 = dungeon2.find_path("A", "G").unwrap();
+
+ match empty_path1 {
+ None => {},
+ _ => panic!()
+ }
+ match empty_path2 {
+ None => {},
+ _ => panic!()
}
}