Решение на Bigint от Йоана Зелова
Резултати
- 14 точки от тестове
- 0 бонус точки
- 14 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
let mut vec = Vec::new();
vec.push(0);
Bigint {
sign: 1,
digits: vec,
}
}
fn subtract_vectors(first: Vec<u8>, second: Vec<u8>) -> Vec<u8> {
let mut copy_first = first.clone();
let mut copy_second = second.clone();
copy_first.reverse();
copy_second.reverse();
if copy_first.len() < copy_second.len() {
while copy_first.len() != copy_second.len() {
copy_first.push(0);
}
} else if copy_second.len() < copy_first.len() {
while copy_first.len() != copy_second.len() {
copy_second.push(0);
}
}
let mut borrow = 0;
let mut result = Vec::new();
for i in 0..copy_first.len() {
let mut first = (copy_first[i] as i8) - borrow;
if copy_first[i] == 0 && borrow == 1 {
first = 9;
}
let mut current_res = first - (copy_second[i] as i8);
if current_res < 0 {
current_res = current_res + 10;
borrow = 1;
} else {
borrow = 0;
}
result.push(current_res as u8);
}
if borrow == 1 {
result.push(9);
}
result.reverse();
return result;
}
fn add_vectors(first: Vec<u8>, second: Vec<u8>) -> Vec<u8> {
let mut copy_first = first.clone();
let mut copy_second = second.clone();
copy_first.reverse();
copy_second.reverse();
if copy_first.len() < copy_second.len() {
while copy_first.len() != copy_second.len() {
copy_first.push(0);
}
} else if copy_second.len() < copy_first.len() {
while copy_first.len() != copy_second.len() {
copy_second.push(0);
}
}
let mut add = 0;
let mut result = Vec::new();
for i in 0..copy_first.len() {
result.push((copy_first[i] + copy_second[i] + add) % 10);
add = (copy_first[i] + copy_second[i] + add) / 10;
}
if add != 0 {
result.push(add);
}
result.reverse();
return result;
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut copy_sign = sign;
let mut copy_digits = digits.clone();
if copy_digits.len() == 1 && copy_digits[0] == 0 {
copy_sign = 1;
}
while copy_digits.len() != 0 && copy_digits[0] == 0 {
copy_digits.remove(0);
}
if copy_digits.len() == 0 {
copy_digits = vec![0];
}
Bigint {
sign: copy_sign,
digits: copy_digits,
}
}
pub fn is_positive(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0 {
false
} else {
self.sign == 1
}
}
pub fn is_negative(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0 {
false
} else {
self.sign == -1
}
}
}
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 s = s;
let mut digits = Vec::new();
let mut sign = 1;
if s.len() == 0 {
return Ok(Bigint::from_components(vec![0], '+' as i8));
} else {
let mut id = 0;
if s.chars().nth(0) == Some('-') {
sign = -1;
id = id + 1;
} else if s.chars().nth(0) == Some('+') {
id = id + 1;
}
s = &s[id..s.len()];
for ch in s.chars() {
if ch.to_digit(10) == None {
return Err(ParseError);
}
digits.push(ch.to_digit(10).unwrap() as u8);
}
}
if digits.len() == 0 {
return Ok(Bigint::new());
}
return 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.is_negative() && other.digits == vec![0] {
return Ordering::Less;
} else if self.is_positive() && other.digits == vec![0] {
return Ordering::Greater;
} else if self.digits == vec![0] && other.is_negative() {
return Ordering::Greater;
} else if self.digits == vec![0] && other.is_positive() {
return Ordering::Less;
} else if self.digits == vec![0] && other.digits == vec![0] {
return Ordering::Equal;
}
if self.is_negative() && other.is_positive() {
return Ordering::Less;
} else if self.is_positive() && other.is_negative() {
return Ordering::Greater;
} else if self.is_negative() && other.is_negative() {
if self.digits.len() > other.digits.len() {return Ordering::Less;}
else if other.digits.len() > self.digits.len() {return Ordering::Greater;}
if self.digits.cmp(&other.digits) == Ordering::Less {
return Ordering::Greater;
} else if self.digits.cmp(&other.digits) == Ordering::Greater {
return Ordering::Less;
} else {
return Ordering::Equal;
}
} else {
if self.digits.len() < other.digits.len() {return Ordering::Less;}
else if other.digits.len() < self.digits.len() {return Ordering::Greater;}
return self.digits.cmp(&other.digits);
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let copy_self;
let copy_other;
if self.is_negative() {copy_self=Bigint::from_components(self.digits.clone(), 1);}
else {copy_self = Bigint::from_components(self.digits.clone(), self.sign);}
if other.is_negative() {copy_other=Bigint::from_components(other.digits.clone(), 1);}
else {copy_other = Bigint::from_components(other.digits.clone(), other.sign);}
if self.is_negative() && other.is_negative() {
Bigint::from_components(Bigint::add_vectors(self.digits, other.digits), -1)
} else if self.is_positive() && other.is_positive() {
Bigint::from_components(Bigint::add_vectors(self.digits, other.digits), 1)
} else {
if copy_self == copy_other {
return Bigint::new();
}
if copy_self < copy_other {
return Bigint::from_components(
Bigint::subtract_vectors(other.digits, self.digits),
other.sign,
);
} else {
return Bigint::from_components(
Bigint::subtract_vectors(self.digits, other.digits.clone()),
self.sign,
);
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let copy_other = Bigint::from_components(other.digits, other.sign*-1);
return self + copy_other;
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1965b7w/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.71s
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 ... FAILED
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
failures:
---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [1, 0, 9, 9] }`,
right: `Bigint { sign: 1, digits: [9, 9, 9] }`', tests/solution_test.rs:157:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
failures:
solution_test::test_sub_3_carry
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'