Решение на Dungeons and Compilers от Ивайло Димитров

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

Към профила на Ивайло Димитров

Код

use std::collections::{VecDeque, HashSet};

use std::{io::BufRead, fs::DirBuilder, collections::HashMap, hash::Hash};

use std::str::FromStr;

/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.

/// Повече детайли по-долу.

///

#[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,

}

impl Direction {

pub fn opposite_direction(self) -> Direction {

match &self {

Direction::East => Direction::West,

Direction::West => Direction::East,

Direction::South => Direction::North,

Direction::North => Direction::South

}

}

}

impl From<Direction> for String {

fn from(direction: Direction) -> String {

match direction {

Direction::North => return String::from("North"),

Direction::South => return String::from("South"),

Direction::East => return String::from("East"),

Direction::West => return String::from("West")

}

}

}

impl FromStr for Direction {

type Err = Errors;

fn from_str(direction: &str) -> Result<Direction, Errors> {

match direction {

"North" => Ok(Direction::North),

"South" => Ok(Direction::South),

"East" => Ok(Direction::East),

"West" => Ok(Direction::West),

_ => Err(Errors::DirectionParseError(direction.to_string()))

}

}

}

/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да

/// държи item-и, противници...

///

///

#[derive(Debug)]

pub struct Room {

pub name: String,

pub neighbours: HashMap<String, String>

}

impl Room {

pub fn new(name: &str) -> Room {

Room {name: name.to_string(), neighbours: HashMap::new() }

}

pub fn add_neighbour(&mut self, direction: Direction, name: &str) {

let direction_string: String = direction.into();

self.neighbours.insert(direction_string, name.to_string());

}

pub fn get_neighbour(&self, direction: Direction) -> Option<&String> {

let direction_string: String = direction.into();

self.neighbours.get(&direction_string)

}

}

/// Контейнер за стаите и не само. Ще работим предимно със тази структура.

///

#[derive(Debug)]

pub struct Dungeon {

pub rooms: HashMap<String, Room>

}

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) {

return Err(Errors::DuplicateRoom(name.to_string()));

}

else {

self.rooms.insert(name.to_string(), Room::new(name));

Ok(())

}

}

/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`

/// структурата с това име.

///

/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.

///

pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {

let res= self.rooms.get(room_name);

match res {

Some(room) => return Ok(room),

None => return 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) {

return Err(Errors::UnknownRoom(room_name.to_string()));

}

else if !self.rooms.contains_key(other_room_name) {

return Err(Errors::UnknownRoom(other_room_name.to_string()));

}

let room1 = self.rooms.get_mut(room_name).unwrap();

room1.add_neighbour(direction, other_room_name);

let room2 = self.rooms.get_mut(other_room_name).unwrap();

room2.add_neighbour(direction.opposite_direction(), room_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> {

if !self.rooms.contains_key(room_name) {

return Err(Errors::UnknownRoom(room_name.to_string()));

}

let room = self.rooms.get(room_name).unwrap();

let neighbour = room.get_neighbour(direction);

match neighbour {

Some(value) => Ok(self.rooms.get(value)),

None => Ok(None)

}

}

/// match_prefix("- ", "- Foo") //=> Some("Foo")

/// match_prefix("- ", "Bar") //=> None

///

fn match_prefix<'a, 'b>(prefix: &'a str, input: &'b str) -> Option<&'b str> {

if input.starts_with(prefix) {

return input.strip_prefix(prefix);

}

else {

None

}

}

fn parse_room(&mut self, room: &str) -> Result<(), Errors> {

let room_name = Dungeon::match_prefix("- ", room);

if let None = room_name {

return Err(Errors::LineParseError{line_number:0});

}

else {

return self.add_room(room_name.unwrap());

}

}

fn parse_link(&mut self, link: &str) -> Result<(), Errors> {

let link = Dungeon::match_prefix("- ", link);

if let None = link {

return Err(Errors::LineParseError{line_number:0});

}

else {

let elements: Vec<&str> = link.unwrap().split(" -> ").collect();

if elements.len() != 3 {

return Err(Errors::LineParseError{line_number : 0});

}

let direction: Result<Direction, _> = FromStr::from_str(elements[1]);

if direction.is_err() {

return Err(direction.unwrap_err());

}

else {

let direction = direction.unwrap();

return self.set_link(elements[0], direction, elements[2]);

}

}

}

/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е

/// файл, или, ако тестваме, може да е просто колекция от байтове.

///

/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.

///

/// Вижте по-долу за обяснение на грешките, които очакваме.

///

pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {

let mut line_number: usize = 0;

let mut line_iter = reader.lines().into_iter();

let first_line = line_iter.next();

if let None = first_line {

return Err(Errors::LineParseError{ line_number });

}

else if let Ok(line) = first_line.unwrap() {

line_number += 1;

if line.trim() != "## Rooms" {

return Err(Errors::LineParseError{ line_number });

}

}

let mut dungeon = Dungeon::new();

loop {

line_number += 1;

let next_line = line_iter.next();

if let None = next_line {

return Err(Errors::LineParseError{ line_number });

}

else if let Ok(line) = next_line.unwrap() {

if line.trim().is_empty() {

break;

}

let res = dungeon.parse_room(&line.trim());

if let Err(err) = res {

if let Errors::LineParseError{ line_number: _ } = err {

return Err(Errors::LineParseError { line_number });

}

return Err(err);

}

}

}

line_number += 1;

let next_line = line_iter.next();

if let None = next_line {

return Err(Errors::LineParseError{ line_number });

}

else if let Ok(line) = next_line.unwrap() {

if line.trim() != "## Links" {

return Err(Errors::LineParseError{ line_number });

}

}

loop {

let next_line = line_iter.next();

if let None = next_line {

break;

}

else if let Ok(line) = next_line.unwrap() {

let res = dungeon.parse_link(&line.trim());

if let Err(err) = res {

if let Errors::LineParseError{ line_number: _ } = err {

return Err(Errors::LineParseError { line_number });

}

return Err(err);

}

}

}

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<&Room> = VecDeque::new();

let mut visited: HashSet<String> = HashSet::new();

let mut parents: HashMap<String, Option<String>> = HashMap::new();

let room = self.get_room(start_room_name);

if let Err(err) = room {

return Err(err);

}

let mut room = room.unwrap();

queue.push_back(room);

visited.insert(room.name.to_string());

parents.insert(room.name.to_string(), None);

loop {

if queue.is_empty() {

return Ok(None);

}

room = queue.pop_front().unwrap();

if room.name == end_room_name {

break;

}

// should be improved

if let Ok(next_room) = self.get_next_room(room.name.as_str(), Direction::East) {

if let Some(next_room_ref) = next_room {

if !visited.contains(&next_room_ref.name.to_string()) {

queue.push_back(next_room_ref);

visited.insert(next_room_ref.name.to_string());

parents.insert(next_room_ref.name.to_string(), Some(room.name.to_string()));

}

}

}

if let Ok(next_room) = self.get_next_room(room.name.as_str(), Direction::West) {

if let Some(next_room_ref) = next_room {

if !visited.contains(&next_room_ref.name.to_string()) {

queue.push_back(next_room_ref);

visited.insert(next_room_ref.name.to_string());

parents.insert(next_room_ref.name.to_string(), Some(room.name.to_string()));

}

}

}

if let Ok(next_room) = self.get_next_room(room.name.as_str(), Direction::South) {

if let Some(next_room_ref) = next_room {

if !visited.contains(&next_room_ref.name.to_string()) {

queue.push_back(next_room_ref);

visited.insert(next_room_ref.name.to_string());

parents.insert(next_room_ref.name.to_string(), Some(room.name.to_string()));

}

}

}

if let Ok(next_room) = self.get_next_room(room.name.as_str(), Direction::North) {

if let Some(next_room_ref) = next_room {

if !visited.contains(&next_room_ref.name.to_string()) {

queue.push_back(next_room_ref);

visited.insert(next_room_ref.name.to_string());

parents.insert(next_room_ref.name.to_string(), Some(room.name.to_string()));

}

}

}

}

let mut res: Vec<&Room> = Vec::new();

let mut current_room_name: &String = &room.name;

res.push(self.get_room(current_room_name).unwrap());

while let Some(room_name_opt) = parents.get(current_room_name) {

if room_name_opt.is_none() {

break;

}

current_room_name = room_name_opt.as_ref().unwrap();

}

res.reverse();

Ok(Some(res))

}

}

#[cfg(test)]

mod tests {

use super::*;

#[test]

fn duplicate_room_test() {

let mut dungeon = Dungeon::new();

dungeon.add_room("Entrance").unwrap();

let res = dungeon.add_room("Entrance").unwrap_err();

match res {

Errors::DuplicateRoom(name) => assert_eq!(name, "Entrance"),

_ => panic!()

}

}

#[test]

fn add_room_AND_get_room_test() {

let mut dungeon = Dungeon::new();

let add_res = dungeon.add_room("Entrance");

assert_eq!(add_res.unwrap(), ());

let get_res_valid = dungeon.get_room("Entrance").unwrap();

assert_eq!(get_res_valid.name, "Entrance");

let get_res_invalid = dungeon.get_room("invalid room name");

if let Errors::UnknownRoom(room_name) = get_res_invalid.unwrap_err() {

assert_eq!(room_name, "invalid room name");

}

else {

panic!();

}

}

#[test]

fn set_link_test() {

let mut dungeon = Dungeon::new();

let entrance = "Entrance";

let hallway = "Hallway";

let wc = "WC";

dungeon.add_room(entrance).unwrap();

dungeon.add_room(hallway).unwrap();

dungeon.set_link(entrance, Direction::East, hallway).unwrap();

// check if link is set successfully

assert_eq!(dungeon.get_room(entrance).unwrap().get_neighbour(Direction::East).unwrap(), hallway);

assert_eq!(dungeon.get_next_room(entrance, Direction::East).unwrap().unwrap().name, hallway);

assert_eq!(dungeon.get_room(hallway).unwrap().get_neighbour(Direction::West).unwrap(), entrance);

assert_eq!(dungeon.get_next_room(hallway, Direction::West).unwrap().unwrap().name, entrance);

// check if no other links are set for entrance and hallway

assert_eq!(dungeon.get_room(entrance).unwrap().get_neighbour(Direction::West), None);

assert_eq!(dungeon.get_room(entrance).unwrap().get_neighbour(Direction::North), None);

assert_eq!(dungeon.get_room(entrance).unwrap().get_neighbour(Direction::South), None);

assert_eq!(dungeon.get_room(hallway).unwrap().get_neighbour(Direction::East), None);

assert_eq!(dungeon.get_room(hallway).unwrap().get_neighbour(Direction::North), None);

assert_eq!(dungeon.get_room(hallway).unwrap().get_neighbour(Direction::South), None);

// try to add link for unknown room

if let Errors::UnknownRoom(room_name) = dungeon.set_link(entrance, Direction::East, wc).unwrap_err() {

assert_eq!(room_name, wc);

}

else {

panic!();

}

dungeon.add_room(wc).unwrap();

// overwrite east neighbour for entrance by setting it to be west neighbour for wc

dungeon.set_link(wc, Direction::West, entrance).unwrap();

// check if link is set successfully

assert_eq!(dungeon.get_room(entrance).unwrap().get_neighbour(Direction::East).unwrap(), wc);

assert_eq!(dungeon.get_next_room(entrance, Direction::East).unwrap().unwrap().name, wc);

assert_eq!(dungeon.get_room(wc).unwrap().get_neighbour(Direction::West).unwrap(), entrance);

assert_eq!(dungeon.get_next_room(wc, Direction::West).unwrap().unwrap().name, entrance);

// check that hallway west is unchanged

assert_eq!(dungeon.get_room(hallway).unwrap().get_neighbour(Direction::West).unwrap(), entrance);

assert_eq!(dungeon.get_next_room(hallway, Direction::West).unwrap().unwrap().name, entrance);

}

#[test]

fn from_reader_with_empty_reader_test() {

if let Errors::LineParseError{ line_number } = Dungeon::from_reader("".as_bytes()).unwrap_err() {

assert_eq!(line_number, 0);

}

else {

panic!();

}

}

const INVALID_FIRST_LINE_INPUT: &str = "

## asdfdsaf

- Entrance

- Hallway

## Links

- Entrance -> East -> Hallway

";

const MISSING_LINKS_HEADER_LINE_INPUT: &str = "

## Rooms

- Entrance

- Hallway

- Entrance -> East -> Hallway

";

#[test]

fn from_reader_with_invalid_lines_test() {

if let Errors::LineParseError{ line_number } = Dungeon::from_reader(INVALID_FIRST_LINE_INPUT.trim().as_bytes()).unwrap_err() {

assert_eq!(line_number, 1);

}

else {

panic!();

}

if let Errors::LineParseError{ line_number } = Dungeon::from_reader(MISSING_LINKS_HEADER_LINE_INPUT.trim().as_bytes()).unwrap_err() {

assert_eq!(line_number, 5);

}

else {

panic!();

}

}

#[test]

fn example_test1() {

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");

}

#[test]

fn example_test2() {

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");

}

#[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);

}

}

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

Compiling solution v0.1.0 (/tmp/d20220116-3533338-1tj2kzw/solution)
warning: unused imports: `fs::DirBuilder`, `hash::Hash`
 --> src/lib.rs:2:24
  |
2 | use std::{io::BufRead, fs::DirBuilder, collections::HashMap, hash::Hash};
  |                        ^^^^^^^^^^^^^^                        ^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: `solution` (lib) generated 1 warning
    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 ... FAILED
test solution_test::test_finding_a_reflexive_path ... ok
test solution_test::test_finding_an_indirect_path ... FAILED
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_a_direct_path stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `["Treasure Room"]`,
 right: `["Entrance", "Treasure Room"]`', tests/solution_test.rs:314:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `["Treasure Room"]`,
 right: `["Entrance", "Treasure Room"]`', tests/solution_test.rs:306:5

---- solution_test::test_finding_an_indirect_path stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `"Treasure Room"`,
 right: `"Entrance"`', tests/solution_test.rs:347:9
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `"Treasure Room"`,
 right: `"Entrance"`', tests/solution_test.rs:320:5

---- solution_test::test_finding_no_path stdout ----
thread '<unnamed>' panicked at 'assertion failed: path.is_err()', tests/solution_test.rs:382:9
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:372:5

---- solution_test::test_io_error stdout ----
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Timeout', tests/solution_test.rs:194:5


failures:
    solution_test::test_finding_a_direct_path
    solution_test::test_finding_an_indirect_path
    solution_test::test_finding_no_path
    solution_test::test_io_error

test result: FAILED. 11 passed; 4 failed; 0 ignored; 0 measured; 0 filtered out; finished in 1.00s

error: test failed, to rerun pass '--test solution_test'

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