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

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

Решение на Dungeons and Compilers от Кристиян Цветанов

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

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

Резултати

  • 20 точки от тестове
  • 0 бонус точки
  • 20 точки общо
  • 15 успешни тест(а)
  • 0 неуспешни тест(а)

Код

use std::io::Lines;
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::BufRead;
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Direction {
North,
South,
East,
West,
}
/// парвса низ до Direction
fn from_str(s: &str) -> Result<Direction, Errors> {
match s {
"North" => Ok(Direction::North),
"South" => Ok(Direction::South),
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
_ => Err(Errors::DirectionParseError(s.to_string())),
}
}
/// връща обратната посока на подадената като параметър
fn opposite(direction: Direction) -> Direction {
match direction {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::East => Direction::West,
Direction::West => Direction::East,
}
}
/// Проверява дали даден низ input започва с низ prefix
pub fn match_prefix<'a, 'b>(prefix: &'a str, input: &'b str) -> Option<&'b str> {
if input.len() >= 2 && prefix == &input[0..2] {
Some(&input[2..])
} else {
None
}
}
/// проверява дали низът link е във формата "- <име на стая> -> <посока> -> <име на друга стая>"
pub fn check_link_format(link: String, num_of_line: usize) -> Result<(String, Direction, String), Errors> {
let vec_chars: Vec<char> = link.chars().collect();
let mut vec_arrow_pos: Vec<usize> = Vec::new();
let mut i = 0;
let len = vec_chars.len();
while i < len {
if vec_chars[i] == '-' && i < len-1 && vec_chars[i+1] == '>' {
vec_arrow_pos.push(i);
}
i += 1;
}
if vec_arrow_pos.len() != 2 {
return Err(Errors::LineParseError{ line_number: num_of_line });
}
let name_size = vec_arrow_pos[0] - 1;
let dir_begin = vec_arrow_pos[0] + 3;
let dir_size = (vec_arrow_pos[1] - 1) - dir_begin;
let other_name_begin = vec_arrow_pos[1] + 3;
if other_name_begin >= link.len() {
return Err(Errors::LineParseError{ line_number: num_of_line });
}
let room_name: String = link.chars().into_iter().take(name_size).collect();
let dir_str: String = link.chars().into_iter().skip(dir_begin).take(dir_size).collect();
let direction = from_str(&dir_str)?;
let other_room_name: String = link.chars().into_iter().skip(other_name_begin).collect();
Ok((room_name, direction, other_room_name))
}
pub struct Room {
pub name: String,
pub neighbours: HashMap<Direction, String>,
}
pub struct Dungeon {
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 name_str = String::from(name);
if self.rooms.contains_key(&name_str) {
Err(Errors::DuplicateRoom(name_str))
} else {
let new_room = Room {
name: name_str.clone(),
neighbours: HashMap::new(),
};
self.rooms.insert(name_str, new_room);
Ok(())
}
}
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let room_name_str = String::from(room_name);
if self.rooms.contains_key(&room_name_str) {
Ok(self.rooms.get(&room_name_str).unwrap())
} else {
Err(Errors::UnknownRoom(room_name_str))
}
}
pub fn set_link(
&mut self,
room_name: &str,
direction: Direction,
other_room_name: &str,
) -> Result<(), Errors> {
let room_name_str = String::from(room_name);
let other_room_name_str = String::from(other_room_name);
if !self.rooms.contains_key(&room_name_str) {
Err(Errors::UnknownRoom(room_name_str))
} else if !self.rooms.contains_key(&other_room_name_str) {
Err(Errors::UnknownRoom(other_room_name_str))
} else {
let first_room = self.rooms.get_mut(&room_name_str).unwrap();
first_room.neighbours.insert(direction, other_room_name_str.clone());
let second_room = self.rooms.get_mut(&other_room_name_str).unwrap();
second_room.neighbours.insert(opposite(direction), room_name_str.clone());
Ok(())
}
}
pub fn get_next_room(&self, room_name: &str, direction: Direction) -> Result<Option<&Room>, Errors> {
let room_name_str = String::from(room_name);
if !self.rooms.contains_key(&room_name_str) {
Err(Errors::UnknownRoom(room_name_str))
} else {
let room = self.rooms.get(&room_name_str).unwrap();
let next_room_name = room.neighbours.get(&direction);
if let Some(s) = next_room_name {
// Стаята има съсед в посока direction
Ok(self.rooms.get(s))
} else {
// Няма съсед
Ok(None)
}
}
}
/// добавя стаите от файла(или друг поток от байтове) параметър на ф-ята from_reader(...)
fn add_rooms_from_reader<B: BufRead>(&mut self, lines_iter: &mut Lines<B>) -> Result<usize, Errors> {
let mut num_of_line: usize = 1;
while let Some(line) = lines_iter.next() {
num_of_line += 1;
let line_str = match line {
Err(e) => return Err(Errors::IoError(e)),
Ok(l) => l,
};
if let Some(room_name) = match_prefix("- ", &line_str) {
// формата на реда е за нова стая, значи добавяме стаята
let _ = self.add_room(room_name)?;
} else if line_str == "" {
// приключваме с добавянето на стаи, връщаме номера на реда
return Ok(num_of_line);
} else {
// грешен формат и не е нов ред
return Err(Errors::LineParseError{ line_number: num_of_line });
}
}
Ok(num_of_line)
}
/// добавя връзките от файла(или друг поток от байтове) параметър на ф-ята from_reader(...)
fn add_links_from_reader<B: BufRead>(
&mut self,
lines_iter: &mut Lines<B>,
num: usize
) -> Result<(), Errors> {
let mut num_of_line = num;
while let Some(line) = lines_iter.next() {
num_of_line += 1;
let line_str = match line {
Err(e) => return Err(Errors::IoError(e)),
Ok(l) => l,
};
if let Some(link) = match_prefix("- ", &line_str) {
// формата на реда започва с "- "
// сега трябва да проверим останалата част дали е "room -> direction -> room"
let (room_name, direction, other_room_name) = check_link_format(link.to_string(), num_of_line)?;
// добавяме връзката
let _ = self.set_link(&room_name, direction, &other_room_name)?;
} else {
// грешен формат
return Err(Errors::LineParseError{ line_number: num_of_line });
}
}
Ok(())
}
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dungeon = Dungeon::new();
let mut num_of_line;
let mut lines_iter = reader.lines();
let line = lines_iter.next();
if line.is_none() {
return Err(Errors::LineParseError{ line_number: 0 });
}
let line_str = match line.unwrap() {
Err(e) => return Err(Errors::IoError(e)),
Ok(l) => l,
};
if line_str == "## Rooms" {
num_of_line = dungeon.add_rooms_from_reader(&mut lines_iter)?;
} else {
return Err(Errors::LineParseError{ line_number: 1 });
}
let line = lines_iter.next();
num_of_line += 1;
if line.is_none() {
return Err(Errors::LineParseError{ line_number: num_of_line });
}
let line_str = match line.unwrap() {
Err(e) => return Err(Errors::IoError(e)),
Ok(l) => l,
};
if line_str == "## Links" {
let _ = dungeon.add_links_from_reader(&mut lines_iter, num_of_line)?;
} else {
return Err(Errors::LineParseError{ line_number: num_of_line });
}
Ok(dungeon)
}
/// построява пътя от структурата parents
fn build_path(
&self,
start_room_name: &str,
end_room_name: &str,
parents: HashMap<String, String>) -> Vec<&Room> {
let mut path: Vec<&Room> = Vec::new();
let mut curr_name = end_room_name;
while parents.contains_key(curr_name) {
let curr_room = self.get_room(curr_name).unwrap();
path.insert(0, curr_room);
curr_name = parents.get(curr_name).unwrap();
}
path.insert(0, self.get_room(start_room_name).unwrap());
path
}
pub fn find_path(
&self,
start_room_name: &str,
end_room_name: &str
) -> Result<Option<Vec<&Room>>, Errors> {
if self.get_room(&start_room_name).is_err() {
return Err(Errors::UnknownRoom(start_room_name.to_string()));
}
if self.get_room(&end_room_name).is_err() {
return Err(Errors::UnknownRoom(end_room_name.to_string()));
}
if start_room_name == end_room_name {
return Ok(Some(vec![self.get_room(start_room_name).unwrap()]));
}
// bfs
let mut visited: HashSet<String> = HashSet::new();
let mut queue: VecDeque<&Room> = VecDeque::new();
let mut parents: HashMap<String, String> = HashMap::new();
visited.insert(start_room_name.to_string());
queue.push_back(self.get_room(&start_room_name).unwrap());
while !queue.is_empty() {
let u = queue.pop_front().unwrap();
println!("curr room: {}", u.name);
let neighbour_vec: Vec<&String> = u.neighbours.values().collect();
for v_name in neighbour_vec {
if !visited.contains(v_name) {
visited.insert(v_name.clone());
parents.insert(v_name.clone(), u.name.clone());
queue.push_back(self.get_room(v_name).unwrap());
}
}
}
if !parents.contains_key(&end_room_name.to_string()) {
return Ok(None);
}
Ok(Some(self.build_path(start_room_name, end_room_name, parents)))
}
}

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

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

running 15 tests
test solution_test::test_adding_rooms_1 ... ok
test solution_test::test_adding_rooms_2 ... ok
test solution_test::test_cyrillic_room_names ... ok
test solution_test::test_finding_a_direct_path ... ok
test solution_test::test_finding_a_reflexive_path ... ok
test solution_test::test_finding_an_indirect_path ... ok
test solution_test::test_finding_no_path ... ok
test solution_test::test_invalid_parsing ... ok
test solution_test::test_io_error ... 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

test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

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

Кристиян качи първо решение на 30.12.2021 22:31 (преди почти 4 години)

Кристиян качи решение на 10.01.2022 15:12 (преди над 3 години)

+use std::io::Lines;
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::BufRead;
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Direction {
North,
South,
East,
West,
}
-/// парса низ до Direction
+/// парвса низ до Direction
fn from_str(s: &str) -> Result<Direction, Errors> {
match s {
"North" => Ok(Direction::North),
"South" => Ok(Direction::South),
"East" => Ok(Direction::East),
"West" => Ok(Direction::West),
_ => Err(Errors::DirectionParseError(s.to_string())),
}
}
/// връща обратната посока на подадената като параметър
fn opposite(direction: Direction) -> Direction {
match direction {
Direction::North => Direction::South,
Direction::South => Direction::North,
Direction::East => Direction::West,
Direction::West => Direction::East,
}
}
/// Проверява дали даден низ input започва с низ prefix
pub fn match_prefix<'a, 'b>(prefix: &'a str, input: &'b str) -> Option<&'b str> {
if input.len() >= 2 && prefix == &input[0..2] {
Some(&input[2..])
} else {
None
}
}
/// проверява дали низът link е във формата "- <име на стая> -> <посока> -> <име на друга стая>"
pub fn check_link_format(link: String, num_of_line: usize) -> Result<(String, Direction, String), Errors> {
let vec_chars: Vec<char> = link.chars().collect();
let mut vec_arrow_pos: Vec<usize> = Vec::new();
let mut i = 0;
let len = vec_chars.len();
while i < len {
if vec_chars[i] == '-' && i < len-1 && vec_chars[i+1] == '>' {
vec_arrow_pos.push(i);
}
i += 1;
}
if vec_arrow_pos.len() != 2 {
return Err(Errors::LineParseError{ line_number: num_of_line });
}
let name_size = vec_arrow_pos[0] - 1;
let dir_begin = vec_arrow_pos[0] + 3;
let dir_size = (vec_arrow_pos[1] - 1) - dir_begin;
let other_name_begin = vec_arrow_pos[1] + 3;
if other_name_begin >= link.len() {
return Err(Errors::LineParseError{ line_number: num_of_line });
}
let room_name: String = link.chars().into_iter().take(name_size).collect();
let dir_str: String = link.chars().into_iter().skip(dir_begin).take(dir_size).collect();
let direction = from_str(&dir_str)?;
let other_room_name: String = link.chars().into_iter().skip(other_name_begin).collect();
Ok((room_name, direction, other_room_name))
}
pub struct Room {
pub name: String,
pub neighbours: HashMap<Direction, String>,
}
pub struct Dungeon {
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 name_str = String::from(name);
if self.rooms.contains_key(&name_str) {
Err(Errors::DuplicateRoom(name_str))
} else {
let new_room = Room {
name: name_str.clone(),
neighbours: HashMap::new(),
};
self.rooms.insert(name_str, new_room);
Ok(())
}
}
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let room_name_str = String::from(room_name);
if self.rooms.contains_key(&room_name_str) {
Ok(self.rooms.get(&room_name_str).unwrap())
} else {
Err(Errors::UnknownRoom(room_name_str))
}
}
pub fn set_link(
&mut self,
room_name: &str,
direction: Direction,
other_room_name: &str,
) -> Result<(), Errors> {
let room_name_str = String::from(room_name);
let other_room_name_str = String::from(other_room_name);
if !self.rooms.contains_key(&room_name_str) {
Err(Errors::UnknownRoom(room_name_str))
} else if !self.rooms.contains_key(&other_room_name_str) {
Err(Errors::UnknownRoom(other_room_name_str))
} else {
let first_room = self.rooms.get_mut(&room_name_str).unwrap();
first_room.neighbours.insert(direction, other_room_name_str.clone());
let second_room = self.rooms.get_mut(&other_room_name_str).unwrap();
second_room.neighbours.insert(opposite(direction), room_name_str.clone());
Ok(())
}
}
pub fn get_next_room(&self, room_name: &str, direction: Direction) -> Result<Option<&Room>, Errors> {
let room_name_str = String::from(room_name);
if !self.rooms.contains_key(&room_name_str) {
Err(Errors::UnknownRoom(room_name_str))
} else {
let room = self.rooms.get(&room_name_str).unwrap();
let next_room_name = room.neighbours.get(&direction);
if let Some(s) = next_room_name {
// Стаята има съсед в посока direction
Ok(self.rooms.get(s))
} else {
// Няма съсед
Ok(None)
}
}
}
/// добавя стаите от файла(или друг поток от байтове) параметър на ф-ята from_reader(...)
- fn add_rooms_from_reader<L: Iterator<Item = String>>(&mut self, lines_iter: &mut L) -> Result<usize, Errors> {
+ fn add_rooms_from_reader<B: BufRead>(&mut self, lines_iter: &mut Lines<B>) -> Result<usize, Errors> {
let mut num_of_line: usize = 1;
while let Some(line) = lines_iter.next() {
num_of_line += 1;
- if let Some(room_name) = match_prefix("- ", &line) {
+ let line_str = match line {
+ Err(e) => return Err(Errors::IoError(e)),
+ Ok(l) => l,
+ };
+
+ if let Some(room_name) = match_prefix("- ", &line_str) {
// формата на реда е за нова стая, значи добавяме стаята
let _ = self.add_room(room_name)?;
- } else if line == "" {
+ } else if line_str == "" {
// приключваме с добавянето на стаи, връщаме номера на реда
return Ok(num_of_line);
} else {
// грешен формат и не е нов ред
return Err(Errors::LineParseError{ line_number: num_of_line });
}
}
Ok(num_of_line)
}
/// добавя връзките от файла(или друг поток от байтове) параметър на ф-ята from_reader(...)
- fn add_links_from_reader<L: Iterator<Item = String>>(
+ fn add_links_from_reader<B: BufRead>(
&mut self,
- lines_iter: &mut L,
+ lines_iter: &mut Lines<B>,
num: usize
) -> Result<(), Errors> {
let mut num_of_line = num;
while let Some(line) = lines_iter.next() {
num_of_line += 1;
+
+ let line_str = match line {
+ Err(e) => return Err(Errors::IoError(e)),
+ Ok(l) => l,
+ };
- if let Some(link) = match_prefix("- ", &line) {
+ if let Some(link) = match_prefix("- ", &line_str) {
// формата на реда започва с "- "
// сега трябва да проверим останалата част дали е "room -> direction -> room"
let (room_name, direction, other_room_name) = check_link_format(link.to_string(), num_of_line)?;
// добавяме връзката
let _ = self.set_link(&room_name, direction, &other_room_name)?;
} else {
// грешен формат
return Err(Errors::LineParseError{ line_number: num_of_line });
}
}
Ok(())
}
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut dungeon = Dungeon::new();
let mut num_of_line;
- let mut lines_iter = reader.lines().map(|l| l.unwrap());
+ let mut lines_iter = reader.lines();
let line = lines_iter.next();
if line.is_none() {
return Err(Errors::LineParseError{ line_number: 0 });
- } else if line.unwrap() == "## Rooms" {
+ }
+ let line_str = match line.unwrap() {
+ Err(e) => return Err(Errors::IoError(e)),
+ Ok(l) => l,
+ };
+ if line_str == "## Rooms" {
num_of_line = dungeon.add_rooms_from_reader(&mut lines_iter)?;
} else {
return Err(Errors::LineParseError{ line_number: 1 });
}
let line = lines_iter.next();
num_of_line += 1;
- if line.is_some() && line.unwrap() == "## Links" {
+ if line.is_none() {
+ return Err(Errors::LineParseError{ line_number: num_of_line });
+ }
+ let line_str = match line.unwrap() {
+ Err(e) => return Err(Errors::IoError(e)),
+ Ok(l) => l,
+ };
+ if line_str == "## Links" {
let _ = dungeon.add_links_from_reader(&mut lines_iter, num_of_line)?;
} else {
return Err(Errors::LineParseError{ line_number: num_of_line });
}
+
Ok(dungeon)
}
/// построява пътя от структурата parents
fn build_path(
&self,
start_room_name: &str,
end_room_name: &str,
parents: HashMap<String, String>) -> Vec<&Room> {
let mut path: Vec<&Room> = Vec::new();
let mut curr_name = end_room_name;
while parents.contains_key(curr_name) {
let curr_room = self.get_room(curr_name).unwrap();
path.insert(0, curr_room);
curr_name = parents.get(curr_name).unwrap();
}
path.insert(0, self.get_room(start_room_name).unwrap());
path
}
pub fn find_path(
&self,
start_room_name: &str,
end_room_name: &str
) -> Result<Option<Vec<&Room>>, Errors> {
if self.get_room(&start_room_name).is_err() {
return Err(Errors::UnknownRoom(start_room_name.to_string()));
}
if self.get_room(&end_room_name).is_err() {
return Err(Errors::UnknownRoom(end_room_name.to_string()));
}
if start_room_name == end_room_name {
return Ok(Some(vec![self.get_room(start_room_name).unwrap()]));
}
// bfs
let mut visited: HashSet<String> = HashSet::new();
let mut queue: VecDeque<&Room> = VecDeque::new();
let mut parents: HashMap<String, String> = HashMap::new();
visited.insert(start_room_name.to_string());
queue.push_back(self.get_room(&start_room_name).unwrap());
while !queue.is_empty() {
let u = queue.pop_front().unwrap();
println!("curr room: {}", u.name);
let neighbour_vec: Vec<&String> = u.neighbours.values().collect();
for v_name in neighbour_vec {
if !visited.contains(v_name) {
visited.insert(v_name.clone());
parents.insert(v_name.clone(), u.name.clone());
queue.push_back(self.get_room(v_name).unwrap());
}
}
}
if !parents.contains_key(&end_room_name.to_string()) {
return Ok(None);
}
Ok(Some(self.build_path(start_room_name, end_room_name, parents)))
}
}