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

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

Решение на Bigint от Ивайло Атовски

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

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

Резултати

  • 15 точки от тестове
  • 1 бонус точка
  • 16 точки общо
  • 15 успешни тест(а)
  • 0 неуспешни тест(а)

Код

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
/// Конструира нов Bigint със стойност "0" и положителен знак.
/// Това означава масив с една цифра `0`.
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
/// Конструира нов Bigint с подадените цифри и знак.
///
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut new_vec: Vec<u8> = Vec::new();
let mut new_sign: i8 = match sign {
-1 | 1 => sign,
_ => 1,
};
let mut has_started: bool = false;
for digit in digits {
if digit != 0 && has_started == false {
has_started = true;
}
if has_started {
new_vec.push(digit);
}
}
if new_vec.len() == 1 && new_vec[0] == 0 {
new_sign = 1;
}
if new_vec.is_empty() {
new_sign = 1;
new_vec.push(0);
}
Self {
sign: new_sign,
digits: new_vec,
}
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
///
pub fn is_positive(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0 {
return false;
}
match self.sign {
1 => true,
_ => false,
}
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
///
pub fn is_negative(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0 {
return false;
}
match self.sign {
-1 => true,
_ => false,
}
}
}
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> {
if !s.is_empty() {
let chars: Vec<char> = s.chars().collect();
let mut digits: Vec<u8> = Vec::new();
let sign = match chars[0] {
'+' => 1,
'-' => -1,
ch if ch.is_digit(10) => 1,
_ => return Err(ParseError),
};
let mut first = true;
for digit in chars {
if digit.is_digit(10) {
digits.push(match digit.to_digit(10) {
Some(val) => val as u8,
None => unreachable!(),
});
first = false;
} else if first && (digit == '+' || digit == '-') {
first = false
} else {
return Err(ParseError);
}
}
Ok(Bigint::from_components(digits, sign))
} else {
Ok(Bigint::new())
}
}
}
use std::cmp::Ordering;
impl PartialOrd for Bigint {
/// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
/// пълното.
///
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
/// Сравнява две числа в масиви когато имат равен брой цифри
///
fn same_len_cmp(left: &Vec<u8>, right: &Vec<u8>) -> Ordering {
for i in 0..left.len() {
if left[i] < right[i] {
return Ordering::Less;
} else if left[i] > right[i] {
return Ordering::Greater;
}
}
Ordering::Equal
}
impl Ord for Bigint {
/// Ако едното от числата е положително, а другото -- отрицателно, положителното е по-голямо.
///
/// Ако и двете числа са положителни, това с повече цифри е по-голямо. Ако имат еднакъв брой
/// цифри, лексикографско сравнение на цифрите от по-значима към по-малко значима цифра ще ви
/// върне по-голямото число. (Внимавайте с нулата -- тя има 1 цифра)
///
/// Ако и двете числа са отрицателни, горната логика е същата, просто сравнението е обърнато
/// (-1 е по-голямо от -2 и от -10).
///
fn cmp(&self, other: &Bigint) -> Ordering {
let self_positive = self.is_positive();
let other_positive = other.is_positive();
match (self_positive, other_positive) {
(true, false) => return Ordering::Greater,
(false, true) => return Ordering::Less,
(true, true) => match (self.digits.len(), other.digits.len()) {
(x, y) if x > y => return Ordering::Greater,
(x, y) if x < y => return Ordering::Less,
(x, y) if x == y => same_len_cmp(&self.digits, &other.digits),
_ => unreachable!(),
},
(false, false) => match (self.digits.len(), other.digits.len()) {
(x, y) if x > y => return Ordering::Less,
(x, y) if x < y => return Ordering::Greater,
(x, y) if x == y => same_len_cmp(&other.digits, &self.digits),
_ => unreachable!(),
},
}
}
}
use std::ops::{Add, Sub};
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
left.reverse();
right.reverse();
let mut left_len = left.len();
let mut right_len = right.len();
while left_len < right_len {
left.push(0);
left_len += 1;
}
while left_len > right_len {
right.push(0);
right_len += 1;
}
let mut carry = 0;
let mut new_vec: Vec<u8> = Vec::new();
for i in 0..left_len {
let val = left[i] + right[i] + carry;
if val > 9 {
carry = 1;
} else {
carry = 0;
}
new_vec.push(val % 10);
}
new_vec.push(carry);
new_vec.reverse();
new_vec
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
larger.reverse();
smaller.reverse();
let mut larger_len = larger.len();
let mut smaller_len = smaller.len();
while larger_len < smaller_len {
larger.push(0);
larger_len += 1;
}
while larger_len > smaller_len {
smaller.push(0);
smaller_len += 1;
}
let mut carry = 0;
let mut new_vec: Vec<u8> = Vec::new();
for i in 0..larger_len {
let val: u8;
if larger[i] < (smaller[i] + carry) {
val = (10 + larger[i]) - (smaller[i] + carry);
carry = 1;
} else {
val = larger[i] - (smaller[i] + carry);
carry = 0;
}
new_vec.push(val);
}
new_vec.reverse();
new_vec
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let self_positive = self.is_positive();
let other_positive = other.is_positive();
match (self_positive, other_positive) {
(true, true) => {
Bigint::from_components(add_digits(self.digits.clone(), other.digits.clone()), 1)
}
(false, false) => {
Bigint::from_components(add_digits(self.digits.clone(), other.digits.clone()), -1)
}
(true, false) => match self.cmp(&Bigint::from_components(other.digits.clone(), 1)) {
Ordering::Equal => Bigint::new(),
Ordering::Less => Bigint::from_components(
subtract_digits(other.digits.clone(), self.digits.clone()),
-1,
),
Ordering::Greater => Bigint::from_components(
subtract_digits(self.digits.clone(), other.digits.clone()),
1,
),
},
(false, true) => match other.cmp(&Bigint::from_components(self.digits.clone(), 1)) {
Ordering::Equal => Bigint::new(),
Ordering::Less => Bigint::from_components(
subtract_digits(self.digits.clone(), other.digits.clone()),
-1,
),
Ordering::Greater => Bigint::from_components(
subtract_digits(other.digits.clone(), self.digits.clone()),
1,
),
},
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if other.is_positive() {
self + Bigint::from_components(other.digits, -1)
} else {
self + Bigint::from_components(other.digits, 1)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_create() {
let val = Bigint {
sign: 1,
digits: vec![0],
};
assert_eq!(val, Bigint::new());
let coustom_number = Bigint::from_components(vec![0, 0, 0, 0, 0, 5, 9], -1);
let val_coustom = Bigint {
sign: -1,
digits: vec![5, 9],
};
assert_eq!(coustom_number, val_coustom);
let coustom_number1 = Bigint::from_components(vec![0, 0, 0, 0, 0, 5, 9], -111);
let val_coustom1 = Bigint {
sign: 1,
digits: vec![5, 9],
};
assert_eq!(coustom_number1, val_coustom1);
assert_ne!(
Bigint::new(),
Bigint::from_components(vec![0, 0, 0, 0, 0, 5, 9], -1)
);
assert_eq!(
Bigint::new(),
Bigint::from_components(vec![0, 0, 0, 0, 0, 0, 0], -1)
);
assert_eq!(Bigint::new(), Bigint::from_components(vec![0, 0], 1));
assert_eq!(Bigint::new(), Bigint::from_components(vec![], -1));
assert_ne!(
Bigint::new(),
Bigint::from_components(vec![1, 2, 3, 4, 5, 6, 7, 8, 9], -1)
);
}
#[test]
fn test_positive_negative() {
let val = Bigint::from_components(vec![1, 2, 3, 4, 5, 6, 7, 8, 9], -1);
assert_eq!(val.is_positive(), !val.is_negative());
assert_eq!(
Bigint::from_components(vec![], -1),
Bigint::from_components(vec![0, 0, 0], 1)
);
}
mod pars_tets {
use super::*;
#[test]
fn test_string_pars() {
let val = match Bigint::from_str("123456") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};

Вместо ръчно да pattern-match-ваш, метода .unwrap() щеше да ти свърши същата работа. А ако искаш да провериш дали резултата е грешка, можеш да провериш .is_err() вместо да panic-ваш. По този начин, ако кода panic-не без да си го очаквал (примерно заради невалиден utf8 достъп или нещо такова), ще можеш да си видиш грешката.

Андрей
assert_eq!(val, Bigint::from_components(vec![1, 2, 3, 4, 5, 6], 1));
let val = match Bigint::from_str("-123456") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert_eq!(val, Bigint::from_components(vec![1, 2, 3, 4, 5, 6], -1));
let val = match Bigint::from_str("-00000000000000000000000000000000000000000000000000000000000000000000000000000000000030003") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert_eq!(val, Bigint::from_components(vec![3, 0, 0, 0, 3], -1));
let val = match Bigint::from_str("+00322001") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert_eq!(val, Bigint::from_components(vec![3, 2, 2, 0, 0, 1], 1));
let val = match Bigint::from_str("-") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert_eq!(val, Bigint::new());
let val = match Bigint::from_str("+") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert_eq!(val, Bigint::new());
let val = match Bigint::from_str("") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert_eq!(val, Bigint::new());
}
#[test]
#[should_panic]
fn test_string_pars_panic1() {
match Bigint::from_str("Здрасти, проверяващия") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
}
#[test]
#[should_panic]
fn test_string_pars_panic2() {
match Bigint::from_str("-12121 1212") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
}
#[test]
#[should_panic]
fn test_string_pars_panic3() {
match Bigint::from_str("+1+123456789") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
}
#[test]
#[should_panic]
fn test_string_pars_panic4() {
match Bigint::from_str(" 123456789") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
}
}
#[test]
fn test_compare() {
let val1 = match Bigint::from_str("+0") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
let val2 = match Bigint::from_str("-0") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert!(val1 == val2, "Асърт сравнение едно");
assert_eq!(val1.cmp(&val2), Ordering::Equal);
assert_eq!(val2.cmp(&val1), Ordering::Equal);
let val1 = match Bigint::from_str("123") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
let val2 = match Bigint::from_str("231") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert!(val1 < val2, "Асърт сравнение три");
assert!(val2 > val1, "Асърт сравнение три");
let val1 = match Bigint::from_str("24") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
let val2 = match Bigint::from_str("24") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert!(val1 >= val2, "Асърт сравнение четири");
assert!(val1 <= val2, "Асърт сравнение четири");
assert_eq!(val1.cmp(&val2), Ordering::Equal);
assert!(val2 >= val1, "Асърт сравнение четири");
assert!(val2 <= val1, "Асърт сравнение четири");
assert_eq!(val2.cmp(&val1), Ordering::Equal);
let val1 = match Bigint::from_str("60") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
let val2 = match Bigint::from_str("-25") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert!(val1 > val2, "Асърт сравнение пет");
assert!(val2 < val1, "Асърт сравнение пет");
assert_eq!(val1.cmp(&val2), Ordering::Greater);
let val1 = match Bigint::from_str("-120") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
let val2 = match Bigint::from_str("-25") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert!(val1 < val2, "Асърт сравнение шест");
assert_eq!(val1.cmp(&val2), Ordering::Less);
}
mod arithmetic_tets {
use super::*;
#[test]
fn test_add() {
let val1 = match Bigint::from_str("120") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
let val2 = match Bigint::from_str("48") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
let result = match Bigint::from_str("168") {
Ok(the_val) => the_val,
Err(val_err) => panic!("{:?}", val_err),
};
assert_eq!(val1 + val2, result);
assert_eq!(
Bigint::from_str("58").unwrap() + Bigint::from_str("67").unwrap(),
Bigint::from_str("125").unwrap()
);
assert_eq!(
Bigint::from_str("24").unwrap() + Bigint::from_str("63").unwrap(),
Bigint::from_str("87").unwrap()
);
assert_eq!(
Bigint::from_str("-67").unwrap() + Bigint::from_str("-55").unwrap(),
Bigint::from_str("-122").unwrap()
);
assert_eq!(
Bigint::from_str("67").unwrap() + Bigint::from_str("-55").unwrap(),
Bigint::from_str("12").unwrap()
);
assert_eq!(
Bigint::from_str("67").unwrap() + Bigint::from_str("-67").unwrap(),
Bigint::from_str("-0").unwrap()
);

Сравнение с -0 тук е малко странно. Защо минус? Парсенето на -0 и +0 би работело по един и същ начин, но това не е нещото, което тестваш тук, тестваш събиране, няма предимство в това да сложиш -0 тук, или "" по-долу. По-скоро има логика да сложиш "каноничната форма" на резултата за яснота.

Андрей
assert_eq!(
Bigint::from_str("11").unwrap() + Bigint::from_str("-6").unwrap(),
Bigint::from_str("5").unwrap()
);
assert_eq!(
Bigint::from_str("11").unwrap() + Bigint::from_str("-32").unwrap(),
Bigint::from_str("-21").unwrap()
);
assert_eq!(
Bigint::from_str("10000").unwrap() + Bigint::from_str("-9999").unwrap(),
Bigint::from_str("1").unwrap()
);
assert_eq!(
Bigint::from_str("1234").unwrap() + Bigint::from_str("-4321").unwrap(),
Bigint::from_str("-3087").unwrap()
);
assert_eq!(
Bigint::from_str("-4321").unwrap() + Bigint::from_str("+1234").unwrap(),
Bigint::from_str("-3087").unwrap()
);
assert_eq!(
Bigint::from_str("-20").unwrap() + Bigint::from_str("55").unwrap(),
Bigint::from_str("35").unwrap()
);
assert_eq!(
Bigint::from_str("-0").unwrap() + Bigint::from_str("+0").unwrap(),
Bigint::from_str("").unwrap()
);
}
#[test]
fn test_sub() {
assert_eq!(
Bigint::from_str("58").unwrap() - Bigint::from_str("67").unwrap(),
Bigint::from_str("-9").unwrap()
);
assert_eq!(
Bigint::from_str("-67").unwrap() - Bigint::from_str("-93").unwrap(),
Bigint::from_str("+26").unwrap()
);
assert_eq!(
Bigint::from_str("123456789123456789123456789").unwrap()
- Bigint::from_str("123456789123456789123456789").unwrap(),
Bigint::from_str("+0").unwrap()
);
assert_eq!(
Bigint::from_str("999999999999999999999").unwrap()
- Bigint::from_str("-1").unwrap(),
Bigint::from_str("1000000000000000000000").unwrap()
);
assert_eq!(
Bigint::from_str("-999999999999999999999").unwrap()
- Bigint::from_str("1").unwrap(),
Bigint::from_str("-1000000000000000000000").unwrap()
);
assert_eq!(
Bigint::from_str("-59").unwrap() - Bigint::from_str("-224").unwrap(),
Bigint::from_str("165").unwrap()
);
assert_eq!(
Bigint::from_str("").unwrap() - Bigint::from_str("-224").unwrap(),
Bigint::from_str("224").unwrap()
);
assert_eq!(
Bigint::from_str("55").unwrap() - Bigint::from_str("66").unwrap(),
Bigint::from_str("-11").unwrap()
);
}
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-63j22j/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.78s
     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 ... ok
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 ... ok
test solution_test::test_sub_2_diferent_lengths ... ok
test solution_test::test_sub_3_carry ... ok
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... ok
test solution_test::test_sum_3_overflow ... ok
test solution_test::test_sum_4_negative ... ok

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

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

Ивайло качи първо решение на 26.11.2020 14:53 (преди почти 5 години)

Тестовете ти са малко хаотични, но си покрил горе-долу добър комплект от тестове. Това с паниката е потенциален проблем, защото може кода ти да връща Err както се очаква, а може теста с [should_panic] да минава, защото парсенето на кирилица неочаквано panic-ва. Прави разлика между двата случая.

Ще ти дам бонус точка за тестовете, но разгледай пълния тест, който сме използвали, за да събереш идеи как да си пишеш тестовете по-ясно (https://github.com/fmi/rust-homework/blob/master/02/test_full.rs).