Search

Предадени решения

Краен срок:
05.01.2018 17:00
Точки:
15

Срокът за предаване на решения е отминал

extern crate solution;
use self::solution::*;
macro_rules! set {
($($item:expr),*) => {
{
let mut hash_set = ::std::collections::HashSet::new();
$( hash_set.insert($item); );*
hash_set
}
};
}
#[test]
fn test_extract_words_basic() {
let words = extract_words("The <cat> is (in the) </bag>");
assert_eq!(vec!["The", "cat", "is", "in", "the", "bag"], words);
let text = String::from("The <cat> is (in the) </bag>");
let words = extract_words(&text);
assert_eq!(vec!["The", "cat", "is", "in", "the", "bag"], words);
}
#[test]
fn test_extract_words_extra() {
let words = extract_words("Кво стаа, Пешо?");
assert_eq!(vec!["Кво", "стаа", "Пешо"], words);
let text = String::from("Кво стаа, Пешо?");
let words = extract_words(&text);
assert_eq!(vec!["Кво", "стаа", "Пешо"], words);
let words = extract_words(" *-~spaces~-* in <<<places>>> ");
assert_eq!(vec!["spaces", "in", "places"], words);
let words = extract_words("");
assert_eq!(Vec::<String>::new(), words);
}
#[test]
fn test_search_word() {
let mut index = TextIndex::new();
index.push("one, two, three");
index.push("two, neon");
index.push("one/five/six");
index.push("five, six, seven");
assert_eq!(set!{"one/five/six", "one, two, three"}, index.search("one"));
assert_eq!(set!{"five, six, seven", "one/five/six"}, index.search("six"));
}
#[test]
fn test_search_multiple_words() {
let mut index = TextIndex::new();
index.push("one, two");
index.push("two, three");
index.push("four, five");
assert_eq!(set!{"four, five", "one, two"}, index.search("one + four"));
}
#[test]
fn test_search_special_cases() {
let mut index = TextIndex::new();
index.push("one, two");
index.push("two, three");
index.push("two, three");
index.push("");
assert_eq!(set!{"one, two", "two, three"}, index.search(" two, two "));
}

First things first: вижте guide-а за предаване на домашни! Дори да сте го гледали преди, може да има нови неща в него. Бъдете сигурни, че решението ви поне се компилира с базовия тест, иначе ще получите 0 точки.

Тази задача имплементира силно опростен search index. Като за начало, искаме да имплементирате една помощна функция:

pub fn extract_words(text: &str) -> Vec<String> {
    // ...
}

Тази функция ще приеме string slice, и ще върне вектор от думите в низа, в правилния ред. "Дума" дефинираме като поредица от символи, за които char::is_alphabetic връща истина. Пример:

extract_words("one + TWO = три") //=> vec!["one", "TWO", "три"]

После, дефинираме структура, която изглежда така:

use std::collections::HashSet;

pub struct TextIndex {
    // ...
}

impl TextIndex {
    pub fn new() -> Self {
        // ...
    }

    pub fn push(&mut self, text: &str) {
        // ...
    }

    pub fn search(&self, query: &str) -> HashSet<&str> {
        // ...
    }
}

Метода push приема string slice, и го индексира по някакъв начин, какъвто вие си решите. Метода search след това търси в индексираните низове за заявка, която се разбива по думи. Тоест:

let mut index = TextIndex::new();
index.push("one, two");
index.push("three, four");

index.search("one, three") // => HashSet{"one, two", "three, four"}

Забележете, че очакваме заявката да се разбие по думи с горната помощна функция, и за всяка дума търсим всички индексирани низове, които я включват. Тоест, OR-ваме резултатите от търсенето на думите. Търсенето на "one, three" води до търсене по думите "one" и "three", и резултата е комбинацията от търсенията на тези две думи.

Думите се сравняват, правейки разлика между малки и големи. Тоест, "one" и "One" се считат за различни думи.

Това не е ли много лесно?

Надяваме се! Едно драматично просто решение на "индексирането" е просто да набутате всички низове идващи от push в един вектор или HashSet, и после за всяка дума да търсите резултатите един по един, използвайки str::contains. Разбиването на думи също може да се направи доста простичко, предвид, че метода връща вектор (от String-ове даже! Толкова неефективно!).

Напълно е ок да имплементирате решението по този начин, да си изкарате 15 точки, и да си почивате по време на празниците.

В случай, обаче, че:

  • имате да компенсирате точки, или
  • искате да упражните някои неща, или
  • просто ви се пише rust код, щото езика e толкова як!

... бихте могли да положите маалко повече усилие и да изкарате бонус точки.

Допълнителни (незадължителни) условия

Ще получите 1 бонус точка, ако имплементирате разбиването на думи с ефективен итератор. Потенциална дефиниция би изглеждала така:

// Опционално
struct WordIterator<'a> {
    // ...
}

// Опционално
impl<'a> WordIterator<'a> {
    pub fn new(text: &'a str) -> Self {
        // ...
    }
}

// Опционално
impl<'a> Iterator for WordIterator<'a> {
    type Item = &'a str;

    fn next(&mut self) -> Option<Self::Item> {
        // ...
    }
}

При това положение, функцията за извличане на думи би инстанцирала един итератор от текста и би изглеждала (примерно) така: WordIterator::new(text).map(String::from).collect().

Забележете, че очакваме един смислен итератор да връща &str-та, тоест, да не алокира допълнителна памет, а да връща slice-ове от оригиналния низ. Разбира се, като викнем итератора в extract_words, все пак алокираме низове, но поне ще се чувствате доволни, че имате, потенциално, начин да циклите ефективно по думи, без излишна алокация.

Ще получите още 1 бонус точка ако имплементирате някакъв по-ефективен word search. Даваме ви свобода да си направите някакво дърво или whatever, но бихме били напълно доволни (така сме го имплементирали ние) и на едно простичко HashMap<String, HashSet<Rc<String>>>-че. При тази структура, всяка дума би сочила към HashSet от низовете, които я съдържат. Rc-та от тях, разбира се, понеже не искаме да копираме всички тия низове.

Стига да направите и двете бонус условия, ще получите още 1 бонус точка, докарвайки ви до цели 3.

Проверка на бонус условията

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

В случай, че решите да имплементирате нещо различно, което е по-ефективно, by all means направете го, стига да минавате нормалните тестове. Ако имплементирате ефективно решение, което има различен интерфейс, няма да минат тестовете (най-вероятно програмата няма да се компилира).

Задължително прочетете (или си припомнете): Указания за предаване на домашни