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

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

Решение на Bigint от Антонина Ускова

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

Към профила на Антонина Ускова

Резултати

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

Код

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
// Little-endian-like representation of the number.
digits: Vec<u8>,
}
impl Bigint{
pub fn new() -> Self {
Bigint {
sign: 1,
digits: Vec::new(),
}
}
/// Конструира нов Bigint с подадените цифри и знак.
///
/// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
/// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
/// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
///
/// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
/// изтриете.
///
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
Bigint { digits, sign }
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
println!("{:?}", self.digits);
self.sign > 0 && !self.digits.is_empty()
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
self.sign < 0 && !self.digits.is_empty()
}
fn add_abs_values(mut first: &Bigint, mut second: &Bigint) -> Vec<u8> {
let mut r_first = first.digits.clone();
r_first.reverse();
let mut r_second = second.digits.clone();
r_second.reverse();
let mut iter_right = r_second.iter();
let mut res: Vec<u8> = Vec::new();
let mut leftover = 0_u8;
let mut n_right: Option<&u8>;
for n_left in r_first.iter() {
n_right = iter_right.next();
if n_right.is_none() {
break;
}
res.push((n_left + n_right.unwrap() + leftover) % 10);
leftover = (n_left + n_right.unwrap() + leftover) / 10;
}
for n_right in iter_right {
res.push((n_right + leftover) % 10);
leftover = (n_right + leftover) / 10
}
if leftover > 0 {
res.push(leftover);
}
res
}
fn sub_second_from_first(first: &Bigint, second: &Bigint) -> Vec<u8> {
let mut r_first = first.digits.clone();
r_first.reverse();
let mut r_second = second.digits.clone();
r_second.reverse();
let mut res: Vec<u8> = Vec::new();
let mut iter_left = r_first.iter();
let n_left_opt = iter_left.next();
let mut n_left: u8;
let mut minus_one = false;
if n_left_opt.is_some(){
n_left = *n_left_opt.unwrap();
for n_right in r_second.iter() {
if n_left < *n_right {
n_left = n_left + 10_u8;
minus_one = true;
}
res.push(n_left - n_right);
n_left = *iter_left.next().unwrap();
if minus_one {
n_left = n_left - 1;
}
minus_one = false;
};
}
res
}
fn abs(self: &Bigint) -> Self {
Bigint::from_components(self.digits.clone(), -1 * self.sign)
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut digits: Vec<u8> = Vec::new();
let mut sign = 1;
if !s.is_empty() {
let mut chars: Vec<char> = s.chars().collect();
match chars[0] {
c if c == '-' || c == '+' => {
if chars.len() == 1 {
return Err(ParseError)
}
if c == '-' {
sign = -1;
}
chars.remove(0);
}
d if d.is_digit(10) => sign = 1,
_ => return Err(ParseError),
}
for ch in chars {
match ch.to_digit(10) {
Some(digit) => {
if !(digit == 0 && digits.is_empty()) {
digits.push(digit as u8);
}
}
None => {
return Err(ParseError)
}
}
}
}
if digits.is_empty() {
sign = 1;
}
Ok(Bigint::from_components(digits, sign))
}
}
use std::cmp::Ordering;
impl PartialOrd for Bigint {
/// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
/// пълното.
///
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
if self.sign != other.sign {
self.sign.cmp(&other.sign)
}
else {
let mut cmp_res = if self.digits.len() == other.digits.len() {
self.digits.cmp(&other.digits)
}
else {
self.digits.len().cmp(&other.digits.len())
};
if self.sign < 0 { cmp_res = cmp_res.reverse(); }
cmp_res
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
Bigint::from_components(
Bigint::add_abs_values(&self, &other),
self.sign
)
}
else {
if other.abs() < self.abs() {
let digits = Bigint::sub_second_from_first(&other, &self);
if digits.is_empty() {
Bigint::from_components(digits, 1)
}
else{
Bigint::from_components(digits, self.sign)
}
}
else {
let digits = Bigint::sub_second_from_first(&self, &other);
let mut sign = self.sign.clone();
if digits.is_empty() {
sign = 1;
}
Bigint::from_components(digits, sign)
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
///
/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
///
fn sub(self, other: Self) -> Self {
Bigint::add(self, Bigint::from_components(other.digits.clone(), -1 * other.sign))
}
}
pub fn main(){
let x = vec![1, 2, 3];
let y = vec![1, 1, 3];
println!("{:?}", x.cmp(&y));
}
#[cfg(test)]
mod tests{
use super::*;
#[test]
fn test_empty_string_is_valid() {
assert!(Bigint::from_str("").is_ok());
}
#[test]
fn test_just_sign_is_not_valid() {
let mut res: Result<Bigint, ParseError>;
res = Bigint::from_str("-");
assert!(res.is_err());
res = Bigint::from_str("+");
assert!(res.is_err());
}
#[test]
fn test_positive_digit_without_sign_is_valid() {
let mut res: Result<Bigint, ParseError>;
for digit in 0..9 {
res = Bigint::from_str(digit.to_string().as_str());
assert!(res.is_ok());
};
}
#[test]
fn test_is_valid_positive_digit_with_sign() {
let mut res: Result<Bigint, ParseError>;
for digit in 0..9 {
res = Bigint::from_str(format!("+{}", digit).as_str());
assert!(res.is_ok());
};
}
#[test]
fn test_negative_digit_is_valid() {
let mut res: Result<Bigint, ParseError>;
for digit in 0..9 {
res = Bigint::from_str(format!("-{}", digit).as_str());
assert!(res.is_ok());
};
}
#[test]
fn test_more_than_one_sign_is_not_valid() {
let mut res: Result<Bigint, ParseError>;
res = Bigint::from_str("+-1");
assert!(res.is_err());
res = Bigint::from_str("-+1");
assert!(res.is_err());
}
#[test]
fn test_positive_number_without_sign_with_many_digits_is_valid(){
assert!(Bigint::from_str("1234567890").is_ok());
}
#[test]
fn test_positive_number_with_sign_with_many_digits_is_valid(){
assert!(Bigint::from_str("+1234567890").is_ok());
}
#[test]
fn test_negative_number_with_many_digits_is_valid(){
assert!(Bigint::from_str("-1234567890").is_ok());
}
#[test]
fn test_number_can_start_with_zero(){
let mut res: Result<Bigint, ParseError>;
res = Bigint::from_str("0123456789");
assert!(res.is_ok());
res = Bigint::from_str("+0123456789");
assert!(res.is_ok());
res = Bigint::from_str("-0123456789");
assert!(res.is_ok());
}
#[test]
fn test_number_can_start_with_many_zeros(){
let mut res: Result<Bigint, ParseError>;
res = Bigint::from_str("000123456789");
assert!(res.is_ok());
res = Bigint::from_str("+000123456789");
assert!(res.is_ok());
res = Bigint::from_str("-000123456789");
assert!(res.is_ok());
}
#[test]
fn test_many_zeroes_are_valid(){
let mut res: Result<Bigint, ParseError>;
res = Bigint::from_str("000");
assert!(res.is_ok());
res = Bigint::from_str("+000");
assert!(res.is_ok());
res = Bigint::from_str("-000");
assert!(res.is_ok());
}
#[test]
fn test_negative_and_positive_zeros_are_equal(){
let positive = Bigint::from_str("+0").unwrap();
let negative = Bigint::from_str("-0").unwrap();
assert_eq!(positive, negative);
}
#[test]
fn test_with_invalid_chars_at_the_beginning(){
assert!(Bigint::from_str("abc0123456789").is_err());
}
#[test]
fn test_with_invalid_chars_at_the_middle(){
assert!(Bigint::from_str("0123mno456789").is_err());
}
#[test]
fn test_with_invalid_chars_at_the_end(){
assert!(Bigint::from_str("0123456789xyz").is_err());
}
#[test]
fn test_with_only_invalid_chars(){
assert!(Bigint::from_str("abc_xyz").is_err());
}
mod test_is_negative {
use super::*;
#[test]
fn test_with_negative_number(){
assert!(Bigint::from_str("-1").unwrap().is_negative());
}
#[test]
fn test_with_positive_number_with_sign(){
assert!(!Bigint::from_str("+1").unwrap().is_negative());
}
#[test]
fn test_with_positive_number_without_sign(){
assert!(!Bigint::from_str("1").unwrap().is_negative());
}
#[test]
fn test_with_positive_zero_without_sign(){
assert!(!Bigint::from_str("0").unwrap().is_negative());
}
#[test]
fn test_with_positive_zero_with_sign(){
assert!(!Bigint::from_str("+0").unwrap().is_negative());
}
#[test]
fn test_with_negative_zero(){
assert!(!Bigint::from_str("-0").unwrap().is_negative());
}
}
mod test_is_positive{
use super::*;
#[test]
fn test_with_positive_number_with_sign(){
assert!(Bigint::from_str("+1").unwrap().is_positive());
}
#[test]
fn test_with_positive_number_without_sign(){
assert!(Bigint::from_str("1").unwrap().is_positive());
}
#[test]
fn test_with_negative_number(){
assert!(!Bigint::from_str("-1").unwrap().is_positive());
}
#[test]
fn test_with_positive_zero_without_sign(){
assert!(!Bigint::from_str("0").unwrap().is_positive());
}
#[test]
fn test_with_positive_zero_with_sign(){
assert!(!Bigint::from_str("+0").unwrap().is_positive());
}
#[test]
fn test_with_negative_zero(){
assert!(!Bigint::from_str("-0").unwrap().is_positive());
}
}
mod test_cmp {
use super::*;
mod test_positive_number {
use super::*;
#[test]
fn test_positive_numbers_with_same_length_but_different(){
let mut first = Bigint::from_str("123").unwrap();
let mut second = Bigint::from_str("124").unwrap();
assert!(first < second);
assert!(second > first);
first = Bigint::from_str("133").unwrap();
second = Bigint::from_str("123").unwrap();
assert!(first > second);
assert!(second < first);
}
#[test]
fn test_equal_positive_numbers(){
let first = Bigint::from_str("123").unwrap();
let second = Bigint::from_str("123").unwrap();
assert!(first == second);
}
#[test]
fn test_positive_numbers_with_different_length(){
let first = Bigint::from_str("111").unwrap();
let second = Bigint::from_str("1111").unwrap();
assert!(first < second);
assert!(second > first);
}
#[test]
fn test_positive_number_with_zero(){
let first = Bigint::from_str("0").unwrap();
let second = Bigint::from_str("1").unwrap();
assert!(first < second);
assert!(second > first);
}
}
mod test_negative_numbers {
use super::*;
#[test]
fn test_negative_numbers_with_same_length_but_different(){
let mut first = Bigint::from_str("-123").unwrap();
let mut second = Bigint::from_str("-124").unwrap();
assert!(first > second);
assert!(second < first);
first = Bigint::from_str("-133").unwrap();
second = Bigint::from_str("-123").unwrap();
assert!(first < second);
assert!(second > first);
}
#[test]
fn test_equal_negative_numbers(){
let first = Bigint::from_str("-123").unwrap();
let second = Bigint::from_str("-123").unwrap();
assert!(first == second);
}
#[test]
fn test_negative_numbers_with_different_length(){
let first = Bigint::from_str("-111").unwrap();
let second = Bigint::from_str("-1111").unwrap();
assert!(first > second);
assert!(second < first);
}
#[test]
fn test_negative_number_with_zero(){
let first = Bigint::from_str("0").unwrap();
let second = Bigint::from_str("-1").unwrap();
assert!(first > second);
assert!(second < first);
}
#[test]
fn test_numbers_with_different_sign_and_same_length(){
let mut first = Bigint::from_str("111").unwrap();
let mut second = Bigint::from_str("-999").unwrap();
assert!(first > second);
assert!(second < first);
first = Bigint::from_str("123").unwrap();
second = Bigint::from_str("-123").unwrap();
assert!(first > second);
assert!(second < first);
}
#[test]
fn test_numbers_with_different_sign_and_different_length(){
let mut first = Bigint::from_str("111").unwrap();
let mut second = Bigint::from_str("-1111").unwrap();
assert!(first > second);
assert!(second < first);
first = Bigint::from_str("1111").unwrap();
second = Bigint::from_str("-111").unwrap();
assert!(first > second);
assert!(second < first);
}
}
#[test]
fn test_zero_with_zero(){
let first = Bigint::from_str("0").unwrap();
let second = Bigint::from_str("0").unwrap();
assert!(first == second);
}
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-1jv6y9a/solution)
warning: variable does not need to be mutable
  --> src/lib.rs:40:23
   |
40 |     fn add_abs_values(mut first: &Bigint, mut second: &Bigint) -> Vec<u8> {
   |                       ----^^^^^
   |                       |
   |                       help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
  --> src/lib.rs:40:43
   |
40 |     fn add_abs_values(mut first: &Bigint, mut second: &Bigint) -> Vec<u8> {
   |                                           ----^^^^^^
   |                                           |
   |                                           help: remove this `mut`

warning: 2 warnings emitted

    Finished test [unoptimized + debuginfo] target(s) in 1.79s
     Running target/debug/deps/solution_test-589a43f0f4b10ca3

running 15 tests
test solution_test::test_bigint_construction ... ok
test solution_test::test_bigint_nonzero_sign ... ok
test solution_test::test_bigint_zero_sign ... ok
test solution_test::test_comparison ... ok
test solution_test::test_invalid_string ... ok
test solution_test::test_neutralization ... FAILED
test solution_test::test_parsing_with_and_without_sign ... ok
test solution_test::test_parsing_with_leading_zeroes ... ok
test solution_test::test_sub_1_basic ... FAILED
test solution_test::test_sub_2_diferent_lengths ... FAILED
test solution_test::test_sub_3_carry ... FAILED
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... FAILED
test solution_test::test_sum_3_overflow ... FAILED
test solution_test::test_sum_4_negative ... FAILED

failures:

---- solution_test::test_neutralization stdout ----
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/lib.rs:102:44
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- solution_test::test_sub_1_basic stdout ----
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/lib.rs:102:44

---- solution_test::test_sub_2_diferent_lengths stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Bigint { sign: 1, digits: [0, 0, 0] }`,
 right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:151:5

---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:104:30

---- solution_test::test_sum_2_different_lengths stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Bigint { sign: 1, digits: [2, 1, 0, 2, 1] }`,
 right: `Bigint { sign: 1, digits: [1, 2, 0, 1, 2] }`', tests/solution_test.rs:88:5

---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Bigint { sign: 1, digits: [0, 1] }`,
 right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5

---- solution_test::test_sum_4_negative stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Bigint { sign: -1, digits: [9, 7, 5] }`,
 right: `Bigint { sign: -1, digits: [5, 7, 9] }`', tests/solution_test.rs:112:5


failures:
    solution_test::test_neutralization
    solution_test::test_sub_1_basic
    solution_test::test_sub_2_diferent_lengths
    solution_test::test_sub_3_carry
    solution_test::test_sum_2_different_lengths
    solution_test::test_sum_3_overflow
    solution_test::test_sum_4_negative

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

error: test failed, to rerun pass '--test solution_test'

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

Антонина качи първо решение на 27.11.2020 16:59 (преди почти 5 години)

Опитала си се да напишеш тестове, което е добре, и добре си подходила откъм случаи -- различни ситуации, конфигурации на входа. Малко са обемни, което може да затрудни разбирането. Виж как сме ги организирали в пълния тест за вдъхновение как можеш да ги направиш по-компактни.

Въпреки детайлните тестове за парсене, изпуснала си и един много интересен случай -- не-ascii текст, примерно кирилица. Винаги е добра идея при низови операции да тествате с нещо такова, защото лесно може да индексирате байтове някъде без да искате.

И тестовете не са довършени, което предполагам че е просто заради липса на време накрая. Какво да се прави :).