Решение на Bigint от Ралица Димитрова

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

Към профила на Ралица Димитрова

Резултати

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

Код

use std::ops::Neg;
use std::cmp::Ordering;
use std::cmp::max;
use std::ops::{Add, Sub};
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self::from_components(Vec::new(), 1)
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut validated_digits: Vec<u8> = Vec::new();
let mut validated_sign = sign;
let mut first_non_zero_index: usize = digits.len();
for i in 0..digits.len() {
if digits[i] != 0 {
first_non_zero_index = i;
break;
}
}
if first_non_zero_index != digits.len() {
validated_digits = digits[first_non_zero_index..digits.len()].iter().cloned().collect();
}
if validated_digits.len() == 0 {
validated_sign = 1;
}
Bigint { sign: validated_sign, digits: validated_digits }
}
pub fn is_positive(&self) -> bool {
!self.digits.is_empty() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.digits.is_empty() && self.sign == -1
}
pub fn abs(&self) -> Self {
Bigint::from_components(self.digits.clone(), 1)
}
}
#[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::new();
let mut i: usize = 0;
if s.starts_with('+') {
i = 1;
} else if s.starts_with('-') {
sign = -1;
i = 1;
}
for c in s[i..].chars() {
if c >= '0' && c <= '9' {
digits.push(c as u8 - '0' as u8);
} else {
return Err(ParseError);
}
}
Ok(Bigint::from_components(digits, sign))
}
}
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn cmp_helper(left: &Bigint, right: &Bigint) -> Ordering {
if left.digits.len() == right.digits.len() {
for i in 0..left.digits.len() {
if left.digits[i] > right.digits[i] {
return Ordering::Greater;
} else if left.digits[i] < right.digits[i] {
return Ordering::Less;
}
}
return Ordering::Equal;
}
return left.digits.len().cmp(&right.digits.len());
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
let self_is_positive = self.is_positive();
let other_is_positive = other.is_positive();
let self_is_zero = self.digits.is_empty();
let other_is_zero = other.digits.is_empty();
match (self_is_positive, other_is_positive) {
(true, false) => return Ordering::Greater,
(false, true) => return Ordering::Less,
(true, true) => cmp_helper(self, other),
(false, false) => match (self_is_zero, other_is_zero) {
(true, true) => return Ordering::Equal,
(true, false) => return Ordering::Greater,
(false, true) => return Ordering::Less,
(false, false) => cmp_helper(other, self),
},
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut sign: i8 = 1;
let mut digits: Vec<u8> = Vec::new();
let self_abs = self.abs();
let other_abs = other.abs();
let self_is_positive = self.is_positive();
let other_is_positive = other.is_positive();
match (self_is_positive, other_is_positive) {
(true, true) => digits = add_digits(self.digits, other.digits),
(true, false) => match self_abs.cmp(&other_abs) {
Ordering::Less => digits = {
sign = -1;
subtract_digits(other.digits, self.digits)
},
Ordering::Equal => {},
Ordering::Greater => digits = subtract_digits(self.digits, other.digits),
},
(false, true) => match self_abs.cmp(&other_abs) {
Ordering::Less => digits = subtract_digits(other.digits, self.digits),
Ordering::Equal => {},
Ordering::Greater => {
sign = -1;
digits = subtract_digits(self.digits, other.digits)
},
},
(false, false) => {
sign = -1;
digits = add_digits(self.digits, other.digits);
},
}
Self::from_components(digits, sign)
}
}
impl Neg for Bigint {
type Output = Self;
fn neg(self) -> Self::Output {
if self.digits.is_empty() {
return self;
}
Bigint::from_components(self.digits, -self.sign)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (- other)
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut result: Vec<u8> = Vec::new();
let size = max(left.len(), right.len());
left.reverse();
right.reverse();
while left.len() < size {
left.push(0)
}
while right.len() < size {
right.push(0)
}
let mut carry: u8 = 0;
for i in 0..size {
let mut digit = left[i] + right[i] + carry;
if digit >= 10 {
carry = 1;
digit = digit % 10;
} else {
carry = 0;
}
result.push(digit);
}
if carry == 1 {
result.push(1)
}
result.reverse();
return result;
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let mut result: Vec<u8> = Vec::new();
let size = max(larger.len(), smaller.len());
larger.reverse();
smaller.reverse();
while larger.len() < size {
larger.push(0)
}
while smaller.len() < size {
smaller.push(0)
}
let mut carry: u8 = 0;
for i in 0..size {
let mut digit = larger[i];
if smaller[i] + carry > larger[i] {
digit = digit + 10 - smaller[i] - carry;
carry = 1;
} else {
digit = digit - smaller[i] - carry;
carry = 0;
}
result.push(digit);
}
result.reverse();
return result;
}
#[cfg(test)]
mod tests {
use super::*;
fn newBigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_create_zero() {
let zero = Bigint::new();
assert_eq!(zero.digits, Vec::new());
assert_eq!(zero.sign, 1);
let zero2 = newBigint("0");
assert_eq!(zero2.digits, Vec::new());
assert_eq!(zero2.sign, 1);
let zero3 = Bigint::from_str("+0").unwrap();
assert_eq!(zero3.digits, Vec::new());
assert_eq!(zero3.sign, 1);
let zero4 = newBigint("-0");
assert_eq!(zero4.digits, Vec::new());
assert_eq!(zero4.sign, 1);
let zero5 = Bigint::from_str("").unwrap();
assert_eq!(zero5.digits, Vec::new());
assert_eq!(zero5.sign, 1);
let zero6 = Bigint::from_str("+").unwrap();
assert_eq!(zero6.digits, Vec::new());
assert_eq!(zero6.sign, 1);
let zero7 = newBigint("-");
assert_eq!(zero7.digits, Vec::new());
assert_eq!(zero7.sign, 1);
}
#[test]
fn test_create_positive() {
let plus1 = newBigint("1");
assert_eq!(plus1.digits, vec![1]);
assert_eq!(plus1.sign, 1);
let plus123 = Bigint::from_str("+123").unwrap();
assert_eq!(plus123.digits, vec![1, 2, 3]);
assert_eq!(plus123.sign, 1);
let plus0000123 = newBigint("0000123");
assert_eq!(plus0000123.digits, vec![1, 2, 3]);
assert_eq!(plus0000123.sign, 1);
let plus00004 = Bigint::from_str("+00004").unwrap();
assert_eq!(plus00004.digits, vec![4]);
assert_eq!(plus00004.sign, 1);
}
#[test]
fn test_create_negative() {
let minus1 = newBigint("-1");
assert_eq!(minus1.digits, vec![1]);
assert_eq!(minus1.sign, -1);
let minus123 = newBigint("-123");
assert_eq!(minus123.digits, vec![1, 2, 3]);
assert_eq!(minus123.sign, -1);
let minus00123 = newBigint("-00123");
assert_eq!(minus00123.digits, vec![1, 2, 3]);
assert_eq!(minus00123.sign, -1);
}
#[test]
fn test_create_panic() {
assert!(Bigint::from_str("-*00123").is_err());
assert!(Bigint::from_str("--00123").is_err());
assert!(Bigint::from_str("++00123").is_err());
assert!(Bigint::from_str("00123+").is_err());
assert!(Bigint::from_str("001.23").is_err());
}
#[test]
fn test_add_neg_neg_eq_length() {
let a = newBigint("-123");
let b = newBigint("-976");
assert_eq!(a + b,newBigint("-1099"));
}
#[test]
fn test_add_neg_shorter_neg_longer() {
let a = newBigint("-12");
let b = newBigint("-976");
assert_eq!(a + b,newBigint("-988"));
}
#[test]
fn test_add_neg_longer_neg_shorter() {
let a = newBigint("-6798");
let b = newBigint("-11");
assert_eq!(a + b,newBigint("-6809"));
}
#[test]
fn test_add_zero() {
let a = newBigint("-123");
let b = newBigint("0");
assert_eq!(a - b,newBigint("-123"));
}
#[test]
fn test_subtract() {
let a = newBigint("-123");
let b = newBigint("0");
assert_eq!(a - b,newBigint("-123"));
}
#[test]
fn cmp_neg() {
assert_eq!(newBigint("-62").cmp(&newBigint("-25")), Ordering::Less);
assert_eq!(newBigint("-62").cmp(&newBigint("0")), Ordering::Less);
assert_eq!(newBigint("0").cmp(&newBigint("-25")), Ordering::Greater);
assert_eq!(newBigint("0").cmp(&newBigint("0")), Ordering::Equal);
assert_eq!(newBigint("121").cmp(&newBigint("0")), Ordering::Greater);
assert_eq!(newBigint("0").cmp(&newBigint("121")), Ordering::Less);
assert_eq!(newBigint("121").cmp(&Bigint::from_str("+121").unwrap()), Ordering::Equal);
assert_eq!(newBigint("-11").cmp(&newBigint("-11")), Ordering::Equal);
assert_eq!(newBigint("123").cmp(&newBigint("-11")), Ordering::Greater);
assert_eq!(newBigint("-11").cmp(&newBigint("123")), Ordering::Less);
assert_eq!(newBigint("345").cmp(&newBigint("34")), Ordering::Greater);
assert_eq!(newBigint("67").cmp(&newBigint("678")), Ordering::Less);
assert_eq!(newBigint("-11").cmp(&newBigint("-111")), Ordering::Greater);
assert_eq!(newBigint("-234").cmp(&newBigint("-99")), Ordering::Less);
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-1x4jn9y/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.72s
     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 версия и 1 коментар)

Ралица качи първо решение на 27.11.2020 16:46 (преди 8 месеца)

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