Решение на Dungeons and Compilers от Никола Кралев
Резултати
- 20 точки от тестове
- 0 бонус точки
- 20 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
//#![allow(unused_variables)]
#![allow(dead_code)]
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(non_camel_case_types)]
use std::collections::HashMap;
use std::collections::VecDeque;
use std::io::BufRead;
type v = usize; //vertex integer ID type
/// Различните грешки, които ще очакваме да върнете като резултат от някои невалидни операции.
/// Повече детайли по-долу.
///
#[derive(Debug)]
pub enum Errors {
DuplicateRoom(String),
UnknownRoom(String),
IoError(std::io::Error),
LineParseError { line_number: usize },
DirectionParseError(String),
}
/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait
/// имплементации, за да си улесните живота.
///
#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
pub enum Direction {
North,
South,
East,
West,
}
impl Direction {
pub fn getOpposite(&self) -> Direction {
match *self {
Direction::North => {
return Direction::South;
}
Direction::South => {
return Direction::North;
}
Direction::East => {
return Direction::West;
}
Direction::West => {
return Direction::East;
}
}
}
}
/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да
/// държи item-и, противници...
///
#[derive(Debug)]
pub struct Room {
pub name: String,
// Каквито други полета ви трябват
}
impl Room {
pub fn new(name: String) -> Room {
let result = Room { name: name };
return result;
}
pub fn getName(&self) -> String {
return String::clone(&self.name);
}
}
#[derive(Debug)]
struct InputValidator {}
impl InputValidator {
pub fn new() -> InputValidator {
let result = InputValidator {};
return result;
}
pub fn isRoomHeader(&self, line: &String) -> bool {
return line.as_str() == "## Rooms";
}
pub fn isRoomLine(&self, line: &String, roomName: &mut String) -> bool {
let pieces: Vec<&str> = line.as_str().split("->").collect();
if pieces.len() != 1 {
return false;
}
let mut elem = pieces[0];
let prefix = "- ";
if !(elem.starts_with(prefix)) {
return false;
}
elem = &elem.strip_prefix(prefix).unwrap();
elem = &elem.trim();
if elem.len() == 0 {
return false;
}
*roomName = String::from(elem);
return true;
}
pub fn isEmptyLineInMiddle(&self, line: &String) -> bool {
return line.as_str() == "";
}
pub fn isLinkHeader(&self, line: &String) -> bool {
return line.as_str() == "## Links";
}
pub fn isLinkLine(
&self,
line: &String,
roomNameFrom: &mut String,
direction: &mut String,
roomNameTo: &mut String,
) -> bool {
let mut pieces: Vec<&str> = line.as_str().split(" -> ").collect();
if pieces.len() != 3 {
return false;
}
//remove the leading "- "
let prefix = "- ";
if !(pieces[0].starts_with(&prefix)) {
return false;
}
pieces[0] = pieces[0].strip_prefix(&prefix).unwrap();
for piece in &mut pieces {
if piece.contains("->") {
return false;
}
*piece = piece.trim();
if piece.len() == 0_usize {
return false;
}
}
*roomNameFrom = String::from(pieces[0]);
*direction = String::from(pieces[1]);
*roomNameTo = String::from(pieces[2]);
return true;
}
pub fn isDirection(&self, line: &String, direction: &mut Direction) -> bool {
match line.as_str() {
"North" => {
*direction = Direction::North;
return true;
}
"South" => {
*direction = Direction::South;
return true;
}
"East" => {
*direction = Direction::East;
return true;
}
"West" => {
*direction = Direction::West;
return true;
}
_ => {
return false;
}
}
}
}
/// Контейнер за стаите и не само. Ще работим предимно със тази структура.
///
#[derive(Debug)]
pub struct Dungeon {
validator: InputValidator,
graph: Vec<HashMap<Direction, v>>, //graph[i] gives the links and the destinations for vertex with id i
roomIds: HashMap<String, v>, // roomIds["Hall"] will reveal the id of the room with name "Hall", from 0 to n-1
rooms: HashMap<v, Room>, // the raw state of each existing room, accessed by room name
}
impl Dungeon {
/// Конструиране на празен Dungeon, в който няма никакви стаи.
///
pub fn new() -> Self {
let result = Dungeon {
validator: InputValidator::new(),
graph: vec![],
roomIds: HashMap::new(),
rooms: HashMap::new(),
};
return result;
}
/// Добавяне на стая към Dungeon с име `name`. Връща `Ok(())` при успех. Ако вече има стая с
/// такова име, очакваме да върнете `Errors::DuplicateRoom` с името.
///
pub fn add_room(&mut self, name: &str) -> Result<(), Errors> {
if self.roomIds.contains_key(name) {
return Err(Errors::DuplicateRoom(
"Failed to add room with name: ".to_owned() + name,
));
}
let nameStr = String::from(name);
let id = self.roomIds.len();
let roomObj = Room::new(String::clone(&nameStr));
self.roomIds.insert(String::clone(&nameStr), id);
self.rooms.insert(id, roomObj);
self.graph.push(HashMap::new());
return Ok(());
}
/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`
/// структурата с това име.
///
/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.
///
pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {
let roomIdOpt = self.roomIds.get(room_name);
match roomIdOpt {
Some(id) => {
return Ok(&self.rooms[id]);
}
None => {
return Err(Errors::UnknownRoom(
"Failed to get room with name: ".to_owned() + room_name,
));
}
}
}
/// Добавяне на съсед на дадена стая. След извикването на функцията, очакваме стаята с име
/// `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 roomIdOpt = self.roomIds.get(room_name);
if roomIdOpt.is_none() {
return Err(Errors::UnknownRoom(
"Failed to make link from room with name: ".to_owned() + room_name,
));
}
let roomIdStart = *roomIdOpt.unwrap();
let otherRoomIdOpt = self.roomIds.get(other_room_name);
if otherRoomIdOpt.is_none() {
return Err(Errors::UnknownRoom(
"Failed to make link to room with name: ".to_owned() + other_room_name,
));
}
let roomIdEnd = *otherRoomIdOpt.unwrap();
//override any existing links, both ways
self.graph[roomIdStart].insert(direction, roomIdEnd);
self.graph[roomIdEnd].insert(direction.getOpposite(), roomIdStart);
return 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 roomIdOpt = self.roomIds.get(room_name);
if roomIdOpt.is_none() {
return Err(Errors::UnknownRoom(
"Failed to get next from room with name: ".to_owned() + room_name,
));
}
let roomStartId = *roomIdOpt.unwrap();
let targetRoomIdOpt = self.graph[roomStartId].get(&direction);
if targetRoomIdOpt.is_none() {
return Ok(None);
}
let targetRoomId = targetRoomIdOpt.unwrap();
let targetRoom = &self.rooms[targetRoomId];
return Ok(Some(&targetRoom));
}
/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е
/// файл, или, ако тестваме, може да е просто колекция от байтове.
///
/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.
///
/// Вижте по-долу за обяснение на грешките, които очакваме.
///
pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {
let mut roomHeaderParsed = false;
let mut emptyMidLineParsed = false;
let mut linkHeaderParsed = false;
let mut currentLineNumber = 0 as v;
let mut resultDungeon = Dungeon::new();
for lineResult in reader.lines() {
let lineStr;
match lineResult {
Err(e) => {
return Err(Errors::IoError(e));
}
Ok(s) => {
lineStr = s;
}
}
currentLineNumber += 1;
if !roomHeaderParsed {
if resultDungeon.validator.isRoomHeader(&lineStr) {
roomHeaderParsed = true;
continue;
} else {
return Err(Errors::LineParseError {
line_number: currentLineNumber,
});
}
}
if !emptyMidLineParsed {
if resultDungeon.validator.isEmptyLineInMiddle(&lineStr) {
emptyMidLineParsed = true;
continue;
} else {
let mut roomName = String::new();
if resultDungeon.validator.isRoomLine(&lineStr, &mut roomName) {
let roomAddingResult = resultDungeon.add_room(&roomName);
match roomAddingResult {
Ok(_) => {
continue;
}
Err(x) => {
return Err(x);
}
}
} else {
return Err(Errors::LineParseError {
line_number: currentLineNumber,
});
}
}
}
if !linkHeaderParsed {
if resultDungeon.validator.isLinkHeader(&lineStr) {
linkHeaderParsed = true;
continue;
} else {
return Err(Errors::LineParseError {
line_number: currentLineNumber,
});
}
}
let mut roomNameFrom = String::new();
let mut directionStr = String::new();
let mut roomNameTo = String::new();
if resultDungeon.validator.isLinkLine(
&lineStr,
&mut roomNameFrom,
&mut directionStr,
&mut roomNameTo,
) {
let mut direction = Direction::North;
if !resultDungeon
.validator
.isDirection(&directionStr, &mut direction)
{
return Err(Errors::DirectionParseError(directionStr));
}
let setLinkResult =
resultDungeon.set_link(roomNameFrom.as_str(), direction, roomNameTo.as_str());
match setLinkResult {
Ok(_) => {
continue;
}
Err(x) => {
return Err(x);
}
}
} else {
return Err(Errors::LineParseError {
line_number: currentLineNumber,
});
}
}
if currentLineNumber == 0 as v {
return Err(Errors::LineParseError {
line_number: currentLineNumber,
});
}
return Ok(resultDungeon);
}
/// Търси път от `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> {
// BFS
let idStart: v;
let idStartRoomOpt = self.roomIds.get(start_room_name);
match idStartRoomOpt {
Some(id) => {
idStart = *id;
}
None => {
return Err(Errors::UnknownRoom(
"Failed to find path from ".to_owned() + start_room_name,
));
}
}
let idEnd: v;
let idEndRoomOpt = self.roomIds.get(end_room_name);
match idEndRoomOpt {
Some(id) => {
idEnd = *id;
}
None => {
return Err(Errors::UnknownRoom(
"Failed to find path to ".to_owned() + end_room_name,
));
}
}
if idStart == idEnd {
return Ok(Some(vec![&(self.rooms[&idStart])]));
}
let mut isVisited = Vec::<bool>::with_capacity(self.roomIds.len());
for _i in 0_usize..self.roomIds.len() {
isVisited.push(false);
}
let mut q = VecDeque::<v>::new();
isVisited[idStart] = true;
q.push_back(idStart);
//backtrackMap[r1] = r2 shows that we reached r1 for the first time from r2
let mut backtrackMap = HashMap::<v, v>::new();
backtrackMap.insert(idStart, idStart);
let mut currentId: v = idStart;
let mut neighbourId: v;
while q.len() != 0 {
currentId = q.pop_front().unwrap();
if currentId == idEnd {
break;
}
let neighbours: &HashMap<Direction, v> = &(self.graph[currentId]);
for currentNeighbour in neighbours {
//ignore the direction
neighbourId = *(currentNeighbour).1;
if !isVisited[neighbourId] {
isVisited[neighbourId] = true;
backtrackMap.insert(neighbourId, currentId);
q.push_back(neighbourId);
}
}
}
//reconstruct the result
if currentId != idEnd {
//no path found
return Ok(None);
}
let mut roomIds: Vec<v> = Vec::<v>::with_capacity(backtrackMap.len());
roomIds.push(idEnd);
currentId = backtrackMap[roomIds.last().unwrap()];
while currentId != *(roomIds.last().unwrap()) {
roomIds.push(currentId);
currentId = backtrackMap[¤tId];
}
roomIds.reverse();
let mut result: Vec<&Room> = Vec::<&Room>::with_capacity(roomIds.len());
for i in &roomIds {
result.push(&self.rooms[i]);
}
return Ok(Some(result));
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20220116-3533338-14kdijh/solution)
Finished test [unoptimized + debuginfo] target(s) in 3.90s
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