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

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

Решение на Bigint от Ивайло Кирязов

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

Към профила на Ивайло Кирязов

Резултати

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

Код

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
is_zero: bool,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
is_zero: true,
}
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
if digits.is_empty() {
return Bigint::new();
}
if digits[0] == 0 {
return Bigint::new();
}
Bigint {
sign: sign,
digits: digits,
is_zero: false,
}
}
pub fn is_positive(&self) -> bool {
if self.is_zero {
println!("Zero is same");
return false;
}
if self.sign == 1 {
return true;
}
false
}
pub fn is_negative(&self) -> bool {
if self.is_zero {
println!("Zero is same");
return false;
}
!self.is_positive()
}
}
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 big = Bigint::new();
if s.is_empty() || s == "0" || s == "-0" || s == "+" || s == "-" {
return Ok(big);
}
let mut result = Vec::new();
let mut sign = 1;
let mut skip_first = false;
if s.chars().next().unwrap() == '-' && s.len() > 1 {
sign = -1;
skip_first = true;
}
if s.chars().next().unwrap() == '+' && s.len() > 1 {
skip_first = true;
}
for c in s.chars() {
if skip_first {
skip_first = false;
continue;
}
if !c.is_numeric() {
return Err(ParseError);
}
if c == '0' && result.is_empty() {
continue;
}
let numb = c.to_digit(10);
for a in numb {
result.push(a as u8);
}
}
big = Bigint::from_components(result, sign as i8);
Ok(big)
}
}
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.is_negative() && other.is_positive() {
return Ordering::Less;
}
if self.is_positive() && other.is_negative() {
return Ordering::Greater;
}
if self.is_positive() && other.is_positive() {
if self.digits.len() > other.digits.len() {
return Ordering::Greater;
} else if self.digits.len() < other.digits.len() {
return Ordering::Less;
} else {
for (i, self_value) in self.digits.iter().enumerate() {
if self_value > &other.digits[i] {
return Ordering::Greater;
} else if self_value < &other.digits[i] {
return Ordering::Less;
}
}
}
}
if self.is_negative() && other.is_negative() {
if self.digits.len() < other.digits.len() {
return Ordering::Greater;
} else if self.digits.len() > other.digits.len() {
return Ordering::Less;
} else {
for (i, self_value) in self.digits.iter().enumerate() {
if self_value < &other.digits[i] {
return Ordering::Greater;
} else if self_value > &other.digits[i] {
return Ordering::Less;
}
}
}
}
Ordering::Equal
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut vec_self = self.digits.clone();
let mut vec_other = other.digits.clone();
vec_self.reverse();
vec_other.reverse();
let mut result = Bigint::new();
if self.is_positive() && other.is_positive() {
//sign is plus
if vec_self.len() >= vec_other.len() {
result.digits = add_digits(vec_self, vec_other);
} else {
result.digits = add_digits(vec_other, vec_self);
}
if result.digits[0] != 0 {
result.is_zero = false;
}
return result;
}
if self.is_negative() && other.is_negative() {
result.sign = -1;
if vec_self.len() <= vec_other.len() {
result.digits = add_digits(vec_self, vec_other);
} else {
result.digits = add_digits(vec_other, vec_self);
}
if result.digits[0] != 0 {
result.is_zero = false;
}
return result;
}
let mut first_is_bigger = true;
if self.digits.len() < other.digits.len() {
first_is_bigger = false;
} else if self.digits.len() > other.digits.len() {
first_is_bigger = true;
} else {
for (i, self_value) in self.digits.iter().enumerate() {
if self_value > &other.digits[i] {
first_is_bigger = true;
} else if self_value < &other.digits[i] {
first_is_bigger = false;
}
}
}
if self.digits == other.digits {
return Bigint::new();
}
if first_is_bigger {
result.digits = subtract_digits(vec_self, vec_other);
if self.is_positive() {
result.sign = 1;
} else {
result.sign = -1;
}
} else {
result.digits = subtract_digits(vec_other, vec_self);
if other.is_positive() {
result.sign = 1;
} else {
result.sign = -1;
}
}
if result.digits[0] != 0 {
result.is_zero = false;
}
result
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let other_new_sign;
if other.is_positive() {
other_new_sign = Bigint::from_components(other.digits.clone(), -1);
} else {
other_new_sign = Bigint::from_components(other.digits.clone(), 1);
}
self + other_new_sign
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
let mut result = Vec::new();
if left.len() < right.len() {
panic!("First vector must be a bigger number!")
}
let len_diff = left.len() - right.len();
let mut carryover = false;
let mut index = 0;
for (i, right_value) in right.iter().enumerate() {
let res;
if carryover {
res = right_value + left[i] + 1;
carryover = false;
} else {
res = right_value + left[i];
}
if res > 9 {
result.push(res % 10);
carryover = true;
} else {
result.push(res);
}
index = i;
}
if len_diff == 0 {
if carryover {
result.push(1);
}
result.reverse();
return result;
}
for i in index + 1..left.len() {
let res;
if carryover {
res = left[i] + 1;
carryover = false;
} else {
res = left[i];
}
if res > 9 {
result.push(res % 10);
carryover = true;
} else {
result.push(res);
}
}
if carryover {
result.push(1);
}
result.reverse();
result
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut result = larger.clone();
if larger.len() < smaller.len() {
panic!("First vector must be a bigger number!")
}
let mut carryover = false;
let mut not_enough = false;
for (i, right_value) in smaller.iter().enumerate() {
let mut res = 0;
if right_value > &result[i] {
if i + 1 > result.len() {
panic!("First vector must be a bigger number!");
}
let next_numb = result[i + 1] * 10 + result[i];
if &next_numb > right_value {
res = next_numb - right_value;
if res > 9 {
res %= 10;
}
} else {
not_enough = true;
}
carryover = true;
} else {
res = result[i] - right_value;
}
if carryover {
let mut j = i + 1;
if not_enough {
j = i;
} else {
result[i] = res;
}
while j < result.len() {
if result[j] == 0 {
result[j] = 9;
} else {
result[j] -= 1;
break;
}
j += 1;
}
carryover = false;
} else {
result[i] = res;
}
}
if result[result.len() - 1] == 0 {
result.pop();
}
result.reverse();
result
}
#[test]
fn test_zero_add() {
let vec = Bigint::from_str("-1");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("0");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_zero_add1() {
let vec = Bigint::from_str("0");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("1");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_zero_add2() {
let vec = Bigint::from_str("1");
let vec1 = Bigint::from_str("0");
let res = Bigint::from_str("1");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_zero_sub() {
let vec = Bigint::from_str("0");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("-1");
assert_eq!((vec.unwrap() - vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int0() {
let vec = Bigint::from_str("1");
let vec1 = Bigint::from_str("10");
let res = Bigint::from_str("11");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int1() {
let vec = Bigint::from_str("12");
let vec1 = Bigint::from_str("10");
let res = Bigint::from_str("22");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int2() {
let vec = Bigint::from_str("10");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("11");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int3() {
let vec = Bigint::from_str("9");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("10");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int4() {
let vec = Bigint::from_str("19");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("20");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int5() {
let vec = Bigint::from_str("99");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("100");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int6() {
let vec = Bigint::from_str("-1");
let vec1 = Bigint::from_str("10");
let res = Bigint::from_str("9");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int7() {
let vec = Bigint::from_str("-12");
let vec1 = Bigint::from_str("10");
let res = Bigint::from_str("-2");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int8() {
let vec = Bigint::from_str("-10");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("-9");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int9() {
let vec = Bigint::from_str("-9");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("-8");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int10() {
let vec = Bigint::from_str("-19");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("-18");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_add_int11() {
let vec = Bigint::from_str("-100");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("-99");
assert_eq!((vec.unwrap() + vec1.unwrap()), res.unwrap());
}
#[test]
fn test_sub_int0() {
let vec = Bigint::from_str("10");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("9");
assert_eq!((vec.unwrap() - vec1.unwrap()), res.unwrap());
}
#[test]
fn test_sub_int1() {
let vec = Bigint::from_str("22");
let vec1 = Bigint::from_str("10");
let res = Bigint::from_str("12");
assert_eq!((vec.unwrap() - vec1.unwrap()), res.unwrap());
}
#[test]
fn test_sub_int2() {
let vec = Bigint::from_str("420");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("419");
assert_eq!((vec.unwrap() - vec1.unwrap()), res.unwrap());
}
#[test]
fn test_sub_int3() {
let vec = Bigint::from_str("11");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("10");
assert_eq!((vec.unwrap() - vec1.unwrap()), res.unwrap());
}
#[test]
fn test_sub_int4() {
let vec = Bigint::from_str("20");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("19");
assert_eq!((vec.unwrap() - vec1.unwrap()), res.unwrap());
}
#[test]
fn test_sub_int5() {
let vec = Bigint::from_str("100");
let vec1 = Bigint::from_str("1");
let res = Bigint::from_str("99");
assert_eq!((vec.unwrap() - vec1.unwrap()), res.unwrap());
}
#[test]
#[should_panic]
fn test_add0() {
let mut vec = vec![1];
let mut vec1 = vec![1, 0];
vec.reverse();
vec1.reverse();
assert_eq!(add_digits(vec, vec1), vec![1, 1]);
}
#[test]
fn test_add1() {
let mut vec = vec![1, 2];
let mut vec1 = vec![1, 0];
vec.reverse();
vec1.reverse();
assert_eq!(add_digits(vec, vec1), vec![2, 2]);
}
#[test]
fn test_add2() {
let mut vec = vec![1, 0];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(add_digits(vec, vec1), vec![1, 1]);
}
#[test]
fn test_add3() {
let mut vec = vec![9];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(add_digits(vec, vec1), vec![1, 0]);
}
#[test]
fn test_add4() {
let mut vec = vec![1, 9];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(add_digits(vec, vec1), vec![2, 0]);
}
#[test]
fn test_add5() {
let mut vec = vec![9, 9];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(add_digits(vec, vec1), vec![1, 0, 0]);
}
#[test]
fn test_sub1() {
let mut vec = vec![2, 2];
let mut vec1 = vec![1, 0];
vec.reverse();
vec1.reverse();
assert_eq!(subtract_digits(vec, vec1), vec![1, 2]);
}
#[test]
fn test_sub2() {
let mut vec = vec![1, 1];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(subtract_digits(vec, vec1), vec![1, 0]);
}
#[test]
fn test_sub6() {
let mut vec = vec![1, 1, 0];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(subtract_digits(vec, vec1), vec![1, 0, 9]);
}
#[test]
fn test_sub3() {
let mut vec = vec![1, 0];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(subtract_digits(vec, vec1), vec![9]);
}
#[test]
fn test_sub4() {
let mut vec = vec![2, 0];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(subtract_digits(vec, vec1), vec![1, 9]);
}
#[test]
fn test_sub7() {
let mut vec = vec![4, 2, 0];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(subtract_digits(vec, vec1), vec![4, 1, 9]);
}
#[test]
fn test_sub5() {
let mut vec = vec![1, 0, 0];
let mut vec1 = vec![1];
vec.reverse();
vec1.reverse();
assert_eq!(subtract_digits(vec, vec1), vec![9, 9]);
}
#[test]
fn test_other_constr() {
let result = vec![1 as u8, 2 as u8, 3 as u8];
let big = Bigint::from_components(result.clone(), 1);
assert_eq!(big.digits, result);
}
#[test]
fn test_other_constr_positive() {
let result = vec![1 as u8, 2 as u8, 3 as u8];
let big = Bigint::from_components(result, 1);
assert!(big.is_positive());
}
#[test]
fn test_other_constr_negative() {
let result = vec![1 as u8, 2 as u8, 3 as u8];
let big = Bigint::from_components(result.clone(), -1);
assert!(big.is_negative());
}
#[test]
#[should_panic]
fn test_positive_zero() {
let big = Bigint::new();
assert!(big.is_positive());
}
#[test]
#[should_panic]
fn test_negative_zero() {
let big = Bigint::new();
assert!(big.is_negative());
}
#[test]
fn test_other_from_str0() {
let big = Bigint::from_str("123");
let result = big.unwrap();
assert!(result.is_positive());
let expected = vec![1 as u8, 2 as u8, 3 as u8];
assert_eq!(result.digits, expected);
}
#[test]
fn test_other_from_str1() {
let big = Bigint::from_str("+123");
let result = big.unwrap();
assert!(result.is_positive());
let expected = vec![1 as u8, 2 as u8, 3 as u8];
assert_eq!(result.digits, expected);
}
#[test]
fn test_other_from_str2() {
let big = Bigint::from_str("-123");
let result = big.unwrap();
assert!(result.is_negative());
let expected = vec![1 as u8, 2 as u8, 3 as u8];
assert_eq!(result.digits, expected);
}
#[test]
fn test_other_from_str3() {
let big = Bigint::from_str("00123");
let result = big.unwrap();
assert!(result.is_positive());
let expected = vec![1 as u8, 2 as u8, 3 as u8];
assert_eq!(result.digits, expected);
}
#[test]
fn test_other_from_str4() {
let big = Bigint::from_str("-00123");
let result = big.unwrap();
assert!(result.is_negative());
let expected = vec![1 as u8, 2 as u8, 3 as u8];
assert_eq!(result.digits, expected);
}
#[test]
fn test_other_from_str5() {
let big = Bigint::from_str("-001230");
let result = big.unwrap();
assert!(result.is_negative());
let expected = vec![1 as u8, 2 as u8, 3 as u8, 0 as u8];
assert_eq!(result.digits, expected);
}
#[test]
fn test_other_from_str4_big() {
let big =
Bigint::from_str("-00123123123123123123123123131312323154135345234235143513451235134614");
let result = big.unwrap();
assert!(result.is_negative());
let expected = vec![
1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3, 1, 3, 1, 2,
3, 2, 3, 1, 5, 4, 1, 3, 5, 3, 4, 5, 2, 3, 4, 2, 3, 5, 1, 4, 3, 5, 1, 3, 4, 5, 1, 2, 3, 5,
1, 3, 4, 6, 1, 4,
];
assert_eq!(result.digits, expected);
}
#[test]
fn test_other_from_jibberish() {
let big = Bigint::from_str("-A00123");
assert!(!big.is_ok());
}
#[test]
fn test_other_from_jibberish1() {
let big = Bigint::from_str("-1-23");
assert!(!big.is_ok());
}
#[test]
fn test_equal() {
let big = Bigint::from_str("123");
let big1 = Bigint::from_str("123");
assert_eq!(big.unwrap(), big1.unwrap());
}
#[test]
fn test_neg_equal() {
let big = Bigint::from_str("-123");
let big1 = Bigint::from_str("-123");
assert_eq!(big.unwrap(), big1.unwrap());
}
#[test]
fn test_pos_less() {
let big = Bigint::from_str("112");
let big1 = Bigint::from_str("143");
assert!(big.unwrap() < big1.unwrap());
}
#[test]
fn test_pos_less_len() {
let big = Bigint::from_str("11");
let big1 = Bigint::from_str("143");
assert!(big.unwrap() < big1.unwrap());
}
#[test]
fn test_pos_great() {
let big = Bigint::from_str("144");
let big1 = Bigint::from_str("112");
assert!(big.unwrap() > big1.unwrap());
}
#[test]
fn test_pos_great_len() {
let big = Bigint::from_str("1440");
let big1 = Bigint::from_str("112");
assert!(big.unwrap() > big1.unwrap());
}
#[test]
fn test_neg_pos() {
let big = Bigint::from_str("-123");
let big1 = Bigint::from_str("123");
assert!(big.unwrap() < big1.unwrap());
}
#[test]
fn test_pos_neg() {
let big = Bigint::from_str("123");
let big1 = Bigint::from_str("-123");
assert!(big.unwrap() > big1.unwrap());
}
#[test]
fn test_neg_less() {
let big = Bigint::from_str("-126");
let big1 = Bigint::from_str("-124");
assert!(big.unwrap() < big1.unwrap());
}
#[test]
fn test_neg_great() {
let big = Bigint::from_str("-112");
let big1 = Bigint::from_str("-143");
assert!(big.unwrap() > big1.unwrap());
}
#[test]
fn test_neg_great_len() {
let big = Bigint::from_str("-12");
let big1 = Bigint::from_str("-124");
assert!(big.unwrap() > big1.unwrap());
}
#[test]
fn test_neg_less_len() {
let big = Bigint::from_str("-1120");
let big1 = Bigint::from_str("-143");
assert!(big.unwrap() < big1.unwrap());
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-14gkfed/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.73s
     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 ... FAILED
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 ... FAILED
test solution_test::test_sum_4_negative ... FAILED

failures:

---- solution_test::test_comparison stdout ----
Zero is same
Zero is same
Zero is same
Zero is same
thread 'main' panicked at 'assertion failed: bigint("0") > bigint("-1")', tests/solution_test.rs:173:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'First vector must be a bigger number!', src/lib.rs:256:9

---- solution_test::test_sum_4_negative stdout ----
thread 'main' panicked at 'First vector must be a bigger number!', src/lib.rs:256:9


failures:
    solution_test::test_comparison
    solution_test::test_sum_3_overflow
    solution_test::test_sum_4_negative

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

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

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

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

Написал си доста редове тестове, но има какво да се желае от тях. Примерно, имаш един тест за 1 + 0 и втори тест за 0 + 1. Окей, може би искаш да тестваш, че събирането работи и в двете посоки. Но после имаш 10 + 1 и 1 + 10, и тази проверка вече не си заслужава. А както виждаш, си изпуснал интересни случаи като сравнение на 0 и -1. Проверките на add_digits и subtract_digits също не би трябвало да са нужни, ако тестваш + и -. Повтарянето на едни и същи проверки не помага -- целта е да покриеш различни варианти, не да повториш едни и същи няколко пъти.

Погледни пълния тест, който сме споделили за идея как ние сме ги групирали. Помисли и върху форматирането на тестовете -- твоите са много, много дълги и не са свързани по никакъв начин -- всеки отделен тест е една проверка, която не казва какво тества. Даже имаш два теста за 10 + 1 и 1 + 10, които очевидно са подобни, но между тях имаш друг тест. Трудно е да се четат така и е трудно да видиш какви случаи си покрил, за да помислиш какви други да покриеш.