Решение на Bigint от Биляна Йорданова
Към профила на Биляна Йорданова
Резултати
- 13 точки от тестове
- 0 бонус точки
- 13 точки общо
- 13 успешни тест(а)
- 2 неуспешни тест(а)
Код
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
match self.digits[0] {
0 => false,
_ => self.sign == 1,
}
}
pub fn is_negative(&self) -> bool {
match self.digits[0] {
0 => false,
_ => 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> {
if s.is_empty() {
return Ok(Bigint::new());
}
let mut input: Vec<u8> = s.bytes().collect();
let sign = if input[0] == b'+' {
input.remove(0);
1
} else if input[0] == b'-' {
input.remove(0);
-1
} else {
1
};
while input.len() > 1 && input[0] == b'0' {
input.remove(0);
}
if input.len() == 1 && input[0] == b'0' {
return Ok(Bigint::new());
}
if input.is_empty() {
return Err(ParseError);
}
for i in input.iter_mut() {
if *i < b'0' || *i > b'9' {
return Err(ParseError);
}
*i -= b'0';
}
Ok(Bigint {
sign: sign,
digits: input,
})
}
}
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.sign != other.sign {
return match self.sign {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => unreachable!(),
};
}
let order = if self.digits.len() != other.digits.len() {
self.digits.len().cmp(&other.digits.len())
} else {
self.digits.cmp(&other.digits)
};
if self.sign == 1 {
order
} else {
order.reverse()
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut result = Vec::<u8>::new();
let mut sign = self.sign;
if self.sign == other.sign {
let mut i = self.digits.len();
let mut j = other.digits.len();
let mut rem = false;
while i != 0 && j != 0 {
let num = self.digits[i - 1] + other.digits[j - 1] + rem as u8;
result.insert(0, num % 10);
rem = num >= 10;
i -= 1;
j -= 1;
}
while i != 0 {
i -= 1;
let num = self.digits[i] + rem as u8;
result.insert(0, num % 10);
rem = num >= 10;
}
while j != 0 {
j -= 1;
let num = other.digits[j] + rem as u8;
result.insert(0, num % 10);
rem = num >= 10;
}
} else {
let (bigger, smaller) = if self.digits.len() == other.digits.len() {
match self.digits.cmp(&other.digits) {
Ordering::Greater => (&self, &other),
Ordering::Less => (&other, &self),
Ordering::Equal => return Bigint::new(),
}
} else {
match self.digits.len() > other.digits.len() {
true => (&self, &other),
false => (&other, &self),
}
};
let mut i = bigger.digits.len();
let mut j = smaller.digits.len();
let mut flag1;
let mut flag2 = false;
while i != 0 && j != 0 {
flag1 = (bigger.digits[i - 1] < smaller.digits[j - 1])
|| (bigger.digits[i - 1] == smaller.digits[j - 1] && flag2 == true);
let num =
10 * flag1 as u8 + bigger.digits[i - 1] - smaller.digits[j - 1] - flag2 as u8;
flag2 = flag1;
result.insert(0, num);
i -= 1;
j -= 1;
}
while i != 0 {
i -= 1;
result.insert(0, bigger.digits[i] - flag2 as u8);
flag2 = false;
}
while j != 0 {
j -= 1;
result.insert(0, smaller.digits[j] - flag2 as u8);
flag2 = false;
}
while result[0] == 0 {
result.remove(0);
}
sign = bigger.sign;
}
return Bigint {
sign: sign,
digits: result,
};
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let new_other = Bigint {
sign: -other.sign,
digits: other.digits,
};
self.add(new_other)
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-aj8nxr/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.96s
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 ... FAILED
test solution_test::test_sum_4_negative ... ok
failures:
---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:182:34
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [0, 0, 0] }`,
right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5
failures:
solution_test::test_sub_3_carry
solution_test::test_sum_3_overflow
test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'