Решение на Bigint от Пламен Николов
Резултати
- 15 точки от тестове
- 1 бонус точка
- 16 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, Sub};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
fn validate_sign(sign: i8) {
if sign != 1 && sign != -1 {
panic!("'sign' should be -1 or 1");
}
}
fn validate_digits(digits: &Vec<u8>) {
if digits.is_empty() {
panic!("'digits' must have at least 1 element");
}
for &digit in digits {
if digit > 9_u8 {
panic!("digits must be numbers between 0 and 9 inclusive");
}
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
let mut max_length = left.len();
if max_length < right.len() {
max_length = right.len();
}
let mut carry = 0;
let mut result: Vec<u8> = vec![];
for i in 0..max_length {
let left_digit = if i < left.len() {
left[i]
} else {
0
};
let right_digit = if i < right.len() {
right[i]
} else {
0
};
let mut sum = left_digit + right_digit + carry;
if sum > 9 {
carry = 1;
sum -= 10;
} else {
carry = 0;
}
result.push(sum);
}
if carry != 0 {
result.push(carry);
}
return result;
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut carry = 0_i8;
let mut result: Vec<u8> = vec![];
for i in 0..larger.len() {
let left_digit = if i < larger.len() {
larger[i] as i8
} else {
0
};
let right_digit = if i < smaller.len() {
smaller[i] as i8
} else {
0
};
let mut sum = left_digit - right_digit + carry;
if sum < 0 {
carry = -1;
sum += 10;
} else {
carry = 0;
}
result.push(sum as u8);
}
Bigint::normalize_digits(&mut result);
return result;
}
fn normalize_digits(digits: &mut Vec<u8>) {
while let Some(0) = digits.last() {
digits.pop();
}
if digits.is_empty() {
digits.push(0);
}
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut digits = digits;
let mut sign = sign;
Bigint::validate_sign(sign);
Bigint::validate_digits(&digits);
Bigint::normalize_digits(&mut digits);
if digits.len() == 1 && digits[0] == 0 {
sign = 1;
}
Bigint {
sign,
digits
}
}
pub fn is_zero(&self) -> bool {
return self.digits.len() == 1 && self.digits[0] == 0
}
pub fn is_positive(&self) -> bool {
return self.sign == 1 && !self.is_zero();
}
pub fn is_negative(&self) -> bool {
return self.sign == -1;
}
pub fn is_non_negative(&self) -> bool {
return self.sign == 1;
}
pub fn is_non_positive(&self) -> bool {
return self.is_negative() || self.is_zero();
}
pub fn negate(self) -> Self {
if self.is_zero() {
return self;
}
return Bigint {sign: -self.sign, digits: self.digits};
}
pub fn abs(self) -> Self {
return Bigint {sign: 1, digits: self.digits};
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut sign: i8 = 1;
let mut digits: Vec<u8> = vec![];
let mut s_iter = s.chars();
match s_iter.next() {
Some('+') => { sign = 1; },
Some('-') => { sign = -1; },
Some(ch) => {
if ch >= '0' && ch <= '9' {
digits.push(ch.to_digit(10).unwrap() as u8);
} else {
return Err(ParseError);
}
},
None => {
return Ok(Self::from_components(vec![0], 1));
}
}
for ch in s_iter {
if ch >= '0' && ch <= '9' {
digits.push(ch.to_digit(10).unwrap() as u8);
} else {
return Err(ParseError);
}
}
digits.reverse();
return Ok(Self::from_components(digits, sign));
}
}
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 {
return self.sign.cmp(&other.sign);
}
if self.digits.len() != other.digits.len() {
if self.is_negative() {
return self.digits.len().cmp(&other.digits.len()).reverse();
}
return self.digits.len().cmp(&other.digits.len());
}
for i in (0..self.digits.len()).rev() {
match self.digits[i].cmp(&other.digits[i]) {
Ordering::Equal => (),
not_equal => {
if self.is_negative() {
return not_equal.reverse();
}
return not_equal;
}
}
}
return Ordering::Equal;
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
return Bigint { digits: Bigint::add_digits(self.digits, other.digits), sign: self.sign };
}
let (left_sign, right_sign) = (self.sign, other.sign);
let abs_self = self.abs();
let abs_other = other.abs();
if abs_self >= abs_other {
Bigint::from_components(Bigint::subtract_digits(abs_self.digits, abs_other.digits), left_sign)
} else {
Bigint::from_components(Bigint::subtract_digits(abs_other.digits, abs_self.digits), right_sign)
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + other.negate()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
#[test]
fn invalid_sign_format() {
assert!(Bigint::from_str("plus123").is_err());
assert!(Bigint::from_str("+-123").is_err());
assert!(Bigint::from_str("+ 123").is_err());
}
#[test]
fn invalid_number_format() {
assert!(Bigint::from_str("100 000 000").is_err());
assert!(Bigint::from_str("-20 20").is_err());
assert!(Bigint::from_str(" 123").is_err());
assert!(Bigint::from_str("123 ").is_err());
assert!(Bigint::from_str(" ").is_err());
}
#[test]
fn zero_neither_positive_nor_negative() {
assert!(!bigint("0").is_positive());
assert!(!bigint("0").is_negative());
}
#[test]
fn empty_string_equals_zero() {
assert_eq!(bigint(""), Bigint::new());
}
#[test]
fn plus_zero_equals_minus_zero_equals_unsigned_zero() {
assert_eq!(bigint("+0"), bigint("-0"));
assert_eq!(bigint("-0"), bigint("0"));
assert_eq!(bigint("0"), bigint("+0"));
}
#[test]
fn add_implicit_plus_sign() {
assert_eq!(bigint("123"), bigint("+123"));
assert_ne!(bigint("2020"), bigint("-2020"));
}
#[test]
fn ignore_bonus_zeroes_when_parsing() {
assert_eq!(bigint("123"), bigint("0000123"));
assert_eq!(bigint("-2020"), bigint("-02020"));
assert_eq!(bigint("0"), bigint("-0000000"));
assert_eq!(bigint("0"), bigint("+0000000"));
}
#[test]
fn compare_with_same_sign() {
assert!(bigint("24") > bigint("3"));
assert!(bigint("10") < bigint("13"));
assert!(bigint("24") >= bigint("8"));
assert!(bigint("8") >= bigint("8"));
assert!(bigint("2") <= bigint("8"));
assert!(bigint("222") <= bigint("222"));
assert!(bigint("22") == bigint("22"));
assert!(!(bigint("2") > bigint("3")));
assert!(!(bigint("10") >= bigint("32")));
assert!(bigint("21") != bigint("22"));
assert!(bigint("-20") < bigint("-1"));
assert!(bigint("-20") > bigint("-100"));
assert!(bigint("-8") >= bigint("-18"));
assert!(bigint("-44") >= bigint("-44"));
assert!(bigint("-5") <= bigint("-1"));
assert!(bigint("-10") <= bigint("-10"));
assert!(bigint("-22") == bigint("-22"));
assert!(!(bigint("-3") > bigint("-2")));
assert!(!(bigint("-10") >= bigint("-5")));
assert!(bigint("-21") != bigint("-22"));
}
#[test]
fn compare_with_different_signs() {
assert!(bigint("10") > bigint("-10"));
assert!(!(bigint("-110") > bigint("10")));
assert!(bigint("-50") < bigint("10"));
assert!(bigint("10") >= bigint("-8"));
assert!(!(bigint("-10") >= bigint("10")));
assert!(bigint("+100") != bigint("-100"));
}
#[test]
fn addition_without_carriage() {
assert_eq!(bigint("123") + bigint("40"), bigint("163"));
assert_eq!(bigint("1111") + bigint("222"), bigint("1333"));
assert_eq!(bigint("0") + bigint("23"), bigint("23"));
assert_eq!(bigint("23") + bigint("0"), bigint("23"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("-1111") + bigint("-222"), bigint("-1333"));
assert_eq!(bigint("-0") + bigint("-222"), bigint("-222"));
assert_eq!(bigint("123") + bigint("-123"), Bigint::new());
assert_eq!(bigint("-2123") + bigint("2123"), Bigint::new());
assert_eq!(bigint("112") + bigint("-11"), bigint("101"));
assert_eq!(bigint("-112") + bigint("10"), bigint("-102"));
}
#[test]
fn addition_with_carriage() {
assert_eq!(bigint("88") + bigint("88"), bigint("176"));
assert_eq!(bigint("9999") + bigint("1"), bigint("10000"));
assert_eq!(bigint("12") + bigint("-8"), bigint("4"));
assert_eq!(bigint("24") + bigint("-111"), bigint("-87"));
assert_eq!(bigint("10000") + bigint("-1"), bigint("9999"));
}
#[test]
fn subtraction_of_positive_bigints() {
assert_eq!(bigint("88") - bigint("88"), Bigint::new());
assert_eq!(bigint("100") - bigint("88"), bigint("12"));
assert_eq!(bigint("10000") - bigint("1"), bigint("9999"));
assert_eq!(bigint("24") - bigint("111"), bigint("-87"));
}
#[test]
fn subtraction_with_double_negation() {
assert_eq!(bigint("88") - bigint("-88"), bigint("176"));
assert_eq!(bigint("-98") - bigint("-98"), Bigint::new());
assert_eq!(bigint("100") - bigint("-88"), bigint("188"));
assert_eq!(bigint("0") - bigint("-15"), bigint("15"));
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-19ynlru/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.57s
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