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

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

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

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

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

Резултати

  • 17 точки от тестове
  • 0 бонус точки
  • 17 точки общо
  • 13 успешни тест(а)
  • 2 неуспешни тест(а)

Код

use std::collections::HashMap;
use std::collections::HashSet;
use std::io::prelude::*;
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Hash, Eq, PartialEq, Clone, Copy, Debug)]
pub enum Direction {
North,
South,
East,
West,
}
impl Direction {
pub fn get_reverse(&self) -> Direction {
match *self {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::East => Direction::West,
Direction::West => Direction::East,
}
}
pub fn from_string(string_direction : &str) -> Result<Direction, Errors> {
match string_direction {
"North" => Ok(Direction::North),
"South" => Ok(Direction::South),
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
_ => Err(Errors::DirectionParseError(string_direction.to_string()))
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
#[derive(Debug)]
pub struct Room {
pub name: String,
pub adjacent: HashMap<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()));
}
self.rooms.insert(name.to_string(),
Room{ name : name.to_string(), adjacent : HashMap::new() });
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
match self.rooms.get(room_name) {
Some(room) => Ok(room),
None => 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()))
}
if !self.rooms.contains_key(other_room_name) {
return Err(Errors::UnknownRoom(other_room_name.to_string()))
}
self.rooms.entry(room_name.to_string()).and_modify(|e| { e.adjacent.insert(direction, other_room_name.to_string()); });
self.rooms.entry(other_room_name.to_string()).and_modify(|e| { e.adjacent.insert(direction.get_reverse(), 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> {
match self.rooms.get(room_name) {
Some(room) => {
match room.adjacent.get(&direction) {
Some(other_room_name) => {
Ok(Some(&self.rooms[other_room_name]))
},
None => Ok(None)
}
},
None => Err(Errors::UnknownRoom(room_name.to_string()))
}
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(mut reader: B) -> Result<Self, Errors> {
let mut buf = String::new();
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
return Err(Errors::LineParseError{ line_number : 0})
}
if buf != "## Rooms" {
return Err(Errors::LineParseError{ line_number : 1});
}
let mut line_number = 1;
let mut dungeon = Dungeon::new();
loop {
buf.clear();
line_number += 1;
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
break;
}
if buf.chars().nth(0) != Some('-') {
return Err(Errors::LineParseError{line_number});
}
match buf.find(|c : char| !c.is_whitespace() && c != '-') {
Some(index) => { dungeon.add_room(&buf[index..])?; },
None => { return Err(Errors::LineParseError{line_number}); }
}
}
buf.clear();
line_number += 1;
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
return Err(Errors::LineParseError{ line_number : 0})
}
if buf != "## Links" {
return Err(Errors::LineParseError{ line_number : 1});
}
loop {
buf.clear();
line_number += 1;
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
break;
}
if buf.chars().nth(0) != Some('-') {
return Err(Errors::LineParseError{line_number});
}
match buf.find(|c : char| !c.is_whitespace() && c != '-') {
Some(index) => {
let split : Vec<&str> = buf[index..].split("->").collect();
if split.len() != 3 {
return Err(Errors::LineParseError{line_number});
}
let direction = Direction::from_string(split[1].to_string().trim())?;
dungeon.set_link(split[0].to_string().trim(), direction, split[2].to_string().trim())?;
},
None => { return Err(Errors::LineParseError{line_number}); }
}
}
//println!("{:?}", dungeon);
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 visited = HashSet::<String>::new();
let mut queue = Vec::<&str>::new();
let mut parents = HashMap::<&str, &str>::new();
let start_room = self.get_room(start_room_name)?;
queue.push(&start_room.name);
while !queue.is_empty() {
let current_room = queue.pop().unwrap();
visited.insert(current_room.to_string());
if current_room == end_room_name {
break;
}
let room = self.get_room(&current_room)?;
for adj in &room.adjacent {
let adj_name = adj.1;
if visited.contains(adj_name) {
continue;
}
visited.insert(adj_name.to_string());
queue.push(&adj_name);
parents.insert(&adj_name, &current_room);
}
}
if !visited.contains(end_room_name) {
return Ok(None)
}
let mut result = Vec::<&Room>::new();
let mut current_reverse = end_room_name;
loop {
match parents.get(current_reverse) {
Some(room_name) => {
result.push(self.get_room(current_reverse)?);
current_reverse = room_name;
},
None => {
result.push(self.get_room(current_reverse)?);
break;
}
}
}
result.reverse();
Ok(Some(result))
}
}

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

Compiling solution v0.1.0 (/tmp/d20220116-3533338-kpnf4w/solution)
    Finished test [unoptimized + debuginfo] target(s) in 3.79s
     Running tests/solution_test.rs (target/debug/deps/solution_test-2e292b23ac75572c)

running 15 tests
test solution_test::test_adding_rooms_1 ... ok
test solution_test::test_adding_rooms_2 ... ok
test solution_test::test_cyrillic_room_names ... ok
test solution_test::test_finding_a_direct_path ... ok
test solution_test::test_finding_a_reflexive_path ... ok
test solution_test::test_finding_an_indirect_path ... ok
test solution_test::test_finding_no_path ... FAILED
test solution_test::test_invalid_parsing ... FAILED
test solution_test::test_io_error ... 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_no_path stdout ----
thread '<unnamed>' panicked at 'assertion failed: path.is_err()', tests/solution_test.rs:382:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:372:5

---- solution_test::test_invalid_parsing stdout ----
thread 'main' panicked at 'assertion failed: matches!(Dungeon :: from_reader(TEST_INPUT_5.trim().as_bytes()),\n         Err(Errors :: LineParseError { line_number : 3 }))', tests/solution_test.rs:278:5


failures:
    solution_test::test_finding_no_path
    solution_test::test_invalid_parsing

test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

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

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

Мартин качи първо решение на 09.01.2022 16:32 (преди почти 4 години)

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

use std::collections::HashMap;
use std::collections::HashSet;
use std::io::prelude::*;
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Hash, Eq, PartialEq, Clone, Copy, Debug)]
pub enum Direction {
North,
South,
East,
West,
}
impl Direction {
pub fn get_reverse(&self) -> Direction {
match *self {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::East => Direction::West,
Direction::West => Direction::East,
}
}
pub fn from_string(string_direction : &str) -> Result<Direction, Errors> {
match string_direction {
"North" => Ok(Direction::North),
"South" => Ok(Direction::South),
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
_ => Err(Errors::DirectionParseError(string_direction.to_string()))
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
#[derive(Debug)]
pub struct Room {
pub name: String,
pub adjacent: HashMap<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()));
}
self.rooms.insert(name.to_string(),
Room{ name : name.to_string(), adjacent : HashMap::new() });
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
match self.rooms.get(room_name) {
Some(room) => Ok(room),
None => 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()))
}
if !self.rooms.contains_key(other_room_name) {
return Err(Errors::UnknownRoom(other_room_name.to_string()))
}
self.rooms.entry(room_name.to_string()).and_modify(|e| { e.adjacent.insert(direction, other_room_name.to_string()); });
self.rooms.entry(other_room_name.to_string()).and_modify(|e| { e.adjacent.insert(direction.get_reverse(), 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> {
match self.rooms.get(room_name) {
Some(room) => {
match room.adjacent.get(&direction) {
Some(other_room_name) => {
Ok(Some(&self.rooms[other_room_name]))
},
None => Ok(None)
}
},
None => Err(Errors::UnknownRoom(room_name.to_string()))
}
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(mut reader: B) -> Result<Self, Errors> {
let mut buf = String::new();
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
return Err(Errors::LineParseError{ line_number : 0})
}
if buf != "## Rooms" {
return Err(Errors::LineParseError{ line_number : 1});
}
let mut line_number = 1;
let mut dungeon = Dungeon::new();
loop {
buf.clear();
line_number += 1;
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
break;
}
if buf.chars().nth(0) != Some('-') {
return Err(Errors::LineParseError{line_number});
}
match buf.find(|c : char| !c.is_whitespace() && c != '-') {
Some(index) => { dungeon.add_room(&buf[index..])?; },
None => { return Err(Errors::LineParseError{line_number}); }
}
}
buf.clear();
line_number += 1;
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
return Err(Errors::LineParseError{ line_number : 0})
}
if buf != "## Links" {
return Err(Errors::LineParseError{ line_number : 1});
}
loop {
buf.clear();
line_number += 1;
match reader.read_line(&mut buf) {
Ok(_) => { buf = buf.trim().to_string(); },
Err(io_error) => { return Err(Errors::IoError(io_error)); }
}
if buf.is_empty() {
break;
}
if buf.chars().nth(0) != Some('-') {
return Err(Errors::LineParseError{line_number});
}
match buf.find(|c : char| !c.is_whitespace() && c != '-') {
Some(index) => {
let split : Vec<&str> = buf[index..].split("->").collect();
if split.len() != 3 {
return Err(Errors::LineParseError{line_number});
}
let direction = Direction::from_string(split[1].to_string().trim())?;
dungeon.set_link(split[0].to_string().trim(), direction, split[2].to_string().trim())?;
},
None => { return Err(Errors::LineParseError{line_number}); }
}
}
//println!("{:?}", dungeon);
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 visited = HashSet::<String>::new();
let mut queue = Vec::<&str>::new();
let mut parents = HashMap::<&str, &str>::new();
let start_room = self.get_room(start_room_name)?;
queue.push(&start_room.name);
while !queue.is_empty() {
let current_room = queue.pop().unwrap();
+ visited.insert(current_room.to_string());
+
if current_room == end_room_name {
break;
}
-
- visited.insert(current_room.to_string());
let room = self.get_room(&current_room)?;
for adj in &room.adjacent {
let adj_name = adj.1;
if visited.contains(adj_name) {
continue;
}
visited.insert(adj_name.to_string());
queue.push(&adj_name);
parents.insert(&adj_name, &current_room);
}
}
if !visited.contains(end_room_name) {
return Ok(None)
}
let mut result = Vec::<&Room>::new();
let mut current_reverse = end_room_name;
loop {
match parents.get(current_reverse) {
Some(room_name) => {
result.push(self.get_room(current_reverse)?);
current_reverse = room_name;
},
None => {
result.push(self.get_room(current_reverse)?);
break;
}
}
}
result.reverse();
Ok(Some(result))
}
}