Решение на Dungeons and Compilers от Иван-Асен Чакъров

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

Към профила на Иван-Асен Чакъров

Код

use std::collections::HashMap;

use std::collections::HashSet;

use std::collections::VecDeque;

use std::io::stdin;

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),

}

/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait

/// имплементации, за да си улесните живота.

///

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]

pub enum Direction {

North,

South,

East,

West,

}

impl FromStr for Direction {

type Err = Errors;

fn from_str(input: &str) -> Result<Direction, Self::Err> {

match input {

"North" => Ok(Direction::North),

"South" => Ok(Direction::South),

"East" => Ok(Direction::East),

"West" => Ok(Direction::West),

_ => Err(Errors::DirectionParseError(input.to_string())),

}

}

}

impl Direction {

fn opposite(&self) -> Self {

match self {

Self::North => Self::South,

Self::South => Self::North,

Self::East => Self::West,

Self::West => Self::East,

}

}

}

/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да

/// държи item-и, противници...

///

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]

pub struct Room {

pub name: String,

// Каквито други полета ви трябват

}

/// Контейнер за стаите и не само. Ще работим предимно със тази структура.

///

pub struct Dungeon {

// Каквито полета ви трябват

rooms: HashMap<Room, HashMap<Direction, 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> {

let key = Room {

name: name.to_string(),

};

match self.rooms.get(&key) {

Some(_) => Err(Errors::DuplicateRoom(name.to_string())),

None => {

self.rooms.insert(key, HashMap::new());

Ok(())

}

}

}

/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`

/// структурата с това име.

///

/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.

///

pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {

let key = Room {

name: room_name.to_string(),

};

match self.rooms.get_key_value(&key) {

Some((result, _)) => Ok(result),

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 let Err(err) = self.get_room(room_name) {

return Err(err);

}

if let Err(err) = self.get_room(other_room_name) {

return Err(err);

}

let opposite = direction.opposite();

let room = &Room {

name: room_name.to_string(),

};

let other_room = &Room {

name: other_room_name.to_string(),

};

match self.rooms[room].get(&direction) {

Some(neighbour) => {

let n = &Room {

name: neighbour.name.clone(),

};

self.rooms.get_mut(n).unwrap().remove(&opposite);

}

None => (),

};

match self.rooms[other_room].get(&opposite) {

Some(neighbour) => {

let n = &Room {

name: neighbour.name.clone(),

};

self.rooms.get_mut(n).unwrap().remove(&direction);

}

None => (),

};

match self.set_link_directed(room_name, direction, other_room_name) {

Ok(_) => {

let opposite = direction.opposite();

self.set_link_directed(other_room_name, opposite, room_name)

}

Err(errors) => Err(errors),

}

}

fn set_link_directed(

&mut self,

room_name: &str,

direction: Direction,

other_room_name: &str,

) -> Result<(), Errors> {

let room = Room {

name: room_name.to_string(),

};

let other_room = Room {

name: other_room_name.to_string(),

};

let neighbours = match self.rooms.get_mut(&room) {

Some(n) => n,

None => return Err(Errors::UnknownRoom(room_name.to_string())),

};

neighbours.insert(direction, other_room);

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: room_name.to_string(),

}) {

None => return Err(Errors::UnknownRoom(room_name.to_string())),

Some(neighbours) => return Ok(neighbours.get(&direction)),

}

}

/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е

/// файл, или, ако тестваме, може да е просто колекция от байтове.

///

/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.

///

/// Вижте по-долу за обяснение на грешките, които очакваме.

///

pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {

let lines = reader.lines();

let mut result = Dungeon::new();

enum State {

FirstPart,

Nodes,

SecondPart,

Edges,

}

let mut state = &State::FirstPart;

for (index, line_or_err) in lines.enumerate() {

let line: String = match line_or_err {

Ok(l) => l,

Err(e) => return Err(Errors::IoError(e)),

};

let line_number = index + 1;

match state {

State::FirstPart => {

if index == 0 && line == "## Rooms" {

state = &State::Nodes;

} else {

return Err(Errors::LineParseError {

line_number: line_number,

});

}

}

State::Nodes => {

if line == "" {

state = &State::SecondPart;

continue;

}

let mut chars = line.chars();

if chars.next().unwrap() != '-'

|| line.len() == 1

|| chars.next().unwrap() != ' '

{

return Err(Errors::LineParseError {

line_number: line_number,

});

}

let room_name = chars.as_str();

match result.add_room(room_name) {

Ok(_) => (),

Err(e) => return Err(e),

};

}

State::SecondPart => {

if line == "## Links" {

state = &State::Edges;

} else {

return Err(Errors::LineParseError {

line_number: line_number,

});

}

}

State::Edges => {

let mut chars = line.chars();

if line.is_empty()

|| chars.next().unwrap() != '-'

|| line.len() == 1

|| chars.next().unwrap() != ' '

{

return Err(Errors::LineParseError {

line_number: line_number,

});

}

let rest: &str = chars.as_str();

let parts = rest.split(" -> ").collect::<Vec<&str>>();

if parts.len() != 3 {

return Err(Errors::LineParseError {

line_number: line_number,

});

}

let room_name = parts[0];

let direction_str = parts[1];

let other_room_name = parts[2];

let direction = match Direction::from_str(direction_str) {

Ok(d) => d,

Err(err) => return Err(err),

};

match result.set_link(room_name, direction, other_room_name) {

Ok(_) => (),

Err(err) => return Err(err),

};

}

}

}

if let State::FirstPart = state {

return Err(Errors::LineParseError { line_number: 0 });

}

Ok(result)

}

/// Търси път от `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 start_room = match self.get_room(start_room_name) {

Ok(r) => r,

Err(err) => return Err(err),

};

let start = vec![start_room];

let mut visited = HashSet::new();

let mut q = VecDeque::new();

visited.insert(start_room_name.to_string());

q.push_back(start);

while !q.is_empty() {

let front = match q.pop_front() {

Some(f) => f,

None => return Ok(None),

};

let last = match front.last() {

Some(l) => l,

None => return Ok(None),

};

if last.name == end_room_name {

let clone = front.clone();

return Ok(Some(clone));

}

let neighbours = match self.rooms.get(last) {

Some(n) => n,

None => return Err(Errors::UnknownRoom(last.name.to_string())),

};

for (_, neighbour) in neighbours {

if !visited.contains(&neighbour.name) {

visited.insert(neighbour.name.clone());

let mut clone = front.clone();

clone.push(neighbour);

q.push_back(clone);

}

}

}

Ok(None)

}

}

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

Compiling solution v0.1.0 (/tmp/d20220116-3533338-14th22t/solution)
warning: unused import: `std::io::stdin`
 --> src/lib.rs:4:5
  |
4 | use std::io::stdin;
  |     ^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: `solution` (lib) generated 1 warning
    Finished test [unoptimized + debuginfo] target(s) in 4.08s
     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 ... FAILED
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_adding_rooms_2 stdout ----
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:99:78
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- solution_test::test_finding_no_path stdout ----
thread '<unnamed>' panicked at 'assertion failed: path.is_err()', tests/solution_test.rs:382:9
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:372:5


failures:
    solution_test::test_adding_rooms_2
    solution_test::test_finding_no_path

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'

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

Иван-Асен качи решение на 05.01.2022 13:50 (преди почти 4 години)

use std::collections::HashMap;

use std::collections::HashSet;

use std::collections::VecDeque;

use std::io::stdin;

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),

}

/// Четирите посоки, в които може една стая да има съседи. Може да добавите още trait

/// имплементации, за да си улесните живота.

///

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]

pub enum Direction {

North,

South,

East,

West,

}

impl FromStr for Direction {

type Err = Errors;

fn from_str(input: &str) -> Result<Direction, Self::Err> {

match input {

"North" => Ok(Direction::North),

"South" => Ok(Direction::South),

"East" => Ok(Direction::East),

"West" => Ok(Direction::West),

_ => Err(Errors::DirectionParseError(input.to_string())),

}

}

}

impl Direction {

fn opposite(&self) -> Self {

match self {

Self::North => Self::South,

Self::South => Self::North,

Self::East => Self::West,

Self::West => Self::East,

}

}

}

/// Една стая в подземията. Дефинира се само с име, макар че в по-интересна имплементация може да

/// държи item-и, противници...

///

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]

pub struct Room {

pub name: String,

// Каквито други полета ви трябват

}

/// Контейнер за стаите и не само. Ще работим предимно със тази структура.

///

pub struct Dungeon {

// Каквито полета ви трябват

rooms: HashMap<Room, HashMap<Direction, 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> {

let key = Room {

name: name.to_string(),

};

match self.rooms.get(&key) {

Some(_) => Err(Errors::DuplicateRoom(name.to_string())),

None => {

self.rooms.insert(key, HashMap::new());

Ok(())

}

}

}

/// Прочитане на дадена стая -- когато извикаме `get_room`, очакваме reference към `Room`

/// структурата с това име.

///

/// Ако няма такава стая, очакваме `Errors::UnknownRoom` с подаденото име.

///

pub fn get_room(&self, room_name: &str) -> Result<&Room, Errors> {

let key = Room {

name: room_name.to_string(),

};

match self.rooms.get_key_value(&key) {

Some((result, _)) => Ok(result),

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 let Err(err) = self.get_room(room_name) {

return Err(err);

}

if let Err(err) = self.get_room(other_room_name) {

return Err(err);

}

let opposite = direction.opposite();

let room = &Room {

name: room_name.to_string(),

};

let other_room = &Room {

name: other_room_name.to_string(),

};

match self.rooms[room].get(&direction) {

Some(neighbour) => {

let n = &Room {

name: neighbour.name.clone(),

};

self.rooms.get_mut(n).unwrap().remove(&opposite);

}

None => (),

};

match self.rooms[other_room].get(&opposite) {

Some(neighbour) => {

let n = &Room {

name: neighbour.name.clone(),

};

self.rooms.get_mut(n).unwrap().remove(&direction);

}

None => (),

};

match self.set_link_directed(room_name, direction, other_room_name) {

Ok(_) => {

let opposite = direction.opposite();

self.set_link_directed(other_room_name, opposite, room_name)

}

Err(errors) => Err(errors),

}

}

fn set_link_directed(

&mut self,

room_name: &str,

direction: Direction,

other_room_name: &str,

) -> Result<(), Errors> {

let room = Room {

name: room_name.to_string(),

};

let other_room = Room {

name: other_room_name.to_string(),

};

let neighbours = match self.rooms.get_mut(&room) {

Some(n) => n,

None => return Err(Errors::UnknownRoom(room_name.to_string())),

};

neighbours.insert(direction, other_room);

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: room_name.to_string(),

}) {

None => return Err(Errors::UnknownRoom(room_name.to_string())),

Some(neighbours) => return Ok(neighbours.get(&direction)),

}

}

/// Прочитаме структурата на dungeon от нещо, което имплементира `BufRead`. Това може да е

/// файл, или, ако тестваме, може да е просто колекция от байтове.

///

/// Успешен резултат връща новосъздадения dungeon, пакетиран в `Ok`.

///

/// Вижте по-долу за обяснение на грешките, които очакваме.

///

pub fn from_reader<B: BufRead>(reader: B) -> Result<Self, Errors> {

let lines = reader.lines();

let mut result = Dungeon::new();

enum State {

FirstPart,

Nodes,

SecondPart,

Edges,

}

let mut state = &State::FirstPart;

for (index, line_or_err) in lines.enumerate() {

let line: String = match line_or_err {

Ok(l) => l,

Err(e) => return Err(Errors::IoError(e)),

};

+ let line_number = index + 1;

match state {

State::FirstPart => {

if index == 0 && line == "## Rooms" {

state = &State::Nodes;

} else {

- return Err(Errors::LineParseError { line_number: index });

+ return Err(Errors::LineParseError {

+ line_number: line_number,

+ });

}

}

State::Nodes => {

if line == "" {

state = &State::SecondPart;

continue;

}

let mut chars = line.chars();

- if chars.next().unwrap() != '-' {

- return Err(Errors::LineParseError { line_number: index });

+ if chars.next().unwrap() != '-'

+ || line.len() == 1

+ || chars.next().unwrap() != ' '

+ {

+ return Err(Errors::LineParseError {

+ line_number: line_number,

+ });

}

- let rest: &str = chars.as_str();

- let room_name = rest.trim();

+ let room_name = chars.as_str();

match result.add_room(room_name) {

Ok(_) => (),

Err(e) => return Err(e),

};

}

State::SecondPart => {

if line == "## Links" {

state = &State::Edges;

} else {

- return Err(Errors::LineParseError { line_number: index });

+ return Err(Errors::LineParseError {

+ line_number: line_number,

+ });

}

}

State::Edges => {

let mut chars = line.chars();

- if line.is_empty() || chars.next().unwrap() != '-' {

- return Err(Errors::LineParseError { line_number: index });

+ if line.is_empty()

+ || chars.next().unwrap() != '-'

+ || line.len() == 1

+ || chars.next().unwrap() != ' '

+ {

+ return Err(Errors::LineParseError {

+ line_number: line_number,

+ });

}

let rest: &str = chars.as_str();

- let parts = rest.split("->").collect::<Vec<&str>>();

+ let parts = rest.split(" -> ").collect::<Vec<&str>>();

if parts.len() != 3 {

- return Err(Errors::LineParseError { line_number: index });

+ return Err(Errors::LineParseError {

+ line_number: line_number,

+ });

}

- let room_name = parts[0].trim();

- let direction_str = parts[1].trim();

- let other_room_name = parts[2].trim();

+ let room_name = parts[0];

+ let direction_str = parts[1];

+ let other_room_name = parts[2];

let direction = match Direction::from_str(direction_str) {

Ok(d) => d,

Err(err) => return Err(err),

};

match result.set_link(room_name, direction, other_room_name) {

Ok(_) => (),

Err(err) => return Err(err),

};

}

}

}

+ if let State::FirstPart = state {

+ return Err(Errors::LineParseError { line_number: 0 });

+ }

+

Ok(result)

}

/// Търси път от `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 start_room = match self.get_room(start_room_name) {

Ok(r) => r,

Err(err) => return Err(err),

};

let start = vec![start_room];

let mut visited = HashSet::new();

let mut q = VecDeque::new();

visited.insert(start_room_name.to_string());

q.push_back(start);

while !q.is_empty() {

let front = match q.pop_front() {

Some(f) => f,

None => return Ok(None),

};

let last = match front.last() {

Some(l) => l,

None => return Ok(None),

};

if last.name == end_room_name {

let clone = front.clone();

return Ok(Some(clone));

}

let neighbours = match self.rooms.get(last) {

Some(n) => n,

None => return Err(Errors::UnknownRoom(last.name.to_string())),

};

for (_, neighbour) in neighbours {

if !visited.contains(&neighbour.name) {

visited.insert(neighbour.name.clone());

let mut clone = front.clone();

clone.push(neighbour);

q.push_back(clone);

}

}

}

Ok(None)

}

-}

+}