Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Dungeons and Compilers от Диана Маркова

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

Към профила на Диана Маркова

Резултати

  • 16 точки от тестове
  • 0 бонус точки
  • 16 точки общо
  • 12 успешни тест(а)
  • 3 неуспешни тест(а)

Код

use std::collections::{HashMap, VecDeque, HashSet};
use std::io::BufRead;
#[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,
}
pub struct adjacent
{
north: Option<String>,
south: Option<String>,
east: Option<String>,
west: Option<String>,
}
impl adjacent{
pub fn new()->Self{
adjacent{
north: None,
south: None,
east: None,
west: None,
}
}
}
pub struct Room {
pub name: String,
pub adj: adjacent
}
impl Room{
pub fn new(n: &str)->Self{
Room { name: n.to_string(), adj: adjacent::new() }
}
}
impl Room{
pub fn set_edge(&mut self, other_name: &str , direction: Direction)->() {
match direction {
Direction::East => {
self.adj.east = Some(other_name.to_string());
}
Direction::West => {
self.adj.west = Some(other_name.to_string());
}
Direction::North => {
self.adj.north = Some(other_name.to_string());
}
Direction::South => {
self.adj.south = Some(other_name.to_string());
}
}
}
pub fn remove_edge(&mut self, direction: Direction)->() {
match direction {
Direction::East => {
self.adj.east = None;
}
Direction::West => {
self.adj.west = None;
}
Direction::North => {
self.adj.north = None;
}
Direction::South => {
self.adj.south = None;
}
}
}
pub fn get_adj_at(&self, direction: Direction) -> Option<String> {
match direction {
Direction::East => {
self.adj.east.clone()
}
Direction::West => {
self.adj.west.clone()
}
Direction::South => {
self.adj.south.clone()
}
Direction::North => {
self.adj.north.clone()
}
}
}
}
pub struct Dungeon {
pub 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 found = self.get_room(name);
let res= match found
{
Ok(_) => Err(Errors::DuplicateRoom(String::from(name))),
Err(_) => {
self.rooms.insert(name.to_string(), Room{name: name.to_string(), adj: adjacent::new()});
Ok(())
}
};
res
}
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let found = self.rooms.get(room_name);
match found
{
Some(val) => Ok(val),
None => 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 r1 = self.rooms.get_mut(room_name);
if r1.is_none() {
return Err(Errors::UnknownRoom(room_name.to_string()));
}
r1.unwrap().set_edge(other_room_name, direction);
let r2 = self.rooms.get_mut(other_room_name);
if r2.is_none() {
return Err(Errors::UnknownRoom(other_room_name.to_string()));
}
r2.unwrap().set_edge(room_name, match direction{ Direction::East => Direction::West,
Direction::West => Direction::East,
Direction::North => Direction::South,
Direction::South => Direction::North, } );
Ok(())
}
pub fn get_next_room(&self, room_name: &str, direction: Direction) -> Result<Option<&Room>, Errors> {
let x = self.get_room(room_name);
match x
{
Ok(val) => {
let adj = val.get_adj_at(direction);
match adj {
Some(n) => (Ok(Some(self.get_room(&n).unwrap()))),
None => Ok(None)
}
}
Err(_) => Err(Errors::UnknownRoom(room_name.to_string())),
}
}
}
impl Dungeon {
pub fn from_reader<B: BufRead>(mut reader: B) -> Result<Self, Errors> {
let mut res = Dungeon::new();
let mut first_line = String::new();
let x = reader.read_line(&mut first_line);
match x {
Ok(_) => {},
Err(val) => return Err(Errors::IoError(val)),
}
first_line = first_line.trim().to_string();
if first_line != "## Rooms"{
return Err(Errors::LineParseError { line_number: 1 });
}
let mut line = String::new();
let mut current_line_count = 1;
while reader.read_line(&mut line).is_ok() {
line = line.trim().to_string();
if line.len() == 0 {
break;
}
if line.len() < 2 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let beg = &line[0..2];
if beg != "- " {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let name = &line[2..line.len()];
let add_res = res.add_room(name);
match add_res {
Ok(()) =>{
current_line_count += 1;
line.clear();}
Err(val) => return Err(val),
}
}
if !line.is_empty() {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let x = reader.read_line(&mut line);
match x {
Ok(_) => {},
Err(val) => return Err(Errors::IoError(val)),
}
current_line_count += 1;
line = line.trim().to_string();
if line != "## Links"{
return Err(Errors::LineParseError { line_number: current_line_count });
}
line.clear();
while reader.read_line(&mut line).is_ok() {
if line.len() == 0 {
break;
}
line = line.trim().to_string();
if line.len() < 2 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let beg = &line[0..2];
if beg != "- " {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let ast: Vec<&str> = line[2..line.len()].split(" -> ").collect();
if ast.len() != 3 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let set_ln_res = res.set_link(ast[0], match ast[1] {
"East" => Direction::East,
"West" => Direction::West,
"North" => Direction::North,
"South" => Direction::South,
_ => return Err(Errors::DirectionParseError(ast[1].to_string())),
}, ast[2]);
match set_ln_res {
Ok(_) => {
current_line_count += 1;
line.clear();
},
Err(val) => return Err(val),
}
}
return Ok(res);
}
}
impl Dungeon {
pub fn find_path(
&self,
start_room_name: &str,
end_room_name: &str
) -> Result<Option<Vec<&Room>>, Errors> {
let start = self.get_room(start_room_name);
let target = self.get_room(end_room_name);
if target.is_err() {
return Err(Errors::UnknownRoom(end_room_name.to_string()));
}
match start {
Ok(val) => {
let mut q = VecDeque::<&Room>::new();
let mut parent_pointers = HashMap::<String, Option<String>>::new();
let mut visited = HashSet::<String>::new();
let mut path = Vec::<&Room>::new();
q.push_back(val);
parent_pointers.insert(val.name.clone(), None);
visited.insert(val.name.clone());
while !q.is_empty()
{
let x = q.pop_back();
if x.unwrap().name == end_room_name {
break;
}
let east = x.unwrap().get_adj_at(Direction::East);
let west = x.unwrap().get_adj_at(Direction::West);
let north = x.unwrap().get_adj_at(Direction::North);
let south = x.unwrap().get_adj_at(Direction::South);
match east
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match west
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match south
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match north
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
}
let target = parent_pointers.get(end_room_name);
match target {
Some(val) => {
// the target room is found, its parent is val
// push target room to path
path.push(self.get_room(end_room_name).unwrap());
// update parent
let mut parent = val;
// while there is parent value
// push to path
while parent.is_some() {
let t = parent_pointers.get(parent.as_ref().unwrap()).unwrap();
path.push(self.get_room(&parent.as_ref().unwrap()).unwrap());
parent = t;
}
Ok(Some(path))
},
None => Ok(None),
}
},
Err(_) => Err(Errors::UnknownRoom(start_room_name.to_string())),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[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 more_on_add_room() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
let temp = dungeon.add_room("Съкровищница");
assert!(temp.is_err());
}
#[test]
fn more_on_get_room() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
let temp = dungeon.get_room("Съкровищница").unwrap();
assert_eq!(temp.name, "Съкровищница");
let temp_bad = dungeon.get_room("несъществуваща");
assert!(temp_bad.is_err());
}
#[test]
fn more_on_set_link() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
// both rooms exist and life is good
dungeon.set_link("Съкровищница", Direction::East, "Вход").unwrap();
assert_eq!(dungeon.get_next_room("Съкровищница", Direction::East).unwrap().unwrap().name, "Вход");
assert_eq!(dungeon.get_next_room("Вход", Direction::West).unwrap().unwrap().name, "Съкровищница");
assert!(dungeon.get_next_room("Съкровищница", Direction::North).unwrap().is_none());
// first room exists, second does not
assert!(dungeon.set_link("Съкровищница", Direction::North, "Non-existent").is_err());
// first room does not exists, first does
assert!(dungeon.set_link("Non-exitent", Direction::North, "Съкровищница").is_err());
// both rooms do not exist
assert!(dungeon.set_link("Non-exitent", Direction::North, "Non-existent2").is_err());
}
#[test]
fn more_on_find_path() {
let mut dungeon = Dungeon::new();
dungeon.add_room("A").unwrap();
dungeon.add_room("B").unwrap();
dungeon.add_room("C").unwrap();
dungeon.add_room("D").unwrap();
dungeon.add_room("E").unwrap();
dungeon.add_room("F").unwrap();
dungeon.add_room("G").unwrap();
dungeon.set_link("A", Direction::West, "B").unwrap();
dungeon.set_link("B", Direction::West, "D").unwrap();
dungeon.set_link("B", Direction::South, "C").unwrap();
dungeon.set_link("C", Direction::West, "F").unwrap();
dungeon.set_link("C", Direction::South, "E").unwrap();
dungeon.set_link("F", Direction::North, "G").unwrap();
assert_eq!(dungeon.get_room("A").unwrap().name, "A");
assert_eq!(dungeon.get_room("B").unwrap().name, "B");
assert_eq!(dungeon.get_room("C").unwrap().name, "C");
assert_eq!(dungeon.get_room("D").unwrap().name, "D");
assert_eq!(dungeon.get_room("E").unwrap().name, "E");
assert_eq!(dungeon.get_room("F").unwrap().name, "F");
assert_eq!(dungeon.get_room("G").unwrap().name, "G");
assert_eq!(dungeon.get_next_room("A", Direction::West).unwrap().unwrap().name, "B");
assert_eq!(dungeon.get_next_room("B", Direction::West).unwrap().unwrap().name, "D");
assert_eq!(dungeon.get_next_room("B", Direction::South).unwrap().unwrap().name, "C");
assert_eq!(dungeon.get_next_room("C", Direction::West).unwrap().unwrap().name, "F");
assert_eq!(dungeon.get_next_room("C", Direction::South).unwrap().unwrap().name, "E");
assert_eq!(dungeon.get_next_room("F", Direction::North).unwrap().unwrap().name, "G");
// Using BFS, we find the shortest path, so a length compare check is made
let path = dungeon.find_path("A", "A").unwrap().unwrap();
assert_eq!(path.len(), 1);
let path = dungeon.find_path("A", "B").unwrap().unwrap();
assert_eq!(path.len(), 2);
let path1 = dungeon.find_path("A", "C").unwrap().unwrap();
assert_eq!(path1.len(), 3);
let path2 = dungeon.find_path("A", "D").unwrap().unwrap();
assert_eq!(path2.len(), 3);
let path3 = dungeon.find_path("A", "E").unwrap().unwrap();
assert_eq!(path3.len(), 4);
let path4 = dungeon.find_path("A", "F").unwrap().unwrap();
assert_eq!(path4.len(), 4);
let path5 = dungeon.find_path("A", "G").unwrap().unwrap();
assert_eq!(path5.len(), 5);
dungeon.add_room("disjoined").unwrap();
let path6 = dungeon.find_path("A", "disjoined").unwrap();
assert!(path6.is_none());
}
#[test]
fn empty_dungeon_is_created_correctly() {
let mut dungeon = Dungeon::new();
let res_get_room = dungeon.get_room("non-existent");
assert!(res_get_room.is_err());
let res_set_link = dungeon.set_link("несъществуваща1",
Direction::East,
"non-existent2");
assert!(res_set_link.is_err());
}
}

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

Compiling solution v0.1.0 (/tmp/d20220116-3533338-1iuw5xl/solution)
warning: type `adjacent` should have an upper camel case name
  --> src/lib.rs:21:12
   |
21 | pub struct adjacent
   |            ^^^^^^^^ help: convert the identifier to upper camel case: `Adjacent`
   |
   = note: `#[warn(non_camel_case_types)]` on by default

warning: `solution` (lib) generated 1 warning
    Finished test [unoptimized + debuginfo] target(s) in 4.55s
     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 ... ok
test solution_test::test_invalid_parsing ... FAILED
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_a_direct_path stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `["Treasure Room", "Entrance"]`,
 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", "Entrance"]`,
 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_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


failures:
    solution_test::test_finding_a_direct_path
    solution_test::test_finding_an_indirect_path
    solution_test::test_invalid_parsing

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'

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

Диана качи първо решение на 11.01.2022 16:01 (преди над 3 години)

Диана качи решение на 11.01.2022 16:12 (преди над 3 години)

use std::collections::{HashMap, VecDeque, HashSet};
use std::io::BufRead;
#[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,
}
pub struct adjacent
{
north: Option<String>,
south: Option<String>,
east: Option<String>,
west: Option<String>,
}
impl adjacent{
pub fn new()->Self{
adjacent{
north: None,
south: None,
east: None,
west: None,
}
}
}
pub struct Room {
pub name: String,
pub adj: adjacent
}
impl Room{
pub fn new(n: &str)->Self{
Room { name: n.to_string(), adj: adjacent::new() }
}
}
impl Room{
pub fn set_edge(&mut self, other_name: &str , direction: Direction)->() {
match direction {
Direction::East => {
self.adj.east = Some(other_name.to_string());
}
Direction::West => {
self.adj.west = Some(other_name.to_string());
}
Direction::North => {
self.adj.north = Some(other_name.to_string());
}
Direction::South => {
self.adj.south = Some(other_name.to_string());
}
}
}
pub fn remove_edge(&mut self, direction: Direction)->() {
match direction {
Direction::East => {
self.adj.east = None;
}
Direction::West => {
self.adj.west = None;
}
Direction::North => {
self.adj.north = None;
}
Direction::South => {
self.adj.south = None;
}
}
}
pub fn get_adj_at(&self, direction: Direction) -> Option<String> {
match direction {
Direction::East => {
self.adj.east.clone()
}
Direction::West => {
self.adj.west.clone()
}
Direction::South => {
self.adj.south.clone()
}
Direction::North => {
self.adj.north.clone()
}
}
}
}
pub struct Dungeon {
pub 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 found = self.get_room(name);
let res= match found
{
Ok(_) => Err(Errors::DuplicateRoom(String::from(name))),
Err(_) => {
self.rooms.insert(name.to_string(), Room{name: name.to_string(), adj: adjacent::new()});
Ok(())
}
};
res
}
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let found = self.rooms.get(room_name);
match found
{
Some(val) => Ok(val),
None => 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 r1 = self.rooms.get_mut(room_name);
if r1.is_none() {
return Err(Errors::UnknownRoom(room_name.to_string()));
}
- let temp = r1.as_ref().unwrap().get_adj_at(direction);
r1.unwrap().set_edge(other_room_name, direction);
let r2 = self.rooms.get_mut(other_room_name);
if r2.is_none() {
return Err(Errors::UnknownRoom(other_room_name.to_string()));
}
r2.unwrap().set_edge(room_name, match direction{ Direction::East => Direction::West,
Direction::West => Direction::East,
Direction::North => Direction::South,
Direction::South => Direction::North, } );
Ok(())
}
pub fn get_next_room(&self, room_name: &str, direction: Direction) -> Result<Option<&Room>, Errors> {
let x = self.get_room(room_name);
match x
{
Ok(val) => {
let adj = val.get_adj_at(direction);
match adj {
Some(n) => (Ok(Some(self.get_room(&n).unwrap()))),
None => Ok(None)
}
}
Err(_) => Err(Errors::UnknownRoom(room_name.to_string())),
}
}
}
impl Dungeon {
pub fn from_reader<B: BufRead>(mut reader: B) -> Result<Self, Errors> {
let mut res = Dungeon::new();
let mut first_line = String::new();
let x = reader.read_line(&mut first_line);
if x.is_err() {
return Err(Errors::LineParseError { line_number: 1 });
}
first_line = first_line.trim().to_string();
if first_line != "## Rooms"{
return Err(Errors::LineParseError { line_number: 1 });
}
let mut line = String::new();
let mut current_line_count = 1;
while reader.read_line(&mut line).is_ok() {
line = line.trim().to_string();
if line.len() == 0 {
break;
}
- if(line.len() < 2) {
+ if line.len() < 2 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let beg = &line[0..2];
- if(beg != "- ") {
+ if beg != "- " {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let name = &line[2..line.len()];
let add_res = res.add_room(name);
match add_res {
Ok(()) =>{
current_line_count += 1;
line.clear();}
Err(val) => return Err(val),
}
}
if !line.is_empty() {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let x = reader.read_line(&mut line);
current_line_count += 1;
if x.is_err() {
return Err(Errors::LineParseError { line_number: current_line_count });
}
line = line.trim().to_string();
if line != "## Links"{
return Err(Errors::LineParseError { line_number: current_line_count });
}
line.clear();
while reader.read_line(&mut line).unwrap() > 0 {
line = line.trim().to_string();
- if(line.len() < 2) {
+ if line.len() < 2 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let beg = &line[0..2];
- if(beg != "- ") {
+ if beg != "- " {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let mut ast: Vec<&str> = line[2..line.len()].split(" -> ").collect();
if ast.len() != 3 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let set_ln_res = res.set_link(ast[0], match ast[1] {
"East" => Direction::East,
"West" => Direction::West,
"North" => Direction::North,
"South" => Direction::South,
- _ => return Err(Errors::LineParseError { line_number: current_line_count }),
+ _ => return Err(Errors::DirectionParseError(ast[1].to_string())),
}, ast[2]);
match set_ln_res {
Ok(_) => {
current_line_count += 1;
line.clear();
},
Err(val) => return Err(val),
}
}
return Ok(res);
}
}
impl Dungeon {
pub fn find_path(
&self,
start_room_name: &str,
end_room_name: &str
) -> Result<Option<Vec<&Room>>, Errors> {
let start = self.get_room(start_room_name);
+ let target = self.get_room(end_room_name);
+ if target.is_err() {
+ return Err(Errors::UnknownRoom(end_room_name.to_string()));
+ }
match start {
Ok(val) => {
let mut q = VecDeque::<&Room>::new();
let mut parent_pointers = HashMap::<String, Option<String>>::new();
let mut visited = HashSet::<String>::new();
let mut path = Vec::<&Room>::new();
q.push_back(val);
parent_pointers.insert(val.name.clone(), None);
visited.insert(val.name.clone());
while !q.is_empty()
{
let x = q.pop_back();
if x.unwrap().name == end_room_name {
break;
}
let east = x.unwrap().get_adj_at(Direction::East);
let west = x.unwrap().get_adj_at(Direction::West);
let north = x.unwrap().get_adj_at(Direction::North);
let south = x.unwrap().get_adj_at(Direction::South);
match east
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match west
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match south
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match north
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
}
let target = parent_pointers.get(end_room_name);
match target {
Some(val) => {
- // the target room is found, its parent it val
- // push targer room to path
+ // the target room is found, its parent is val
+ // push target room to path
path.push(self.get_room(end_room_name).unwrap());
- // set x to be the parent
+ // update parent
let mut parent = val;
// while there is parent value
- // push it to path
+ // push to path
while parent.is_some() {
let t = parent_pointers.get(parent.as_ref().unwrap()).unwrap();
- path.push(self.get_room(&parent.as_ref().unwrap()).unwrap());
- // find parent of parent in parent pointers
+ path.push(self.get_room(&parent.as_ref().unwrap()).unwrap());
parent = t;
}
Ok(Some(path))
},
None => Ok(None),
}
},
Err(_) => Err(Errors::UnknownRoom(start_room_name.to_string())),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[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 more_on_add_room() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
let temp = dungeon.add_room("Съкровищница");
assert!(temp.is_err());
}
#[test]
fn more_on_get_room() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
let temp = dungeon.get_room("Съкровищница").unwrap();
assert_eq!(temp.name, "Съкровищница");
let temp_bad = dungeon.get_room("несъществуваща");
assert!(temp_bad.is_err());
}
#[test]
fn more_on_set_link() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
// both rooms exist and life is good
dungeon.set_link("Съкровищница", Direction::East, "Вход").unwrap();
assert_eq!(dungeon.get_next_room("Съкровищница", Direction::East).unwrap().unwrap().name, "Вход");
assert_eq!(dungeon.get_next_room("Вход", Direction::West).unwrap().unwrap().name, "Съкровищница");
assert!(dungeon.get_next_room("Съкровищница", Direction::North).unwrap().is_none());
// first room exists, second does not
assert!(dungeon.set_link("Съкровищница", Direction::North, "Non-existent").is_err());
// first room does not exists, first does
assert!(dungeon.set_link("Non-exitent", Direction::North, "Съкровищница").is_err());
// both rooms do not exist
assert!(dungeon.set_link("Non-exitent", Direction::North, "Non-existent2").is_err());
}
#[test]
fn more_on_find_path() {
let mut dungeon = Dungeon::new();
dungeon.add_room("A").unwrap();
dungeon.add_room("B").unwrap();
dungeon.add_room("C").unwrap();
dungeon.add_room("D").unwrap();
dungeon.add_room("E").unwrap();
dungeon.add_room("F").unwrap();
dungeon.add_room("G").unwrap();
dungeon.set_link("A", Direction::West, "B").unwrap();
dungeon.set_link("B", Direction::West, "D").unwrap();
dungeon.set_link("B", Direction::South, "C").unwrap();
dungeon.set_link("C", Direction::West, "F").unwrap();
dungeon.set_link("C", Direction::South, "E").unwrap();
dungeon.set_link("F", Direction::North, "G").unwrap();
assert_eq!(dungeon.get_room("A").unwrap().name, "A");
assert_eq!(dungeon.get_room("B").unwrap().name, "B");
assert_eq!(dungeon.get_room("C").unwrap().name, "C");
assert_eq!(dungeon.get_room("D").unwrap().name, "D");
assert_eq!(dungeon.get_room("E").unwrap().name, "E");
assert_eq!(dungeon.get_room("F").unwrap().name, "F");
assert_eq!(dungeon.get_room("G").unwrap().name, "G");
assert_eq!(dungeon.get_next_room("A", Direction::West).unwrap().unwrap().name, "B");
assert_eq!(dungeon.get_next_room("B", Direction::West).unwrap().unwrap().name, "D");
assert_eq!(dungeon.get_next_room("B", Direction::South).unwrap().unwrap().name, "C");
assert_eq!(dungeon.get_next_room("C", Direction::West).unwrap().unwrap().name, "F");
assert_eq!(dungeon.get_next_room("C", Direction::South).unwrap().unwrap().name, "E");
assert_eq!(dungeon.get_next_room("F", Direction::North).unwrap().unwrap().name, "G");
// Using BFS, we find the shortest path, so a length compare check is made
let path = dungeon.find_path("A", "A").unwrap().unwrap();
assert_eq!(path.len(), 1);
let path = dungeon.find_path("A", "B").unwrap().unwrap();
assert_eq!(path.len(), 2);
let path1 = dungeon.find_path("A", "C").unwrap().unwrap();
assert_eq!(path1.len(), 3);
let path2 = dungeon.find_path("A", "D").unwrap().unwrap();
assert_eq!(path2.len(), 3);
let path3 = dungeon.find_path("A", "E").unwrap().unwrap();
assert_eq!(path3.len(), 4);
let path4 = dungeon.find_path("A", "F").unwrap().unwrap();
assert_eq!(path4.len(), 4);
let path5 = dungeon.find_path("A", "G").unwrap().unwrap();
assert_eq!(path5.len(), 5);
dungeon.add_room("disjoined").unwrap();
let path6 = dungeon.find_path("A", "disjoined").unwrap();
assert!(path6.is_none());
}
#[test]
fn empty_dungeon_is_created_correctly() {
let mut dungeon = Dungeon::new();
let res_get_room = dungeon.get_room("non-existent");
assert!(res_get_room.is_err());
let res_set_link = dungeon.set_link("несъществуваща1",
Direction::East,
"non-existent2");
assert!(res_set_link.is_err());
}
}

Диана качи решение на 11.01.2022 16:31 (преди над 3 години)

use std::collections::{HashMap, VecDeque, HashSet};
use std::io::BufRead;
#[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,
}
pub struct adjacent
{
north: Option<String>,
south: Option<String>,
east: Option<String>,
west: Option<String>,
}
impl adjacent{
pub fn new()->Self{
adjacent{
north: None,
south: None,
east: None,
west: None,
}
}
}
pub struct Room {
pub name: String,
pub adj: adjacent
}
impl Room{
pub fn new(n: &str)->Self{
Room { name: n.to_string(), adj: adjacent::new() }
}
}
impl Room{
pub fn set_edge(&mut self, other_name: &str , direction: Direction)->() {
match direction {
Direction::East => {
self.adj.east = Some(other_name.to_string());
}
Direction::West => {
self.adj.west = Some(other_name.to_string());
}
Direction::North => {
self.adj.north = Some(other_name.to_string());
}
Direction::South => {
self.adj.south = Some(other_name.to_string());
}
}
}
pub fn remove_edge(&mut self, direction: Direction)->() {
match direction {
Direction::East => {
self.adj.east = None;
}
Direction::West => {
self.adj.west = None;
}
Direction::North => {
self.adj.north = None;
}
Direction::South => {
self.adj.south = None;
}
}
}
pub fn get_adj_at(&self, direction: Direction) -> Option<String> {
match direction {
Direction::East => {
self.adj.east.clone()
}
Direction::West => {
self.adj.west.clone()
}
Direction::South => {
self.adj.south.clone()
}
Direction::North => {
self.adj.north.clone()
}
}
}
}
pub struct Dungeon {
pub 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 found = self.get_room(name);
let res= match found
{
Ok(_) => Err(Errors::DuplicateRoom(String::from(name))),
Err(_) => {
self.rooms.insert(name.to_string(), Room{name: name.to_string(), adj: adjacent::new()});
Ok(())
}
};
res
}
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let found = self.rooms.get(room_name);
match found
{
Some(val) => Ok(val),
None => 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 r1 = self.rooms.get_mut(room_name);
if r1.is_none() {
return Err(Errors::UnknownRoom(room_name.to_string()));
}
r1.unwrap().set_edge(other_room_name, direction);
let r2 = self.rooms.get_mut(other_room_name);
if r2.is_none() {
return Err(Errors::UnknownRoom(other_room_name.to_string()));
}
r2.unwrap().set_edge(room_name, match direction{ Direction::East => Direction::West,
Direction::West => Direction::East,
Direction::North => Direction::South,
Direction::South => Direction::North, } );
Ok(())
}
pub fn get_next_room(&self, room_name: &str, direction: Direction) -> Result<Option<&Room>, Errors> {
let x = self.get_room(room_name);
match x
{
Ok(val) => {
let adj = val.get_adj_at(direction);
match adj {
Some(n) => (Ok(Some(self.get_room(&n).unwrap()))),
None => Ok(None)
}
}
Err(_) => Err(Errors::UnknownRoom(room_name.to_string())),
}
}
}
impl Dungeon {
pub fn from_reader<B: BufRead>(mut reader: B) -> Result<Self, Errors> {
let mut res = Dungeon::new();
let mut first_line = String::new();
let x = reader.read_line(&mut first_line);
- if x.is_err() {
- return Err(Errors::LineParseError { line_number: 1 });
+ match x {
+ Ok(_) => {},
+ Err(val) => return Err(Errors::IoError(val)),
}
first_line = first_line.trim().to_string();
if first_line != "## Rooms"{
return Err(Errors::LineParseError { line_number: 1 });
}
let mut line = String::new();
let mut current_line_count = 1;
while reader.read_line(&mut line).is_ok() {
line = line.trim().to_string();
if line.len() == 0 {
break;
}
if line.len() < 2 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let beg = &line[0..2];
if beg != "- " {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let name = &line[2..line.len()];
let add_res = res.add_room(name);
match add_res {
Ok(()) =>{
current_line_count += 1;
line.clear();}
Err(val) => return Err(val),
}
}
if !line.is_empty() {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let x = reader.read_line(&mut line);
- current_line_count += 1;
- if x.is_err() {
- return Err(Errors::LineParseError { line_number: current_line_count });
+ match x {
+ Ok(_) => {},
+ Err(val) => return Err(Errors::IoError(val)),
}
+ current_line_count += 1;
line = line.trim().to_string();
if line != "## Links"{
return Err(Errors::LineParseError { line_number: current_line_count });
}
line.clear();
- while reader.read_line(&mut line).unwrap() > 0 {
+ while reader.read_line(&mut line).is_ok() {
+ if line.len() == 0 {
+ break;
+ }
line = line.trim().to_string();
if line.len() < 2 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let beg = &line[0..2];
if beg != "- " {
return Err(Errors::LineParseError { line_number: current_line_count });
}
- let mut ast: Vec<&str> = line[2..line.len()].split(" -> ").collect();
+ let ast: Vec<&str> = line[2..line.len()].split(" -> ").collect();
if ast.len() != 3 {
return Err(Errors::LineParseError { line_number: current_line_count });
}
let set_ln_res = res.set_link(ast[0], match ast[1] {
"East" => Direction::East,
"West" => Direction::West,
"North" => Direction::North,
"South" => Direction::South,
_ => return Err(Errors::DirectionParseError(ast[1].to_string())),
}, ast[2]);
match set_ln_res {
Ok(_) => {
current_line_count += 1;
line.clear();
},
Err(val) => return Err(val),
}
}
return Ok(res);
}
}
impl Dungeon {
pub fn find_path(
&self,
start_room_name: &str,
end_room_name: &str
) -> Result<Option<Vec<&Room>>, Errors> {
let start = self.get_room(start_room_name);
let target = self.get_room(end_room_name);
if target.is_err() {
return Err(Errors::UnknownRoom(end_room_name.to_string()));
}
match start {
Ok(val) => {
let mut q = VecDeque::<&Room>::new();
let mut parent_pointers = HashMap::<String, Option<String>>::new();
let mut visited = HashSet::<String>::new();
let mut path = Vec::<&Room>::new();
q.push_back(val);
parent_pointers.insert(val.name.clone(), None);
visited.insert(val.name.clone());
while !q.is_empty()
{
let x = q.pop_back();
if x.unwrap().name == end_room_name {
break;
}
let east = x.unwrap().get_adj_at(Direction::East);
let west = x.unwrap().get_adj_at(Direction::West);
let north = x.unwrap().get_adj_at(Direction::North);
let south = x.unwrap().get_adj_at(Direction::South);
match east
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match west
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match south
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
match north
{
Some(val) => {
if !visited.contains(&*val) {
q.push_back(self.get_room(&val).unwrap());
visited.insert(val.clone());
parent_pointers.insert(val, Some(x.unwrap().name.clone()));
}
}
None => {
},
}
}
let target = parent_pointers.get(end_room_name);
match target {
Some(val) => {
// the target room is found, its parent is val
// push target room to path
path.push(self.get_room(end_room_name).unwrap());
// update parent
let mut parent = val;
// while there is parent value
// push to path
while parent.is_some() {
let t = parent_pointers.get(parent.as_ref().unwrap()).unwrap();
path.push(self.get_room(&parent.as_ref().unwrap()).unwrap());
parent = t;
}
Ok(Some(path))
},
None => Ok(None),
}
},
Err(_) => Err(Errors::UnknownRoom(start_room_name.to_string())),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[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 more_on_add_room() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
let temp = dungeon.add_room("Съкровищница");
assert!(temp.is_err());
}
#[test]
fn more_on_get_room() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
let temp = dungeon.get_room("Съкровищница").unwrap();
assert_eq!(temp.name, "Съкровищница");
let temp_bad = dungeon.get_room("несъществуваща");
assert!(temp_bad.is_err());
}
#[test]
fn more_on_set_link() {
let mut dungeon = Dungeon :: new();
dungeon.add_room("Вход").unwrap();
dungeon.add_room("Съкровищница").unwrap();
// both rooms exist and life is good
dungeon.set_link("Съкровищница", Direction::East, "Вход").unwrap();
assert_eq!(dungeon.get_next_room("Съкровищница", Direction::East).unwrap().unwrap().name, "Вход");
assert_eq!(dungeon.get_next_room("Вход", Direction::West).unwrap().unwrap().name, "Съкровищница");
assert!(dungeon.get_next_room("Съкровищница", Direction::North).unwrap().is_none());
// first room exists, second does not
assert!(dungeon.set_link("Съкровищница", Direction::North, "Non-existent").is_err());
// first room does not exists, first does
assert!(dungeon.set_link("Non-exitent", Direction::North, "Съкровищница").is_err());
// both rooms do not exist
assert!(dungeon.set_link("Non-exitent", Direction::North, "Non-existent2").is_err());
}
#[test]
fn more_on_find_path() {
let mut dungeon = Dungeon::new();
dungeon.add_room("A").unwrap();
dungeon.add_room("B").unwrap();
dungeon.add_room("C").unwrap();
dungeon.add_room("D").unwrap();
dungeon.add_room("E").unwrap();
dungeon.add_room("F").unwrap();
dungeon.add_room("G").unwrap();
dungeon.set_link("A", Direction::West, "B").unwrap();
dungeon.set_link("B", Direction::West, "D").unwrap();
dungeon.set_link("B", Direction::South, "C").unwrap();
dungeon.set_link("C", Direction::West, "F").unwrap();
dungeon.set_link("C", Direction::South, "E").unwrap();
dungeon.set_link("F", Direction::North, "G").unwrap();
assert_eq!(dungeon.get_room("A").unwrap().name, "A");
assert_eq!(dungeon.get_room("B").unwrap().name, "B");
assert_eq!(dungeon.get_room("C").unwrap().name, "C");
assert_eq!(dungeon.get_room("D").unwrap().name, "D");
assert_eq!(dungeon.get_room("E").unwrap().name, "E");
assert_eq!(dungeon.get_room("F").unwrap().name, "F");
assert_eq!(dungeon.get_room("G").unwrap().name, "G");
assert_eq!(dungeon.get_next_room("A", Direction::West).unwrap().unwrap().name, "B");
assert_eq!(dungeon.get_next_room("B", Direction::West).unwrap().unwrap().name, "D");
assert_eq!(dungeon.get_next_room("B", Direction::South).unwrap().unwrap().name, "C");
assert_eq!(dungeon.get_next_room("C", Direction::West).unwrap().unwrap().name, "F");
assert_eq!(dungeon.get_next_room("C", Direction::South).unwrap().unwrap().name, "E");
assert_eq!(dungeon.get_next_room("F", Direction::North).unwrap().unwrap().name, "G");
// Using BFS, we find the shortest path, so a length compare check is made
let path = dungeon.find_path("A", "A").unwrap().unwrap();
assert_eq!(path.len(), 1);
let path = dungeon.find_path("A", "B").unwrap().unwrap();
assert_eq!(path.len(), 2);
let path1 = dungeon.find_path("A", "C").unwrap().unwrap();
assert_eq!(path1.len(), 3);
let path2 = dungeon.find_path("A", "D").unwrap().unwrap();
assert_eq!(path2.len(), 3);
let path3 = dungeon.find_path("A", "E").unwrap().unwrap();
assert_eq!(path3.len(), 4);
let path4 = dungeon.find_path("A", "F").unwrap().unwrap();
assert_eq!(path4.len(), 4);
let path5 = dungeon.find_path("A", "G").unwrap().unwrap();
assert_eq!(path5.len(), 5);
dungeon.add_room("disjoined").unwrap();
let path6 = dungeon.find_path("A", "disjoined").unwrap();
assert!(path6.is_none());
}
#[test]
fn empty_dungeon_is_created_correctly() {
let mut dungeon = Dungeon::new();
let res_get_room = dungeon.get_room("non-existent");
assert!(res_get_room.is_err());
let res_set_link = dungeon.set_link("несъществуваща1",
Direction::East,
"non-existent2");
assert!(res_set_link.is_err());
}
}