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

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

Решение на Dungeons and Compilers от Петър Ангелов

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

Към профила на Петър Ангелов

Резултати

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

Код

use std::collections::{HashMap, VecDeque};
use std::io;
use std::io::BufRead;
use std::str::FromStr;
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
impl From<io::Error> for Errors {
fn from(e: io::Error) -> Self {
Errors::IoError(e)
}
}
/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub enum Direction {
North,
South,
East,
West,
}
impl Direction {
pub fn opposite(self) -> Direction {
match self {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::East => Direction::West,
Direction::West => Direction::East,
}
}
}
impl FromStr for Direction {
type Err = Errors;
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"North" => Ok(Direction::North),
"South" => Ok(Direction::South),
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
x => Err(Errors::DirectionParseError(String::from(x))),
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
#[derive(Debug, PartialEq, Eq)]
pub struct Room {
pub name: String,
// Каквито други полета ви трябват
pub neighbours: HashMap<Direction, String>,
}
impl Room {
pub fn new(name: String) -> Self {
Room {
name: name,
neighbours: HashMap::new(),
}
}
pub fn get_neighbour(&self, direction: Direction) -> Option<String> {
self.neighbours.get(&direction).map(|x| x.clone())
}
pub fn add_neighbour(&mut self, direction: Direction, neighbour: String) -> () {
self.neighbours.insert(direction, neighbour);
}
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
#[derive(Debug)]
pub struct Dungeon {
// Каквито полета ви трябват
pub to_room: HashMap<String, Room>,
}
#[derive(Clone, Debug)]
enum ReadType {
Empty,
Rooms,
Room(String),
EmptyLine,
Links,
Link(String, Direction, String),
}
impl ReadType {
fn new() -> Self {
return ReadType::Empty;
}
fn can_follow(&self, other: &Self) -> bool {
match (self, other) {
(ReadType::Empty, ReadType::Rooms) => true,
(ReadType::Rooms, ReadType::Room(_)) => true,
(ReadType::Rooms, ReadType::EmptyLine) => true,
(ReadType::Room(_), ReadType::Room(_)) => true,
(ReadType::Room(_), ReadType::EmptyLine) => true,
(ReadType::EmptyLine, ReadType::Links) => true,
(ReadType::Links, ReadType::Link(_, _, _)) => true,
(ReadType::Link(_, _, _), ReadType::Link(_, _, _)) => true,
_ => false,
}
}
}
impl FromStr for ReadType {
type Err = Errors;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let default_error = Errors::LineParseError { line_number: 0 };
match s {
"## Rooms" => Ok(ReadType::Rooms),
"## Links" => Ok(ReadType::Links),
"" => Ok(ReadType::EmptyLine),
x if match_prefix("- ", x).is_some() => {
let trimmed = match_prefix("- ", x).unwrap();
if trimmed.contains("->") {
// then it should be link
let split = trimmed.split(" -> ").collect::<Vec<&str>>();
if split.len() != 3 {
return Err(default_error);
}
let direction: Direction = split[1].parse()?;
Ok(ReadType::Link(
String::from(split[0]),
direction,
String::from(split[2]),
))
} else {
// then it should be room
Ok(ReadType::Room(String::from(trimmed)))
}
}
_ => Err(default_error),
}
}
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
Dungeon {
to_room: HashMap::new(),
}
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
let s = String::from(name);
if self.to_room.contains_key(&s) {
return Err(Errors::DuplicateRoom(s));
}
let s_copy = s.clone();
self.to_room.insert(s, Room::new(s_copy));
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let s = String::from(room_name);
match self.to_room.get(&s) {
None => Err(Errors::UnknownRoom(s)),
Some(room) => Ok(room),
}
}
/// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
/// `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> {
let s = String::from(room_name);
let s_other = String::from(other_room_name);
let s_copy = s_other.clone();
match self.to_room.get_mut(&s) {
None => return Err(Errors::UnknownRoom(s)),
Some(r) => r.add_neighbour(direction, s_other),
};
match self.to_room.get_mut(&s_copy) {
None => return Err(Errors::UnknownRoom(s_copy)),
Some(r) => r.add_neighbour(direction.opposite(), s),
};
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 s = String::from(room_name);
match self.to_room.get(&s) {
None => Err(Errors::UnknownRoom(s)),
Some(r) => Ok(r
.get_neighbour(direction)
.map(|x| self.to_room.get(&x))
.flatten()),
}
}
}
impl Dungeon {
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dungeon = Dungeon::new();
let mut previous = ReadType::new();
let mut line_number = 0;
for line in reader.lines() {
line_number += 1;
let line = line?;
let current: ReadType = line.parse().map_err(|err| match err {
Errors::LineParseError { line_number: _ } => Errors::LineParseError { line_number },
_ => err,
})?;
if !previous.can_follow(&current) {
return Err(Errors::LineParseError { line_number });
}
match &current {
ReadType::Room(room_name) => dungeon.add_room(&room_name)?,
ReadType::Link(room_name, direction, other_room_name) => {
dungeon.set_link(&room_name, *direction, &other_room_name)?
}
_ => (),
}
previous = current;
}
// make sure input ends where it needs to
match &previous {
ReadType::Links | ReadType::Link(_, _, _) => Ok(dungeon),
_ => Err(Errors::LineParseError { line_number }),
}
}
}
/// 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) {
None
} else {
input.strip_prefix(prefix)
}
}
impl 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 nodes = VecDeque::<String>::new();
let mut parents = HashMap::<String, Option<String>>::new();
nodes.push_back(String::from(start_room_name));
parents.insert(String::from(start_room_name), None);
while nodes.len() > 0 {
let curr = nodes.pop_front().unwrap();
for dir in [
Direction::West,
Direction::East,
Direction::North,
Direction::South,
] {
match self.get_next_room(&curr, dir)? {
None => (),
Some(neighbour) => {
if !parents.contains_key(&neighbour.name) {
parents.insert(neighbour.name.clone(), Some(curr.clone()));
nodes.push_back(neighbour.name.clone());
}
if neighbour.name == end_room_name {
break;
}
}
}
}
}
match parents.get(&String::from(end_room_name)) {
None => Ok(None),
Some(_) => {
let mut path = Vec::<&Room>::new();
let mut curr = &Some(String::from(end_room_name));
while curr.is_some() {
let curr_some = curr.clone().unwrap();
let curr_room = self.get_room(&curr_some.clone())?;
path.push(curr_room);
curr = parents.get(&curr_some.clone()).unwrap();
}
path.reverse();
Ok(Some(path))
}
}
}
}

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

Compiling solution v0.1.0 (/tmp/d20220116-3533338-j6ao4a/solution)
    Finished test [unoptimized + debuginfo] target(s) in 4.54s
     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 ... ok
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


failures:
    solution_test::test_finding_no_path

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 коментара)

Петър качи първо решение на 08.01.2022 16:11 (преди почти 4 години)

Петър качи решение на 11.01.2022 15:32 (преди над 3 години)

use std::collections::{HashMap, VecDeque};
use std::io;
use std::io::BufRead;
use std::str::FromStr;
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
impl From<io::Error> for Errors {
fn from(e: io::Error) -> Self {
Errors::IoError(e)
}
}
/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub enum Direction {
North,
South,
East,
West,
}
impl Direction {
pub fn opposite(self) -> Direction {
match self {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::East => Direction::West,
Direction::West => Direction::East,
}
}
}
impl FromStr for Direction {
type Err = Errors;
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"North" => Ok(Direction::North),
"South" => Ok(Direction::South),
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
x => Err(Errors::DirectionParseError(String::from(x))),
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
#[derive(Debug, PartialEq, Eq)]
pub struct Room {
pub name: String,
// Каквито други полета ви трябват
pub neighbours: HashMap<Direction, String>,
}
impl Room {
pub fn new(name: String) -> Self {
Room {
name: name,
neighbours: HashMap::new(),
}
}
pub fn get_neighbour(&self, direction: Direction) -> Option<String> {
self.neighbours.get(&direction).map(|x| x.clone())
}
pub fn add_neighbour(&mut self, direction: Direction, neighbour: String) -> () {
self.neighbours.insert(direction, neighbour);
}
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
#[derive(Debug)]
pub struct Dungeon {
// Каквито полета ви трябват
pub to_room: HashMap<String, Room>,
}
#[derive(Clone, Debug)]
enum ReadType {
Empty,
Rooms,
Room(String),
EmptyLine,
Links,
Link(String, Direction, String),
}
impl ReadType {
fn new() -> Self {
return ReadType::Empty;
}
fn can_follow(&self, other: &Self) -> bool {
match (self, other) {
(ReadType::Empty, ReadType::Rooms) => true,
(ReadType::Rooms, ReadType::Room(_)) => true,
+ (ReadType::Rooms, ReadType::EmptyLine) => true,
(ReadType::Room(_), ReadType::Room(_)) => true,
(ReadType::Room(_), ReadType::EmptyLine) => true,
(ReadType::EmptyLine, ReadType::Links) => true,
(ReadType::Links, ReadType::Link(_, _, _)) => true,
(ReadType::Link(_, _, _), ReadType::Link(_, _, _)) => true,
_ => false,
}
}
}
impl FromStr for ReadType {
type Err = Errors;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let default_error = Errors::LineParseError { line_number: 0 };
match s {
"## Rooms" => Ok(ReadType::Rooms),
"## Links" => Ok(ReadType::Links),
"" => Ok(ReadType::EmptyLine),
x if match_prefix("- ", x).is_some() => {
let trimmed = match_prefix("- ", x).unwrap();
if trimmed.contains("->") {
// then it should be link
let split = trimmed.split(" -> ").collect::<Vec<&str>>();
if split.len() != 3 {
return Err(default_error);
}
let direction: Direction = split[1].parse()?;
Ok(ReadType::Link(
String::from(split[0]),
direction,
String::from(split[2]),
))
} else {
// then it should be room
Ok(ReadType::Room(String::from(trimmed)))
}
}
_ => Err(default_error),
}
}
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
Dungeon {
to_room: HashMap::new(),
}
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
let s = String::from(name);
if self.to_room.contains_key(&s) {
return Err(Errors::DuplicateRoom(s));
}
let s_copy = s.clone();
self.to_room.insert(s, Room::new(s_copy));
Ok(())
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let s = String::from(room_name);
match self.to_room.get(&s) {
None => Err(Errors::UnknownRoom(s)),
Some(room) => Ok(room),
}
}
/// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
/// `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> {
let s = String::from(room_name);
let s_other = String::from(other_room_name);
let s_copy = s_other.clone();
match self.to_room.get_mut(&s) {
None => return Err(Errors::UnknownRoom(s)),
Some(r) => r.add_neighbour(direction, s_other),
};
match self.to_room.get_mut(&s_copy) {
None => return Err(Errors::UnknownRoom(s_copy)),
Some(r) => r.add_neighbour(direction.opposite(), s),
};
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 s = String::from(room_name);
match self.to_room.get(&s) {
None => Err(Errors::UnknownRoom(s)),
Some(r) => Ok(r
.get_neighbour(direction)
.map(|x| self.to_room.get(&x))
.flatten()),
}
}
}
impl Dungeon {
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dungeon = Dungeon::new();
let mut previous = ReadType::new();
let mut line_number = 0;
for line in reader.lines() {
line_number += 1;
let line = line?;
let current: ReadType = line.parse().map_err(|err| match err {
Errors::LineParseError { line_number: _ } => Errors::LineParseError { line_number },
_ => err,
})?;
if !previous.can_follow(&current) {
return Err(Errors::LineParseError { line_number });
}
match &current {
ReadType::Room(room_name) => dungeon.add_room(&room_name)?,
ReadType::Link(room_name, direction, other_room_name) => {
dungeon.set_link(&room_name, *direction, &other_room_name)?
}
_ => (),
}
previous = current;
}
// make sure input ends where it needs to
match &previous {
ReadType::Links | ReadType::Link(_, _, _) => Ok(dungeon),
_ => Err(Errors::LineParseError { line_number }),
}
}
}
/// 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) {
None
} else {
input.strip_prefix(prefix)
}
}
impl 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 nodes = VecDeque::<String>::new();
let mut parents = HashMap::<String, Option<String>>::new();
nodes.push_back(String::from(start_room_name));
parents.insert(String::from(start_room_name), None);
while nodes.len() > 0 {
let curr = nodes.pop_front().unwrap();
for dir in [
Direction::West,
Direction::East,
Direction::North,
Direction::South,
] {
match self.get_next_room(&curr, dir)? {
None => (),
Some(neighbour) => {
if !parents.contains_key(&neighbour.name) {
parents.insert(neighbour.name.clone(), Some(curr.clone()));
nodes.push_back(neighbour.name.clone());
}
if neighbour.name == end_room_name {
break;
}
}
}
}
}
match parents.get(&String::from(end_room_name)) {
None => Ok(None),
Some(_) => {
let mut path = Vec::<&Room>::new();
let mut curr = &Some(String::from(end_room_name));
while curr.is_some() {
let curr_some = curr.clone().unwrap();
let curr_room = self.get_room(&curr_some.clone())?;
path.push(curr_room);
curr = parents.get(&curr_some.clone()).unwrap();
}
path.reverse();
Ok(Some(path))
}
}
}
}