Използване на Option като итератор

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

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

Trigrams

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

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

extern crate solution;
use self::solution::*;
#[test]
fn test_trigram_iterator() {
let trigrams = TrigramIterator::new("cat").collect::<Vec<String>>();
assert_eq!(trigrams, vec![" c", " ca", "cat", "at "]);
let trigrams = TrigramIterator::new(&String::from("cat")).collect::<Vec<String>>();
assert_eq!(trigrams, vec![" c", " ca", "cat", "at "]);
let trigrams = TrigramIterator::new("баба").collect::<Vec<String>>();
assert_eq!(trigrams, vec![" б", " ба", "баб", "аба", "ба "]);
}

Искаме да напишете итератор, който разбива една дума на триграми. Ето едно обяснение на това какво е "триграма", от postgresql документацията:

A trigram is a group of three consecutive characters taken from a string. We can measure the similarity of two strings by counting the number of trigrams they share. This simple idea turns out to be very effective for measuring the similarity of words in many natural languages.

Each word is considered to have two spaces prefixed and one space suffixed when determining the set of trigrams contained in the string. For example, the set of trigrams in the string "cat" is " c", " ca", "cat", and "at ".

Тоест, очакваме да генерирате всички поредици от три символа, които се намират в думата, която ви подаваме. Като специални случаи:

  • първата триграма е два интервала и първия символ, ако има първи символ (в горния пример -- " c")
  • вторатa триграма е един интервал и първите два символа, ако има поне два символа (в горния пример -- " ca")
  • последната триграма е последните два символа и интервал, ако има поне два символа (в горния пример -- "at ")

Тестовете ще се викат само с валидни думи (само char::is_alphabetic символи), само с малки букви, така че не се притеснявайте за специални символи или вътрешни интервали, и не мислете за case-sensitivity. Все пак, както винаги, мислете за edge cases.

Следва интерфейса, който очакваме. Забележете, че резултата, който се връща от next е String, а не &str -- заради интервалите в началото и края. Това значи, че, на теория, бихте могли да го имплементирате по сравнително лесен и неефективен начин. Бихме искали да не го правите, но не можахме да измислим начин да ви спрем :). Все пак бихме предпочели да итерирате максимално ефективно по низа, и се надяваме и вие да предпочитате същото.

// Lifetime-а е да ви стимулира да пазите някаква форма на reference към оригиналната дума. Може би
// &'a str, а може би Chars<'a>? Ако случайно не ви трябва, махнете си го.
//
pub struct TrigramIterator<'a> {
    // ...
}

impl<'a> TrigramIterator<'a> {
    pub fn new(word: &'a str) -> Self {
        // ...
    }
}

impl<'a> Iterator for TrigramIterator<'a> {
    type Item = String;

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

Решения

Андрей
  • Коректно
  • 1 успешни тест(а)
  • 0 неуспешни тест(а)
Андрей

use std::str::Chars;
pub struct TrigramIterator<'a> {
chars: Chars<'a>,
at_first_char: bool,
at_second_char: bool,
}
impl<'a> TrigramIterator<'a> {
pub fn new(word: &'a str) -> Self {
TrigramIterator {
chars: word.chars(),
at_first_char: true,
at_second_char: false,
}
}
}
impl<'a> Iterator for TrigramIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
if self.at_first_char {
self.at_first_char = false;
self.at_second_char = true;
return Some(format!(" {}", self.chars.clone().next()?));
}
if self.at_second_char {
self.at_second_char = false;
let mut next_chars = self.chars.clone();
return Some(format!(" {}{}", next_chars.next()?, next_chars.next()?));
}
let next_char = self.chars.next()?;
let mut next_chars = self.chars.clone();
Some(format!("{}{}{}", next_char, next_chars.next()?, next_chars.next().unwrap_or(' ')))
}
} 
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-1cmqdty/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 2.48 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Михаил Младенов
  • Коректно
  • 1 успешни тест(а)
  • 0 неуспешни тест(а)
Михаил Младенов

pub struct TrigramIterator<'a> {
iter: ::std::str::Chars<'a>,
// Пазим последните два символа, които сме видели. Всъщност тук със сигурност трябва
// да сложим поне още нещо освен този итератор, но компилатора така или иначе ще падне
// последното поле до 8 байта за да мачне алайнмънта на пойнтърите в Chars.
// Тази структура изглежда по малка от пийкъбъл версията (която върши по лоша рабта).
prev_char: u32,
prev_prev_char: u32,
// Сега като пробвах ми изкарва размера на Chars 10 байта, което е мега странно. Това
// не мога да си го обясня, може би не разбирам как работят примитивните типове в ръст
// на фундаментално ниво, но това някак си е объркващо in general.
// В сайта показва, че имплементацията na Chars е Iter<u8>, което се състои от два
// пойнтъра към u8 и за всеки от тях дава по 8 байта. Този размер от 10 байта не прави
// смисъл и от гледна точка на алайнмънт.
// Наистина нямам идея какво правя тук, но имам да пиша 3 проекта (и само този по Ръст
// е приятен за писане :(, за съжаление ще бъде тежка ваканция). Ще пробвам да разнищя
// нещата после ако остане време, може би изпускам нещо елементарно.
}
// Възползваме се от това, че не всички 32 битови числа са валидни коудпойнтове в юникод за
// да различаваме случаите, в които думата е приключила, думата е започнала итн...
const INVALID_UNICODE_CODEPOINT0: u32 = 0x0000FFFF;
const INVALID_UNICODE_CODEPOINT1: u32 = 0x0000FFFE;
impl<'a> TrigramIterator<'a> {
pub fn new(word: &'a str) -> Self {
TrigramIterator {
iter: word.chars(),
prev_char: INVALID_UNICODE_CODEPOINT0,
prev_prev_char: INVALID_UNICODE_CODEPOINT0,
}
}
}
impl<'a> Iterator for TrigramIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
let mut result = String::with_capacity(12);
match self.prev_char {
// Това значи, че сме на първа итерация
INVALID_UNICODE_CODEPOINT0 => {
match self.iter.next() {
None => None,
Some(c) => {
self.prev_char = c as u32;
result.push(' ');
result.push(' ');
result.push(c);
Some(result)
}
}
}
// Край на итерациите
INVALID_UNICODE_CODEPOINT1 => None,
_ => {
match self.prev_prev_char {
// Втора итерация
INVALID_UNICODE_CODEPOINT0 => {
match self.iter.next() {
None => None,
Some(c) => {
self.prev_prev_char = self.prev_char;
self.prev_char = c as u32;
result.push(' ');
// Знаем, че тази стойност сме я взели от някой чар и значи
// този "reinterpret_cast" трябва да е "безопасен".
unsafe {
result.push(::std::mem::transmute(self.prev_prev_char));
result.push(::std::mem::transmute(self.prev_char));
}
Some(result)
}
}
}
_ => {
match self.iter.next() {
None => {
unsafe {
result.push(::std::mem::transmute(self.prev_prev_char));
result.push(::std::mem::transmute(self.prev_char));
}
result.push(' ');
self.prev_char = INVALID_UNICODE_CODEPOINT1;
Some(result)
}
Some(c) => {
unsafe {
result.push(::std::mem::transmute(self.prev_prev_char));
result.push(::std::mem::transmute(self.prev_char));
}
result.push(c);
self.prev_prev_char = self.prev_char;
self.prev_char = c as u32;
Some(result)
}
}
}
}
}
}
}
} // Пак стана елха... :( 
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-1o098iz/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 2.79 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Николай Коцев
  • Некоректно
  • 0 успешни тест(а)
  • 1 неуспешни тест(а)
Николай Коцев

// Might not be the most elegant solution, but still should work
#[derive(Debug)]
pub struct TrigramIterator<'a> {
chars: std::str::Chars<'a>,
original_len: usize,
start: usize,
len: usize,
}
impl<'a> TrigramIterator<'a> {
const FINISHED_LEN: usize = 4;
pub fn new(word: &'a str) -> Self {
let chars_iter = word.chars();
let len = if word.is_empty() {
TrigramIterator::FINISHED_LEN
}
else {
1
};
TrigramIterator {
chars: chars_iter.clone(),
original_len: chars_iter.count(),
start: 0,
len: len
}
}
}
impl<'a> Iterator for TrigramIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
if self.len == TrigramIterator::FINISHED_LEN { return None }
let cloned_iterator = self.chars.clone();
let result = cloned_iterator.skip(self.start)
.take(self.len)
.collect::<String>();
if self.start + self.len > self.original_len {
self.len = TrigramIterator::FINISHED_LEN;
return None;
}
else if self.len < 3 && self.start == 0 {
self.len += 1;
}
else if self.len == 3 && self.start + self.len == self.original_len {
self.len -= 1;
self.start += 1;
}
else {
self.start += 1;
}
Some(result)
}
}
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-1jhw9p8/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 3.2 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... FAILED

failures:

---- solution_test::test_trigram_iterator stdout ----
	thread 'solution_test::test_trigram_iterator' panicked at 'assertion failed: `(left == right)`
  left: `["c", "ca", "cat", "at"]`,
 right: `["  c", " ca", "cat", "at "]`', tests/solution_test.rs:8:4
note: Run with `RUST_BACKTRACE=1` for a backtrace.


failures:
    solution_test::test_trigram_iterator

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--test solution_test'
Димитър Узунов
  • Коректно
  • 1 успешни тест(а)
  • 0 неуспешни тест(а)
Димитър Узунов

use std::str::Chars;
pub struct TrigramIterator<'a> {
chars: Chars<'a>,
first: char,
second: char,
}
impl<'a> TrigramIterator<'a> {
pub fn new(word: &'a str) -> Self {
TrigramIterator { chars: word.chars(), first: ' ', second: ' ' }
}
fn trigram(first: char, second: char, third: char) -> String {
let mut result = String::with_capacity(3);
result.push(first);
result.push(second);
result.push(third);
result
}
}
impl<'a> Iterator for TrigramIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
self.chars
.next()
.and_then(|third| {
let result = Self::trigram(self.first, self.second, third);
self.first = self.second;
self.second = third;
Some(result)
})
.or_else(|| {
if self.first != ' ' && self.second != ' ' {
let result = Self::trigram(self.first, self.second, ' ');
self.first = ' ';
Some(result)
} else {
None
}
})
}
}
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-hhk7ui/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 2.83 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Иван Иванов
  • Коректно
  • 1 успешни тест(а)
  • 0 неуспешни тест(а)
Иван Иванов

// First test passing the test.
pub struct TrigramIterator<'a> {
word: &'a str,
word_len: usize,
curr_pos: usize,
curr_word: String,
}
impl<'a> TrigramIterator<'a> {
pub fn new(word: &'a str) -> Self {
TrigramIterator{
word: word,
word_len: word.chars().count(),
curr_pos: 0,
curr_word: String::from(" "),
}
}
}
impl<'a> Iterator for TrigramIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
if self.word_len < self.curr_pos {
None
} else if self.word_len == self.curr_pos {
self.curr_word.push(' ');
self.curr_word.remove(0);
self.curr_pos = self.curr_pos + 1;
Some(self.curr_word.clone())
} else {
self.curr_word.push(self.word.chars().nth(self.curr_pos).unwrap());
self.curr_word.remove(0);
self.curr_pos = self.curr_pos + 1;
Some(self.curr_word.clone())
}
}
}
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-1qv2448/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 2.76 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Георги Божинов
  • Коректно
  • 1 успешни тест(а)
  • 0 неуспешни тест(а)
Георги Божинов

use std::rc::Rc;
pub struct TrigramIterator {
pub word: Rc<String>,
}
impl TrigramIterator {
pub fn new(word: &str) -> Self {
let new_word = TrigramIterator::add_spaces(word);
Self { word: Rc::from(new_word) }
}
fn add_spaces(word: &str) -> String {
format!(" {} ", word)
}
}
impl Iterator for TrigramIterator {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
let length = self.word.chars().count();
if length < 3 {
return None;
}
let word = Rc::clone(&self.word);
let chunk;
if length == 3 {
chunk = &*word.as_str();
} else {
chunk = &word[..word.char_indices().nth(3).unwrap().0];
}
self.word = Rc::new(
(&self.word[word.char_indices().nth(1).unwrap().0..]).to_owned(),
);
Some(chunk.to_owned())
}
}
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-1ekfofq/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 2.94 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Исмаил Алиджиков
  • Коректно
  • 1 успешни тест(а)
  • 0 неуспешни тест(а)
Исмаил Алиджиков

pub struct TrigramIterator {
word: Vec<char>,
index: usize,
}
impl TrigramIterator {
pub fn new(word: &str) -> Self {
TrigramIterator {
word: word.chars().collect(),
index: 0,
}
}
}
impl Iterator for TrigramIterator {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
let count = self.word.len();
if count == 0 || count + 1 <= self.index {
return None
}
let i = self.index;
let trigram = match i {
0 => {
format!(" {}", self.word[0])
},
1 => {
if count == 1 {
return None
}
format!(" {}{}", self.word[0], self.word[1])
},
j if (j == count) => {
format!("{}{} ", self.word[i-2], self.word[i-1])
},
_ => {
format!("{}{}{}", self.word[i-2], self.word[i-1], self.word[i])
},
};
self.index += 1;
Some(trigram)
}
} 
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-1s689wp/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 3.7 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Недялко Андреев
  • Коректно
  • 1 успешни тест(а)
  • 0 неуспешни тест(а)
Недялко Андреев

use std::str::Chars;
use std::iter::Chain;
// Доста неоптимално решение, но ми се играеше с итератори...
pub struct TrigramIterator<'a> {
c1: Chain<Chars<'a>, Chars<'a>>,
c2: Chain<Chars<'a>, Chars<'a>>,
c3: Chain<Chars<'a>, Chars<'a>>,
}
impl<'a> TrigramIterator<'a> {
pub fn new(word: &'a str) -> Self {
let tail = if word.chars().count() > 1 { " " } else { "" };
TrigramIterator {
c1: " ".chars().chain(word.chars()),
c2: " ".chars().chain(word.chars()),
c3: word.chars().chain(tail.chars()),
}
}
}
impl<'a> Iterator for TrigramIterator<'a> {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
match (self.c1.next(), self.c2.next(), self.c3.next()) {
(Some(c1), Some(c2), Some(c3)) => {
let mut result = String::with_capacity(3);
result.push(c1);
result.push(c2);
result.push(c3);
Some(result)
}
_ => None,
}
}
} 
Compiling solution v0.1.0 (file:///tmp/d20180105-6053-19bly65/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 2.85 secs
     Running target/debug/deps/solution-3f98bfa5c86a5dd9

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-3d9e4ea2eafbbc82

running 1 test
test solution_test::test_trigram_iterator ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out